Back to Search
Start Over
A Powerful Genetic Algorithm Using Edge Assembly Crossover for the Traveling Salesman Problem.
- Source :
- INFORMS Journal on Computing; Spring2013, Vol. 25 Issue 2, p346-363, 18p, 3 Diagrams, 4 Charts, 3 Graphs
- Publication Year :
- 2013
-
Abstract
- 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 10919856
- Volume :
- 25
- Issue :
- 2
- Database :
- Complementary Index
- Journal :
- INFORMS Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 87120578
- Full Text :
- https://doi.org/10.1287/ijoc.1120.0506