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 GenerationalEvolutionEngine<String>(factory,
                                              pipeline,
                                              fitnessEvaluator,
                                              selection,
                                              rng);
      

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. Elitism is explained in Chapter 3, Selection Strategies & 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 because we have 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));
System.out.println(result);
        

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:

  HELLO WORLD
        

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: %s\n",
                          data.getGenerationNumber(),
                          data.getBestCandidate());
    }
});
        

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
  HELLO WORLD