Genetic Algorithm Solution of the TSP Avoiding Special.pdfVIP

Genetic Algorithm Solution of the TSP Avoiding Special Crossover and Mutation ¨ ¨ ¨ Gokturk Uc¸oluk Department of Computer Engineering Middle East Technical University 06531 Ankara, Turkey Email: ucoluk@.tr Abstract Ordinary representations of permutations in Genetic Algorithms (GA) is hand- icapped with producing offspring which are not permutations at all. The conven- tional 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 ordi- nary (n-point) crossover. There is a one-to-one mapping from ordinary permutation representation to the inversion sequence representation. The proposed method is used for solving TSPs and is compared to the well known PMX special crossover method. It is observed that this method outperforms PMX in convergence rate by a factor which can be as high as 11.1 times, on a cost of obtaining slightly worse solutions on average. Key Words: genetic algorithms, permutation representation, traveling salesman problem, crossover, partially mapped Crossover, PMX, T