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

作者：Nagata Yuichi^*; Kobayashi Shigenobu

来源：INFORMS Journal on Computing, 2013, 25(2): 346-363.

DOI：10.1287/ijoc.1120.0506

• genetic algorithm
• traveling salesman
• crossover
• population diversity

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.

• 出版日期2013