一种基于优质边求解TSP的蚁群算法

计算机工程与应用 ›› 2013, Vol. 49 ›› Issue (10): 32-34.

一种基于优质边求解TSP的蚁群算法

胡银厚，王世卿

郑州大学信息工程学院，郑州 450052

出版日期:2013-05-15 发布日期:2013-05-14

Ant colony algorithm based on quality edge to solve TSP

HU Yinhou, WANG Shiqing

School of Information Engineering, Zhengzhou University, Zhengzhou 450052, China

Online:2013-05-15 Published:2013-05-14

摘要/Abstract

摘要： 应用蚁群算法求解旅行商问题时发现，算法易陷入局部最优解而停滞，并导致其探索新解能力的降低。提出了一种基于优质边的求解方法，根据算法运行过程中的相关信息选取优质边，在停滞时调整优质边上的信息素；使用改进的选路规则将蚂蚁的路径选择尽可能限制在优质边中，从而改进蚂蚁构造解的质量以增强算法的探索能力。实验结果表明，改进的策略是合理有效的。

关键词: 蚁群优化, 旅行商问题, 最大－最小蚁群算法, 智能计算, 优质边

Abstract: On the research of ant colony algorithm to the Traveling Salesman Problem shows that it can easily fall into the local optimal solution, leading to lower ability to explore better solutions. This paper proposes a solving approach which based on the quality edge to solve this problem. Choose the quality edge according to the information from the algorithm. While the algorithm is in stagnation, adjust the pheromone on quality edge, it will enhance the ability of algorithm to explore better solutions. At the same time, improved routing rules will limit the ant to choose the quality edge as much as possible, thereby improving the quality of solution. The?experiment results show that?the?improved?solution strategy?is reasonable and effective.

Key words: Ant Colony Optimization（ACO）, Traveling Salesman Problem（TSP）, Max-Min Ant System（MMAS）, intelligent computation, quality edge

胡银厚，王世卿. 一种基于优质边求解TSP的蚁群算法[J]. 计算机工程与应用, 2013, 49(10): 32-34.

HU Yinhou, WANG Shiqing. Ant colony algorithm based on quality edge to solve TSP[J]. Computer Engineering and Applications, 2013, 49(10): 32-34.

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