An Improved Ant Colony Optimization Based on an Adaptive Heuristic Factor for the Traveling Salesman Problem
The traveling salesman problem (TSP) is a typical combinatorial optimization problem, which is often applied to sensor placement, path planning, etc. In this paper, an improved ACO algorithm based on an adaptive heuristic factor (AHACO) is proposed to deal with the TSP. In the AHACO, three main impr...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2021-01-01
|
| Series: | Journal of Advanced Transportation |
| Online Access: | http://dx.doi.org/10.1155/2021/6642009 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849472831158484992 |
|---|---|
| author | Pengzhen Du Ning Liu Haofeng Zhang Jianfeng Lu |
| author_facet | Pengzhen Du Ning Liu Haofeng Zhang Jianfeng Lu |
| author_sort | Pengzhen Du |
| collection | DOAJ |
| description | The traveling salesman problem (TSP) is a typical combinatorial optimization problem, which is often applied to sensor placement, path planning, etc. In this paper, an improved ACO algorithm based on an adaptive heuristic factor (AHACO) is proposed to deal with the TSP. In the AHACO, three main improvements are proposed to improve the performance of the algorithm. First, the k-means algorithm is introduced to classify cities. The AHACO provides different movement strategies for different city classes, which improves the diversity of the population and improves the search ability of the algorithm. A modified 2-opt local optimizer is proposed to further tune the solution. Finally, a mechanism to jump out of the local optimum is introduced to avoid the stagnation of the algorithm. The proposed algorithm is tested in numerical experiments using 39 TSP instances, and results shows that the solution quality of the AHACO is 83.33% higher than that of the comparison algorithms on average. For large-scale TSP instances, the algorithm is also far better than the comparison algorithms. |
| format | Article |
| id | doaj-art-d9f410c59cb34d8c8dba7512851dc98f |
| institution | Kabale University |
| issn | 0197-6729 2042-3195 |
| language | English |
| publishDate | 2021-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Advanced Transportation |
| spelling | doaj-art-d9f410c59cb34d8c8dba7512851dc98f2025-08-20T03:24:25ZengWileyJournal of Advanced Transportation0197-67292042-31952021-01-01202110.1155/2021/66420096642009An Improved Ant Colony Optimization Based on an Adaptive Heuristic Factor for the Traveling Salesman ProblemPengzhen Du0Ning Liu1Haofeng Zhang2Jianfeng Lu3School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing, ChinaNanjing Customs, Nanjing, ChinaSchool of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing, ChinaSchool of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing, ChinaThe traveling salesman problem (TSP) is a typical combinatorial optimization problem, which is often applied to sensor placement, path planning, etc. In this paper, an improved ACO algorithm based on an adaptive heuristic factor (AHACO) is proposed to deal with the TSP. In the AHACO, three main improvements are proposed to improve the performance of the algorithm. First, the k-means algorithm is introduced to classify cities. The AHACO provides different movement strategies for different city classes, which improves the diversity of the population and improves the search ability of the algorithm. A modified 2-opt local optimizer is proposed to further tune the solution. Finally, a mechanism to jump out of the local optimum is introduced to avoid the stagnation of the algorithm. The proposed algorithm is tested in numerical experiments using 39 TSP instances, and results shows that the solution quality of the AHACO is 83.33% higher than that of the comparison algorithms on average. For large-scale TSP instances, the algorithm is also far better than the comparison algorithms.http://dx.doi.org/10.1155/2021/6642009 |
| spellingShingle | Pengzhen Du Ning Liu Haofeng Zhang Jianfeng Lu An Improved Ant Colony Optimization Based on an Adaptive Heuristic Factor for the Traveling Salesman Problem Journal of Advanced Transportation |
| title | An Improved Ant Colony Optimization Based on an Adaptive Heuristic Factor for the Traveling Salesman Problem |
| title_full | An Improved Ant Colony Optimization Based on an Adaptive Heuristic Factor for the Traveling Salesman Problem |
| title_fullStr | An Improved Ant Colony Optimization Based on an Adaptive Heuristic Factor for the Traveling Salesman Problem |
| title_full_unstemmed | An Improved Ant Colony Optimization Based on an Adaptive Heuristic Factor for the Traveling Salesman Problem |
| title_short | An Improved Ant Colony Optimization Based on an Adaptive Heuristic Factor for the Traveling Salesman Problem |
| title_sort | improved ant colony optimization based on an adaptive heuristic factor for the traveling salesman problem |
| url | http://dx.doi.org/10.1155/2021/6642009 |
| work_keys_str_mv | AT pengzhendu animprovedantcolonyoptimizationbasedonanadaptiveheuristicfactorforthetravelingsalesmanproblem AT ningliu animprovedantcolonyoptimizationbasedonanadaptiveheuristicfactorforthetravelingsalesmanproblem AT haofengzhang animprovedantcolonyoptimizationbasedonanadaptiveheuristicfactorforthetravelingsalesmanproblem AT jianfenglu animprovedantcolonyoptimizationbasedonanadaptiveheuristicfactorforthetravelingsalesmanproblem AT pengzhendu improvedantcolonyoptimizationbasedonanadaptiveheuristicfactorforthetravelingsalesmanproblem AT ningliu improvedantcolonyoptimizationbasedonanadaptiveheuristicfactorforthetravelingsalesmanproblem AT haofengzhang improvedantcolonyoptimizationbasedonanadaptiveheuristicfactorforthetravelingsalesmanproblem AT jianfenglu improvedantcolonyoptimizationbasedonanadaptiveheuristicfactorforthetravelingsalesmanproblem |