A Hybrid Local Search and Genetic Algorithm with Enhanced Population Initialization for the Traveling Salesman Problem

Abstract

The Traveling Salesman Problem (TSP) remains a fundamental NP-hard combinatorial optimization challenge with significant theoretical and practical implications. While Genetic Algorithms (GAs) have demonstrated considerable promise for solving TSP instances, their performance is often hindered by poor initial population quality, leading to slow convergence and suboptimal solutions, particularly for large-scale problems. This paper presents a novel Hybrid Local Search and Genetic Algorithm (HLGA) that addresses these limitations through strategic population initialization. The proposed approach synergistically combines high-quality solutions generated by 2-opt and 3-opt local search heuristics with diversity-enhancing random permutations to create an enriched initial population. This hybrid initialization strategy accelerates convergence while maintaining solution space exploration capabilities. Comprehensive experiments conducted on 27 TSPLIB benchmark instances (30-200 cities) demonstrate HLGA's superior performance compared to standalone 3-opt heuristics and five state-of-the-art algorithms (GGSC-SSA, SCGA, IMODE/J2020, ACO-DSA, and RL-SA). Notably, HLGA achieves or surpasses the Best-Known Solution (BKS) for 11 instances, with an overall average relative error of 9.22%—significantly outperforming the 3-opt baseline (83.91%). These results validate that integrating targeted local search into population initialization substantially enhances both convergence speed and solution quality, establishing HLGA as a competitive and scalable approach for large-scale TSP optimization