Take a look at the new version of this page: [ beta version ]. Tell us what you think.

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.

REFERENCES

• 1: Takeshi Yamada , Ryohei Nakano, Scheduling by Genetic Local Search with Multi-Step Crossover, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.960-969, September 22-26, 1996
• 2: Farid Alizadeh , Richard M. Karp , Lee A. Newberg , Deborah K. Weisser, Physical mapping of chromosomes: a combinatorial problem in molecular biology, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.371-381, January 25-27, 1993, Austin, Texas, United States
• 3: H. Bohr and S. Brunak, A Traveling Salesman Approach to Protein Conformation, Complex Systems, 3, 9--28, 1989.
• 4: L. Darrell Whitley , Timothy Starkweather , D'Ann Fuquay, Scheduling Problems and Traveling Salesmen: The Genetic Edge Recombination Operator, Proceedings of the 3rd International Conference on Genetic Algorithms, p.133-140, June 01, 1989
• 5: K. Maekawa, N. Mori, H. Kita, and H. Nishikawa, A Genetic Solution for the Traveling Salesman Problem by Means of a Thermodynamical Selection Rule, Proc. 1996 IEEE Int. Conference on Evolutionary Computation, 529--534, 1996.
• 6: Y. Nagata and S. Kobayashi, Edge Assembly Crossover: A High-power Genetic Algorithm for the Traveling Salesman Problem., Proc. of the 7th Int. Conf. on Genetic Algorithms, 450--457, 1997.
• 7: H.-K. Tsai, J.-M. Yang, and C.-Y. Kao, Solving Traveling Salesman Problems by Combining Global and Local Search Mechanisms., Proc. of the 2002 Congress on Evolutionary Computation, 12920--12925, 2002.
• 8: Y. Nagata, The EAX Algorithm Considering Diversity Loss, In Parallel Problem Solving from Nature - PPSN VIII, LNCS 3242, X. Yao, et al., Eds., Springer-Verlag, 2004, 332--341.
• 9: Jean-Paul Watson , C. Ross , V. Eisele , J. Denton , José Bins , C. Guerra , L. Darrell Whitley , Adele E. Howe, The Traveling Salesrep Problem, Edge Assembly Crossover, and 2-opt, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.823-834, September 27-30, 1998
• 10: Y. Nagata, Genetic Algorithm for Traveling Salesman Problem using Edge Assembly Crossover: its Proposal and Analysis., Ph.D. Thesis, Tokyo Institute of Technology, 2000.
• 11: H.-K. Tsai, J.-M. Yang, Y.-F. Tsai, and C.-Y. Kao, An Evolutionary Algorithms for Large Traveling Salesman Problems, IEEE Trans. Systems, Man, and Cybernetics - Part B: Cybernetics, 34, 1718--1729, 2004.
• 12: Kokolo Ikeda , Shigenobu Kobayashi, Deterministic Multi-step Crossover Fusion: A Handy Crossover Composition for GAs, Proceedings of the 7th International Conference on Parallel Problem Solving from Nature, p.162-171, September 07-11, 2002

INDEX TERMS

General Terms:
Algorithms

Keywords:
combinatorial optimization, edge assembly crossover (EAX), genetic algorithm, genetic algorithms, local search, restricted 2-opt, traveling salesman problem (TSP)