An evolutionary game algorithm for minimum weighted vertex cover problem.

The minimum weighted vertex cover (MWVC) problem is to find a subset of vertices that can cover all the edges of the network and minimize the sum of the vertex weights in the vertex subset. MWVC is a generalization of the minimum vertex cover (MVC) problem and can be regarded as a combinatorial optimization problem. This paper proposes an evolutionary algorithm based on the snowdrift game to solve the MWVC problem. We use the evolutionary algorithm framework, and the snowdrift game is combined to construct and improve the initial solution. First, the network's vertex is regarded as an intelligent agent, and each vertex and its neighbors play a snowdrift game to form an initial solution. Then local search and global search are used to improve the initial solution. The solution is improved according to the proposed score function in the local search stage to obtain a better MWVC solution. The evolutionary algorithm is used in the global search stage to escape the local optimum. Experiments on different networks show that the proposed algorithm are effective on weighted networks. [ABSTRACT FROM AUTHOR]