Research On Vertex Cover Problem Based On Ant Colony Optimization

Vertex cover problem refers to the existence of a subset K in the vertex set V of undirected graph G=(V,E),and at least one end point of any given ledge in G exists in K.Minimum vertex coverage problem is to cover all edges with as few vertices as possible in a graph.This problem is NP-complete in the classical combinatorial optimization field.The solution of the minimum vertex coverage problem can be applied to many aspects of life,such as:network node selection problem,garbage dump and parking lot location problem,sharing bicycle delivery problem and so on.It has attracted much attention because of its wide application.The main research directions of solving this problem are direct algorithm,parametric algorithm and intelligent algorithm.Ant colony optimization was earliest use in solving combinatorial optimization problem,in the field of combinatorial optimization,it is the most widely researched and applied.The main work of this paper is as follows:(1)Comparing the TSP problem with the minimum vertex coverage problem,we find two differences:the selection of vertex in TSP problem is related to their ranking order,while the ranking order in the minimum vertex coverage problem does not affect the final result.The heuristic function in TSP is static while the minimum vertex coverage problem is dynamically updated.According to these two differences,the ant colony optimization is improved to solve TSP problem,and then the ant colony optimization is obtained to solve the minimum vertex coverage problem.(2)Although ant colony optimization has the advantages of systematic,distributed computing,strong robustness and positive feedback,it will take a long time to solve or not get the optimal solution when dealing with large amount of data,and the ant may appear early stagnation problem in the cycle,which leads to the algorithm falling into local optimum.In order to prevent the occurrence of this situation,the maximum and minimum ant colony optimization is used to solve the problem.By limiting the concentration of pheromones,it is not possible to make them stronger at good points,or to ignore weak points.The phenomenon of local optimum is avoided.The calculation shows that the accuracy of the algorithm is high.(3)In order to avoid the stagnation of local optimal solution in the algorithm,a hybrid ant colony optimization is proposed to solve the problem.The main purpose of this algorithm is to correct the optimal solution.This mixed concept directly suspects that some elements in the optimal solution are bad,and points directly to the suspicious search area during the search process,and guides the search by reducing pheromone update values of suspicious points.The skepticism criterion is set to filter the points,and then the vertex is corrected by the correction rule.Numerical examples show that the optimal solution is optimized by introducing the doubt criterion.