An Adaptive Ant Colony Optimization for Solving Large-Scale Traveling Salesman Problem

被引:6
作者
Tang, Kezong [1 ]
Wei, Xiong-Fei [1 ]
Jiang, Yuan-Hao [2 ]
Chen, Zi-Wei [1 ]
Yang, Lihua [1 ]
机构
[1] Jingdezhen Ceram Univ, Sch Informat Engn, Jingdezhen 333403, Peoples R China
[2] East China Normal Univ, Sch Comp Sci & Technol, Shanghai 200062, Peoples R China
关键词
meta-heuristic algorithm; adaptive optimization; traveling salesman problem; large-scale optimization; path optimization; ALGORITHM; SYSTEM;
D O I
10.3390/math11214439
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
The ant colony algorithm faces dimensional catastrophe problems when solving the large-scale traveling salesman problem, which leads to unsatisfactory solution quality and convergence speed. To solve this problem, an adaptive ant colony optimization for large-scale traveling salesman problem (AACO-LST) is proposed. First, AACO-LST improves the state transfer rule to make it adaptively adjust with the population evolution, thus accelerating its convergence speed; then, the 2-opt operator is used to locally optimize the part of better ant paths to further optimize the solution quality of the proposed algorithm. Finally, the constructed adaptive pheromone update rules can significantly improve the search efficiency and prevent the algorithm from falling into local optimal solutions or premature stagnation. The simulation based on 45 traveling salesman problem instances shows that AACO-LST improves the solution quality by 79% compared to the ant colony system (ACS), and in comparison with other algorithms, the PE of AACO-LST is not more than 1% and the Err is not more than 2%, which indicates that AACO-LST can find high-quality solutions with high stability. Finally, the convergence speed of the proposed algorithm was tested. The data shows that the average convergence speed of AACO-LST is more than twice that of the comparison algorithm. The relevant code can be found on our project homepage.
引用
收藏
页数:26
相关论文
共 52 条
[1]   Visibility Adaptation in Ant Colony Optimization for Solving Traveling Salesman Problem [J].
Bin Shahadat, Abu Saleh ;
Akhand, M. A. H. ;
Kamal, Md Abdus Samad .
MATHEMATICS, 2022, 10 (14)
[2]   Metaheuristics in combinatorial optimization: Overview and conceptual comparison [J].
Blum, C ;
Roli, A .
ACM COMPUTING SURVEYS, 2003, 35 (03) :268-308
[3]   Symmetric uncertainty based decomposition multi-objective immune algorithm for feature selection [J].
Chai, Zhengyi ;
Li, Wangwang ;
Li, Yalun .
SWARM AND EVOLUTIONARY COMPUTATION, 2023, 78
[4]  
[陈斌 Chen Bin], 2021, [计算机科学与探索, Journal of Frontiers of Computer Science & Technology], V15, P1680
[5]   A discrete tree-seed algorithm for solving symmetric traveling salesman problem [J].
Cinar, Ahmet Cevahir ;
Korkmaz, Sedat ;
Kiran, Mustafa Servet .
ENGINEERING SCIENCE AND TECHNOLOGY-AN INTERNATIONAL JOURNAL-JESTECH, 2020, 23 (04) :879-890
[6]   Multi-Subdomain Grouping-Based Particle Swarm Optimization for the Traveling Salesman Problem [J].
Cui, Ying ;
Zhong, Jiabao ;
Yang, Fengru ;
Li, Shixin ;
Li, Penghao .
IEEE ACCESS, 2020, 8 :227497-227510
[7]   Dynamic Flying Ant Colony Optimization (DFACO) for Solving the Traveling Salesman Problem [J].
Dahan, Fadl ;
El Hindi, Khalil ;
Mathkour, Hassan ;
AlSalman, Hussien .
SENSORS, 2019, 19 (08)
[8]  
Dorigo M., 1997, IEEE Transactions on Evolutionary Computation, V1, P53, DOI 10.1109/4235.585892
[9]   Ant system: Optimization by a colony of cooperating agents [J].
Dorigo, M ;
Maniezzo, V ;
Colorni, A .
IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS, 1996, 26 (01) :29-41
[10]   一种面向对象的多角色蚁群算法及其TSP问题求解 [J].
杜鹏桢 ;
唐振民 ;
孙研 .
控制与决策, 2014, 29 (10) :1729-1736