Abstract: To deal with the difficulty to find the optimal solution and the premature of ant colony algorithm when it is used to solve Traveling Salesman Problems（TSPs）, a novel Entropy-Game based Multi-Population Ant Colony Optimization（EGMACO） is proposed. First, the master-slave cooperative game mechanism is used, and the Shapley formula as well as the information entropy are used to adjust the weight of each operator. Meanwhile, the rewarding-publishing operator is built to improve the convergence. Then, the introduction of tit-for-tat strategy for sub-populations can help the collaborative learning and improve the diversity. Next, the introduction of coordination game mechanism based on Pareto optimality can facilitate the adaptive cooperation and improve the performance. Finally, EGMACO is tested in several TSP instances. The experimental results suggest that EGMACO has good performance with higher stability and higher precision in TSP instances.

Key words: information entropy, game theory, multi-population algorithm, ant colony algorithm, Traveling Salesman Problem（TSP）

摘要： 针对蚁群算法在旅行商问题（Traveling Salesman Problem，TSP）求解中难以找到最优解、容易早熟的问题，提出一种基于信息熵的多种群博弈蚁群算法。首先，算法采用主从合作博弈机制，引入夏普里公式和信息熵，自适应调整各算子的使用权重，同时构造奖惩算子，提高算法收敛性；然后，对从种群引入针锋相对策略，进行协同学习，提高从种群多样性；进一步，根据帕累托最优原则，对从种群引入协调博弈机制进行自适应合作，提高算法性能。最后，以TSPLIB标准库中的多组TSP问题作为实验算例，进行算法性能分析。实验结果表明，对比传统算法，该算法具有良好的求解精度和求解稳定性。

关键词: 信息熵, 博弈论, 多种群算法, 蚁群算法, 旅行商问题（TSP）