Practical Evolutionary Computation: Implementation

Posted in Evolutionary Computation, Java by Dan on January 21st, 2009

If an evolutionary algorithm is a good fit for a particular problem, there are plenty of options when it comes to implementing it. You may choose to use a high-level programming language for simplicity, or a low-level language for performance. You could write all of the code yourself from scratch, or you could reuse pre-written components and libraries. In this article we will necessarily be using one particular approach, but it is worth noting that there are alternatives.

Evolution Frameworks

As we saw previously, the basic outline of an evolutionary algorithm is fairly straightforward. It consists of a main loop that performs one generation per iteration, supplemented by a few functions to perform fitness evaluation, selection and mutation/cross-over. When implementing a simple EA, writing this structural code is not particularly onerous. However, if you write many different evolutionary programs, you end up writing code that is very similar over and over again.

A good programmer will usually want to extract and reuse this common code. Once you have done this, you have the basis of an evolutionary computation framework. Typically this will consist of an evolution engine that is reusable and that can accept different functions to customise fitness evaluation, selection and evolutionary operators.

An alternative to using a home-grown framework is to choose a ready-made one. There are open source evolutionary computation frameworks available for most programming languages. For popular languages, such as C, C++ and Java, there are dozens.

The advantage of a ready-made framework that is used by many other programmers is that it will have been well tested and should be free of significant bugs and performance problems. It may also provide advanced features such as parallel and/or distributed processing.

The Watchmaker Framework

The Watchmaker Framework for Evolutionary Computation is an extensible, high-performance, object-oriented framework for implementing platform-independent evolutionary algorithms in Java. It is freely available under a permissive Open Source licence.

This article introduces the core components of the Watchmaker Framework and shows how they can be used to implement simple evolutionary algorithms such as the “Hello World” example outlined previously.

The Evolution Engine

The central object of an evolutionary program built with the Watchmaker Framework is the evolution engine. An evolution engine is a general-purpose implementation of the evolutionary algorithm outline introduced previously.

The framework provides multiple implementations of the EvolutionEngine interface, but the one that you will usually want to use is ConcurrentEvolutionEngine. As its name suggests, it takes advantage of the parallel processing facilities of your computer in order to speed-up the evolutionary process.

An EvolutionEngine has a single generic type parameter that indicates the type of object that it can evolve. For the “Hello World” program, we need to be able to evolve Java strings. Code that creates an engine that can evolve strings would look something like this:

EvolutionEngine<String> engine
    = new ConcurrentEvolutionEngine<String>(candidateFactory,

Once you have created an EvolutionEngine, your program is as simple as calling the evolve method with appropriate arguments. However, as you can see from the code snippet above, there is a little bit of work to be done first in order to create an EvolutionEngine that is configured appropriately for the given problem. The constructor of the ConcurrentEvolutionEngine class requires five objects. These are:

  • A Candidate Factory
  • An Evolutionary Operator
  • A Fitness Evaluator
  • A Selection Strategy
  • A Random Number Generator

The Candidate Factory

The first object that needs to be plugged into the evolution engine is a candidate factory. Every evolutionary simulation must start with an initial population of candidate solutions and the CandidateFactory interface is the mechanism by which the evolution engine creates this population.

A candidate factory implementation has an associated type. It can only create objects of that type. The type must match the type of the evolution engine that it is plugged into. You can write your own implementation of CandidateFactory for your program or, if you are using a common type such as strings, lists or arrays, you may be able to use a ready-made factory from the org.uncommons.watchmaker.framework.factories package.

For our “Hello World” program, we can use the provided StringFactory:

// Define the set of permitted characters (A-Z plus space).
char[] chars = new char[27];
for (char c = 'A'; c <= 'Z'; c++)
    chars[c - 'A'] = c;
chars[26] = ' ';
// Factory for random 11-character Strings.
CandidateFactory<String> factory = new StringFactory(chars, 11);

Tip: When writing your own CandidateFactory implementations, it is easiest to extend the provided AbstractCandidateFactory base class since there is then only a single method that must be implemented.

Evolutionary Operators

Evolutionary operators are the components that perform the actual evolution of a population. Cross-over is an evolutionary operator, as is mutation.

In the Watchmaker Framework, evolutionary operators are defined in terms of the EvolutionaryOperator interface. This interface declares a single method that takes a list of selected individuals and returns a list of evolved individuals. Some operators (i.e. mutation) will process one individual at a time, whereas others will process individuals in groups (cross-over processes two individuals at a time).

As with candidate factories, evolutionary operators have associated types that must be compatible with the type of the evolution engine that they are used with. And, as with candidate factories, the framework provides several ready-made operators for common types. These can be found in the org.uncommons.watchmaker.framework.operators package. The cross-over and mutation operators that we need for our “Hello World” program are provided by the StringCrossover and StringMutation classes.

The Evolution Pipeline

Alert readers will have noticed that the evolution engine constructor only accepts a single evolutionary operator. So how can we use both cross-over and mutation? The answer is provided by the EvolutionPipeline operator. This is a compound evolutionary operator that chains together multiple operators of the same type.

List<EvolutionaryOperator<String>> operators
    = new LinkedList<EvolutionaryOperator<String>>();
operators.add(new StringCrossover());
operators.add(new StringMutation(chars, new Probability(0.02)));
EvolutionaryOperator<String> pipeline = new EvolutionPipeline<String>(operators);

Note: The evolution pipeline is just one of many useful operators included in the org.uncommons.watchmaker.framework.operators package. Elaborate evolution schemes can be constructed from combinations of these operators. Users of the Watchmaker Framework should take a few minutes to browse the API documentation and familiarise themselves with the available classes.

The Fitness Evaluator

So far we’ve been able to build our evolutionary program by simply combining instances of classes provided by the framework. There is one part of the program that we will always have to write for ourselves though and that is the fitness fuction, which is necessarily different for every program.

In the Watchmaker Framework, a fitness function is written by implementing the FitnessEvaluator interface. The getFitness method of this interface takes a candidate solution and returns its fitness score as a Java double. The method actually takes two arguments, but we can ignore the second for now.

The listing below is a fitness evaluator for the “Hello World” program. It simply assigns one point for each character in the candidate string that matches the corresponding position in the target string.

public class StringEvaluator implements FitnessEvaluator<String>
    private final String targetString = "HELLO WORLD";
      * Assigns one "fitness point" for every character in the
      * candidate String that matches the corresponding position in
      * the target string.
    public double getFitness(String candidate,
                             List<? extends String> population)
        int matches = 0;
        for (int i = 0; i < candidate.length(); i++)
            if (candidate.charAt(i) == targetString.charAt(i))
        return matches;
    public boolean isNatural()
        return true;

By some fitness measures, a higher value indicates a fitter solution. In other cases a lower value is better. The isNatural method of a fitness evaluator simply specifies which scenario applies. In Watchmaker Framework terminology, a natural fitness function is one that returns higher values for fitter individuals.

Selection Strategy

Selection is a key ingredient in any evolutionary algorithm. It’s what determines which individuals survive to reproduce and which are discarded. All we’ve said about selection so far is that it should favour fitter individuals. This definition permits several different implementations. The Watchmaker Framework includes all of the most common selection strategies in the org.uncommons.watchmaker.framework.selection package. These are sufficient for most evolutionary algorithms but, if necessary, it is straightforward to write your own implementation of the SelectionStrategy interface.

Some selection strategies work better than others for certain problems. Often a little trial-and-error is required to pick the best option. For now we will just create an instance of the RouletteWheelSelection class and use that for our “Hello World” application.  Roulette wheel selection is the most common type of fitness-proportionate selection. It gives all individuals a chance of being selected but favours the fitter individuals since an individual’s selection probability is derived from its fitness score.

Random Number Generator

The final dependency that must be satisfied in order to create an evolution engine is the random number generator (RNG). An evolution engine has a single RNG that it passes to its candidate factory, evolutionary operator and selection strategy. A discussion of the merits of various RNGs is beyond the scope of this article.  The standard java RNG (java.util.Random) is flawed, so instead we will use the provided org.uncommons.maths.random.MersenneTwisterRNG.

Completing the Jigsaw

We’ve now got all of the necessary pieces to complete the “Hello World” example application. Assuming that you’ve already created the StringEvaluator class (defined above) in a separate file, the code needed to create the evolution engine looks like this:

// Create a factory to generate random 11-character Strings.
char[] chars = new char[27];
for (char c = 'A'; c <= 'Z'; c++)
    chars[c - 'A'] = c;
chars[26] = ' ';
CandidateFactory<String> factory = new StringFactory(chars, 11);
// Create a pipeline that applies cross-over then mutation.
List<EvolutionaryOperator<String>> operators
    = new LinkedList<EvolutionaryOperator<String>>();
operators.add(new StringMutation(chars, new Probability(0.02)));
operators.add(new StringCrossover());
EvolutionaryOperator<String> pipeline = new EvolutionPipeline<String>(operators);
FitnessEvaluator<String> fitnessEvaluator = new StringEvaluator();
SelectionStrategy<Object> selection = new RouletteWheelSelection();
Random rng = new MersenneTwisterRNG();
EvolutionEngine<String> engine
    = new ConcurrentEvolutionEngine<String>(factory,

The listing above only creates the evolution engine, it does not perform any evolution. For that we need to call the evolve method. The evolve method takes three parameters. The first is the size of the population. This is the number of candidate solutions that exist at any time. A bigger population will often result in a satisfactory solution being found in fewer generations. On the other hand, the processing of each generation will take longer because there are more individuals to deal with. For the “Hello World” program, a population size of 10 is fine.

The second parameter is concerned with elitism. For now, just use a value of zero. The final varargs parameter specifies one or more termination conditions.

Termination Conditions

Termination conditions make the evolution stop. There are a few reasons why we would like the evolution to stop. The most obvious is when it has found the solution that we are looking for. In the case of the “Hello World” program, that is when we have found the target string. The target string has a fitness score of 11, so we use the TargetFitness condition.

To complete the evolutionary “Hello World” application, add the following two lines:

String result = engine.evolve(10, 0, new TargetFitness(11));

Note: When we move on to less trivial evolutionary programs, we will rarely be able to specify the outcome so precisely. The org.uncommons.watchmaker.framework.termination package includes other termination conditions that can be used. For example, we may want the program to run for a certain period of time, or a certain number of generations, and then return the best solution it has found up until that point. The ElapsedTime and GenerationCount conditions provide this functionality. Alternatively, we may want the program to continue as long as it is finding progressively better solutions. The Stagnation condition will terminate the evolution after a set number of generations pass without any improvement in the fitness of the fittest candidate. If multiple termination conditions are specified, the evolution will stop as soon as any one of them is satisfied.

Evolution Observers

Compile and run the above code and, perhaps after a brief pause, you’ll see the following output:


This is quite probably the most convoluted “Hello World” program you’ll ever write. It also gives no hints as to its evolutionary nature. We can make the program more interesting by adding an EvolutionObserver to report on the progress of the evolution at the end of each generation. Add the following code to your program before the call to the evolve method:

engine.addEvolutionObserver(new EvolutionObserver<String>()
    public void populationUpdate(PopulationData<? extends String> data)
        System.out.printf("Generation %d: %sn",

Re-compile the program and run it again. This time you’ll see all of the steps taken to arrive at the target string:

  Generation 0: JIKDORHOQZJ
  Generation 1: ULLLFQWZPXG
  Generation 2: UEULKFVFZLS
  Generation 3: KLLLFKZGRLS
  Generation 4: HLLLFKZGRLS
  Generation 5: HEDPOYWOZLS
  Generation 6: HEULKIWWZLD
  Generation 7: HPRLOYWOZLS
  Generation 8: HEULOYWOZLS
  Generation 9: HEULOYWORLS
  Generation 10: HEULOYWORLS
  Generation 11: HPLLK WQRLH
  Generation 12: HEBLOYWQRLS
  Generation 13: HEULOYWOBLA
  Generation 14: HEBLOIWMRLD
  Generation 15: HEBLOIWMRLD
  Generation 16: HEYLFNWQRLD
  Generation 17: HEBLOIWORLS
  Generation 18: HEBLOIWORLT
  Generation 19: HEBLOKWGRLD
  Generation 20: HELLAYWORLS
  Generation 21: HELHOIWORLT
  Generation 22: HEWLOIWORLS
  Generation 23: HEBLOYCORLD
  Generation 24: HELLKQWORLD
  Generation 25: HELLOIWORLT
  Generation 26: HELLOIWORLS
  Generation 27: HELLKQWORLD
  Generation 28: HELLFYWORLD
  Generation 29: HELLOIWORLD
  Generation 30: HELLOIWORLD
  Generation 31: HELLOIWORLD
  Generation 32: HELLOIWORLD
  Generation 33: HELLOIWORLD
  Generation 34: HELLOIWORLD
  Generation 35: HELLOIWDRLD
  Generation 36: HELLOIWORLD
  Generation 37: HELLOIWORLD
  Generation 38: HELLOPWORLD
  Generation 39: HELLOIWORLD
  Generation 40: HELLO WORLD

This is the second in a short series of articles on practical Evolutionary Computation.  The text is taken from the work-in-progress documentation for the Watchmaker Framework for Evolutionary Computation.  The first article provided an introduction to the field of evolutionary computation.

Further Reading

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