A Stagnation-Aware Genetic Algorithm with Spectral Graph Cuts and Adaptive Neighborhood Search for solving Traveling-Salesman Problem

Purpose: The Traveling-Salesman Problem (TSP) is a classical NP-hard combinatorial optimization problem with significant theoretical and practical importance. Although Genetic Algorithms (GAs) are widely used for solving TSP, conventional GA-based approaches often suffer from premature convergence and limited local exploitation, restricting their solution quality. Methods: We propose a Spectral-Adaptive Genetic Algorithm (SAGA) that integrates spectral graph partitioning and adaptive local search into a standard GA framework. Upon detecting population stagnation, the best individual is transformed into a graph representation of the tour, partitioned using the Fiedler vector of the normalized Laplacian, and locally refined within the resulting substructures. The improved solution is then reinjected into the population. Results: The proposed method is evaluated on standard TSPLIB benchmarks, with a detailed experimental study on the berlin52 dataset. Both the baseline GA and SAGA are executed under identical parameter settings using paired random seeds across 200 independent runs. Results demonstrate that SAGA achieves an average improvement of approximately 3.9% in tour length over the baseline GA, with the best solution reaching a tour length of 7744 units compared to the baseline’s best of 8636 units. Conclusion: These findings indicate that incorporating spectral information and adaptive local refinement significantly enhances the effectiveness of Genetic Algorithms for the TSP and provides a promising direction for hybrid metaheuristic design.