MMAS-EC算法求解旅行商问题

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (9): 41-44.

MMAS-EC算法求解旅行商问题

李哲1，夏立1，庄浩俊2，董红生3

1.海军工程大学电气与信息工程学院，武汉 430033
2.中国人民解放军 91656部队
3.中国人民解放军 92665部队

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-03-21 发布日期:2011-03-21

MMAS-EC algorithm for solving traveling salesman problem

LI Zhe1，XIA Li1，ZHUANG Haojun2，DONG Hongsheng3

1.School of Electric and Information，Naval University of Engineering，Wuhan 430033，China
2.Unit 91656 of the PLA
3.Unit 92665 of the PLA

Received:1900-01-01 Revised:1900-01-01 Online:2011-03-21 Published:2011-03-21

摘要/Abstract

摘要： 针对蚁群算法在求解旅行商问题容易出现搜索精度不高的问题，提出一种结合排出算法的最大-最小蚁群系统算法（MMAS-EC）。算法采用全局寻优和局部搜索结合的策略，利用寻优效果较好的最大-最小蚁群系统指导全局搜索方向，同时引入排出算法来探索局部解空间，并采用2-opt操作减小了排出算法对初始位置的依赖，提高了解的稳定性。仿真实验表明：结合了排出算法的最大-最小蚁群系统算法与标准蚁群算法相比，在时间开销增加较小的情况下，取得了质量更高的解。

关键词: 蚁群优化算法, 旅行商问题, 排出算法, 最大-最小蚁群系统

Abstract: One of the problems encountered when ant colony optimization is applied to traveling salesman problem is that sometimes this algorithm results in a lower performance.According to this problem，a new Max-Min Ant System combining with Ejection Chains is presented（MMAS-EC）.A new strategy based on global search and neighborhood search is used in this algorithm.Firstly，Max-Min Ant System which performs effectively in ant colony optimization is used to guide the global search.Then Ejection Chains（EC） is introduced to exploit the neighborhood space.Because the results generated by ejection chains depend on their original state，2-opt operation is adopted，which can help avoid instability of results.Theorems and simulations show that the new MMAS-EC outperforms traditional MMAS algorithm with less time increased in all the instances.

Key words: ant colony optimization, Traveling Salesman Problem（TSP）, ejection chains, max-min ant system

李哲1，夏立1，庄浩俊2，董红生3. MMAS-EC算法求解旅行商问题[J]. 计算机工程与应用, 2011, 47(9): 41-44.

LI Zhe1，XIA Li1，ZHUANG Haojun2，DONG Hongsheng3. MMAS-EC algorithm for solving traveling salesman problem[J]. Computer Engineering and Applications, 2011, 47(9): 41-44.

[1]	张松灿，普杰信，司彦娜，孙力帆. 基于种群相似度的自适应改进蚁群算法及应用[J]. 计算机工程与应用, 2021, 57(8): 70-77.
[2]	卜冠南，刘建华，姜磊，张冬阳. 一种自适应分组的蚁群算法[J]. 计算机工程与应用, 2021, 57(6): 67-73.
[3]	张铭，邓文瀚，林娟，钟一文. 改进蚁群优化算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2021, 57(13): 85-95.
[4]	张海南，游晓明，刘升，刘中强. 交互式学习的布谷鸟搜索算法[J]. 计算机工程与应用, 2020, 56(7): 147-154.
[5]	陈思远，林丕源，黄沛杰. 指针网络改进遗传算法求解旅行商问题[J]. 计算机工程与应用, 2020, 56(19): 231-236.
[6]	周克良，龚达欣，张宇龙. 区域破坏重建的蚁群优化算法[J]. 计算机工程与应用, 2020, 56(14): 62-67.
[7]	薛文艳，赵江，郝崇清，刘慧贤. 基于信息素负反馈的超启发式蚁群优化算法[J]. 计算机工程与应用, 2019, 55(4): 163-172.
[8]	刘明霞1，游晓明1，刘升2. 基于聚度的自适应动态混沌蚁群算法[J]. 计算机工程与应用, 2019, 55(3): 15-22.
[9]	胡士娟，鲁海燕，黄洋，许凯波. 求解工作量平衡多旅行商问题的改进遗传算法[J]. 计算机工程与应用, 2019, 55(17): 150-155.
[10]	陈佳，游晓明，刘升，李娟. 结合信息熵的多种群博弈蚁群算法[J]. 计算机工程与应用, 2019, 55(16): 170-178.
[11]	李娟，游晓明，刘升，陈佳. 自适应模糊蚁群系统[J]. 计算机工程与应用, 2019, 55(15): 75-81.
[12]	赵亚文，熊瑞平，乔治，梁齐齐，罗勇. 应用捕食搜索策略的改进多态蚁群算法[J]. 计算机工程与应用, 2019, 55(14): 115-121.
[13]	姚书婷，胡志华，魏晨. 多禁止时间窗约束的路径恢复问题研究[J]. 计算机工程与应用, 2019, 55(12): 265-270.
[14]	姜道银1，2，葛洪伟1，2. 基于信息交流策略的连续域蚁群优化算法[J]. 计算机工程与应用, 2019, 55(11): 153-159.
[15]	姜道银1，2，葛洪伟1，2，袁罗1. 一种动态划分的混合连续域蚁群优化算法[J]. 计算机工程与应用, 2018, 54(7): 144-151.