计算机工程与应用 ›› 2019, Vol. 55 ›› Issue (16): 170-178.DOI: 10.3778/j.issn.1002-8331.1804-0361

• 模式识别与人工智能 • 上一篇    下一篇

结合信息熵的多种群博弈蚁群算法

陈佳,游晓明,刘升,李娟   

  1. 1.上海工程技术大学 电子电气工程学院,上海 201620
    2.上海工程技术大学 管理工程学院,上海 201620
  • 出版日期:2019-08-15 发布日期:2019-08-13

Entropy-Game Based Multi-Population Ant Colony Optimization

CHEN Jia, YOU Xiaoming, LIU Sheng, LI Juan   

  1. 1.School of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China
    2.School of Management, Shanghai University of Engineering Science, Shanghai 201620, China
  • Online:2019-08-15 Published:2019-08-13

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

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

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)