Why does adding Crossover to my Genetic Algorithm gives me worse results?

Question

I have implemented a Genetic Algorithm to solve the Traveling Salesman Problem (TSP). When I use only mutation, I find better solutions than when I add in crossover. I know that normal crossover methods do not work for TSP, so I implemented both the Ordered Crossover and the PMX Crossover methods, and both suffer from bad results.

Here are the other parameters I'm using:

Mutation: Single Swap Mutation or Inverted Subsequence Mutation (as described by Tiendil here) with mutation rates tested between 1% and 25%.

Selection: Roulette Wheel Selection

Fitness function: 1 / distance of tour

Population size: Tested 100, 200, 500, I also run the GA 5 times so that I have a variety of starting populations.

Stop Condition: 2500 generations

With the same dataset of 26 points, I usually get results of about 500-600 distance using purely mutation with high mutation rates. When adding crossover my results are usually in the 800 distance range. The other confusing thing is that I have also implemented a very simple Hill-Climbing algorithm to solve the problem and when I run that 1000 times (faster than running the GA 5 times) I get results around 410-450 distance, and I would expect to get better results using a GA.

Any ideas as to why my GA performing worse when I add crossover? And why is it performing much worse than a simple Hill-Climb algorithm which should get stuck on local maxima as it has no way of exploring once it finds a local max?

Answer 1

It looks like your crossover operator is introducing too much randomness into the new generations, so you are losing your computational effort trying to improve bad solutions. Imagine that the Hill-Climb algorithm can improve a given solution to the best of its neighborhood, but your Genetic Algorithm can only make limited improvements to almost random population (solutions).

It is also worth to say that GA is not the best tool to solve the TSP. Anyway, you should look like at some examples of how to implement it. e.g. http://www.lalena.com/AI/Tsp/

Answer 2

One reason for your results being worse when crossover is added because may be it is not doing what it should- combine the best features of two individuals. Try with a low crossover probability may be? Population diversity could be a issue here. Morrison and De Jong in their work Measurement of Population Diversity proposes a novel measure of diversity. Using that measure you can see how your population diversity is changing over the generations. See what difference it makes when you use crossover or don't use crossover.

Also, there could be some minor mistake/missed detail in your OX or PMX implementation. Maybe you have overlooked something? BTW, may be you want to try the Edge Recombination crossover operator? (Pyevolve has an implementation).

Answer 3

In order to come up with 'innovative' strategies genetic algorithms generally use crossover to combine feats of different candidate solutions in order to explore the search space very quickly and find new strategies of higher fitness - not at all unlike the inner workings of human intelligence (this is why it is arguable that we never really 'invent' anything, but merely mix up stuff we already know).

By doing so (randomly combining different individuals) crossover does not preserve symmetry or ordering, and when the problem is highly dependent on symmetry of some sort or on the order of the genes in the chromosome (as in your particular case) it is indeed likely that adopting crossover will lead to worse results. As you mention yourself, it is well known that known that crossover doesn't work for the traveling salesman.

It's worth underlining that without this symmetry breaking feat of crossover genetic algorithms would not be able to fill evolutionary 'niches' (where lack of symmetry is often necessary) - and that's why crossover (in all its variants) is essentially important in a vast majority of cases.

Answer 4

With roulette-wheel selection, you're introducing bad parents into the mix. If you'd like to weight the wheel somehow to choose some better parents, this may help.

Remember, much of your population might be unfit parents. If you're not weighting parent selection at all, there's a good chance you'll be breeding consistently bad solutions that overrun the pool. Weight your selection to choose better parents more frequently, and use mutation to correct a too-similar pool by adding randomness.

Answer 5

You might try introducing elitism into your selection process. Elitism means that the two highest fitness individuals in the population are preserved and copied to the new population before any selection is done. After elitism is completed, selection continues as normal. Doing this means that no matter which parents are selected by the roulette wheel or what they produce during crossover, the two best individuals will always be preserved. This prevents the new population from losing fitness because its two best solutions can't be any worse than the previous generation.