TY - JOUR
T1 - Heuristic smoothing ant colony optimization with differential information for the traveling salesman problem
AU - Li, Wei
AU - Wang, Cancan
AU - Huang, Ying
AU - Cheung, Yiu-ming
N1 - Publisher Copyright:
© 2022 Elsevier B.V. All rights reserved.
PY - 2023/1
Y1 - 2023/1
N2 - The traveling salesman problem (TSP) is an NP complete problem with potential applications. Thus far, numerous approaches have been proposed to solve the TSP including exact, heuristic and metaheuristic methods. Among them, the ant colony optimization (ACO) algorithm, belonging to metaheuristic methods, has proven to be an efficient method for solving the TSP. However, the phenomena of rapid convergence to local optima and unsatisfactory computational accuracy distinctly limit the performance of ACO. This study therefore proposes a novel ACO algorithm (HSDACO) to compensate for these shortcomings. In the HSDACO algorithm, the involvement of heterogeneous population automation at each iteration generates better candidate solutions with maintaining parameter diversity. Then, the implementation of three smoothing techniques with the 2-Opt method guarantees the effective assessment of candidate solutions in favor of higher quality. Next, the introduction of a differential information updating mechanism, using differential edge information obtained from the candidate solutions, enables the evaporation operation of the pheromone trail to obtain more reasonable guidance. Subsequently, the design of evolutionary state estimation and adjustment is used to monitor the population under correct guidance and regulate the evolutionary state effectively and efficiently. Finally, the HSDACO algorithm is evaluated on public TSP benchmark instances and compared with the other state-of-the-art algorithms. Experimental results show that the proposed HSDACO achieves substantial improvement for mid-scale TSP instances and overwhelming advantages for small-scale TSP instances, in terms of solution accuracy and convergence speed.
AB - The traveling salesman problem (TSP) is an NP complete problem with potential applications. Thus far, numerous approaches have been proposed to solve the TSP including exact, heuristic and metaheuristic methods. Among them, the ant colony optimization (ACO) algorithm, belonging to metaheuristic methods, has proven to be an efficient method for solving the TSP. However, the phenomena of rapid convergence to local optima and unsatisfactory computational accuracy distinctly limit the performance of ACO. This study therefore proposes a novel ACO algorithm (HSDACO) to compensate for these shortcomings. In the HSDACO algorithm, the involvement of heterogeneous population automation at each iteration generates better candidate solutions with maintaining parameter diversity. Then, the implementation of three smoothing techniques with the 2-Opt method guarantees the effective assessment of candidate solutions in favor of higher quality. Next, the introduction of a differential information updating mechanism, using differential edge information obtained from the candidate solutions, enables the evaporation operation of the pheromone trail to obtain more reasonable guidance. Subsequently, the design of evolutionary state estimation and adjustment is used to monitor the population under correct guidance and regulate the evolutionary state effectively and efficiently. Finally, the HSDACO algorithm is evaluated on public TSP benchmark instances and compared with the other state-of-the-art algorithms. Experimental results show that the proposed HSDACO achieves substantial improvement for mid-scale TSP instances and overwhelming advantages for small-scale TSP instances, in terms of solution accuracy and convergence speed.
KW - Ant colony optimization
KW - Differential information updating
KW - Evolutionary state estimation
KW - Search smooth method
KW - Traveling salesman problem
UR - http://www.scopus.com/inward/record.url?scp=85144496676&partnerID=8YFLogxK
U2 - 10.1016/j.asoc.2022.109943
DO - 10.1016/j.asoc.2022.109943
M3 - Journal article
AN - SCOPUS:85144496676
SN - 1568-4946
VL - 133
JO - Applied Soft Computing
JF - Applied Soft Computing
M1 - 109943
ER -