Some issues of designing genetic algorithms for traveling salesman problems

H. K. Tsai*, Jinn-Moon Yang, Y. F. Tsai, C. Y. Kao

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

This paper demonstrates that a robust genetic algorithm for the traveling salesman problem (TSP) should preserve and add good edges efficiently, and at the same time, maintain the population diversity well. We analyzed the strengths and limitations of several well-known genetic operators for TSPs by the experiments. To evaluate these factors, we propose a new genetic algorithm integrating two genetic operators and a heterogeneous pairing selection. The former can preserve and add good edges efficiently and the later will be able to keep the population diversity. The proposed approach was evaluated on 15 well-known TSPs whose numbers of cities range from 101 to 13509. Experimental results indicated that our approach, somewhat slower, performs very robustly and is very competitive with other approaches in our best surveys. We believe that a genetic algorithm can be a stable approach for TSPs if its operators can preserve and add edges efficiently and it maintains population diversity.

Original languageEnglish
Pages (from-to)689-697
Number of pages9
JournalSoft Computing
Volume8
Issue number10
DOIs
StatePublished - 1 Dec 2004

Keywords

  • Edge assembly crossover
  • Genetic algorithm
  • Heterogeneous pairing selection
  • Neighbor-join mutation
  • Traveling salesman problem

Fingerprint Dive into the research topics of 'Some issues of designing genetic algorithms for traveling salesman problems'. Together they form a unique fingerprint.

Cite this