Genetic Algorithms

• Genetic Algorithms
  • Starts with a large population of (random) possible solutions, and "breeds" new solutions from the best (fitest) existing ones.
  • A solution consists of a vector (chromosome) of discrete elements (genes).
  • New solutions are bred by crossover and mutation.
  • Complete replacement of a population by new solutions is a generation.
  • Population size and chromosome size are normally fixed.
  • Fitter solutions are often allowed to breed proportionally more new solutions.

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

  • Chance of breeding is proportional to fraction of total, e.g., random numbers 0.56 and 0.38 select 0011 and 1001.
  • Two random pairs are selected, and four new solutions are bred using a randomly selected single crossover point.
  • 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