Study On The Local Search Algorithm For Generalized Vertex Cover Problem

Vertex cover problem is an important area of research in artificial intelligence and its computation complexity is NP. The minimum vertex cover problem, weighted minimum vertex cover problem, generalized vertex cover problem are an extension of the vertex cover problem. Generalized vertex cover problem can be widely used in many fields, such as network engineering, communication engineering and biological information engineering. So the research of generalized vertex cover problem has a very important theoretical significance and practical value.Vertex cover problem can be solved using the generalized exact algorithms and heuristic algorithm. Exact algorithms can find the exact solution, heuristic algorithm cannot find out the exact solution, but can find out the optimal solution. But to solve the large scale problem, the exact algorithm difficult to find the exact solution in a relatively short period of time, while the heuristic algorithm for the time is very short.As a result, most of the heuristic algorithms are used to solve the large-scale problem instances. The most important part of the heuristic algorithms is the local search algorithm. The main work of this paper is to design a local search algorithm for solving the generalized vertex cover problem.This paper proposes LSTP, an iterated local search algorithm for generalized vertex cover problem, based on tabu strategy and perturbation mechanism. The LSTP algorithm proposed in this paper is the three strategies in the local search, which is added into tabu strategy, vertex selection and perturbation mechanism. LSTP use tabu strategy to prevent the local search immediately back to the previously visited candidate solutions and to avoid cycling problem. Secondly, LSTP propose flip gain for each vertex, then the tabu strategy is combined with the flip gain for vertex selecting. LSTP apply a simple perturbation mechanism to help the search to escape from deep local optima and to bring diversification into the search.Examples of this paper is randomly generated by the original literature algorithm, while expanding the experiment generalized vertex cover problem instances in the range, which can solve the large-scale generalize vertex cover problem. After comparing LSTP algorithm with GA algorithm proposed by Milanovic, the experimental results show that LSTP algorithm performs better than GA algorithm under the same parameters. In this paper, LSTP is added to the tabu search strategy and the perturbation mechanism to carry out a comparative experiment, it is proved that the effectiveness of the two strategies to join.