A Hybrid Algorithm for the Traveling Salesman Problem with Adaptive Three-Stage Coordination

Abstract

The Traveling Salesman Problem (TSP) is a classic NP-hard combinatorial optimization problem where traditional intelligent algorithms often suffer from slow convergence and premature convergence to local optima. This paper proposes a novel hybrid optimization framework (HGA-PSO-ACO) that integrates the global exploration capability of the Genetic Algorithm (GA), the rapid convergence characteristics of Particle Swarm Optimization (PSO), and the positive feedback mechanism of Ant Colony Optimization (ACO) through a three-stage adaptive coordination model. The key design challenge is to determine when each component should dominate the search and how information should be transferred across stages without causing premature homogenization of the population. To address this issue, the algorithm employs fitness variance (FVD) for real-time population state monitoring and implements dynamic algorithm switching strategies. Experimental validation on a 40-city TSP benchmark demonstrates that the hybrid algorithm achieves a 40% faster convergence speed, a 2.1% lower relative error, and a 58.3% reduction in run-to-run standard deviation compared to individual algorithms, indicating improved solution stability together with favorable parameter sensitivity control.