TY - GEN
T1 - A game theoretic solver for the minimum weighted vertex cover
AU - Sun, Changhao
AU - Wang, Xiaochu
AU - Qiu, Huaxin
AU - Chen, Qian
N1 - Publisher Copyright:
© 2019 IEEE.
PY - 2019/10
Y1 - 2019/10
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/85076743094
U2 - 10.1109/SMC.2019.8914409
DO - 10.1109/SMC.2019.8914409
M3 - 会议稿件
AN - SCOPUS:85076743094
T3 - Conference Proceedings - IEEE International Conference on Systems, Man and Cybernetics
SP - 1920
EP - 1925
BT - 2019 IEEE International Conference on Systems, Man and Cybernetics, SMC 2019
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2019 IEEE International Conference on Systems, Man and Cybernetics, SMC 2019
Y2 - 6 October 2019 through 9 October 2019
ER -