A Game Theoretic Solver for the Minimum Weighted Vertex Cover
Changhao Sun, Xiaochu Wang, Huaxin Qiu, Qián Chen · 2019
Toward the global optimality and computation time reduction, we address the minimum weighted vertex cover (MWVC) problem by proposing a population based game theoretic optimizer (PGTO) that combines learning in games with population based optimization. A population of candidate solutions are iterated through the procedures of swarm evolution (SE), learning in games (LIG), and local search (LS). Via strict theoretic analysis, we prove that LIG converges with probability one to Nash equilibria which could be further refined by LS. Numerical simulations show that a larger population size and a proper mutation probability are more likely to provide the best performance. Comparison experiments with typical algorithms demonstrate the superiority of the presented methodology to the state of the art, both in terms of solution efficiency and computation time.