How can I improve this genetic algorithm for the TSP?

Question

This is my genetic algorithm, step by step:

1. Generate two initial population's randomly, and select the fittest tour from both.

2. Perform an ordered crossover, which selects a random portion of the first fit tour and fills in the rest from the second, in order.

3. Mutates this tour by randomly swapping two cities if the tour is only 1.3 times as good as the top 10% tour in the initial population (which I have literally just done by induction, singling out poor tours that are produced) - I would love to change this but can't think of a better way.

   • The mutation is selected from a population of several mutations.

4. Returns the tour produced.

The mutation, however is almost ALWAYS worse, if not the same as the crossover.

I'd greatly appreciate some help. Thanks!

Answer 1

A problem in GA's is narrowing your search space too quickly and reaching a local maxima solution. You need to ensure that you are not leading your solution in any way other than in the selection/fitness function. So when you say,

why would you take a good solution and then perform a function that will most likely make it a worse solution

,the reason is that you WANT a chance for the solution to take a step back, it will likely need to get worse before it gets better. So really you should remove any judgement logic from your genetic operators, leave this to the selection process.

Also, crossover and mutation should be seen as 2 different ways of generating a child individual, you should use one or the other. In practice, this means you have a chance of performing either a mutation of a single parent or a crossover between 2 parents. Usually the mutation chance is only 5% with crossover being used to generate the other 95%.

A crossover keeps the genetic information from both parents (children are mirror images), so one child will be worse than the parents and the other better (or both the same). So in this sense with crossover, if there is a change, you will always get a better individual.

Mutation on the other hand offers no guarantee of a better individual, yet it exists for the purpose of introducing new data, helping to move the GA from the local maxima scenario. If the mutation fails to improve the individual and makes it worse, then it has less chance of being selected for parenting a child anyway (i.e. you don't need this logic in the mutation operator itself).

you select the best one to mutate

This is not strictly true, good individuals should have a higher CHANCE of being selected. In here there is a subtle difference that BAD individuals may also be selected for parents. Again this helps reduce the chance of reaching a local maxima solution. This also means that the best individual for a generation could (and often does) actually get worse. To solve this we usually implement 'elitism', whereby the best individual is always copied to the next generation (at it is/undergoing no operations).

It would also be beneficial if I could comment on which genetic operators you are using. I have found cycle crossover and inversion mutation to work well in my experience.