Crossover operation in genetic algorithm for TSP

Question

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 1

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.

Answer 2

Rather than using the standard GA cross-over technique (as outlined by MusiGenesis), it's better to use ordered cross-over for the Travelling Salesman problem.

The usual approach doesn't work so well for the TSP because the fitness function is very sensitive to the relative positions of the different cities in the evolved route rather than their absolute positions. For example, if you were visiting all European capitals, the shortest route doesn't really depend on whether you visit Bratislava 1st, 2nd, or 9th. What's more important is that you visit it immediately before or immediately after visiting Vienna rather than visiting Helsinki, Athens and 6 other capitals in between.

Of course, as mjv also points out, the traditional cross-over will also introduce duplicates in your route. If one parent has Paris in position 2 and another has Paris in position 14, cross-over could result in one evolved route that visits Paris twice (and misses out another city), and another evolved route that doesn't visit it at all. The ordered cross-over genetic operator does not suffer from this problem. It preserves the elements and modifies the ordering.

Answer 3

Here is a C# program approach for what you are looking for.

With regards to the interest (or lack thereof) of implementing cross-over, it all hinges on the particular selection logic your implementation will use (and/or the evaluation function itself, if for example it includes an evaluation of the speed of improvement). In many cases, cross-over operations will "rescue from the chopping block" some solutions that are effective/optimal in an area of the graph but somehow "stuck" in others. This is not to say that if the overall algorithm is slow-enough and covers a good percentage of the solution space the same solutions may not have been discovered anew, but cross-over may also increase these discoveries (and/or letting you stuck in another local minima ;-) )

Not directly related but of noteworthy interest to whomever looks into GA, is the original "ultimate" experiment in GA original "ultimate" experiment in GA by Prof. Alderman (of RSA fame), who used actual DNA molecules [into a C program - just kidding] to solve a related graph problem, that of hamiltonian graphs.

Edit: In re-reading the question I understand why you asked it or more precisely why you'd like a "No you don't want cross-over" reply ;-)
Your genonme is directly tied to the graph itself (nothing wrong with that, a priori), but this brings the impediment that most cross-over offsrpings will not be viable, since they may may have duplicate nodes (visit same city twice or more) and be missing nodes (failing to visit some cities)... Furthermore, viable cross-overs will affect similar graphs, and hence maybe merely incrementally expend the search, compared with what mutations would have discovered...
Hum... Then maybe cross-over, in this particular implementation won't help the algorithm very much (and indeed take much of its CPU to create, test and often discard cross-over offsprings, CPU which would be better used by affording more iterations, and a slower cooling rate...). Unless! You find a clever way of performing cross-over operatitions ;-)

Answer 4

The purpose of crossover is to expand the evolutionary search space by bringing together novel genomic combinations.

The only real criteria required for the evolutionary process is that the product of crossover contains portions of both parents and represents a valid genome.

Only you know the validity rules for your algorithm so only you can specify a crossover method that will work (unless you want to share more details of the validation rules for you genome structure).

Answer 5

Here is my exact implementation of the so called "partially mapped crossover" method in a GA for TSP.

Here is a paper which explains the partially mapped crossover in theory and below is my code.

//construct a new individual with the genes of the parents
//method used is cross over mapping
//note that Individual datastrucuture contains an integer array called Genes which            //contains the route.
//
public Individual Breed(Individual father, Individual mother)
{
    int[] genes = new int[father.Genes.Length];
    int[] map = new int[father.Genes.Length + 1]; //create a map to map the indices
    int crossoverPoint1 = rand.Next(1, father.Genes.Length - 2); //select 2 crossoverpoints, without the first and last nodes, cuz they are always thje same
    int crossoverPoint2 = rand.Next(1, father.Genes.Length - 2);
    father.Genes.CopyTo(genes, 0); //give child all genes from the father
    for (int i = 0; i < genes.Length; i++) //create the map
    {
        map[genes[i]] = i;
    }
    //int[] genesToCopy = new int[Math.Abs(crossoverPoint1 - crossoverPoint2)]; //allocate space for the mother genes to copy
    if (crossoverPoint1 > crossoverPoint2) //if point 1 is bigger than point 2 swap them
    {
        int temp = crossoverPoint1;
        crossoverPoint1 = crossoverPoint2;
        crossoverPoint2 = temp;
    }
    //Console.WriteLine("copy mother genes into father genes from {0} to {1}", crossoverPoint1, crossoverPoint2);
    for (int i = crossoverPoint1; i <= crossoverPoint2; i++) //from index one to the 2nd
    {
        int value = mother.Genes[i];
        int t = genes[map[value]]; //swap the genes in the child
        genes[map[value]] = genes[i];
        genes[i] = t;
        t = map[genes[map[value]]]; //swap the indices in the map
        map[genes[map[value]]] = map[genes[i]];
        map[genes[i]] = t;
    }
    Individual child = new Individual(genes);
    return child;
}

Answer 6

When I was on the first course in my university, I was doing some calculations (which took about 30 pages) about the impact of various GA operators on the convergence of solution. As I remember, crossover is not the best solution for TSP, more suitable solution is mutation, which is inverting of sub-sequence of the vertexes.

example:

before: ABCDEFGH

after: AFEDCBGH

Answer 7

"Crossover" in genetic algorithms just refers to an arbitrary way of mixing two "genetic sequences", each of which represents a particular solution to a problem (how a sequence maps to a solution is up to you). So, for example, say you have a population that consists of the following two sequences:

AAAAAAAAAA
BBBBBBBBBB

One way to recombine these two "parent" sequences is to randomly pick a crossover point (say, position 3), resulting in these two "child" sequences:

AAABBBBBBB
BBBAAAAAAA

Or, you could randomly pick two crossover points (say, 3 and 8), resulting in these two sequences:

AAABBBBBAA
BBBAAAAABB

For fun and extra variability, you can also introduce the possibility of occasional point mutations:

AAABBBABAA
BBBAAAAABB

There aren't really any hard-and-fast rules regarding how you implement crossover in a genetic algorithm, just as there aren't really any hard-and-fast rules governing Evolution in the biological world. Whatever works, works.