Prevent inbreeding and monoculture in genetic algorithm (newbie question)

Question

I am writing a genetic algorithm. My population quickly develops a monoculture. I am using a small population (32 individuals) with a small number of discrete genes (24 genes per individual) and a single point cross-over mating approach. Combine that with a roulette wheel selection strategy and it is easy to see how all the genetic diversity is lost in just a few dozen generations.

What I would like to know is, what is the appropriate response? I do not have academic-level knowledge on GAs and only a few solutions come to mind:

1. Use a larger population. (slow)
2. Use runtime checks to prevent in-breeding. (slow)
3. Use more cross-over points. (not very effective)
4. Raise the number of mutations.

What are some appropriate responses to the situation?

Answer 1

I would look at a larger population, 32 induviduals is a very small population. I usually run GAs with a population at least in the number of chromosomes^2 range (by experience) to get a good starting distribution of individuals.

A possible way to speed things upwith a larger population is to spawn different threads (1 per individual, possibly in batches) when running your fitness function (usually the most expensive part of a GA).

Assuming a population of 32, and a Quad core system, spawn threads in batches of 8 (2 threads per cpu will interleave nicely) and you should be able to run approx 4 * faster.

Therefore if you have a time limit on how long to run your GA, this may be a solution.

Answer 2

You can add to that:

• tournament selection instead of roulette wheel
• island separated multi population scheme, with migration
• restarts
• incorporating ideas from estimation of distribution algorithms (EDA) (resampling the domain close to promising areas to introduce new individuals)