A Simple Genetic Algorithm
(from Genetic Algorithms by David Goldberg)


     A simple genetic algorithm that yields good results in many practical
problems is composed of three operators:
   1. Reproduction
   2. Crossover
   3. Mutation

     Reproduction is a process in which individual strings are copied 
according to their objective function values, f (biologists call this
function the fitness function).  Copying strings according to their 
fitness values means that strings with a higher value have a higher
probability of contributing one or more offspring in the next generation.
This operator is an artificial version of natural selection, a Darwinian 
survival of the fittest among string creatures.
   One easy way to implement the reproduction operator is to create a 
biased roulette wheel where each current string in the population has
a roulette wheel slot sized in proportion to its fitness.
  Suppose the sample population of four strings has objective or fitness
values f as follows:  

No.      String       Fitness  % of total
-----------------------------------------
1        0 1 1 0 1     169      14.4 
2        1 1 0 0 0     576      49.2
3        0 1 0 0 0      64       5.5 
4        1 0 0 1 1     361      30.9
-----------------------------------------
Sum                   1170     100.0

    Summing the fitness over all four strings, we obtain a total of 1170. 
The percentage of population total fitness is also shown in the table.  The 
corresponding weighted roulette wheel for this generation's reproduction
is shown below.  To reproduce, spin the weighted roulette wheel four times.
For this example, string number 1 has a fitness value of 169, which 
represents 14.4 percent of the total fitness.  As a result, string 1 is
given 14.4 percent of the biased roulette wheel, and each spin turns up
string 1 with probability 0.144.  Each time we require another offspring, a
spin of the weighted roulette wheel yields the reproduction candidate.
In this way, more highly fit strings have a higher number of offspring in
the succeeding generation.  Once a string has been selected for
reproduction, an exact replica of the string is made.  This string is then
entered into a mating pool, a tentative new population, for further 
genetic operator action.
   After reproduction, simple crossover may proceed in two steps.  First,
members of the newly reproduced strings in the mating pool are mated at
random.  Second, each pair of strings undergoes crossing over as follows:
an integer position k along the string is selected uniformly at random
between 1 and the string length less one [1, len(str)-1].  Two strings are
created by swapping all characters between positions k + 1 and len(str)
inclusively.  For example, consider the two strings A1 and A2:

     A1 = 0 1 1 0 | 1
     A2 = 1 1 0 0 | 0

Suppose k = 4.  The resulting crossover yields two new strings:

     A1new = 0 1 1 0 0
     A2new = 1 1 0 0 1