Worksheet on a Simulation of a Genetic Algorithm
(from Genetic Algorithms by David Goldberg)

                                             Name ______________

   (Here's a sample starter program.
   Write a program to simulate this process for n generations.
     - Print out statistical results such as
         max, min, and average values for each generation,
         initial and final populations
         fitness levels
     - demonstrate the effect of changing the probabilities for
         crossover and mutation.  For example, with no mutations,
         p = 0, your program should frequently get "hung up" on
         local minimums.
 
          Initial                                     Expected       Actual
         Population   x Value             pselect      count         Count 
String   (randomly   (unsigned    f(x)  f(i)/sum(f)   f(i)/avg(f)  (roulette
No.      generated)   integer)     x^2                              wheel)
-----------------------------------------------------------------------------
1        0 1 1 0 1     13         169     0.14         0.58          1
2        1 1 0 0 0     24         576     0.49         1.97          2
3        0 1 0 0 0      8          64     0.06         0.22          0
4        1 0 0 1 1     19         361     0.31         1.23          1
-----------------------------------------------------------------------------
Sum                              1170     1.00         4.00         4.0
Average                           293     0.25         1.00         1.0
Max                               576     0.49         1.97         2.0

                     
                     (NOTE: FOR THIS TABLE THE INDEXES START ON 1) 

Mating Pool after      Mate      Crossover Site
 Reproduction       (Randomly    (Randomly         New         x     f(x)
(Cross site shown)   selected)    selected)      Population  Value   x^2
-----------------------------------------------------------------------------
0 1 1 0 | 1             2           4           0 1 1 0 0     12     144
1 1 0 0 | 0             1           4           1 1 0 0 1     25     625
1 1 | 0 0 0             4           2           1 1 0 1 1     27     729
1 0 | 0 1 1             3           2           1 0 0 0 0     16     256
-----------------------------------------------------------------------------
Sum                                                                 1754
Average                                                              439
Max                                                                  729

(Go here for a continuation of this trace.)

Reproduction is the first genetic "operator" used in this simulation.
Crossover is the second genetic operator used. 
Mutation is the third genetic operator used here.

The crossover probability is assumed to be unity, p(c) = 1.0
The mutation probability is assumed to be low, p(m) = 0.001.  No mutation 
  occurred in the above example.

Crossover proceeds as follows:
   1. Choose randomly two different strings to be mated.
   2. Choose a random crossover point, k, between 1 and len(string).
      For 0 indexing, choose a point between 0 and len(string)-1. 
 Create two new individuals with crossover:
   3. Copy the bits 1..k (or 0..k-1) from individual #1 to the new
      individual #1.  Copy the bits k+1..len(str) (or k..len(str)-1) 
      from individual #2 to the new individual #1.
   4. Copy the bits 1..k (or 0..k-1) from individual #2 to the new
      individual #2.  Copy the bits k+1..len(str) (or k..len(str)-1)
      from individual #1 to the new individual #2.

   In the example above, with a crossing site of 4, the two strings
     01101 and 11000 cross and yield two new strings 01100 and 11001.
   The remaining two strings in the mating pool are crossed at site 2,
     and the two new individuals are 11011 and 10000.

Mutation - mutation is a second operator used in genetic algorithms (
   also called evolutionary computation)
   Mutation is done on a bit by bit basis, choosing a random bit to alter.
   The effect is to change a 0 to a 1, or a 1 to a 0.