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

doi:10.3778/j.issn.1002-8331.1804-0361

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

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

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

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.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

摘要/Abstract

摘要： 针对蚁群算法在旅行商问题（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）

陈佳，游晓明，刘升，李娟. 结合信息熵的多种群博弈蚁群算法[J]. 计算机工程与应用, 2019, 55(16): 170-178.

CHEN Jia, YOU Xiaoming, LIU Sheng, LI Juan. Entropy-Game Based Multi-Population Ant Colony Optimization[J]. Computer Engineering and Applications, 2019, 55(16): 170-178.

[1]	史春天，曾艳阳，侯守明. 群体智能算法在图像分割中的应用综述[J]. 计算机工程与应用, 2021, 57(8): 36-47.
[2]	张松灿，普杰信，司彦娜，孙力帆. 基于种群相似度的自适应改进蚁群算法及应用[J]. 计算机工程与应用, 2021, 57(8): 70-77.
[3]	朱佳莹，高茂庭. 融合粒子群与改进蚁群算法的AUV路径规划算法[J]. 计算机工程与应用, 2021, 57(6): 267-273.
[4]	卜冠南，刘建华，姜磊，张冬阳. 一种自适应分组的蚁群算法[J]. 计算机工程与应用, 2021, 57(6): 67-73.
[5]	马向华，张谦. 改进蚁群算法在机器人路径规划上的研究[J]. 计算机工程与应用, 2021, 57(5): 210-215.
[6]	王鹏，叶学义，王涛，钱丁炜. 双偏差双空间局部方向模式的人脸识别[J]. 计算机工程与应用, 2021, 57(4): 91-99.
[7]	李壮阔，常凯旋. 合作博弈的连续蚁群算法求解[J]. 计算机工程与应用, 2021, 57(24): 198-204.
[8]	江魁，丘远东，郑浩城. 基于信息熵与LSTM的ICMPv6 DDoS攻击检测方法[J]. 计算机工程与应用, 2021, 57(21): 148-154.
[9]	王晓光，杨培蓓. 航运物流企业数字化转型设计与效果分析[J]. 计算机工程与应用, 2021, 57(21): 241-247.
[10]	张子然，黄卫华，陈阳，章政，李梓远. 基于双向搜索的改进蚁群路径规划算法[J]. 计算机工程与应用, 2021, 57(21): 270-277.
[11]	王军，曹雷，陈希亮，赖俊，章乐贵. 多智能体博弈强化学习研究综述[J]. 计算机工程与应用, 2021, 57(21): 1-13.
[12]	李二超，齐款款. 改进双向蚁群算法的移动机器人路径规划[J]. 计算机工程与应用, 2021, 57(18): 281-288.
[13]	宋世杰，陈开颜，张阳. 信息熵角度下的深度学习旁路安全评估框架[J]. 计算机工程与应用, 2021, 57(17): 138-146.
[14]	何雅颖，范昕炜. 改进蚁群算法在机器人路径规划中的应用[J]. 计算机工程与应用, 2021, 57(16): 276-282.
[15]	付朝晖，刘长石. 多物流中心共同配送的车辆路径问题研究[J]. 计算机工程与应用, 2021, 57(16): 291-298.

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

Entropy-Game Based Multi-Population Ant Colony Optimization

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics