Genetic algorithm solution of the TSP avoiding special crossover and mutation

Creative Commons License

Ucoluk G.

INTELLIGENT AUTOMATION AND SOFT COMPUTING, cilt.8, sa.3, ss.265-272, 2002 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 8 Sayı: 3
  • Basım Tarihi: 2002
  • Doi Numarası: 10.1080/10798587.2000.10642829
  • Dergi Adı: INTELLIGENT AUTOMATION AND SOFT COMPUTING
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.265-272
  • Anahtar Kelimeler: genetic algorithms, permutation representation, traveling salesman problem, crossover, partially mapped crossover, PMX, TSP, OPTIMIZATION, EVOLUTION
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

Ordinary representations of permutations in Genetic Algorithms (GA) is handicapped with producing offspring which are not permutations at all. The conventional solution for crossover and mutation operations of permutations is to device 'special' operators. Unfortunately these operators suffer from violating the nature of crossover. Namely, considering the gene positions on the chromosome, these methods do not allow n-point crossover techniques which are known to favour building-block formations. In this work, an inversion sequence is proposed as the representation of a permutation. This sequence allows repetitive values and hence is robust under ordinary (n-point) crossover. There is a one-to-one mapping from ordinary permutation representation to the inversion sequence representation.