A Powerful Genetic Algorithm Using Edge Assembly Crossover for the Traveling Salesman Problem

This paper presents a genetic algorithm GA for solving the traveling salesman problem TSP. To construct a powerful GA, we use edge assembly crossover EAX and make substantial enhancements to it: i localization of EAX together with its efficient implementation and ii the use of a local search procedure in EAX to determine good combinations of building blocks of parent solutions for generating even better offspring solutions from very high-quality parent solutions. In addition, we develop iii an innovative selection model for maintaining population diversity at a negligible computational cost. Experimental results on well-studied TSP benchmarks demonstrate that the proposed GA outperforms state-of-the-art heuristic algorithms in finding very high-quality solutions on instances with up to 200,000 cities. In contrast to the state-of-the-art TSP heuristics, which are all based on the Lin--Kernighan LK algorithm, our GA achieves top performance without using an LK-based algorithm.