首页|A population-based game-theoretic optimizer for the minimum weighted vertex cover
A population-based game-theoretic optimizer for the minimum weighted vertex cover
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
Toward higher solution efficiency and faster computation, this paper addresses the minimum weighted vertex cover (MWVC) problem by introducing game theory into iterated optimization and proposing a population-based game-theoretic optimizer (PGTO). A group of candidate solutions are iterated through the specially designed procedures of swarm evolution (SE), learning in games (LIG), and local search (LS) successively. Within the framework of potential game theory, we prove that LIG computes in finite time Nash equilibria that represent vertex cover solutions where no redundant nodes exist. Moreover, theoretical analysis is presented that by exchanging the actions of certain neighbours, LS is capable of generating better results upon the input Nash equilibrium. Through intensive numerical experiments, we show that while enlarging the population size could boost the global objective, a mutation probability between 0.05 and 0.2 is more likely to provide the best performance. Comparison experiments against the state of the art demonstrate the superiority of the presented methodology, both in terms of solution quality and computation speed.
Combinatorial optimizationExploration and exploitationLearning in gamesMinimum weighted vertex cover (MWVC)Nash equilibrium
Qiu H.、Sun C.、Wang X.、Zhou Q.、Sun W.
展开 >
Qian Xuesen Laboratory of Space Technology China Academy of Space Technology
School of Aerospace Science and Technology Xidian University
NSTL
Elsevier
