Heuristic smoothing ant colony optimization with differential information for the traveling salesman problem

Wei Li, Cancan Wang, Ying Huang*, Yiu-ming Cheung

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

12 Citations (Scopus)

Abstract

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.

Original languageEnglish
Article number109943
JournalApplied Soft Computing
Volume133
DOIs
Publication statusPublished - Jan 2023

Scopus Subject Areas

  • Software

User-Defined Keywords

  • Ant colony optimization
  • Differential information updating
  • Evolutionary state estimation
  • Search smooth method
  • Traveling salesman problem

Fingerprint

Dive into the research topics of 'Heuristic smoothing ant colony optimization with differential information for the traveling salesman problem'. Together they form a unique fingerprint.

Cite this