Research On Algorithms For Solving Covering Problems Based On Local Search

The generalized vertex covering problem and the k-cover set problem are extensions of the covering problem.The generalized vertex cover problem extends the classic vertex covering problem,and the k-cover set problem extends the classic set covering problem.Both of these problems have a wide range of applications.For example,computational biology,wireless network technology.In addition,the generalized vertex covering problem and the k-cover set problem are both NP-hard problems.In real world,the common feature of a large number of NP-hard problems is that as the scale of examples continues to increase,the number of feasible solutions and the difficulties of solving tend to increase exponentially,which make it difficult for the accurate solution algorithm to obtain a good accurate solution in a satisfactory time.The local search algorithm can get a feasible solution in a reasonable time.At present,heuristic algorithm is a commonly used local search algorithm and one of the methods to solve optimization problems.The local search algorithm can be seen as a simple greedy search algorithm.Each time an optimal operation is selected from the adjacent solution space of the current solution to execute,and then a new current solution is generated till a local optimal solution is reached.This paper designs two local search algorithms to solve the generalized vertex covering problem and the k-cover set problem respectively.The algorithm proposed to solve the generalized vertex covering problem is a hybrid heuristic algorithm based on evolutionary search and iterative neighborhood search.The algorithm uses a new initialization method to generate high-quality initial solutions,then uses crossover operations to generate offspring solutions,and finally uses the best-selected neighborhood search to find better solutions.Experimental results prove that the algorithm has excellent performance on random instances and DIMACS instances.The algorithm used to solve the k-covering set problem is a local search algorithm based on configuration check and scoring mechanism.First,in order to overcome the loop problem in local search,a k-set coverage configuration check strategy is proposed.Second,for the sake of finding better solutions,the element cost is proposed to define the scoring mechanism.The local search algorithm based on configuration check and scoring mechanism proposed in this paper is compared with two state-of-the-art algorithms.The experimental results show that,in most classic cases,the quality of the solution provided by configuration check and scoring mechanism is better than other algorithms.