CODEWITHSUNDEEP
genetic-algorithm
ahoffer
ahoffer

Reputation: 6526

Prevent inbreeding and monoculture in genetic algorithm (newbie 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?

Upvotes: 8

Views: 3310

Answers (2)

user571138
user571138

Reputation:

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.

Upvotes: 5

mitch
mitch

Reputation: 1900

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)

Upvotes: 3

Related Questions