求解旅行商问题的高效自适应混合蚂蚁算法

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (27): 84-87.

求解旅行商问题的高效自适应混合蚂蚁算法

陈星宇,全惠云,肖伟

湖南师范大学数学与计算机科学学院,长沙 410081

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-09-21 发布日期:2007-09-21
通讯作者: 陈星宇

Improved adaptive hybrid ant algorithm for traveling salesman problem

CHEN Xing-yu,QUAN Hui-yun,XIAO Wei

School of Mathematics and Computer Science,Hunan Normal University,Changsha 410081,China

Received:1900-01-01 Revised:1900-01-01 Online:2007-09-21 Published:2007-09-21
Contact: CHEN Xing-yu

摘要/Abstract

摘要： 在目前求解TSP问题效果最好的混合算法——最大最小蚂蚁算法和3-opt局部搜索算法的基础上,提出了一种改进的混合蚂蚁算法。算法前期使用局部搜索的解初始化信息素矩阵,加快收敛速度,后期依Metropolis接受准则概率接受局部优化解,有效地避免陷入局部最优,自适应的信息素调节机制使算法更加灵活,而K近邻候选集则使之适应大规模问题求解,理论分析和TSPLIB中部分实例仿真结果表明,此算法能比其他改进蚁群算法具有更多优越性。

关键词: 最大最小蚂蚁算法, 3-opt局部搜索优化, 自适应调节, K近邻候选集, 旅行商问题

Abstract: This paper presents IHAS,an improved hybrid algorithm combines Max-Min Ant System（MMAS） with a local search strategy.IHAS also uses adaptive pheromone trail information,neighbourhood candidate list and Metropolis rules to instruct solutions,which can speed up convergence,avoid local optimization and solve scalable instances.Theory analysis and experimental result show that IHAS outperforms other hybrid ant colony algorithms due to its ability to find the satisfactory results effectively when applied to the Traveling Salesman Problem.

Key words: Max-Min Ant System（MMAS）, 3-opt local search optimization, adaptive adjustment, K neighbours candidate list, Traveling Salesman Problem（TSP）

陈星宇,全惠云,肖伟. 求解旅行商问题的高效自适应混合蚂蚁算法[J]. 计算机工程与应用, 2007, 43(27): 84-87.

CHEN Xing-yu,QUAN Hui-yun,XIAO Wei. Improved adaptive hybrid ant algorithm for traveling salesman problem[J]. Computer Engineering and Applications, 2007, 43(27): 84-87.

[1]	张松灿，普杰信，司彦娜，孙力帆. 基于种群相似度的自适应改进蚁群算法及应用[J]. 计算机工程与应用, 2021, 57(8): 70-77.
[2]	卜冠南，刘建华，姜磊，张冬阳. 一种自适应分组的蚁群算法[J]. 计算机工程与应用, 2021, 57(6): 67-73.
[3]	陈思远，林丕源，黄沛杰. 指针网络改进遗传算法求解旅行商问题[J]. 计算机工程与应用, 2020, 56(19): 231-236.
[4]	周克良，龚达欣，张宇龙. 区域破坏重建的蚁群优化算法[J]. 计算机工程与应用, 2020, 56(14): 62-67.
[5]	刘明霞1，游晓明1，刘升2. 基于聚度的自适应动态混沌蚁群算法[J]. 计算机工程与应用, 2019, 55(3): 15-22.
[6]	胡士娟，鲁海燕，黄洋，许凯波. 求解工作量平衡多旅行商问题的改进遗传算法[J]. 计算机工程与应用, 2019, 55(17): 150-155.
[7]	陈佳，游晓明，刘升，李娟. 结合信息熵的多种群博弈蚁群算法[J]. 计算机工程与应用, 2019, 55(16): 170-178.
[8]	李娟，游晓明，刘升，陈佳. 自适应模糊蚁群系统[J]. 计算机工程与应用, 2019, 55(15): 75-81.
[9]	赵亚文，熊瑞平，乔治，梁齐齐，罗勇. 应用捕食搜索策略的改进多态蚁群算法[J]. 计算机工程与应用, 2019, 55(14): 115-121.
[10]	姚书婷，胡志华，魏晨. 多禁止时间窗约束的路径恢复问题研究[J]. 计算机工程与应用, 2019, 55(12): 265-270.
[11]	陈雷，张红梅，张向利. 自适应动态邻域布谷鸟混合算法求解TSP问题[J]. 计算机工程与应用, 2018, 54(23): 42-50.
[12]	白景波，李宏伟，陈亮，冯玉芳，刘建永. 双链量子蚁群系统及应用[J]. 计算机工程与应用, 2018, 54(21): 1-6.
[13]	徐小平，张东洁. 基于猴群算法求解旅行商问题[J]. 计算机工程与应用, 2018, 54(2): 144-148.
[14]	赵勇1，2，巨永锋1. 基于条件先验人体模型的人体姿态估计[J]. 计算机工程与应用, 2018, 54(16): 24-29.
[15]	林敏，钟一文，刘必雄，林晓宇. 基因-表现型的布谷鸟算法求解旅行商问题[J]. 计算机工程与应用, 2017, 53(24): 172-181.