IEEE Trans Cybern. 2019 Mar;49(3):974-988. doi: 10.1109/TCYB.2018.2789930. Epub 2018 Jan 31.
The minimum vertex cover (MVC) is a well-known combinatorial optimization problem. A game-based memetic algorithm (GMA-MVC) is provided, in which the local search is an asynchronous updating snowdrift game and the global search is an evolutionary algorithm (EA). The game-based local search can implement (k,l)-exchanges for various numbers of k and l to remove k vertices from and add l vertices into the solution set, thus is much better than the previous (1,0)-exchange. Beyond that, the proposed local search is able to deal with the constraint, such that the crossover operator can be very simple and efficient. Degree-based initialization method is also provided which is much better than the previous uniform random initialization. Each individual of the GMA-MVC is designed as a snowdrift game state of the network. Each vertex is treated as an intelligent agent playing the snowdrift game with its neighbors, which is the local refinement process. The game is designed such that its strict Nash equilibrium (SNE) is always a vertex cover of the network. Most of the SNEs are only local optima of the problem. Then an EA is employed to guide the game to escape from those local optimal Nash equilibriums to reach a better Nash equilibrium. From comparison with the state of the art algorithms in experiments on various networks, the proposed algorithm always obtains the best solutions.
最小顶点覆盖 (MVC) 是一个著名的组合优化问题。提出了一种基于博弈的进化算法 (GMA-MVC)，其中局部搜索是一个异步更新的 snowdrift 博弈，全局搜索是一个进化算法 (EA)。基于博弈的局部搜索可以针对各种 k 和 l 的值执行 (k,l)-交换，从解集中删除 k 个顶点并添加 l 个顶点，因此比之前的 (1,0)-交换要好得多。除此之外，所提出的局部搜索能够处理约束条件，使得交叉算子可以非常简单和高效。还提供了基于度数的初始化方法，比以前的均匀随机初始化要好得多。GMA-MVC 的每个个体都被设计为网络的 snowdrift 博弈状态。每个顶点都被视为一个智能体，与邻居玩 snowdrift 博弈，这是局部细化过程。该博弈的设计使得其严格纳什均衡 (SNE) 始终是网络的顶点覆盖。大多数 SNE 只是问题的局部最优解。然后，采用 EA 引导博弈从这些局部最优纳什均衡中逃脱，以达到更好的纳什均衡。通过在各种网络上的实验与最先进的算法进行比较，所提出的算法始终获得最佳解决方案。
