Representation

Up until this point, we have been talking a lot about individuals, but not really discussing what these individuals are made of. We know that GP aims to evolve computer programs, but what kind of computer programs? Does GP evolve Java programs like the ones you and I might write, or something entirely different. This is the representation problem.

The computer programs GP evolves are programs written in some functional programming language. If you are new to computer science, you probably don't have any experience with functional programming languages. Imperative programming languages, the ones most of us are more familiar with like Java and C have some computer state with variables and values and the various commands alter the computer's state. In functional programs, the idea is to take some input and simply return a value without dealing with computer state. You can think of functional programming more like mathematical expressions than instructions for somebody to follow.

There are many functional programming languages, including LISP and OCaml. In Koza's 1992 Book, he used the LISP programming language to evolve his computer programs.

Another option is to represent the individuals using objects of whatever programming language you are using to code the GP system. This is the way our Darwin GP Environment handles representation, but it is currently being written to optionally evolve OCaml programs.

Regardless of whether you choose to represent individuals in some functional programming language or with objects in memory, GP evolves individuals that can be represented as a tree structure. It is more functionally useful to consider them in this way when thinking about GP. Tree structures are a basic data structure common throughout computer science. Let us discuss some features of tree structures, and then we will look at an easy example.

  • Trees are made of several nodes.
  • All nodes (except the first, or root node) have one parent and any number of children.
  • In GP, the number of children a node has is called its arity.
  • In GP, nodes with one or more children are called functions and nodes with no children are called terminals.
  • Tree structures are traversed recursively.

Let us consider an easy example. We will consider the mathematical expression 3 + 2 * x. We know from middle school mathematics, that if we had a value for x, to figure out the value of this expression, we would first multiply 2 by x and then add 3. The picture on the right shows the tree reprentation of this function.

In this tree, we have two functions, the plus and times operators. Both of these have arity 2, so they take two arguments. There are three terminals, 3, 2, and x. They simply return values that can be processed. The root node is the plus operator, since it has no parent node. Every node on the tree returns a value if we provide it with a value of x. For instance, the following code might be found in the definition of the x node:

public double getValue(double xValue) {
        return xValue;
}

...or for the plus node:

public double getValue(double xValue) {
        return childNode[0].getValue(xValue) 
             + childNode[1].getValue(xValue);
}

So by now, you are beginning to see how trees are processed recursively. If we wanted to evaluate this function for, let's say x = 5, we might be able to make a call to rootNode.getValue(5). Here's how it would be processed:

  1. We make the call to rootNode.getValue(5).
  2. rootNode is a plus node, so it first needs to find the value of its first child node, so it calls childNode[0].getValue(5).
  3. childNode[0] is a constant, so it simply returns the value 3.
  4. rootNode then needs to find the value of its second child node, so it calls childNode[1].getValue(5).
  5. childNode[1] is a times node, so it has to evaluate both of its child nodes.
  6. The values returned by its child nodes are 2, since its first child is a constant and then 5, since its second child node returns the value of xValue.
  7. childNode[1] then multiplies 2 and 5, returning 10.
  8. rootNode then adds 3 and 10 to return 13.
  9. The result of 13 is returned!

This may seem like a lot of work just to evaluate a simple mathematical expression, but computers are quite good at this and can computer millions of values with extremely large expression trees very quickly. These tree structures are what Darwin actually works with. Whenever work is done in GP, the set of functions and terminals are described to provide an idea of what kinds of programs can be evolved. Let us look at these for our three simple problems.

Symbolic Regression

We have already begun looking at the individuals for the symbolic regression problem. Symbolic regression attempts to evolve mathematical functions of x, just like the one we discussed above. The set of functions is as follows:

  • Addition: Arity-2. Returns the value of the first child node plus the value of the second.
  • Subtraction: Arity-2. Returns the value of the first child node minus the value of the second.
  • Multiplication: Arity-2. Returns the value of the first child node times the value of the second.
  • Division: Arity-2. In order to avoid division by zero issues, if the second child node returns 0, division simply returns 0. Otherwise, it returns the value of the first child node plus the value of the second.

The four functions are all pretty straightforward. There is however, one intersting thing to consider. The division operator can potentially throw and exception if we attempt to divide by zero. Unless we specifically set up some kind of error handling, this can cripple a GP run, and since GP's trees are inherently random, these kinds of exceptions can become quite commonplace. For this reason, whenever we find an exception might be thrown, we need to figure out a way to handle this, without crippling an otherwise good individual. In the case of division, we create the protected division operator which will never have to deal with a division by zero exception.

The set of terminals is as follows:

  • Constant: Returns the value of the constant, given at instantiation.
  • Variable: Returns the value of x.

Fairly straightforward. The variable node simply returns whatever value of x is passed into it. The constant node is a little more complicated. Constants in GP usually operate as ephemeral random constants. When we first generate the tree and create the node, we assign the constant some random value within a range, for instance 3 or -2. The constant then keeps this value for its entire life. Almost every time constants are used in GP, they behave this way.

Cart Centering

For the cart centering problem, we are looking for the individuals to return one of two possible choices, accelerate forward or backwards. However, it would be particularly useful to mathematically manipulate numerical values. The solution to this problem in more complicated GP systems would be to enforce a strong system of node types, but that is beyond the scope of this guide. Another, easier solution is to use a concept called wrapping.

The way this works is all nodes in the cart centering tree will return numerical values. In the end, when we get the value of the root node, if it is greater than 0, we call it forward acceleration, otherwise reverse acceleration.

Our function set is as follows:

  • Addition: Arity-2. Same as for symbolic regression problem.
  • Subtraction: Arity-2. Same as for symbolic regression problem.
  • Multiplication: Arity-2. Same as for symbolic regression problem.
  • Division: Arity-2. Same as for symbolic regression problem.
  • Absolute Value: Arity-1. Returns the absolute value of its child node.
  • Greater Than: Arity-2. Returns 1 if the value returned by the first child node is greater than the value returned by the second child node, -1 otherwise.

...and the terminals:

  • Constant: Same as for symbolic regression problem.
  • Velocity: Returns the value of the cart's velocity.
  • Position: Returns the value of the cart's position.

Santa Fe Ant Trail

For the other two problems, we were concerned with the return value of a function given some current state. Sometimes, we are more interested in the side effects the tree produces. The artificial ant problem is one of these cases. For the artificial ant problem, some of our nodes will make the ant perform an action. Let us first examine the nodes; we will consider how artificial ant individuals are processed afterwards.

The set of functions for this problem is:

  • If Food Ahead: Arity-2. If there is food directly in front of the ant, the first child is evaluated, otherwise the second child is processed.
  • Progn-2: Arity-2. The first child is evaluated and then the second child is evaluated, in that order.
  • Progn-3: Arity-3. The three child nodes are evaluated in order.

The functions essentially define how the tree is traversed, and the terminals define how the ant behaves:

  • Move: Move the ant one space forward.
  • Turn Left: Rotate the ant 90 degrees left.
  • Turn Right: Rotate the ant 90 degrees right.

The way these individuals are processed is slightly more difficult to understand than the first two problems, but it is fairly intuitive. We begin by processing the root node and according to the conditional branches, we traverse the tree. Whenever we happen upon a terminal, an action is taken and the time increases by one step. As the tree continues to be processed, we may have a new value for whether or not food is ahead. At some point, we reach the end of the processable tree, and the process begins again at the root node. Let's consider a simple example.

For our example, let us consider the following two images:

The image on the left is our example tree structure; the image on the right is our small test-grid. The ant is initially placed in square A-1 facing right, and the green circles are the food. Let us examine how this tree would be processed and how the ant would behave:

1. We begin with the root node, which asks is there food ahead? The answer is yes, so we evaluate the first child.

2. The node tells the ant to move forward, so it moves to square A-2 and eats the food there.

3. Because there is nowhere else to go in the tree, we begin back at the root node.

4. There is food ahead, so again, we move forward to square A-3 and eat the food there. Back to the root node.

5. Now we ask, is there food ahead? The answer is no, so we evaluate instead the second child node.

6. The second child node is a Progn-2 node, so that means we first evaluate whatever its first child is.

7. That node is the turn right terminal, so the ant rotates right; now it is facing downwards.

8. The next step is to evaluate the second child of Progn-2, which asks if there is food ahead.

9. The answer is yes, so the ant moves forward, eats the last piece of food, and we return to the root.

10. Can you figure out what happens next? (Answer at the bottom of this page)

So now you have a better understanding of how individuals are represented in basic GP systems. More complicated systems have advanced type-structures and incorporate various elements of modular programming, but most basic problems can be solved with tree structures like the ones described here.

The nodes we define for a given problem are the building blocks GP will use to evolve a solution to the problem, the first input to a Genetic Programming system. The second input, as you may recall from the What Is Genetic Programming? section, is the fitness metric. Let us move on to Fitness.

The answer is the ant keeps spinning in a circle!