Improved adaptive hybrid ant algorithm for traveling salesman problem

Computer Engineering and Applications ›› 2007, Vol. 43 ›› Issue (27): 84-87.

• 学术探讨 • Previous Articles Next Articles

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

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

陈星宇,全惠云,肖伟

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

通讯作者: 陈星宇

Abstract

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）

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

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

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.

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

[1]	BU Guannan, LIU Jianhua, JIANG Lei, ZHANG Dongyang. Ant Colony Algorithm with Adaptive Grouping [J]. Computer Engineering and Applications, 2021, 57(6): 67-73.
[2]	SONG Mei, GE Yuhui, LIU Jusheng. Improved Dynamic Dual Adaptive PSO Algorithm Based on Theory of Co-evolution [J]. Computer Engineering and Applications, 2020, 56(13): 54-62.
[3]	MIAO Xianglin1, HE Feijuan1, MIAO Yalin2, XIAO Chun3, ZHOU Jianlong1. Intelligent Augmented Reality System for Dynamic User Cognitive Load Adjustment [J]. Computer Engineering and Applications, 2019, 55(7): 182-187.
[4]	TANG Shenwei, JIA Ruiyu. [K]-Means Cluster Algorithm Based on Improved PSO [J]. Computer Engineering and Applications, 2019, 55(18): 140-145.
[5]	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.
[6]	ZHAO Yawen, XIONG Ruiping, QIAO Zhi, LIANG Qiqi, LUO Yong. Improved Polymorphic Ant Colony Algorithm with Predatory Search Strategy [J]. Computer Engineering and Applications, 2019, 55(14): 115-121.
[7]	BAI Jingbo, LI Hongwei, CHEN Liang, FENG Yufang, LIU Jianyong. Double-chain quantum-inspired ant colony system and its application [J]. Computer Engineering and Applications, 2018, 54(21): 1-6.
[8]	XU Xiaoping, ZHANG Dongjie. Solving traveling salesman problem based on monkey algorithm [J]. Computer Engineering and Applications, 2018, 54(2): 144-148.
[9]	ZHAO Yong1，2, JU Yongfeng1. Human pose estimation based on human model using conditional prior [J]. Computer Engineering and Applications, 2018, 54(16): 24-29.
[10]	CHEN Guanyu1, SUN Peng1，2, ZHANG Jieyong1, WU Junsheng3. Adaptive adjustment of command and control structure based on discrete firefly algorithm [J]. Computer Engineering and Applications, 2018, 54(15): 112-119.
[11]	DUAN Yanming1, XIAO Huihui1，2. Improved fruit fly algorithm for TSP problem [J]. Computer Engineering and Applications, 2016, 52(6): 144-149.
[12]	WAN Zhengyi, PENG Yuxu. Improved quantum ant colony algorithm for Traveling Salesman Problem [J]. Computer Engineering and Applications, 2016, 52(22): 59-63.
[13]	LI Xu, LIU Zhengyan. Fuzzy self-adaptive ant colony algorithm based on cloud model [J]. Computer Engineering and Applications, 2016, 52(2): 24-27.
[14]	ZHOU Hu, ZHAO Hui, ZHOU Huan, WANG Xiaofei. Symbiotic organisms search algorithm using adaptive elite opposition-based learning [J]. Computer Engineering and Applications, 2016, 52(19): 161-166.
[15]	HE Xueming1, SU Lili1, KONG Lijuan1, WU Meiping1, ZHANG Rong2, JI Xiaogang1. Unknown surface adaptive measurement based on non-uniform B-splines [J]. Computer Engineering and Applications, 2016, 52(12): 189-193.

Improved adaptive hybrid ant algorithm for traveling salesman problem

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics