Archive

Archive for August, 2009

ECJ: A First/Simple Tutorial

August 22, 2009 7 comments

(This is going to be another long one.)

When we last left our heroes they were looking into JGAP as a cool framework for the creation of genetic algorithms. One simple example left them warm and fuzzy and the second left them temporarily bewildered. Taking a better look at the Watchmaker Framework helped clear their minds and made them realize that more thought was needed. They stopped, took a deep breath and ordered cappuccinos.

In the course of human events, research is inevitable. In my research I ran across Mehdi Khoury’s tutorial page which included a comparison of different genetic programming packages as of June 2007. The package he rated the highest? A package named ECJ developed at George Mason University’s Evolutionary Computation Laboratory.

In the course of my research in GP frameworks I decided I wanted to give ECJ a try as well. Nothing like a recommendation from a web site I’ve never heard of to influence my decision making capabilities about cool technologies.

I will be reversing the examples as the Hello World example is really about genetic algorithms while the Simple Math Test, taken from Toby Segaran’s Programming Collective Intelligence, is about genetic programming. It just makes sense to do GA before GP.

If you disagree I look forward to reading your blog posting where you do the reverse.

Hello World – A Genetic Algorithm

Input: the alphabet + a comma + an exclamation point + a space
Output: “Hello, world!”

The ECJ Properties File

The use of properties files is a very Java thing. Not to say that other programming languages don’t use something similar, but Java has made their use a virtue. In some cases, properties files are fantastic, while in other cases XML files are better. Folks who prefer verbose descriptions prefer XML and all others prefer the key=value format of properties; which you decide to use should be based on the problem at hand and not a knee-jerk reaction. Good luck figuring out if you’re having a brain-based knee-jerk reaction right now.

For this ECJ example, I rearranged the various properties so that related key/value pairs would be together. I hope this will make the explanation more coherent.

The first thing to bear in mind with ECJ is that you don’t get to write main(). The properties file tells the controller class ec.Evolve what to do and it does it with great verve and joie de vivre. I am sure you could write your own controller class to execute ECJ within your own applications, but that is left as an exercise for the reader.

The properties file is called from the command line like so:

java ec.Evolve -file [properties file]

As long as the ECJ framework is in the classpath (there is no JAR file to speak of, but you can always make your own), your custom classes are in the classpath, and the path to the properties file is accurate you should be good to go. I have run this example from within Eclipse and on the command line (using Kubuntu) and the results are the same.

verbosity    = 0

breedthreads = 1
evalthreads  = 1
seed.0       = 4357

The first batch of properties are global framework configurations:

  • log file level verbosity (0 – output everything, all the way to 5000 – output nothing). More detail here.
  • number of threads used for crossover/breeding
  • number of threads used for population evaluation
  • random number seed
state       = ec.simple.SimpleEvolutionState

pop         = ec.Population
init        = ec.simple.SimpleInitializer
finish      = ec.simple.SimpleFinisher
breed       = ec.simple.SimpleBreeder
eval        = ec.simple.SimpleEvaluator
stat        = ec.simple.SimpleStatistics
exch        = ec.simple.SimpleExchanger

generations          = 100
quit-on-run-complete = true

Next comes a number of existing classes to accomplish basic tasks. I am eternally grateful to them for the amount of work they saved me. The ones deserving of an explanation are:

  • ec.simple.SimpleEvolutionState – a subclass of EvolutionState. It contains the configuration information needed by the framework to get your genes evolving.
  • ec.Population – contains the current collection of Individuals/chromosomes that have been bred and/or evaluated.
  • ec.simple.SimpleBreeder – creates/breeds Individuals. While ECJ can handle multiple sub-populations the SimpleBreeder does not.

The generations and quit-on-run-complete are complementary; continue to evolve until 100 generations are completed or our fitness function has a perfect match.

checkpoint           = false
prefix               = ec
checkpoint-modulo    = 1

stat.file            = $out.stat

breed.elites.0       = 1

Checkpoint file configurations are defined here. The non-obvious ones are:

  • prefix – the prefix used for the checkpoint file (not used in this example, but necessary to run Evolve)
  • checkpoint-modulo – run a checkpoint every generation or after every N generations?
  • stat.file – name of the output file. The $ means write it in the folder where the Java process started. If a relative path is used then use the folder where the process started as the anchor for the relative path.
pop.subpops  = 1
pop.subpop.0 = ec.Subpopulation

pop.subpop.0.size                   = 100
pop.subpop.0.duplicate-retries      = 0
pop.subpop.0.species                = ec.vector.GeneVectorSpecies
pop.subpop.0.species.ind            = ec.vector.GeneVectorIndividual
pop.subpop.0.species.fitness        = ec.simple.SimpleFitness
#
# Hello, world! is 13 characters long
#
pop.subpop.0.species.genome-size    = 13
pop.subpop.0.species.crossover-type = two
pop.subpop.0.species.crossover-prob = 1.0
pop.subpop.0.species.mutation-prob  = 0.05

pop.subpop.0.species.pipe          = ec.vector.breed.VectorMutationPipeline
pop.subpop.0.species.pipe.source.0 = ec.vector.breed.VectorCrossoverPipeline
pop.subpop.0.species.pipe.source.0.source.0 = ec.select.TournamentSelection
pop.subpop.0.species.pipe.source.0.source.1 = ec.select.TournamentSelection

select.tournament.size = 2

The next group defines the configuration of the population:

  • Only one sub-population
  • Use the ec.Subpopulation class as its container
  • Create 100 Individuals
  • Use the GeneVectorSpecies and GeneVectorIndividual as the container for my custom gene
  • Use SimpleFitness to determine who are the current winners. Our custom fitness function will configure this for every individual
  • The genome size matches the length of our string…in this case 13. One character per gene
  • The crossover-type defines one of five possible ways to breed between the selected individuals. Type two means that the genes between two points in the chromosome will be swapped out with each other.
  • The crossover probability and mutation probability defines how often a crossover and mutation will occur: a one means all the time, 0.05 means not so often.
  • The mutation and crossover pipelines contain selection objects that decide who gets to breed and who gets mutated. TounamentSelection selects a number of individuals at random (how many is defined in the property select.tournament.size) and picks a winner based on the individual’s fitness value.
# each of these is really on one line
pop.subpop.0.species.gene
                = hiddenclause.example.ecj.CharVectorGene
pop.subpop.0.species.gene.alphabet
                = abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXY Z,!

eval.problem = hiddenclause.example.ecj.HelloWorld

Finally, I defined my 2 implementation classes (my gene and my fitness function) and their parameters.

There was no gene/individual type I could use so I defined a subclass of VectorGene and called it (wait for it) CharVectorGene. Since that gene is responsible for creating more genes, a Prototype for you Design Patterns geeks, it will also contain the alphabet containing the allowed characters to be used in this example.

HelloWorld is the fitness function that will push the population into evolving into a greeting.

Fitness Function

ECJ has the concept of an Individual where JGAP has a Chromosome and Watchmaker has AbstractCandidateFactorys to create the chromosomes out of any type you want. In the code I do the same check as before: check that the proper character is at the proper location; give it a point for every hit.

        int fitnessValue = 0;

        GeneVectorIndividual charVectorIndividual
                              = (GeneVectorIndividual) individual;
        long length = charVectorIndividual.size();
        for (int i = 0; i < length; i++) {
            CharVectorGene charVectorGene
                      = (CharVectorGene) charVectorIndividual.genome[i];
            char actual = charVectorGene.getAllele();
            if (actual == _expected[i]) {
                fitnessValue += 1;
            }
        }

In ECJ I am responsible for configuring the Fitness object as we get closer to the perfect message so my fitness function is not the ultimate arbiter of a gene’s fitness.

    SimpleFitness fitness = (SimpleFitness) charVectorIndividual.fitness;
    fitness.setFitness(evolutionState, fitnessValue,
                    fitnessValue == charVectorIndividual.genomeLength());

CharVectorGene – A Gene for Chars

This is where the gene is both created and initialized. The setup() method is only called once for the entire run to load up any parameters, in this case the desired alphabet.

    public void setup(final EvolutionState state, final Parameter base) {
        super.setup(state, base);

        Parameter def = defaultBase();

        String alphabetStr = state.parameters.getStringWithDefault(
                     base.push(P_ALPHABET), def.push(P_ALPHABET), "");
        if (alphabetStr.length() == 0)
            state.output.fatal(
                  "CharVectorGene must have a default alphabet", 
                  base.push(P_ALPHABET));

        alphabet = alphabetStr.toCharArray();
    }

Every gene has to have a character. This method randomly assigned a character to itself.

    public void reset(EvolutionState state, int thread) {
        int idx = state.random[thread].nextInt(alphabet.length);
        allele = alphabet[idx];
    }

There are four standard Java methods that turn out to be quite important to ECJ.

    public boolean equals(Object other)
    public int hashCode()
    public Object clone()
    public String toString()

Standard Java rules apply as to how you should implement them. I probably did not do such a good job.

ECJ’s HelloWorld Output

After running HelloWorld I found that the output to stdout doesn’t do anything more than tell you how many generations have passed and that (maybe) a solution was found. For the really interesting output you want to look at the out.stat file (ECJ automatically adds a space between each letter when it collects the stringified version of each gene):

...
Generation: 45
Best Individual:
Evaluated: T
Fitness: 13.0
 H e l l o ,   w o r l d !

Best Individual of Run:
Evaluated: T
Fitness: 13.0
 H e l l o ,   w o r l d !

The most interesting thing about the above is that ECJ came up with the solution in the least number of generations (JGAP: 233, Watchmaker: 125, ECJ: 45). It would appear that ECJ, though it took me longer to figure out, is the best petri dish so far. I am sure there is fine tuning that could be done to make the various toy example behave similarly, but I think I’ll leave that to someone who cares as an exercise for the reader.

Miscellaneous Comments

Okay, maybe I should have titled this section Miscellaneous Complaints.

The above example took me about a week of on-and-off thought. There was no simple way for me to discover what I did not know about ECJ, but it did a great job of highlighting over and over again that I knew nothing. Since there was no existing class to handle strings I had to figure out, sans documentation, what I needed to do. While intellectually interesting, it was quite frustrating. As you might expect there were a lot of dead-ends in my search.

In addition, due to the flexible method of assigning classes to various categories there should be a lot of checks for class types to insure the run doesn’t crash due to a bad case of downcasting. The ECJ examples used them; I removed them from my code.

While I was happy to finally figure out how to make ECJ work I also have to admit I was exhausted by the time that happened. Hunting through the Javadocs and various README files was decidedly unsatisfying.

Without going into a lot of detail, and I won’t, the ECJ framework appears to be quite powerful. While it has self-admitted warts the most interesting design choice I found was the use of properties files to glue everything together. JGAP and Watchmaker don’t use properties files at all though they might; I just didn’t run into them. ECJ’s use of them is very Spring-like only without the XML and the strict usage of interfaces. I am a big fan of the Spring Framework so ECJ gained points on the use of properties as a pseudo-dependency-injection file, but lost points by not using interfaces properly.

My big suggestion to the ECJ team: port ECJ to Spring and use more interfaces in the implementation code (or more accurately, stop downcasting the interfaces if you know that someone could mess with the properties files). Yeah, the use of XML is ugly, but it makes extending ECJ more consistent and should make writing tests for the various framework components easier.

Or not. I know it is going to be a lot of work and who knows how much code you want to maintain backward compatibility with.

On second thought, leave it alone. How about some more documentation?

The Code

helloworld.params

verbosity    = 0

breedthreads = 1
evalthreads  = 1
seed.0       = 4357

state  = ec.simple.SimpleEvolutionState

pop    = ec.Population
init   = ec.simple.SimpleInitializer
finish = ec.simple.SimpleFinisher
breed  = ec.simple.SimpleBreeder
eval   = ec.simple.SimpleEvaluator
stat   = ec.simple.SimpleStatistics
exch   = ec.simple.SimpleExchanger

generations             = 100
quit-on-run-complete    = true
checkpoint              = false
prefix                  = ec
checkpoint-modulo       = 1

stat.file       = $out.stat

pop.subpops     = 1
pop.subpop.0    = ec.Subpopulation

pop.subpop.0.size                  = 100
pop.subpop.0.duplicate-retries     = 0
pop.subpop.0.species               = ec.vector.GeneVectorSpecies
pop.subpop.0.species.ind           = ec.vector.GeneVectorIndividual
pop.subpop.0.species.fitness       = ec.simple.SimpleFitness

# Place on one line
pop.subpop.0.species.gene          
    = hiddenclause.example.ecj.CharVectorGene
# Place on one line
pop.subpop.0.species.gene.alphabet 
    = abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXY Z,!
#
# Hello, world! is 13 characters long
#
pop.subpop.0.species.genome-size    = 13
pop.subpop.0.species.crossover-type = two
pop.subpop.0.species.crossover-prob = 1.0
pop.subpop.0.species.mutation-prob  = 0.05

# Place on one line
pop.subpop.0.species.pipe                   
    = ec.vector.breed.VectorMutationPipeline
# Place on one line
pop.subpop.0.species.pipe.source.0          
    = ec.vector.breed.VectorCrossoverPipeline
pop.subpop.0.species.pipe.source.0.source.0 = ec.select.TournamentSelection
pop.subpop.0.species.pipe.source.0.source.1 = ec.select.TournamentSelection

select.tournament.size = 2

eval.problem = hiddenclause.example.ecj.HelloWorld

breed.elites.0 = 1

HelloWorld.java

/**
 * HelloWorld.java
 *
 * This is an example only! Use it for anything else at your own risk!
 * You have been warned! Coder/user beware!
 */
package hiddenclause.example.ecj;

import ec.EvolutionState;
import ec.Individual;
import ec.Problem;
import ec.simple.SimpleFitness;
import ec.simple.SimpleProblemForm;
import ec.vector.GeneVectorIndividual;

public class HelloWorld extends Problem implements SimpleProblemForm {
    private char[] _expected = "Hello, world!".toCharArray();

    public void evaluate(final EvolutionState evolutionState, 
                                    final Individual individual, 
                                    final int subPopulation, 
                                    final int threadNum) {
        if (individual.evaluated)
            return;

        int fitnessValue = 0;

        GeneVectorIndividual charVectorIndividual = (GeneVectorIndividual) individual;
        long length = charVectorIndividual.size();
        for (int i = 0; i < length; i++) {
            CharVectorGene charVectorGene 
                    = (CharVectorGene) charVectorIndividual.genome[i];
            char actual = charVectorGene.getAllele();
            if (actual == _expected[i]) {
                fitnessValue += 1;
            }
        }

        SimpleFitness fitness 
                         = (SimpleFitness) charVectorIndividual.fitness;
        fitness.setFitness(evolutionState, fitnessValue, 
                fitnessValue == charVectorIndividual.genomeLength());

        charVectorIndividual.evaluated = true;
    }

    public void describe(final Individual individual, 
                         final EvolutionState state, 
                         final int subPopulation, 
                         final int threadNum,
                         final int log, final int verbosity) {
        // Do Nothing
    }
}

CharVectorGene.java

/**
 * CharVectorGene.java
 *
 * This is an example only! Use it for anything else at your own risk!
 * You have been warned! Coder/user beware!
 */
package hiddenclause.example.ecj;

import ec.EvolutionState;
import ec.util.Parameter;
import ec.vector.VectorGene;

/**
 * @author carlos
 */
public class CharVectorGene extends VectorGene {
    public final static String P_ALPHABET = "alphabet";

    private static char[]      alphabet;
    private char               allele;

    @Override
    public void setup(final EvolutionState state, final Parameter base) {
        super.setup(state, base);

        Parameter def = defaultBase();

        String alphabetStr = state.parameters.getStringWithDefault(
                          base.push(P_ALPHABET), def.push(P_ALPHABET), "");
        if (alphabetStr.length() == 0)
            state.output.fatal(
                       "CharVectorGene must have a default alphabet", 
                       base.push(P_ALPHABET));

        alphabet = alphabetStr.toCharArray();
    }

    /*
     * (non-Javadoc)
     * @see ec.vector.VectorGene#reset(ec.EvolutionState, int)
     */
    @Override
    public void reset(EvolutionState state, int thread) {
        int idx = state.random[thread].nextInt(alphabet.length);
        allele = alphabet[idx];
    }

    public char getAllele() {
        return allele;
    }

    /*
     * (non-Javadoc)
     * @see ec.vector.VectorGene#equals(java.lang.Object)
     */
    @Override
    public boolean equals(Object other) {
        if (!this.getClass().isInstance(other)) {
            return false;
        }

        CharVectorGene that = (CharVectorGene) other;

        return allele == that.allele;
    }

    /*
     * @see ec.vector.VectorGene#hashCode()
     */
    @Override
    public int hashCode() {
        int hash = this.getClass().hashCode();

        hash = (hash << 1 | hash >>> 31) ^ allele;

        return hash;
    }

    @Override
    public Object clone() {
        CharVectorGene charVectorGene = (CharVectorGene) (super.clone());

        return charVectorGene;
    }

    @Override
    public String toString() {
        return Character.toString(allele);
    }
}

Next time: the ECJ version of Toby Segaran’s Simple Math Test.

Or maybe I will do that first in Watchmaker.

Advertisements

JGAP: Revisiting the Second Example

August 15, 2009 Leave a comment

Something happened on the way to my next post: I thought I discovered the reason why the Hello World example under JGAP did not work, or at least why it might not have worked (I am not sure if I could characterize it as failing as GP is all about combinations, not directed choice).

There were no mutations in the population! It was kind of like expecting Vanilla ice cream to become French Vanilla without any help. How could I have been so blind?

There was only one problem: I check the source code for the DefaultConfiguration object created by JGAP and it creates a MutationOperator with a default value of 1/12 (or .08). I traced the logic through my HelloWorld object and, lo and behold, the MutationOperator is created and used. The StringGene is told to mutate and it (occasionally) does.

The Watchmaker Framework recommends a mutation value of 0.02-0.05. The JGAP value is higher which means that it should work.

The problem is…it doesn’t. What could be wrong? What appeared to be a straightforward problem has turned into a white sperm whale tasking me.

I wanted to talk about ECJ. Now I have to talk about the Watchmaker Framework and what it does differently than JGAP. I really did not want to do that.I wanted to save it for later.

Now I have to.

The example code found in the Watchmaker Framework (WF) for the Hello World Example is different than the code in the documentation so if you go to the Completing the Jigsaw section the code located there and in the rest of Chapter 2 will not reflect the code in the actual example code shipped with the project. A shame, but nothing we can’t overcome by taking on a sunny disposition and a winning smile.

If you happen to have a favorite between JGAP and WF I apologize. This is liable to get ugly.

Time to compare.

The Fitness Function

The fitness functions are logically the same; check the letters at all positions. The difference: my JGAP fitness value goes up as more letters match; WF’s fitness value goes up as more don’t match. Nothing more to talk about there.

Evolving: Breeding/Crossover and Mutating

In JGAP the evolving population is made up of Chromosomes which are themselves made up of Genes. In the case of the Hello World example I wanted to evolve a string so I created a StringGene and made it part of a Chromosome.

...
    Gene stringGene = new StringGene(conf, MESSAGE.length(),
                                     MESSAGE.length(), "!dehlorw ,");
    IChromosome sampleChromosome = new Chromosome(conf, stringGene, 1);
...

Makes sense. A StringGene is a kind of Gene and a Chromosome is a kind of IChromosome (I know, I know…what the heck is an IChromosome? It is a naming convention that has been in use for many years now and used extensively, but not exclusively, by folks who use Eclipse. For now, let’s just call an IChromosome a Chromosome. Work with me).

In WF the evolving population is whatever type you want it to be. In this case, we want to evolve a String so it becomes the chromosome. No special wrappers here. Nothing wrong with using a StringGene; from an OO perspective it is a perfectly reasonable abstraction. It is just not used in WF. In addition, the population of Strings is created by a factory: the StringFactory which is a type of CandidateFactory. In JGAP I passed a selection of characters into the StringGene constructor, while in WF the selection of characters is passed into the StringFactory constructor (the following is example code shipped with WF).

...
    private static final char[] ALPHABET = new char[27];
    static
    {
        for (char c = 'A'; c <= 'Z'; c++)
        {
            ALPHABET[c - 'A'] = c;
        }
        ALPHABET[26] = ' ';
    }
...
    EvolutionEngine engine = new ConcurrentEvolutionEngine(
                                 new StringFactory(ALPHABET, target.length()),
                                 ...)
...

(Yes, it is different than the WF documentation. I also would not have used a for() to create a static array of 26 letters when actually listing the letters would have worked as well and been more obvious, but that is a different story and it is example code anyway. Jeez, just relax…)

After combing through the JGAP code, and taking a walk with my mom, I realized what was wrong: Watchmaker handles the string as a complete chromosome. I implemented the JGAP code for the string to be one gene!

Of course it didn’t work. The JGAP crossover was doing nothing.

I changed the JGAP example code to:

...
   private static final String ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ ";
...
   Gene stringGene = new StringGene(conf, 1, 1, ALPHABET);
   IChromosome sampleChromosome = new Chromosome(conf, stringGene, MESSAGE.length());
...

The above configures one StringGene to hold one character and create as many StringGene objects in the Chromosome as the length of the MESSAGE. I changed the list of characters to reflect the data used in the WF example.

In addition, I changed the fitness function to check each individual allele against each individual character of the target string:

...
    protected double evaluate(IChromosome aSubject) {
        int fitnessValue = 0;

        int length = aSubject.size();
        for (int i = 0; i < length; i++) {
            String actual = (String) aSubject.getGene(i).getAllele();
            if (actual.toCharArray()[0] == _expected[i]) {
                fitnessValue += 1;
            }
        }

        return fitnessValue;
    }
...

I also changed the loop that evolves the population to continue until a perfect match is found.

Running the code to use the message “HELLO WORLD” and “ABCDEFGHIJKLMNOPQRSTUVWXYZ ” as the alphabet string I got:

Stopped at generation 123
Total evolution time: 0:0
The best solution has a fitness value of 11
Looking for 'HELLO WORLD':
	 'HELLO WORLD'

Much more reasonable than failure after 1 million tries with a population of 800K.

If I change the message to mixed case and a more complete alphabet:

...
    private static final String MESSAGE = "Hello, world!";
    private static final String ALPHABET =
                           "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ ,!";
...
        Gene stringGene = new StringGene(conf, 1, 1, ALPHABET);
...

The results become:

Stopped at generation 233
Total evolution time: 0:0
The best solution has a fitness value of 13
Looking for 'Hello, world!':
	 'Hello, world!'

I slightly modified the WF StringsExample code to accommodate my compulsion desire to avoid using command line args in examples. With an input of “HELLO WORLD” and alphabet of “ABCDEFGHIJKLMNOPQRSTUVWXYZ ” the output was:

...
Generation 46: HELLO WORLD
Evolution result: HELLO WORLD

If I changed the inputs to mixed case:

...
Generation 125: Hello, world!
Evolution result: Hello, world!

WF took fewer generations to find the solution than JGAP. Interesting. Perhaps WF is a better petri dish.

I suspect there is some fine tuning that could be done with JGAP, but works better in this particular WF example.

JGAP is at version 3.4.3. WF is at version 0.6.1. If you would like to see the WF example code please download the package and have a look.

So there you have it.

The reason why it didn’t work with JGAP was operator error.

The cat was dead and I didn’t notice even after opening the box.

I hate when that happens.

The Code

HelloWorld2.java

package hiddenclause.example;

import org.jgap.Chromosome;
import org.jgap.Configuration;
import org.jgap.FitnessFunction;
import org.jgap.Gene;
import org.jgap.Genotype;
import org.jgap.IChromosome;
import org.jgap.InvalidConfigurationException;
import org.jgap.impl.DefaultConfiguration;
import org.jgap.impl.StringGene;

public class HelloWorld2 {

//    private static final String MESSAGE = "HELLO WORLD";
//    private static final String ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ ";

//    private static final String ALPHABET = "dehlorw ,!";
//    private static final String MESSAGE = "hello, world!";

    private static final String MESSAGE = "Hello, world!";
    private static final String ALPHABET =
                                  "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ ,!";

    public static void main(String[] args) throws Exception {
        long startTime = 0;
        long endTime = 0;
        HelloWorld2 hello = new HelloWorld2();

        Genotype population = hello.create(10);

        startTime = System.currentTimeMillis();
        IChromosome solution = null;
        int popIdx = 0;
        do {
            population.evolve();
            popIdx++;
            solution = population.getFittestChromosome();
        } while (solution.getFitnessValue() != MESSAGE.length());
        endTime = System.currentTimeMillis();

        outputSolution(population, startTime, endTime, popIdx);
    }

    private Genotype create(int popSize) throws InvalidConfigurationException {
        Configuration conf = new DefaultConfiguration();
        conf.setPreservFittestIndividual(true);

        FitnessFunction myFunc = new HelloWorldFitnessFunction2(MESSAGE);
        conf.setFitnessFunction(myFunc);

        Gene stringGene = new StringGene(conf, 1, 1, ALPHABET);
        IChromosome sampleChromosome = new Chromosome(conf, stringGene, MESSAGE.length());
        conf.setSampleChromosome(sampleChromosome);
        conf.setPopulationSize(popSize);

        Genotype population;
        population = Genotype.randomInitialGenotype(conf);

        return population;
    }

    private static void outputSolution(Genotype population, long startTime,
            long endTime, int evolutionIdx) {
        System.out.println("Stopped at generation " + evolutionIdx);

        long totalSeconds = (endTime - startTime) / 1000;
        long actualSeconds = totalSeconds % 60;
        long actualMinutes = totalSeconds / 60;
        System.out.println("Total evolution time: " + actualMinutes + ":"
                + actualSeconds);

        IChromosome solution = population.getFittestChromosome();
        int fitnessValue = (int) solution.getFitnessValue();
        System.out.println("The best solution has a fitness value of " + fitnessValue);

        System.out.println("Looking for '" + MESSAGE + "':");
        String message = getMessage(solution);
        System.out.println("\t '" + message + "'");
    }

    private static String getMessage(IChromosome solution) {
        String result = ""; 

        int length = solution.size();
        for (int i = 0; i < length; i++) {
            result += (String) solution.getGene(i).getAllele();
        }

        return result;
    }
}

HelloWorldFitnessFunction2.java

package hiddenclause.example;

import org.jgap.FitnessFunction;
import org.jgap.IChromosome;

public class HelloWorldFitnessFunction2 extends FitnessFunction {

    private char[] _expected;

    public HelloWorldFitnessFunction2(String desiredMessage) {
        _expected = desiredMessage.toCharArray();
    }

    @Override
    protected double evaluate(IChromosome aSubject) {
        int fitnessValue = 0;

        int length = aSubject.size();
        for (int i = 0; i < length; i++) {
            String actual = (String) aSubject.getGene(i).getAllele();
            if (actual.toCharArray()[0] == _expected[i]) {
                fitnessValue += 1;
            }
        }

        return fitnessValue;
    }

}

JGAP: A Second Example and Observations

August 11, 2009 2 comments

In the first chapter of the documentation for the Watchmaker Framework Daniel W. Dyer presents an interesting genetic algorithm example: what if we wanted to evolve the string “HELLO WORLD”?

The fitness function would be straightforward: check every letter of a possible solution and every matching letter at a matching position would raise that chromosome’s fitness value.

I highly recommend you read the chapter referenced above before continuing. It is quite well written and will make the pain I describe below clearer.

My first thought: implementing this in JGAP shouldn’t be that hard.

Implementing it: easy. Getting a good solution: not so much. This is not a problem with JGAP so much as it is a problem with monkeys and Shakespeare. Before I go into that let me present the code.

My target was a little bit more ambitious: instead of hello world in all upper case characters I wanted to evolve the string “hello, world!” all in lower case and containing a space, a comma and an exclamation point.

The fitness function was easy: check every letter and its position and if it matches the target string increment the fitness value by 1. The higher the fitness value the better the match.

Here is my fitness function:

package hiddenclause.example;

import org.jgap.FitnessFunction;
import org.jgap.IChromosome;

public class HelloWorldFitnessFunction extends FitnessFunction {

    private char[] _expected;

    public HelloWorldFitnessFunction(String desiredMessage) {
        _expected = desiredMessage.toCharArray();
    }

    @Override
    protected double evaluate(IChromosome aSubject) {
        int fitnessValue = 0;

        String msg = (String) aSubject.getGene(0).getAllele();
        char [] actual = msg.toCharArray();
        for (int i = 0; i < actual.length; i++) {
            if (actual[i] == _expected[i]) {
                fitnessValue += 1;
            }
        }

        return fitnessValue;
    }

}

Next step: implement the chromosome that will contain the letters that will evolve into the target string.

In order to accomplish the next step I decided to use the JGAP genetic algorithm* class StringGene. I configured it to randomly generate a string of exactly the length desired and use an alphabet of just the letters and punctuation from the target string. Why not add the entire alphabet and punctuation to add to the diversity? Monkeys, remember? More on that later.

The chromosome creation code is:

package hiddenclause.example;

import org.jgap.Chromosome;
import org.jgap.Configuration;
import org.jgap.FitnessFunction;
import org.jgap.Gene;
import org.jgap.Genotype;
import org.jgap.IChromosome;
import org.jgap.InvalidConfigurationException;
import org.jgap.impl.DefaultConfiguration;
import org.jgap.impl.StringGene;

public class HelloWorld {

    private static final String MESSAGE = "hello, world!";
    private static final int MAX_EVOLUTION = 1000000;

    public static void main(String[] args) throws Exception {
        long startTime = 0;
        long endTime = 0;
        HelloWorld hello = new HelloWorld();

        Genotype population = hello.create(1000);

        startTime = System.currentTimeMillis();
        int i = 0;
        for (i = 0; i < MAX_EVOLUTION; i++) {
            population.evolve();
            IChromosome solution = population.getFittestChromosome();
            if (solution.getFitnessValue() == MESSAGE.length()) {
                break;
            }
        }
        endTime = System.currentTimeMillis();

        outputSolution(population, startTime, endTime, i);
    }

    private Genotype create(int popSize) throws InvalidConfigurationException {
        Configuration conf = new DefaultConfiguration();
        conf.setPreservFittestIndividual(true);

        FitnessFunction myFunc = new HelloWorldFitnessFunction(MESSAGE);
        conf.setFitnessFunction(myFunc);

        Gene stringGene = new StringGene(conf, MESSAGE.length(), MESSAGE.length(),
                "!dehlorw ,");
        IChromosome sampleChromosome = new Chromosome(conf, stringGene, 1);
        conf.setSampleChromosome(sampleChromosome);
        conf.setPopulationSize(popSize);

        Genotype population;
        population = Genotype.randomInitialGenotype(conf);

        return population;
    }

    private static void outputSolution(Genotype population, long startTime,
            long endTime, int evolutionIdx) {
        System.out.println("Stopped at generation " + evolutionIdx);

        long totalSeconds = (endTime - startTime) / 1000;
        long actualSeconds = totalSeconds % 60;
        long actualMinutes = totalSeconds / 60;
        System.out.println("Total evolution time: " + actualMinutes + ":"
                + actualSeconds);

        IChromosome solution = population.getFittestChromosome();
        int fitnessValue = (int) solution.getFitnessValue();
        System.out.println("The best solution has a fitness value of " + fitnessValue);

        System.out.println("Looking for '" + MESSAGE + "':");
        String message = (String) solution.getGene(0).getAllele();
        System.out.println("\t '" + message + "'");
    }
}

Notice that the HelloWorld class will handle any kind of incoming string; I just happened to use a hard coded constant. One of its assumptions (euphemism for bug) is that the incoming string and the solution string are the same length. If the two strings are not the same length the loop might try to access part of an array that doesn’t exist and there are very few exceptions that cause as severe a level of mental anguish as the ArrayIndexOutOfBoundsException (however, NullPointerException is right up there).

The above gave the following output after 1 million generations:
Break: Executed evolution 1000000 times.
Total evolution time: 76:45
The best solution has a fitness value of 10
Looking for 'hello, world!':
'!ello,  or!d!'

Not pretty.

What happened?

While the use of crossover should make the evolution progress faster there are certain statistical issues that must be taken into account. For a chromosome to get a high value it has to have 2 things in its favor:

  1. it has to have one or more letters in the new string
  2. the letter(s) have to be in the proper position(s)

This is where the monkeys come in.

The more I thought of it the more I thought about the scenario of an infinite number of monkeys trying to write Shakespeare. To begin their arduous task one or more of the monkeys has to hit the proper first letter. Assuming a keyboard with just the alphabet, and no punctuation, they have a 1 in 52 chance of hitting the right first letter. Shouldn’t be too hard with an infinite number of primates.

The next letter becomes a little harder. Of the subset of monkeys that hit the proper first letter the chances of any of them hitting that second letter has a statistical probability of 1 in 2704. The third: 1 in 140608. The fourth: 1 in 7,311,616. The fifth: 1 in 380,204,032.

And that doesn’t include punctuation and white space.

That mean that if the letter h never makes it to the first character the system will never (never, as in…well, never) evolve the target string. Never. In order to up the statistical odds of my chromosome succeeding I created an alphabet of just the letters that comprise the target string: “!dehlorw ,”.

And yet, with that small set of characters, an ever changing population of 1000 chromosomes at 1 million generations was unable to generate the string. Can it succeed? Of course. The proper population (random generation of strings) in the petri dish that is JGAP would generate the target string. But it is random and random does not mean regular.

So, adding more letters and punctuation adds more noise to the mix and just makes the combinations even worse (though possibly better as more randomly mixed letters could elevate the use of letters from the target string).

When I changed the StringGene’s alphabet to include a few more letters, “!abcdefghlmnorstwxyz ,”, this is what the output was:

Stopped at generation 1000000
Total evolution time: 77:20
The best solution has a fitness value of 7
Looking for 'hello, world!':
'zblxo, ,orrdx'

Defintely not an improvement.

Is there a way of configuring this differently to encourage a solution? Perhaps a better fitness function? Custom gene? Better randomizer? I will gladly take any suggestions and try them out. Maybe.

Exercise for the reader: up the population value to create more opportunities for the desired letters to end up in the desired positions. Bake overnight.

When I increased the population number to 800K and ran it again my Kubuntu box locked up after 2 days because I continued to do things like run Eclipse, read PDFs and back-up my work. I guess 800 trillion iterations of the fitness function was exhausting.

No joy in Mudville.

Update 8/15/09: the problem solved.

* To create a genetic program using JGAP you would create a GPGenotype using a class that inherits from GPProblem and a fitness function that inherits from GPFitnessFunction.

JGAP: A First/Simple Tutorial

August 4, 2009 1 comment

(This is going to be a long one.)

Genetic Programming. The only thing that strikes more fear in my heart is Lisp. Another blogger whose post I can’t find described learning Lisp as being similar to scaling a vertical wall. I have spent quite a bit of time reading about Lisp and sadly have to agree.

However, I have hope. I am reading Peter Norvig’s Paradigms of Artificial Intelligence Programming and while it is endlessly fascinating the Lisp is only marginally more appealing. He does a great job of describing certain Lisp concepts in a way that even I can understand. The chapter on Eliza is one of the best of the book.

Another on the scale of interesting, but daunting, software concepts, is Genetic Programming (GP). After reading the chapter of genetic programming (Evolving Intelligence) in Toby Segaran’s book Programming Collective Intelligence I found my interest rather piqued and started to look deeper and deeper into GP. I follow a lot of topics related to software, but most I only follow enough to know they exist and may or may not be interesting. GP has always been on the interesting side, but with the potential to be quite involved.

After reading the chapter on GP in Programming Collective Intelligence, and forcing a number of my colleagues to read it as well, I came away thinking that perhaps it was time to start delving into it. After all, it looks hard and if it looks hard it must be worth looking trying.

<MyThoughts>

Hmm.

Python. Looks a lot like Lisp.

Uses lambda functions. Looks a lot like Java inner classes without all the syntactic sugar.

Cool. Small functions. Maybe I should learn more Python after all…

Running it from the Python command line interpreter. Interesting. I wonder how hard that would be to do in Eclipse? I have only used Pydev for small Python objects at work.

Hmm. The code creates a number of wrappers to functions.

Primitive tests.

Wouldn’t I have to write a lot of Java to duplicate this? Might be an interesting project, but looks tedious.

</MyThoughts>

Over time I had collected links to various open source projects about GP, but it was not until I read the Segaran chapter that I decided to look at any of them.

I settled on JGAP. Why? Laziness…I mean…less work. That’s it; less work. Also, it is written in Java so I feel comforted.

JGAP purports to do quite a bit of work for the developer, but allows you to extend things if you so choose. There are a number of examples shipped with the framework so how hard can it be?

The example from the GP chapter in Collective Intelligence looks like this: here are a list of inputs and their associated output (Programming Collective Intelligence, page 259):

Input 1 Input 2 Output
26 35 829
8 24 141
20 1 467
33 11 1215
37 16 1517

The point of the exercise is to discover what equation will return the result given the 2 input values. The answer is x^2+2y+3x+5 where x is input 1 and y is input 2 (Programming Collective Intelligence, page 259).

Eventually, the Python code breeds a solution that looks like this (Programming Collective Intelligence, page 267):

(X*(2+X))+X+4+Y+Y+(10>5)

If you simplify the above you get:

2x+x^2+x+4+2y+1

x^2+2x+x+2y+4+1

x^2+3x+2y+5

Which is pretty much what Toby Segaran was looking for. He briefly talks about how inefficient the code out of a genetically created program can be, but it is pretty awesome in any case.

If you want to take a look at the Python code that was used then read the sample chapter on Safari Books Online.

So today’s goal is: duplicate the Python result with JGAP using the least amount of code possible. How to do that?

I am not going to discuss GP in any real depth. I want to get JGAP up and running and see what I can do with a simple example.

The JGAP document lists 4 steps involved in creating a GP using JGAP:

  1. Create a GP Configuration Object
  2. Create an initial Genotype
  3. Evolve the population
  4. Optionally implement custom functions and terminals (a mutable static number)

The JGAP documentation leaves out the use of a fitness function in their GP section, even though you have to use one and they have one implemented. I would list that as the first thing you should do.

In Test-driven Development it would be:

  1. Write a test
  2. Write whatever code it takes to pass the test
  3. Refactor the code so you won’t be embarrassed when your mom sees it
  4. Repeat

If we think of the fitness function as a test program then we can think of GP as a type of programming that can make use of TDD. In fact, the folks at NeoCoreTechs are working on extreme genetic programming (XGP) as a way of growing applications rather than writing them. Sounds like a noble goal, but a hard one. In other words, sounds like it’s worth doing.

Let’s port the example from the Programming Collective Intelligence book to JGAP.

Implement a Fitness Function

The fitness function (unit test for you TDD’ers) needs to score the incoming chromosomes/solutions. The original Python fitness function is:

def scorefunction(tree,s):
  dif=0
  for data in s:
    v=tree.evaluate([data[0],data[1]])
    dif+=abs(v-data[2])
  return dif

As the value returned by the chromosome gets closer to the desired output the result of the subtraction gets closer to 0.

The Java evaluate():double method looks like:

    protected double evaluate(final IGPProgram program) {
        double result = 0.0f;

        long longResult = 0;
        for (int i = 0; i < _input1.length; i++) {
            // Set the input values
            _xVariable.set(_input1[i]);
            _yVariable.set(_input2[i]);
            // Execute the genetically engineered algorithm
            long value = program.execute_int(0, NO_ARGS);

            // The closer longResult gets to 0 the better the algorithm.
            longResult += Math.abs(value - _output[i]);
        }

        result = longResult;

        return result;
    }

(I know: I could have gotten away with just the longResult and let the return do an autoboxing, but I didn’t want to.)

Looks rather similar to the original Python code only with autoboxing. The _xVariable and _yVariable are references to objects under the control of the chromosomes in the population and having them means we can give the chromosomes new values to help them do their job: figuring out what the formula is that will get us the desired output.

Create a GP Configuration Object

I have the SimpleMathTest class initialize itself in its constructor so this is where I create the GPConfiguration object. Values for the maximum initialization depth, population size and maximum crossover depth are arbitrary for now. These are numbers I found used in some of the other JGAP examples and figured they were good enough.

In addition, I assigned the fitness function to GPConfiguration using setFitnessFunction().

    public SimpleMathTest() throws InvalidConfigurationException {
        super(new GPConfiguration());

        GPConfiguration config = getGPConfiguration();

        _xVariable = Variable.create(config, "X", CommandGene.IntegerClass);
        _yVariable = Variable.create(config, "Y", CommandGene.IntegerClass);

        config.setGPFitnessEvaluator(new DeltaGPFitnessEvaluator());
        config.setMaxInitDepth(4);
        config.setPopulationSize(1000);
        config.setMaxCrossoverDepth(8);
        config.setFitnessFunction(new SimpleMathTestFitnessFunction(INPUT_1, INPUT_2, OUTPUT, _xVariable, _yVariable));
        config.setStrictProgramCreation(true);
    }

Create an initial genotype

The genotype represents a configured GP environment. This is where we pass the references to _xVariable and _yVariable used by the fitness function.

    public GPGenotype create() throws InvalidConfigurationException {
        GPConfiguration config = getGPConfiguration();

        // The return type of the GP program.
        Class[] types = { CommandGene.IntegerClass };

        // Arguments of result-producing chromosome: none
        Class[][] argTypes = { {} };

        // Next, we define the set of available GP commands and terminals to
        // use.
        CommandGene[][] nodeSets = {
            {
                _xVariable,
                _yVariable,
                new Add(config, CommandGene.IntegerClass),
                new Multiply(config, CommandGene.IntegerClass),
                new Terminal(config, CommandGene.IntegerClass, 0.0, 10.0, true)
            }
        };

        GPGenotype result = GPGenotype.randomInitialGenotype(config, types, argTypes,
                nodeSets, 20, true);

        return result;
    }

Evolve the population

At this stage all we are doing is creating the population, which calls the fitness function, and checking to see if our test values match.

        GPGenotype gp = problem.create();
        gp.setVerboseOutput(true);
        gp.evolve(30);

        System.out.println("Formula to discover: x^2 + 2y + 3x + 5");
        gp.outputSolution(gp.getAllTimeBest());

The final output from all the above work is (and this may vary based on the created population):

(Y + Y) + ((5 + X) + ((X * X) + (X + X)))

which, when simplified, becomes the desired formula. Not bad for a few hours work. Of course, I did not come up with this in my first pass. I hit a dead end at one point and refactored like mad once I had it working, but the results are impressive given that I worked on it for a short amount of time.

The Actual Pieces

The fitness function in class SimpleMathTestFitnessFunction:

package hiddenclause.example;

import org.jgap.gp.GPFitnessFunction;
import org.jgap.gp.IGPProgram;
import org.jgap.gp.terminal.Variable;

public class SimpleMathTestFitnessFunction extends GPFitnessFunction {

    private Integer[] _input1;
    private Integer[] _input2;
    private int[] _output;
    private Variable _xVariable;
    private Variable _yVariable;

    private static Object[] NO_ARGS = new Object[0];

    public SimpleMathTestFitnessFunction(Integer input1[], Integer input2[],
            int output[], Variable x, Variable y) {
        _input1 = input1;
        _input2 = input2;
        _output = output;
        _xVariable = x;
        _yVariable = y;
    }

    @Override
    protected double evaluate(final IGPProgram program) {
        double result = 0.0f;

        long longResult = 0;
        for (int i = 0; i < _input1.length; i++) {
            // Set the input values
            _xVariable.set(_input1[i]);
            _yVariable.set(_input2[i]);
            // Execute the genetically engineered algorithm
            long value = program.execute_int(0, NO_ARGS);

            // The closer longResult gets to 0 the better the algorithm.
            longResult += Math.abs(value - _output[i]);
        }

        result = longResult;

        return result;
    }

}

The actual GP program to find the secret formula in class SimpleMathTest:

package hiddenclause.example;

import org.jgap.InvalidConfigurationException;
import org.jgap.gp.CommandGene;
import org.jgap.gp.GPProblem;
import org.jgap.gp.function.Add;
import org.jgap.gp.function.Multiply;
import org.jgap.gp.function.Pow;
import org.jgap.gp.impl.DeltaGPFitnessEvaluator;
import org.jgap.gp.impl.GPConfiguration;
import org.jgap.gp.impl.GPGenotype;
import org.jgap.gp.terminal.Terminal;
import org.jgap.gp.terminal.Variable;

/**
 * @author carlos
 *
 */
public class SimpleMathTest extends GPProblem {
    @SuppressWarnings("boxing")
    private static Integer[] INPUT_1 = { 26, 8, 20, 33, 37 };

    @SuppressWarnings("boxing")
    private static Integer[] INPUT_2 = { 35, 24, 1, 11, 16 };

    private static int[] OUTPUT = { 829, 141, 467, 1215, 1517 };

    private Variable _xVariable;
    private Variable _yVariable;

    public SimpleMathTest() throws InvalidConfigurationException {
        super(new GPConfiguration());

        GPConfiguration config = getGPConfiguration();

        _xVariable = Variable.create(config, "X", CommandGene.IntegerClass);
        _yVariable = Variable.create(config, "Y", CommandGene.IntegerClass);

        config.setGPFitnessEvaluator(new DeltaGPFitnessEvaluator());
        config.setMaxInitDepth(4);
        config.setPopulationSize(1000);
        config.setMaxCrossoverDepth(8);
        config.setFitnessFunction(new SimpleMathTestFitnessFunction(INPUT_1, INPUT_2, OUTPUT, _xVariable, _yVariable));
        config.setStrictProgramCreation(true);
    }

    @Override
    public GPGenotype create() throws InvalidConfigurationException {
        GPConfiguration config = getGPConfiguration();

        // The return type of the GP program.
        Class[] types = { CommandGene.IntegerClass };

        // Arguments of result-producing chromosome: none
        Class[][] argTypes = { {} };

        // Next, we define the set of available GP commands and terminals to
        // use.
        CommandGene[][] nodeSets = {
            {
                _xVariable,
                _yVariable,
                new Add(config, CommandGene.IntegerClass),
                new Multiply(config, CommandGene.IntegerClass),
                new Terminal(config, CommandGene.IntegerClass, 0.0, 10.0, true)
            }
        };

        GPGenotype result = GPGenotype.randomInitialGenotype(config, types, argTypes,
                nodeSets, 20, true);

        return result;
    }

    public static void main(String[] args) throws Exception {
        GPProblem problem = new SimpleMathTest();

        GPGenotype gp = problem.create();
        gp.setVerboseOutput(true);
        gp.evolve(30);

        System.out.println("Formula to discover: x^2 + 2y + 3x + 5");
        gp.outputSolution(gp.getAllTimeBest());
    }

}

(And remember: I don’t warrant any of the above code to do anything but crash. Please do not use it for anything at all except as examples of using the JGAP framework. Especially don’t use the above code in nuclear submarines, nuclear power plants or Cylons. Okay, maybe Cylons.)

Yeah, Java is more verbose. We really need to do something about that.

Much thanks to Toby Segaran for his lucid explanation of GP principles and to the JGAP team for what appears to be an awesome framework.