Crossover operation in genetic algorithm for TSP
I'm trying to solve the Travelling Salesman Problem (TSP) with Genetic algorithm. My genome is a permutation of a vertex in graph (path for salesman).
How should I perform the crossover operation over my genomes?
Where can I find implementations of my problem in C#?
Answer
You should check "Genetic Algorithm Solution of the TSP Avoiding Special Crossover and Mutation" by Gokturk Ucoluk. It gives an overview of the special crossover operators for permutations and proposes a clever representation of permutations that works well with standard crossover (i.e. crossing over two permutations always produces two permutations).
The key insight is to represent the permutation as its inversion sequence, i.e. for each element i, store in a[i] how many elements larger than i are to the left of i in the permutation. Unlike the direct representation, the only constraint on a[i] is local, i.e. a[i] cannot be larger than N - i. This means that simple crossover of two valid inversion sequences always produces two valid inversion sequences - no need for special handling of repeating elements.