Practical Evolutionary Computation: Elitism

Posted in Evolutionary Computation, Java, Software Development by Dan on February 12th, 2009

In my previous article about evolutionary computation, I glossed over the concept of elitism. The Watchmaker Framework‘s evolve methods require you to specify an elite count. I told you to set this parameter to zero and forget about it. This brief article ties up that loose end by explaining how to use elitism to improve the performance of your evolutionary algorithm.

In an evolutionary algorithm (EA), sometimes good candidates can be lost when cross-over or mutation results in offspring that are weaker than the parents. Often the EA will re-discover these lost improvements in a subsequent generation but there is no guarantee of this. To combat this we can use a feature known as elitism. Elitism involves copying a small proportion of the fittest candidates, unchanged, into the next generation. This can sometimes have a dramatic impact on performance by ensuring that the EA does not waste time re-discovering previously discarded partial solutions. Candidate solutions that are preserved unchanged through elitism remain eligible for selection as parents when breeding the remainder of the next generation.

NOTE: One potential downside of elitism is that it may make it more likely that the evolution converges on a sub-optimal local maximum.

The Watchmaker Framework supports elitism via the second parameter to the evolve method of an EvolutionEngine. This elite count is the number of candidates in a generation that should be copied unchanged from the previous generation, rather than created via evolution. Collectively these candidates are the elite. So for a population size of 100, setting the elite count to 5 will result in the fittest 5% of each generation being copied, without modification, into the next generation.

If you run the Hello World example from the previous article both with and without elitism, you will see that it completes in fewer generations with elitism enabled (22 generations vs. 40 when I ran it – though your mileage may vary due to the random nature of the evolution).

Source code for the Hello World example (and several other, more interesting evolutionary programs) is included in the download.

This is the third in a short and irregular series of articles on practical Evolutionary Computation, based on the work-in-progress documentation for the Watchmaker Framework for Evolutionary Computation.  The first article provided an introduction to the field of evolutionary computation and the second article showed how to implement a simple evolutionary algorithm using the Watchmaker Framework.

Further Reading

An Introduction to Genetic Algorithms Introduction to Evolutionary Computing The Blind Watchmaker