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.

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


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?