Solving Problems using Genetic Programming with JGAP

Identifying Candidate Problems

Genetic Programming has been applied to a wide variety of problems. In particular, Koza [TBD reference] has demonstrated that many problems can be reformulated so that they share a similar software architecture and so that they can be solved with Genetic Programming techniques. This architecture consists of presenting the genetic programming component with a suite of inputs, running the inputs through a series of genetically generated programs, and then measuring the success of each program against the expected answer for the corresponding input. The process is repeated again and again until the success measure meets the exit criteria you’ve provided.

The first challenge is identifying an interesting problem and determining that the selected problem has a reasonable chance for success. The key characteristic about finding a genetic programming solution to a problem is that you are trading computer processing effort against human development effort. There are problems that can be developed with traditional programming that can be also solved with genetic programming. However, you may find in some cases that the effort to create the genetic programming software architecture above is equal to or greater than the effort to create the solution with traditional programming.

However, you might receive by creating a genetic solution to a previously solved problem or a simple problem. I definitely learned about using JGAP by trying to solve a simple problem and to repeat a research result. This tutorial will start by identifying how to use JGAP to find programs using a previously solved genetic problem.

Problem Statement

For this tutorial, we’ll repeat the solution that Koza found in his paper, “Evolution of Emergent Cooperative Behavior using Genetic Programming”. This paper can be found at [TBD]. We’ll first solve this problem by carefully repeating the elements that Koza used in the JGAP system. This means that we’ll program Java classes that emulate the Lisp functions that Koza used in his paper. The intent of starting with this approach is that we can learn how to use JGAP with a problem that has a known solution. Once we’ve learned lessons about using JGAP by repeating this solution, then we can proceed to solving the problem with a more modern approach. At the current time, I’ve only implemented the lisp-like solution and it conversion of this solution to a more modern approach may be a exercise for the reader.

Painted Desert Ant Problem

The problem consists of 10 ants in a 10x10 toroidal grid with 10 black sand grains, 10 gray sand grains, and 10 striped sand grains. The goal is to find a single program that when run on each ant, moves the grains of sands into the first three columns.

Starting map

Final Map with Sand aligned into columns

Selecting the Function Set

For a problem with an unknown solution, we need to identify a set of functions that are sufficient to solve the problem. For our problem, we are using the function set identified by Koza.

Terminals = {X, Y, Carrying, SandColor, GO_N, GO_E, GO_S, GO_W, MoveRandom, Pickup}

Functions = {IfLessThanOrEqual, IfLessThanZero, IfDrop}

For the first solution, we’ll be mimicking the Lisp programming language by having each function return an integer value according to the rules in the paper.

Creating the Domain classes

I chose to implement the business logic in two classes. The AntMap contains the knowledge of the locations and the set of ants. It is responsible for loading the problem from a file location that contains the sand and ant locations. It is also responsible for presenting the current state of the map on System.out. The ant class is responsible for any ant specific behavior. The approach of using the domain classes allowed unit testing the behavior outside of the JGAP framework and subsequently creating JGAP based unit tests to compare against the domain behavior.

The domain classes can easily be modified to a more modern approach by changing the return values from int’s to void’s. These procedures can then be mapped to appropriate genetic classes.

Creating the Function Set

Now that we know the functions that we want to try for our program, we need to convert the functions into appropriate JGAP compatible classes. For each terminal and each function listed above there is a corresponding Java class. You can browse the classes in the paintedDesert package. For this tutorial, we’ll focus on the key concepts to integrate with the JGAP framework.

Key JGAP concepts

Class constructor – Each function class needs a constructor that extends from CommandGene. Just like the JGAP anttrail example, we’ve created an AntCommand class to provide the common behavior related to retrieving the AntMap. Somewhere in the construction of the object, the instance must identify the number of arguments and the return type. The number of arguments is the second argument in the CommandGene constructor and passed in as the a_arity of the argument. The third argument in the constructor is the return type. You should use the CommandGene static definitions of types; BooleanClass, IntegerClass, LongClass, FloatClass, and VoidClass. I must admit that I don’t currently understand how the last two arguments work: final int a_subReturnType, final int[] a_childSubTypes.

Function Operations

The return type is used to determine which operation to call on the function class. A function class may support more than one return type. As mentioned above, the return type is identified in the constructor. The available functions are execute_boolean, execute_int, execute_long, execute_float, execute_double, execute_void and execute_object. For our Lisp-like sample solution, only execute_int is used.

Arguments

The allowable set of argument types are defined in the operation getChildType(IGPProgram a_ind, int a_chromNum). The a_chrom_Num is the key argument. It identifies the 0-based index of the arguments. If you want to support combinations of argument types, then you’ll need to return the appropriate types. For example, if the first argument is a VoidClass and the second argument needs to be an IntegerClass, you would want a method like:

if(a_chromNum == 0){

return CommandGene.VoidClass;

}else if(a_chromNum == 1){

Return CommandGene.IntegerClass;

}

String Representations for the Function Class

There are two mechanisms where the system creates a string representation of the class. The first is the getName() function that returns the name of the function. This version is utilized in the various Exceptions thrown by the CommandGene class.

The second mechanism provides feedback on the genetically derived function. The IGPProgram instance function of toStringNorm(int a_startNode) is used to return a string representing the program the JGAP system has created. It hierarchically calls the toString() operation to return the program representation.

Putting it all Together

We’ve analyzed our problem and created our functions that are hopefully sufficient to solve the problem, now we need to add the logic that I called the “Process Control” in the first diagram.

We’ll extend from the GPProblem class to create our PaintedDesertProblem class. One of the key methods is the GPGenotype create() method. I must admit that I don’t fully understand the various options for controlling the learning process. I’d like to identify the items that I’d like to learn more about. What is the advantage of the array of CommandGene array in the nodeSets variable help us? I only had a one dimensional array.

Running our Test

The next step is to create a batch command or other mechanism to invoke the PaintedDesertProblem’s main subprogram. However, if your experience is like mine, then the program runs and it doesn’t solve the problem as you had hoped.

Creating Unit Tests

Like all programming exercises, it’s important to create unit tests. You’re hoping to find the reason why JGAP didn’t solve the problem as you expected. You could have made a mistake in the sufficiency test. Can the available functions be combined to solve the problem? Is your fitness function returning the proper results? What actually is happening in that magic JGAP black box? Is JGAP putting the program together in a way that you expected? Did you find a bug in JGAP?

Or you could have made a traditionally programming mistake? In the Painted Desert problem, the domain object approach allows for traditional junit testing on the Ant and AntMap classes. Certainly, I had my mistakes in the domain classes. The advantage of the existing solution approach is that in addition to the unit tests, I could write a program that demonstrated that the solution works.

I’d like to add a note about the kinds of mistakes you can make. I’ve identified that mistakes were made in the domain classes. I put together some elemental unit test examples to work through the issues. Certainly, the unit test coverage is not complete, but it provides an idea that may help you with your challenge. You might notice that one test case, OneElementGenElementsTest, compares the result of the hand coded solution against a solution using the JGAP function classes. One other confession to note, as simple as this problem is, I made a key mistake in programming the IfDrop class. It did not drop the sand. Therefore, the genetic program could never solve the problem. It was a simple oversight that cost too many hours of frustration and exploration, but helped me understand more about JGAP.

Writing Unit Tests in JGAP

JGAP is a Java program just like your traditional programming approaches. It is possible to create a unit test using the function classes that we created.

public void testGO_W()

throws Exception {

GPProgram prog = new GPProgram(m_gpconf, 3);

m_antMap.resetMap();

prog.setApplicationData(m_antMap);

ProgramChromosome pc1 = new ProgramChromosome(m_gpconf, 50, prog);

pc1.getFunctions()[0] = new GO_W(m_gpconf);

pc1.redepth();

prog.setChromosome(0, pc1);

Object[] noargs = new Object[0];

int answer = prog.execute_int(0, noargs);

assertEquals(1, m_antMap.getAnt().getXpos());

assertEquals(1, m_antMap.getAnt().getYpos());

answer = prog.execute_int(0, noargs);

assertEquals(0, m_antMap.getAnt().getXpos());

assertEquals(1, m_antMap.getAnt().getYpos());

answer = prog.execute_int(0, noargs);

assertEquals(2, m_antMap.getAnt().getXpos());

assertEquals(1, m_antMap.getAnt().getYpos());

}

The second argument in new GPProgram(m_gpconf, 3) identifies the number of programs that you are going to add to the GPProgram instance. One trick is that you must run the redepth() subprogram before you add the program to the GPProgram instance using setChromosome(…).

Another minor trick is how you handle nesting subfunctions with arguments. The testSolution subprogram of the OneAntGenElementsTest class is an example of how nesting works.

// IFLTE (GO-W) (IF-DROP COLOR (IFLTE (GO-W) X (GO-S) (PICK-UP))) (IFLTE X

// COLOR COLOR (PICK-UP)) (GO-S)

ProgramChromosome pc1 = new ProgramChromosome(m_gpconf, 50, prog);

pc1.getFunctions()[0] = new IfLessThanOrEqual(m_gpconf, CommandGene.IntegerClass);

pc1.getFunctions()[1] = new GO_W(m_gpconf);

pc1.getFunctions()[2] = new IfDrop(m_gpconf, CommandGene.IntegerClass);

pc1.getFunctions()[3] = new SandColor(m_gpconf);

pc1.getFunctions()[4] = new IfLessThanOrEqual(m_gpconf, CommandGene.IntegerClass);

pc1.getFunctions()[5] = new GO_W(m_gpconf);

pc1.getFunctions()[6] = new X(m_gpconf);

pc1.getFunctions()[7] = new GO_S(m_gpconf);

pc1.getFunctions()[8] = new Pickup(m_gpconf, "First Pickup");

pc1.getFunctions()[9] = new IfLessThanOrEqual(m_gpconf, CommandGene.IntegerClass);

pc1.getFunctions()[10] = new X(m_gpconf);

pc1.getFunctions()[11] = new SandColor(m_gpconf);

pc1.getFunctions()[12] = new SandColor(m_gpconf);

pc1.getFunctions()[13] = new Pickup(m_gpconf, "Second Pickup");

pc1.getFunctions()[14] = new GO_S(m_gpconf);

pc1.redepth();

prog.setChromosome(0, pc1);

If the function class requires one or more arguments, then the classes are added in the following array elements and are used by the nested function class before continuing to add arguments to the parent function class.

Summary

Genetic programming with JGAP can work if you’ve set your problem up correctly. Debugging a program that the system automatically created offers a significant challenge. To combat the delegation of control to JGAP, consider writing unit tests that check your domain logic and seriously consider checking your genetic functions with JGAP unit tests.