A Multi-Strategy Adaptive Ant Colony Optimization Algorithm for Solving the Traveling Salesman Problem

Abstract

Traditional ant colony optimization (ACO) often suffers from insufficient initial pheromone information, premature convergence, and limited adaptability across problem scales when solving the traveling salesman problem (TSP). This study proposes a multi-strategy adaptive ant colony optimization algorithm, termed MSA-ACO. Unlike hybrid ACO methods whose added strategies are governed by separate or predetermined rules, MSA-ACO uses smoothed normalized pheromone entropy as a shared internal search-state signal. This signal coordinates search-stage switching, exploitation preference, pheromone evaporation intensity, heuristic-information dependence, and the adaptive 3-opt budget under scale-dependent control profiles. A rank-weighted multi-elite initialization method and candidate-restricted hierarchical 2-opt/3-opt search are further incorporated to improve early guidance and solution refinement. Experiments on 35 TSPLIB instances show that MSA-ACO attains the best-known solution on 22 instances and achieves an average best-solution deviation of 0.17%, compared with 3.87% for ACS and 5.27% for MMAS. Its maximum deviation is 1.22%, and the deviation remains within 1% on 33 instances. Nonparametric tests confirm significantly better overall solution quality than ACS and MMAS. Under equal distance-query budgets, MSA-ACO obtains the lowest mean tour length on st70, kroC100, and kroA150, with significant improvements over ACS-based local search on kroC100 and kroA150. Component-wise ablation and sequential timing results reveal instance-dependent component effects and identify 3-opt as a major source of computational cost as well as an important refinement mechanism on the larger instance. Moreover, compared with the fixed 1000-iteration setting, the scale-segmented iteration budget reduces average running time by 28.06–83.75% across four representative instances, while still attaining the BKS on eil76 and ts225 and yielding mean deviations of approximately 0.30% and 0.20% on ch150 and kroA200, respectively. Overall, MSA-ACO provides an effective scale-aware optimization framework for symmetric TSPs, combining consistently high solution quality with controlled computational effort across different instance scales.