Overview of Genetic Algorithms
  
  
  A genetic algorithm searches a (potentially) vast
  solution space for an optimal (or near optimal) solution
  to the problem at hand.
  
  -  Solutions are encoded as strings over a finite alphabet
  (often 0 and 1).
  
-  A fitness function (or objective function)
  is used to evaluate each string (solution).
  
-  Bits and pieces of the fittest strings (solutions)
  are used to generate new strings (solutions).
  
  Each time step (or generation) of the algorithm produces
  a population of possible solutions based on the population
  from the previous time step (or generation).
  
  -  Natural selection:
  strings with a good fitness value survive from one generation
  to the next with high probability; strings with a poor fitness
  value perish with high probability.
  
   
-  Reproduction: two strings chosen via natural selection
  mate (via crossover, which picks a position within the strings
  at random and exchanges the upper halves of the two strings)
  to produce new strings.
  
   
-  Mutation: strings can undergo spontaneous changes
  (with small probability)
  to produce new strings in a different part of the solution space.
  
  The Algorithm
  
  
  -  Randomly initialize the population of solutions
  
  Use a population sufficiently large to be representative of
  the search space as a whole.
   
   
-  Evaluate the fitness of each individual
  
  That is, evaluate the fitness function for each solution in the
  population to see if the termination criteria for optimality are met.
   
   
-  While termination condition does not hold
       
        
       -  Replicate individuals based on their fitness
       
       Use a weighted roulette wheel to reproduce strings in the
       next generation in proportion to their fitness.
        
        
-  Transform the individuals in the population
  	  
  	      
  	       
-  Randomly pick two parents from the population
  	      
                 
-  Crossover the parents (pick a random point in the
  	      strings and exchange their top parts) to produce offspring
  	      
                 
-  Mutate each offspring (randomly decide whether to
  	      flip each bit in the string) optionally flip each bit)
  	  
 
        
-  Evaluate the fitness of each new individual
       
 
  Selection using a Roulette Wheel
  
  
  /*
     Select an individual for the next generation
     in proportion to its contribution to the total
     fitness of the population
  */
  
  /* Assumes fitness values in global array fitness */
  
  /* Returns a single selected individual */
  
  int select (real sum_of_fitness_values)
      int index;
      index = 0;
      sum = 0.0;
      /* Random number between 0 and fitness total */
      r = drand48() * sum_of_fitness_values;
      do
  	index++;
  	sum = sum + fitness[index];
      while (index < SIZE-1) and (sum < r);
      return index;
  
  
  
  Termination Criteria
  
  
  A GA can be expected to produce good solutions, but might never
  find a perfect solution.
  When is a good solution 'good enough'?
  
  
  When should a GA terminate?
  
  
  
-  after a prespecified number of generations.
  
   
-  when an individual solution reaches a prespecified level of fitness.
  
   
-  when the variation of individuals from one generation to the next
  reaches a prespecified level of stability.