Ant Colony Algorithm For Vertex Covering Problem

Given an undirected graph G=(V,E),the minimum vertex cover problem(MVCP)is to find a subset S of V such that for each edge in G,at least one of its two end vertices belongs to the subset S.This problem is a classical NP complete problem,and there is no polynomial time algorithm at present,so the focus of the research is to find a feasible solution which is close to the optimal solution within a reasonable calculation time.In this paper,we use ant colony algorithm to study the minimum vertex cover problem.The main work is as follows:(1)Compared the minimum vertex cover problem with the TSP problem.By modifying the state transition rules and pheromone update rules,obtained the basic principles of the ant colony algorithm to solve the problem.Then using the improved ant colony algorithm,studied the minimum vertex cover problem of unweighted graph and weighted graph respectively,and designed the algorithm.Finally,given an example to analyze the rationality and effectiveness of the algorithm.(2)The positive feedback mechanism of the ant colony algorithm tends to cause the search to fall into local convergence and a local optimal solution appears.By comparing the basic ant colony algorithm with the maximum and minimum ant colony algorithm,obtained the basic principle of the maximum and minimum ant colony algorithm to solve the problem.By adding limiting conditions to the state transition rules and pheromone update rules,the local optimal phenomenon is effectively avoided.Using the improved maximum and minimum ant colony algorithm,studied the minimum vertex cover problem of unweighted graphs.(3)Considering the impact of shared bicycles on urban traffic and the operating costs of enterprises,regarded the selection of shared bicycle drop-off points as a conditional minimum vertex cover problem,and used the improved ant colony algorithm to solve and get a better solution of shared bicycle drop-off problem.