A Powerful Genetic Algorithm Using Edge Assembly Crossover for the Traveling Salesman Problem
Yuichi Nagata, Shigenobu Kobayashi · INFORMS journal on computing · 2012
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.
Cited by 221 works. doi:10.1287/ijoc.1120.0506
Authors
References
- An Effective Heuristic Algorithm for the Traveling-Salesman Problem
- Scheduling Problems and Traveling Salesmen: The Genetic Edge Recombination Operator
- Genetic Algorithms for the Traveling Salesman Problem
- An effective implementation of the Lin–Kernighan traveling salesman heuristic
- Local Search in Combinatorial Optimization
- Scheduling problems and traveling salesman: the genetic edge recombination
- Alleles, loci and the traveling salesman problem
- Genetic local search algorithms for the traveling salesman problem
- A new adaptive multi-start technique for combinatorial global optimizations
- The Traveling Salesman Problem: A Case Study in Local Optimization