Paul Grobstein, Bryn Mawr College Department of Biology
Clare Congdon, Bryn Mawr College Computer Science Program

Lab 9: Genetic Programming

Genetic Algorithms were originally used primarily as "function optimizers", used to evolve the optimal parameter settings for a particular function. The approach has been extended in a variety of ways, to allow more complex behaviors to evolve.

One of the interesting extensions is called Genetic Programming, in which the "individuals" in the evolving population are computer programs. The fitness of these programs is determined by how well they solve the problem at hand, and the reproduction operators involve swapping parts of two parent programs.

In this lab, we will explore the evolution of three different functions:

1. A function to calculate an exclusive-or function
   

   The function has two inputs and produces one output; the output should be "on" if exactly one of the two inputs is on, and "off" if both inputs are off or if both inputs are on.

2. A function to calculate a simple version of a lateral inhibition edge-detector
   

   This can be viewed as a "souped up" version of the exclusive-or: the function has four inputs and produces one output; the output is "on" if and only if there is an edge in the middle, which is to say that either the first two inputs are on and the last two are off, or the first two are off and the last two are on. In all other situations, the output should be "off".

3. A function to calculate a more sophisticated lateral inhibition edge-detector
   

   The function has four inputs and produces one output; the output is "off" when there is not an obvious edge, where to produce an "edge" there must be at least two consecutive inputs that have the same value, neighbored by one of the opposite value.

   More simply, the function is "off" if the four inputs are the same, or if they are strictly alternating (on/off/on/off or off/on/off/on).

You are provided with three Lisp programs to evolve the three different tasks. For each task, you can easily change the "primitives" -- the basic functions that can be used to evolve programs out of. The initial set includes and, or, not, and if. (See the web page on Lisp basics for explanations of these functions.) You should experiment with altering the set of primitives to see how this affects the functions that evolve. (And remember that events are determined randomly in several places, so if you run exactly the same problem with the same primitives multiple times, you'll may well get a different answer.)

As with previous labs, you should note in your journals what you've tried, what you've discovered, and how this challenged your intuitions.

One caveat: Running Lisp puts a big drain on computer memory. The implications of this are first, that some of these functions may take a while to evolve, even if you do only 100 generations, and second, that if all of you were to try to do your experiments at the same time, mainline would grind to a halt.
Maintained by: