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

Lab 8: Working with Genetic Algorithms

Your work with neural nets has no doubt convinced you that the ability to adapt gives a computer system a great deal of problem-solving potential, allowing relatively simple mechanisms to find solutions to complex problems.

This week, we will look at another form of adaptation, using another approach that is inspired by a biological process. Genetic Algorithms model a solution to a problem as a bit string (a series of 1's and 0's) that exists in a population of other bit-string solutions. The population is then allowed to "evolve": solutions "mate" with other solutions to produce new solutions, and there is a selection pressure (called the fitness function) towards better solutions to the problem. Over a series of "generations", the population contains better and better solutions.

The assignment: Read the Scientific American articles by Holland and Riolo. We will be working with a program called "sa2", written by Riolo as an accompaniment to the article.

Alas, this is not as "user-friendly" software as the tlearn package, so you will have to read the instructions for using sa2, and spend some time familiarizing yourself with how you interact with the software. This is entirely a "command-line" interface, meaning that you have to type (correctly) one of the commands that the software is expecting, or you'll get a "huh?" type response. (We will try to ignore many of the options.)

The sa2 program has been modified for this lab, so that we can try a few different fitness functions without having to recompile the program. (You can switch functions while the program is running; see the instructions.) The four built-in functions are:

• Function 1: the function described in the Scientific American article (x + |sin(32x)| )

• Function 2: favors strings that have more 1's in them
  More specifically, the fitness of the strings is a count of the number of 1's in the string.

• Function 3: favors strings that strictly alternate between 0's and 1's.
  More specifically, the fitness is derived by
  1. Looking at the first bit
  2. Counting the pairs of "10" if the first bit is a 1, or
     counting the pairs of "01" if the first bit is a 0

• Function 4: looks at the bit string in two distinct parts:
  1. The first half (8 bits) represents a number
  2. The second half (8 bits) represents a series of function compositions to be called on that number.

     The last 8 bits of the string signal which of 8 different functions to call, F1(x), F2(x), F3(x), ... F8(x). If all 8 bits are 1's, all 8 functions will be called on the number, and the fitness of the string will be:

     F8( F7( F6( F5( F4( F3( F2( F1(x))))))))

     When some of these last 8 bits are 0's, the corresponding function call is omitted. For example, if the last 8 bits are 10010000, the function composition will be:

     F4( F1(x))

     (only the first and fourth functions are called).

  In this case, the bit string should evolve to a solution that finds a number and a series of function compositions that together yield the highest fitness solution. As you can imagine, a change to the numeric part of the solution may change the "best functions", and a change to the functional part of the solution may change the "best number", so we can view this as two solutions that must co-evolve.

  Note: This particular function will work only with bit strings that are 16 bits long (8 bits for number and 8 bits for functions).

1. Try the "all 1's" fitness function, and watch the evolution of strings
   try this with different "seeds" to the random number generator
   try this with strings of different lengths

   for beginners: pay attention to the mechanisms

2. Try the other fitness functions:
   notice how long it takes (on average) to find the best each time
   notice how this changes as bitstrings get longer
   notice how this changes with different crossover rates and mutation rates

3. Which is easier to find: a string of all 1's, or a string of every other 1?
   try strings of different lengths (16, 32, 64), and different seeds
   get a sense for average generation number that the max is found on

   How do you explain the difference?

4. For programmers: write a function of your own to do something interesting (nonlinear)

   For non-programmers: play with the 8 functions -- change them, recompile the program, and run again

   How do your results differ from your intuitions?