Research On Network Vertex Cover Problem Based On Evolutionary Computatio

There are various networks in real life,the common ones are: transportation networks,social networks,electric power networks and so on.The minimum vertex cover problem is a classic NP-hard problem in the field of combinatorial optimization.The minimum weighted vertex cover problem is an extension of the minimum vertex cover problem.Its purpose is to find the vertex cover set that can cover all the edges of the network with the smallest sum of weights.The minimum weighted vertex cover problem has a wide range of applications in planning problems,scheduling problems,network optimization and so on.It is also a key point to solve some important problems such as the robustness of the measurement network.Evolutionary algorithm is an algorithm for global search by simulating the biological evolution mechanism of nature.It plays an important role in hot research fields such as computer science,artificial intelligence,economic management and biology.It is also one of the key technologies to solve the minimum weighted vertex cover problem.The evolutionary algorithm starts from a set of randomly generated initial individuals and generates the next generation of individuals through the biological heredity of replication,crossover,and mutation.Then the fitness function is used to eliminate the fittest and improve the quality of the individual in the population.After many iterations,the optimal solution is approached.Based on the framework of evolutionary algorithm,this paper designs a reasonable optimization operator,and focuses on the minimum weighted vertex cover problem,and studies two types of single-objective minimum weighted vertex cover problem and multi-objective minimum weighted vertex cover problem.The main contents are as follows:Aiming at the single-objective minimum weighted vertex cover problem,a Memetic algorithm based on snowdrift game to solve the minimum weighted vertex cover problem is proposed.The algorithm is based on the idea of snowdrift game in game theory,uses the Memetic algorithm framework in evolutionary algorithm to improve the population initialization and local search methods.By adjusting the population initialization and local search,the search space is reduced while maintaining the diversity of the population.Experimental results show that the performance of the proposed algorithm is better than the other four contrast algorithm.Aiming at the problem of multi-objective minimum weighted vertex cover,using the idea of multi-objective optimization,the MOEA/D algorithm is improved accordingly,and an algorithm for solving the multi-objective minimum weighted vertex cover problem based on MOEA/D is proposed.According to the characteristics of the problem to be solved,an appropriate optimization method is designed.In order to better accelerate the search convergence speed,an adaptive strategy is introduced to search the solution space.Simulation experiments show that the proposed algorithm is better than the contrast algorithm in terms of convergence and diversity.