At the forefront of Artificial Intelligence

Home » Articles » Genetic Algorithms » Genetic Programming

An Introduction to Genetic Programming

By Zach Garner

For this essay, I will assume you have a basic understanding of Genetic Algorithms.

Introduction

The goals of Genetic Programming (GP) are to use the concepts of genetics and Darwinian natural selection to generate and evolve entire computer programs. GP largely resembles GA in terms of its basic algorithm. The notions of mutation, reproduction (crossover) and fitness are essentially the same, with GP requiring a bit of special care when using those operations. While Genetic Algorithms (GA) is concerned with modifying fixed-length strings, usually associated with parameters to a function, Genetic Programming is concerned with actually creating and manipulating the (non-fixed length) structure of the program (or function). As a result, GP is a much more complex and difficult topic.

Parse Trees

One of the main requirements that must be met when generating possible programs is that they must be valid in their syntax. With some languages like C++, it is almost impossible to do in its native form. As a result, the program must first be turned into a more elegant representations. Parse trees are simple, homogenous representations of programs. In the process of compiling a high level program (like one written in C/C++), your code is turned into a parse tree for ease of manipulation by the computer. As a result of that elegance, parse trees are GP's native tongue allowing genetic operators can be applied easily and coherently. Another benefit is that all Lisp programs (the primary language in which GP is done, though it is in no way limited to a certain language) can be easily written as a parse tree, and vice versa. Lets say you want to evaluate a simple expression such as x + 3. In terms of a parse tree, that would be written as:

     +
    / \
   x   3

A more complex expression such as (x * y + (56 + 3)) - (3 / (dist x y)) would be written as:

          -
        /   \
      +       /
    /  \     / \
   *    +    3  dist
  / \  / \       /\
 x  y 56  3     x  y

Now is that when viewing the expression as a tree, we only have to worry about one thing when it comes to syntax: Whether or not something is a leaf node. (ok, ok, so its not THAT simple, but bare with me.) Every function that requires a parameter (such as addition, multiplication or finding the distance between points) will be the head of a subtree. Every leaf node will be a variable, a constant or a functions without parameters. The leaf nodes do not depend on anything else for their value and are referred to as terminals. We now have a consistent and simple way of expressing a program. As mentioned above, Lisp programs are basically parse trees. The first example, x + 3 would be written in Lisp's prefix notation as (+ x 3). The second example would be written as (- (+ (* x y) (+ 56 3)) (/ 3 (dist x y))). As can be seen, subtrees and Lisp's nested lists can be interchanged fairly easily, especially with a little practice.

Additional Requirements

Before we move on, there are two necessary properties that must be addressed for everything to play well with each other. First, we must have closure. Closure requires that any function that takes a value will be able to handle any value that it can be given. If we limit ourselves to the standard arithmetic functions: {+, -, *, /} and the values: {0, 1, 2} as terminals, we do not have closure. It is possible that (/ 2 0) (remember that this is the same as (2 / 0) in infix notation) may come up and will abort the program with a divide-by-zero error. Closure can be forced in most situations by redefining the function to fail gracefully. As an example, a divide function could be written to return the number 0 when divide-by-zero is received. Or if you have a unary function that needs to take two options, you could simple ignore the second. That is an adequate, but not elegant, solution to the problematic exceptions.

The second property that we need to check for is that the combination of functions and terminals that we are using is sufficient to solving the problem. If we are limiting ourselves to the functions: {+, -} and any integer {1, 2, 3, 4,...}, it will be impossible to find a function that implements log(x). At best, an approximation of log(x) can be obtained. And now, we can move on.

The Algorithm

If you read the introduction to GA essay here on Generation 5, you would have seen an outline of a general algorithm for GA:

1. Create a Random Initial State
2. Evaluate Fitness
3. Crossover (sexual recombination)
4. Mutate
5. Repeat until successful.

I'm going to use an example of using GP to find an implementation of XOR with only AND, OR, and NOT. The following is the truth table for those logical operators:

A	B	A and B	A or B	not A	not B	A xor B
True	True	True	True	False	False	False
True	False	False	True	False	True	True
False	True	False	True	True	False	True
False	False	False	False	True	True	False

XOR, as can be seen, is identical to the regular OR, except when both A and B are true XOR returns false. The three logical operators {AND, OR, NOT} and the terminals {A, B, True, False} are sufficient to derive XOR, for reasons beyond the scope of this essay. Furthermore, as long as A and B are limited to being either True or False, we have closure as well.

Step 1: Initialize Population. There are two primary methods for selecting the initial population. In order to stop the initial trees from expanding infinitely, we need to set a maximum Depth of the trees. For simplicity, I'm going to limit the depth to one level of subtrees, but this should vary depending on the application. In the "Full" method, complete (i.e. Full) Trees are formed by randomly selecting functions to fill up the tree. So, pseudo-randomly, we choose AND as the parent. Then as the left node, OR. AND again as the right node. Now that we have reached the right depth, we need to fill in the leaves with terminals. The diagrams below show the progression.

   AND        AND              AND
  /   \      /   \            /   \
            OR   AND        OR    AND
           /  \  / \       / \    / \
                       False  B  A   B

In the other method, Functions and Terminals are selected at the same time. The possibility that a terminal may show up before the maximum depth has reached makes for trees of different shapes. First the operator AND is selected as the parent. Then the terminal B is selected for the left node, then OR for the right node. Finally, terminals fill up the remaining slots since the maximum is reached:

   AND        AND             AND
  /   \      /   \           /   \
            B    OR         B    OR
                 / \             / \
                                A   B

Step 2: Calculate Fitness. Evaluating the fitness of a program is going to require translating how well a program performs into a numerical value. Usually, this requires running the program a number of different times with different parameters, evaluating the output each time. For our example, we need to check the return value for four cases as can be seen by the truth table above. For more complicated programs, more tests will have to be made. There are a number of ways to represent fitness. The most common representation is just to take the difference between what the value should be and what the value is. In this way, the lower the fitness value the lower the error. Zero becomes the best fitness. For the XOR example, let's simply return a 1 for if one of the tests returns the wrong answer, and a 0 for a correct answer. Then sum up the four tests for the fitness.

So, lets see how fit the AND function is in respect to the correct implementation of XOR. As can be seen from the truth table, every pair of inputs of A and B for AND differs from XOR except for when both A and B are false. So AND has a fitness value of 3.

Step 3: Crossover. Crossover is simple for parse trees. Any subtree or terminal may be switched with any other subtree or terminal. As an example, lets take the two programs from above:

           AND               AND  
          /   \             /    \
         B    OR           OR     AND
              / \         / \     / \
             A   B     False  B  A   B

In an actual program, you would recurse through the two trees until two nodes are selected at random, and these would be switched. For example, switch the left nodes of the two programs:

           AND               AND 
          /   \             /   \
         OR    OR          B    AND
        / \    / \              / \
     False B  A   B            A   B

Step 4: Mutation. Mutation is as simple as Crossover. Any function symbol can be replaced by any other function symbol and any terminal can be replaced by any other terminal. Or any subtree or terminal can be replaced with an entirely new subtree generated the same way the initial population was generated.

           AND 			              AND		              AND	
          /   \			             /   \			     /   \
         B    OR 	---- Mutate --->    A    OR    ---- Mutate --->    AND   OR
              / \ 			         / \			  /  \   / \
             A   B   			        A   B			 B    B A   B

Problems

Consider the number of possible functions, operators, variables, numerical constants and conditionals that go into you're average program. Now consider the number of permutations of those functions and variables. The search space is vast. Also think about how long it takes to run a program of moderate complexity. Now multiply that by 500 members per population and multiply that by 50 or so generations and multiply that by a dozen or so tests to determine fitness. The numbers can get obscenely large. That is why most GPs are limited in the available operators and terminals they can use. Its also why John R. Koza, the person accredited with the discovery of Genetic Programming, has a 1,000 node Pentium II computer cluster and a 70 node Alpha cluster. Genetic Programming requires a lot of computer work, even when a good set of operations, terminals and controlling algorithm are chosen.

Last Words

Hopefully, someone reading this found it usefull. I meant to have a working copy of a GP to implement XOR, but it currently just isn't happy. Hopefully, I'll have coerced it into working within a few days. Any comments, questions, flames, threats, etc can be mailed to zach@neurosoft.org.
^Z

Submitted: 01/06/2000

Article Toolbar

BibTeX entry