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

1. Randomly initialize the population of solutions

   Use a population sufficiently large to be representative of the search space as a whole.

2. 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.

3. While termination condition does not hold
   1. Replicate individuals based on their fitness

      Use a weighted roulette wheel to reproduce strings in the next generation in proportion to their fitness.

   2. Transform the individuals in the population

      1. Randomly pick two parents from the population

      2. Crossover the parents (pick a random point in the strings and exchange their top parts) to produce offspring

      3. Mutate each offspring (randomly decide whether to flip each bit in the string) optionally flip each bit)

   3. 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.