Hidden Clause

Time to look at the framework that I was sure I was going to like more than JGAP and ECJ.

I do like it; more than JGAP, but not as much as ECJ. I’ll send flowers later.

Since both of the examples, Hello World (genetic algorithm) and Simple Math Test (a genetic program), are already done in Watchmaker all I will be doing is explaining how they were done using the Watchmaker framework.

Hello World – A Genetic Algorithm

This is straight out of the Watchmaker Framework example code. Only two classes are needed:

• StringEvaluator, the fitness function
• StringsExample, the class that starts the evolution

The StringEvaluator class does three things:

• hold onto the string the chromosomes are supposed to evolve into
• check every character of the candidate string to determine how close it is to the desired string
• return false when asked if a valid fitness value increases or decreases.

The StringsExample class creates the evolutionary environment in which the strings will evolve. The interesting stuff happens in here (reformatted to fit on this page).

This first section creates crossover and mutation objects specific to strings.

• StringMutation mutates the evolving string using the alphabet as mutation values with a probability value of 0.02.
• StringCrossover handles the crossover of strings based on the defined number of crossover points. The default is 1 crossover point.

The pipeline contains the list of operators to be applied to the population; in this case just the two we just discussed.

StringsExample.java
...
public static String evolveString(String target)
{
    List<EvolutionaryOperator> operators
                       = new ArrayList<EvolutionaryOperator>(2);
    operators.add(new StringMutation(ALPHABET, new Probability(0.02d)));
    operators.add(new StringCrossover());
    EvolutionaryOperator pipeline
                      = new EvolutionPipeline(operators);

The EvolutionEngine is the petri dish where everything happens. The configuration objects are as follows:
– StringFactory, creates the initial chromosomes/individuals for the population
– pipeline, defined above
– StringEvaluator, the fitness function also discussed above
– RouletteWheelSelection, selects candidates at random where the probability is proportional to the candidates fitness score
– MersenneTwisterRNG, a faster more reliable random number generator

StringsExample.java
    ...
    EvolutionEngine engine
          = new ConcurrentEvolutionEngine(
                      new StringFactory(ALPHABET, target.length()),
                      pipeline,
                      new StringEvaluator(target),
                      new RouletteWheelSelection(),
                      new MersenneTwisterRNG());

The EvolutionObserver is an interesting construct. This visitor gives you a front row seat of things as they happen. It prints out a basic string, but has the potential for coolness.

StringsExample.java
    ...
    engine.addEvolutionObserver(new EvolutionLogger());

Finally, turn on the engine for a population of 100 with a 5% elitism rate. Stop evolving when the fitness score equals 0.

StringsExample.java
    ...
    return engine.evolve(100, // 100 individuals in the population.
                           5, // 5% elitism.
                         new TargetFitness(0, false));
}

The code for the above is part of the Watchmaker Framework so download and poke it to your heart’s content.

Simple Math Test – A Genetic Program

The Watchmaker documentation states that it is a framework for genetic algorithms. That made me quite concerned as Toby Segaran’s Simple Math Test is not an example of a genetic algorithm. However, a quick look at the examples in the WF download revealed a package named org.uncommons.watchmaker.example.geneticprogramming. In that package there is a file named GeneticProgrammingExample.java and it states:

GeneticProgrammingExample.java
...
/**
 * Simple tree-based genetic programming application based on the first example
 * in Chapter 11 of Toby Segaran's Progamming Collective Intelligence.
 * @author Daniel Dyer
 */

Gotta love it. Less work for me and I don’t have to fight my way into the framework to figure out how to use WF in a genetic programming context. It seems unfair that both of the examples I chose are already done in WF, but that’s life. However, I will come up with a GP example that WF, JGAP, and ECJ have not done and see what it takes to implement them. One day. Soon.

[Perhaps Daniel Dyer will include the GP-related bits in an upcoming version of Watchmaker. Code reuse is a nice thing. I am hoping ECJ does that as well.]

The example geneticprogramming package contains the following files:
Node.java
BinaryNode.java
LeafNode.java

IfThenElse.java
IsGreater.java

Addition.java
Subtraction.java
Multiplication.java
Constant.java
Parameter.java

Simplification.java

TreeCrossover.java
TreeEvaluator.java
TreeFactory.java
TreeMutation.java

GeneticProgrammingExample.java

That’s a lot of files. Not having many of those classes in the framework shows.

In GP, the solution is an executable tree. During the evolution of the solution there will be trees that are not executable as well as trees that execute, but produce incorrect solutions.

In Watchmaker, the EvolutionEngine controls the process of creating a population, evolving them using various operators like crossover and mutation, checking their fitness and selecting the survivors for the next generation. This entails configuring it with:

• a CandidateFactory which produces the population
• an EvolutionaryOperator which contains other EvolutionaryOperators such as TreeCrossover and TreeMutation
• a FitnessEvaluator
• a SelectionStrategy
• a random number generator that inherits from Random

In this case, the EvolutionEngine, an instance of ConcurrentEvolutionEngine, is configured with:

• a TreeFactory which produces a tree of Nodes
• an EvolutionPipeline which contains the crossover, mutation and simplification operators
• a TreeEvaluator which will evaluate the fitness of the current tree/chromosome (given 2 input values does the tree produce the desired output value?)
• a RouletteWheelSelection strategy
• a MersenneTwisterRNG random number generator

You can read more about the RouletteWheelSelection in the Watchmaker Javadocs and at the Newcastle University Engineering Design Center, and about the MersenneTwisterRNG in the Uncommons Math Package Javadocs and at the university where it was developed. The Reader’s Digest version:

• RouletteWheelSelection – selects candidates by giving them a higher chance of being randomly selected based on their fitness score. The higher the score the higher ther probability of their being chosen. They might be chosen more than once.
• MersenneTwisterRNG – a random number generator that is very random, very fast and very predictable. It is used by various pieces of Watchmaker to guarantee randomness where it is needed.

Let’s look at the fitness function next. The TreeEvaluator is initialized with an array of two input values and an output value. The code, while different than that found in Collective Intelligence, heads for the same target: if the difference between the result from the evolved formula and the supplied output value is zero then we have a winner.

TreeEvaluator.java
  ...
  double actualValue = candidate.evaluate(entry.getKey());
  double diff = actualValue - entry.getValue();
  error += (diff * diff);

The Watchmaker code takes the difference between the actual and the expected values, squares it and adds it to the error value for each iteration of the input values. When error equals zero then the formula works. Same goal, different path.

The EvolutionPipeline contains three operators that are executed in the order in which they are given:

GeneticProgrammingExample.java
...
    List<EvolutionaryOperator<Node>> operators = new ArrayList<EvolutionaryOperator<Node>>(3);
    operators.add(new TreeMutation(factory, new Probability(0.4d)));
    operators.add(new TreeCrossover());
    operators.add(new Simplification());
...
    EvolutionEngine<Node> engine
        = new ConcurrentEvolutionEngine<Node>(...
                                        new EvolutionPipeline<Node>(operators),
                                        ...);

When a new population is created the EvolutionaryOperators are called in order:

1. TreeMutation, with a mutation probability of 40%
2. TreeCrossover, which is a single-point crossover
3. Simplification, which asks each Node to simplify itself; for example, if the Node contains 3 + 5 then simplify it to 8, but if the Node contains x + 5 (a variable and a constant), then leave it alone.

All that is left is the TreeFactory. The TreeFactory needs to know 4 things to do its job:

• the parameter count for the nodes that are not constants (for example, Addition gets 2 parameters)
• the maximum depth of any given tree (too shallow doesn’t allow for a rich enough execution tree, too deep might generate a bunch of useless code)
• the probability to use in the creation of functions
• the probability to use in the creation of parameters

The EvolutionEngine will call TreeFactory.generateRandomCandidate(), which will call TreeFactory.makeNode(), to randomly create Nodes of functions, parameters or constants:

TreeFactory.java
  ...
private Node makeNode(Random rng, int maxDepth)
{
  if (functionProbability.nextEvent(rng) && maxDepth > 1)
  {
      // Max depth for sub-trees is one less than max depth for this node.
      int depth = maxDepth - 1;
      switch (rng.nextInt(5))
      {
        case 0: return new Addition(makeNode(rng, depth), makeNode(rng, depth));
        case 1: return new Subtraction(makeNode(rng, depth), makeNode(rng, depth));
        case 2: return new Multiplication(makeNode(rng, depth), makeNode(rng, depth));
        case 3: return new IfThenElse(makeNode(rng, depth), makeNode(rng, depth), makeNode(rng, depth));
        default: return new IsGreater(makeNode(rng, depth), makeNode(rng, depth));
      }
  }
  ...

When the TreeFactory creates a function it is only creating one of five possibilities. Adding additional baseline functions is pretty trivial once you see it presented like this. Daniel Dyer really has done a great job.

The last thing the TreeFactory does is either create a parameter with a parameter count of 1 or 0, or return a constant with a value of 0-10. All too easy.

TreeFactory.java
  ...
  else if (parameterProbability.nextEvent(rng))
  {
    return new Parameter(rng.nextInt(parameterCount));
  }
  else
  {
    return new Constant(rng.nextInt(11));
  }
}

Just for fun I have included an example of the code from two of the Nodes: Addition and IfThenElse.

Addition.java
  ...
  public Addition(Node left, Node right)
  {
      super(left, right, '+');
  }

  ...
  public double evaluate(double[] programParameters)
  {
    return left.evaluate(programParameters) + right.evaluate(programParameters);
  }
  ...

The constructor for Addition takes in two Nodes and a printable version of the operation. There is no check to see if the Nodes can evaluate to something useable by the Addition object; this is part of the evolution process. The trees that don’t work will be disposed of.

The evaluate() method calls evaluate() on the left and right Nodes and adds them together. ‘Nuff said.

The next example is the IfThenElse Node. It contains three nodes: a condition, code to execute if the condition is true, or code to execute if the condition is false.

IfThenElse.java
  ...
  public IfThenElse(Node condition, Node then, Node otherwise)
  {
    this.condition = condition;
    this.then = then;
    this.otherwise = otherwise;
  }
  ...

Again, notice no check on the actual capabilities of each Node.

IfThenElse.java
  ...
  public double evaluate(double[] programParameters)
  {
    return condition.evaluate(programParameters) > 0 // If...
           ? then.evaluate(programParameters)   // Then...
           : otherwise.evaluate(programParameters);  // Else...
  }
  ...

The evaluate() method resolves to the Java ternary operator and returns the result of either the then Node or otherwise Node. Yes, there is more code in the IfThenElse class (about 200 lines including comments), but the concepts are approachable and the code is quite clean/clear.

There. The Watchmaker framework and the Hello World and Simple Math Test examples.

I feel better now.

The Output

...
Generation 28: 493.0
Generation 29: 233.0
Generation 30: 233.0
Generation 31: 45.0
Generation 32: 5.0
Generation 33: 0.0
(((arg0 + 4.0) * arg0) + ((arg1 + -5.0) + (((6.0 + arg1) + 4.0) - arg0)))

The above simplified becomes:

(((arg0 + 4.0) * arg0) + ((arg1 + -5.0) + (((6.0 + arg1) + 4.0) - arg0)))
arg0^2 + 4*arg0 + arg1 - 5 + 6 + arg1 + 4 - arg0
arg0^2 + 3*arg0 + 2*arg1 + 5

If we make arg0 –> x and arg1 –> y then the above becomes x^2 + 3*x + 2*y + 5 which matches Toby Segaran’s formula. Go team!

And finally, in my never ending attempt to compare apples-to-apples, and failing miserably I might add, I present the same problem run by each of the three frameworks:

JGAP: 25 generations @ 1000 individuals/generation;
ECJ: 7 generations @ 1024 individuals/generation;
Watchmaker: 33 generations @ 1000 individuals/generation;

ECJ wins again.

The Bad

I was kinda disappointed when I realized that GP was not supported out of the box; the example above was an easy way to discover how to implement GP in Watchmaker, but it felt strange that such a good framework would leave it out. However, Watchmaker is at version 0.6.2 so I have high hopes for the future. Keep going!

The Good

Watchmaker is so easy to use! It uses all kinds of great design ideas, naming conventions, examples, etc. C’mon! You’re using generics! You rock!

The Code

Download the Watchmaker framework and go to town.