Genetic Algorithms

• Genetic Algorithms
  • A solution consists of a vector (chromosome) of discrete elements (genes).
  • Starts with a large population of (random) candidate solutions, and "breeds" new candidates from the best (fitest) existing ones.
  • New solutions are bred by crossover and mutation, with a preference for using better candidate solutions.
  • Complete replacement of a population by new candidate solutions is a generation.
  • Population size and chromosome size are normally fixed.

• Breeding
  • Single point crossover takes two solution vectors, selects a point in the vector, and produces two new solutions by swapping the suffixes. (Suited to ordered data that has a bottom and top, e.g., bits in binary arithmetic, sequences of events, DNA!)
  • Two point crossover takes two solution vectors, treats them as rings, selects two points in the vector, and produces two new solutions by swapping the elements between the two points. (Suited to ordered data that is modulo, e.g., WHAT?)
  • Uniform crossover takes two solution vectors, selects elements from one parent with probability P (often 0.5), and from the other parent otherwise, and produces one new solution with the selected elements. This can be repeated. (Suited to independent data, e.g., control room switches)
  • Mutation takes one solution vector, randomly changes some elements, to produce one new solution.

• Termination
  • A limit on the number of generations is reached
  • A solution of high enough quality is found
  • Quality of solutions levels off

• Example: Optimizing a function - what input is best?
  • Consider the sin function over 0-15 (radians)
  • Optima are at pi/2 + N*2*pi, for N = 1 .. 4
  • 0-15 is represented by four bits, to form a solution
  • Initial (toy size) population

    1001 = 9   sin = 0.41   fraction of total = 0.46  cumulative = 0.46
    0011 = 3   sin = 0.14   fraction of total = 0.37  cumulative = 0.83
    1010 = 10  sin = -0.54  fraction of total = 0.15  cumulative = 0.98
    0101 = 5   sin = -0.96  fraction of total = 0.02  cumulative = 1.00
               Total 3.05 (taking -1 as the base)
    

  • The chance of breeding is proportional to the fraction of total.
  • A random pair of candidate is selected by generating two random numbers from 0.0 to 1.0, and using the candidates whose cumulative total is next greater, e.g., for the random numbers 0.56 and 0.38 select 0011 and 1001, and for 0.22 and 0.92 select 1001 and 1010
  • Two new solutions are bred using a random crossover point, e.g., 2 and 3.
  • Example of one generation:

    1001 + 0011 @ 2 = 1011 & 0001
    1001 + 1010 @ 3 = 1000 & 1011
    

  • The new generation is

    1000 = 8   sin = 0.99   fraction of total = 0.52  cumulative = 0.52
    0001 = 1   sin = 0.84   fraction of total = 0.48  cumulative = 1.00
    1011 = 11  sin = -1.00  fraction of total = 0.00  cumulative = 0.00
    1011 = 11  sin = -1.00  fraction of total = 0.00  cumulative = 0.00
    

Exam Style Questions