Heterogeneous selection genetic algorithms for traveling salesman problems

Huai Kuang Tsai*, Jinn-Moon Yang, Yuan Fang Tsai, Cheng Yan Kao

*Corresponding author for this work

Research output: Contribution to journalArticle

10 Scopus citations

Abstract

This paper proposes a genetic algorithm, called the heterogeneous selection genetic algorithm (HSGA), integrating local and global strategies via family competition and edge similarity, for the traveling salesman problem (TSP). Local strategies include neighbor-join mutation and family competition, and global strategies consist of heterogeneous pairing selection and edge assembly crossover. Based on the mechanisms of preserving and adding edges, the search behaviors of neighbor-join mutation and edge assembly crossover are studied. The proposed method has been implemented and applied to 17 well-known TSPs whose numbers of cities range from 101 to 13,509. Experimental results indicate that this approach, although somewhat slower, performs very robustly and is very competitive with other approaches in the best surveys. This approach is able to find the optimum, and the average solution quality is within 0.00048 above the optima of each test problem.

Original languageEnglish
Pages (from-to)297-311
Number of pages15
JournalEngineering Optimization
Volume35
Issue number3
DOIs
StatePublished - 1 Jun 2003

Keywords

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

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

  • Cite this