Home > Genetic Programming, Software Development > JGAP: A Second Example and Observations

JGAP: A Second Example and Observations


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.

Advertisements
  1. No comments yet.
  1. August 13, 2009 at 1:47 am

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: