What happens when things go wrong? This article goes into a few of the major factors that could be affecting the performance of your Genetic Algorithm. It is obviously not comprehensive, but these are the most common in my experience.

Enemy: Non-Convergence

What happens when your population doesn't make any progress after hundreds of generations? What kind of adjustments need to be made? This is where developing Genetic Algorithms gets tricky, because the problem could be any combination of dozens of factors in the design of your algorithm. The first thing you should do is look for possible bugs in your program. (to most programmers this should be second-nature, but it bears repeating). The next thing you do when your population doesn't converge is to rerun it from the beginning. Since Genetic Algorithms are probabilistic, there is always a (very slight) chance that this population was a fluke - and you don't want to worry about fixing anything that's not broken. Assuming you've got those two things off the checklist, take a look at some of these factors to check.

Mutation Rate is too high. The mutation operator ought to be only a subtle effect that shouldn't affect the overall performance of the algorithm. Make sure that your mutation operator isn't having too big of an effect - maybe make the elite genomes immune to mutation.

Diluting the talent. If your population size is too big, then sometimes the best genome aren't really getting a good chance of being chosen because they are being washed out by the sheer amount of genomes in the rest of the population. Make the population have less genomes so that new talent can express itself. Using a Tournament operator helps this, too.

Fitness Function is not specific enough. A genetic algorithm will never work if the possible fitness values range from 1 to 10 - there needs to be more precision than that. The population will evolve over many generations to eventually get a good idea only if the fitness function can point out the "best" from the "almost best". If every genome has a fitness score of 3, then finding the right ideas to exploit and evolve is just a shot in the dark.

Selection Operator parameters need adjustment. Are most of the genomes getting a chance to mate? Even the worst genomes should mate because their child has a chance at being really good. Or maybe a 2-tiered tournament would work better than a 1-tiered in this case. Go over the selection operator and the kinds of parameters you give it to see if there are any adjustments.

Consider the search space versus the population size. Is the search space too big for the given population size? If so, consider limiting the search space, using subpopulations, or using speciation (more discussion on this in the next article).

Enemy: Uniformity

Suppose your population "jumps to conclusions". It converges after only, say, fifty generations and won't accept any new ideas after that because all of the genome are too similar. This is a more typical problem to have than non-convergence, and you want to approach it the same way: debug your software then rerun the algorithm to make sure. Look at some of these other factors that could lead to a uniform population.

The fitness function could be biased toward a certain solution. It's easy to write a fitness function which evaluates a genome with a particular solution in mind - this is wrong. The population needs to evolve into a good solution and not play "guess what the programmer is thinking". Instead of making your fitness function compare each genome to a "best genome", evaluate it some way assuming you don't already know the answer. If you don't know the answer ahead of time, or if you pretend you don't know the answer, the fitness function is a lot easier to write.

Mutation only goes so far. Don't expect the mutation operator to be the one factor which keeps the population from jumping to conclusions. The purpose of mutation is to provide new ideas, it doesn't have much effect in uniformity.

Consider the killing operator. Most of the ideas for this were discussed in the Surival Operator section, but make sure that good genomes aren't replacing slightly lesser genomes because that will eventually stunt the growth.

If using Roulette Wheel, consider using Fitness Scaling. Fitness Scaling is a magical tool which will "level the playing field" if the elite genomes are too influential on the rest of the population. After obtaining fitness from each genome, take either the square root of each fitness or the logarithm. There's no point in using fitness scaling in a Tournament selector because square root and logarithms are both order-preserving. In either case, for practical reasons, make sure you multiply those by a power of 10 so that your fitness is just as precise. I once read an article which argued to take the square root, which does work reasonably well, but I think taking the log and multiplying by a power of 10 works really well partway through the evolution because a really good genome will propagate itself exponentially through the population, so that will limit its immediate influence. The inspiration for this came when graphing the average fitness of a population and noticing that at one point the graph look like an exponential function.

Left: Graph of average fitness for the first 400 generations. Right: graph of f(x) = log(1+x).
Doesn't it look like a logarithm for the increasing portion?

News | Research | Personal Profile | Photo Album
Contact Me