This is a proof of concept for a clean way to solve the traveling salesman problem with a genetic algorithm.
It is not straightforward how to encode the traveling salesman problem for a genetic algorithm, because the crossover and mutation operators should not produce illegal routes. Most suggestions introduce rather complicated variations of these operators or of the encoding of a route to deal with this problem.
I have found a very simple alternative: instead of encoding routes directly, encode permutations. As is known from group theory, every permutation can be written as a sequence of transpositions (swapping of two elements). Therefore for n cities, as a gene I use n transpositions (for example (1 3)(4 2)(1 1)...). The final route is derived from the gene by applying the transpositions to the sequence (1 ... n) (for example (1 2 3 4) with transpositions (1 3)(2 4) becomes (3 4 1 2)). That way, the standard crossover and mutation operators can not produce illegal elements.
I have verified that it works for small n, but have not put much further work into it yet. I can not say how well this encoding performs compared to other solutions. There might be disadvantages, for example because the transpositions are applied in order, the first transposition carries much more weight than the later ones. On the other hand, it is conceivable that the GA can correct for this by itself. Certainly some more experiments could be run for this approach.
I would be delighted to be contacted by anyone who would be interested into looking further into this, or simply for helpful comments.
