A study of permutation crossover operators on the traveling salesman problem

The application of Genetic Algorithms to problems which are not amenable to bit string representation and traditional has been a growing area of interest. One approach has been to represent solutions by permutations of a list, and crossover operators have been introduced to preserve legality of offspring. Three permutation crossovers are analyzed to characterize how they sample the o-schema space, and hence what type of problems they may be applicable to. Experiments performed on the Traveling Salesman Problem go some way to support the theoretical analysis.