Paper Info
Title
Improving EAX with restricted 2-opt
Abstract
Edge Assembly Crossover (EAX) is by far the most successful crossover operator in solving the traveling salesman problem (TSP) with Genetic Algorithms (GAs). Various improvements have been proposed for EAX in GA. However, some of the improvements have to make compromises between performance and solution quality. In this work, we have combined several improvements proposed in the past, including heterogeneous pair selection (HpS), iterative child generation (ICG), and 2-opt. We also incorporate 2-opt into EAX, and restricted the 2-opt local searches to sub-tours in the intermediates generated by EAX.Our proposed method can improve the performance of EAX with decreased number of generations, error rates, and computation time. The applications of conventional 2-opt and our restricted 2-opt concurrently have additive effect on the performance gain, and this performance improvement is more obvious in larger problems. The proposed method also enhanced the solution quality of EAX. The significances of the restricted 2-opt and the conventional 2-opt in EAX were analyzed and discussed.
Year
DOI
Venue
2005
10.1145/1068009.1068242
GECCO
Keywords
Field
DocType
improving eax,genetic algorithms,performance improvement,2-opt concurrently,computation time,additive effect,2-opt local search,edge assembly crossover,performance gain,solution quality,restricted 2-opt,traveling salesman problem,genetic algorithm,combinatorial optimization,generalization error,local search
Computer science,Travelling salesman problem,Artificial intelligence,Genetic algorithm,EAX mode,Mathematical optimization,Crossover,Algorithm,Combinatorial optimization,2-opt,Local search (optimization),Machine learning,Performance improvement
Conference
ISBN
Citations 
PageRank 
1-59593-010-8
2
0.49
References 
Authors
9
4
Name
Order
Citations
PageRank
Chen-Hsiung Chan11155.42
Sheng-An Lee21114.77
Cheng-yan Kao358661.50
Huai-Kuang Tsai413214.33