Hello everybody. I'm trying to solve the Travelling Salesman Problem (TSP) with Genetic algorithm
My Genome is permutation of vertex in graph (path for Salesman).
How should I perform the crossover operation over my genomes?
Where I can find implementations of my problem in C#?
Here is a C# program approaching 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 ;-)
The purpose of crossover to 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).
"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.
When I was on first course of 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 this problem, more suitable solution is mutation, which inverting subsequence of the vertexes.
example:
before: A**BCDEF**GH
after: A**FEDCB**GH
P.S. sorry for my English :-)
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.
You should check "Genetic Algorithm Solution of the TSP Avoiding Special Crossover and Mutation" by Gokturk Ucoluk. PDF here. 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).