Genetic Algorithm with Guided Search and Multi-Heuristic Operators for Solving Traveling Salesman Problems
TL;DR
Experimental results show that GA-GSMHO outperforms the original GA and six state-of-the-art metaheuristic algorithms and achieves higher solution quality, faster convergence, and greater stability of results.
Abstract
To address the poor solution quality, slow convergence, and susceptibility to premature convergence of genetic algorithm (GA) in solving the Traveling Salesman Problem (TSP), this study introduces a guided search framework with multi-heuristic operators. The proposed approach integrates three novel heuristic operators and an enhanced local search mechanism: (1) a hybrid initialization technique that combines a greedy approach to prioritize high-quality starting points with random sampling to maintain population variance; (2) a novel bidirectional greedy sequential constructive crossover integrated with order crossover (BGSCX-OX) to achieve an ideal equilibrium between local refinement and global search; (3) an adaptive hybrid mutation strategy that self-adjusts based on real-time search conditions; and (4) an improved 3-Opt for local refinement. The effectiveness of the proposed algorithm is validated using 26 benchmark instances from the TSPLIB dataset. Experimental results show that GA-GSMHO outperforms the original GA and six state-of-the-art metaheuristic algorithms. It achieves higher solution quality, faster convergence, and greater stability of results.