Introduction to AI - Week 5

Genetic Algorithms
Evolutionary Computation (also called evolutionary programming) copied from nature:

Principles of Darwinism


Why Genetic Algorithms

Taken from [Tom Mitchell, p.250] (from where also most of the rest of this lecture is adapted.)

Genetic Algorithms

In order to apply genetic algorithms, answer

Components of Genetic Algorithms


Pseudo Code for Genetic Algorithms

GA(Fitness,Threshold,p,r,m)
;;; Fitness: a function that assign a score given a hypothesis
;;; Threshold: specifies the termination criterion
;;; p: the population size
;;; r: fraction of population replaced at each step
;;; m: mutation rate
Randomly initialize population P;
While maxh in P fitness(h) < Threshold do
    Create new generation PS
end_do
Return h from P with highest fitness.

How to create the next generation

    Create new generation PS
  1. Probabilistically select (1-r)p members of P to add to PS. Probability of an element to be selected in one step is proportional to its fitness, i.e. ratio of its fitness divided by the sum of all fitness values.

  2. Probabilistically select [r* p]/[2] pairs of P for crossover. Probability of an element to be selected in one step is proportional to its fitness. For each pair generate two offsprings. Add all offsprings to PS.
  3. Randomly flip each bit in PS in the representation with (small) probability m.

  4. Update P as PS

How to create the next generation (Cont'd)

  1. The survival from one generation to the next is proportional to the fitness of an element. (A fit gazelle is less likely to be eaten by a lion than a less fit one.)

  2. Propagation of elements is proportional to fitness. Fit elements are more likely to succeed in reproduction than non-fit ones.

  3. Totally new features can be generated by random mutations, which occur only with very small probability. They are important in order to avoid local maxima.

Example, Key Steps in Genetic Algorithms


Example

Learn decision list for the restaurant waiting problem

Genetic Operators

Single-point crossover
 11101001000    11101010101
     
 00001010101    00001001000
The procedure takes two bitstrings of length n, randomly selects a number i between 1 and n and breaks up the strings at position i and puts together the first part of the first string with the second part of the second as well as the first part of the second string with the second part of the first string.

Genetic Operators (Cont'd)

Two-point crossover
 11101001000    11001011000
     
 00001010101    00101000101
The procedure takes two bitstrings of length n, randomly selects two numbers i and j between 1 and n and breaks up the strings at positions at i and j and puts together the first and last part of the first string with the middle part of the second as well as the first and last part of the second string with the middle part of the first string.

Genetic Operators (Cont'd)

Uniform Crossover
 11101001000    10001000100
     
 00001010101    01101011001
The procedure takes two bitstrings of length n, randomly decides for each position of whether the bit of the first or the second should go in the first or in the second child.

Point Mutation

 11101001000    11101011000

Further Aspects


Genetic Programming


Tree Representation of Programs

Example:
Representation of
sin(x)+sqrt(x2+y)
in form of a tree.

General programs can be represented in a similar form, assumed the corresponding primitives are available, e.g., conditionals, loops, boolean expressions.


Crossover in Genetic Programming


Example: Stacking Blocks

Stack blocks which are on a table to spell in a tower the word "universal." Use a set of 166 such initial configurations to evaluate the fitness of a candidate program.


Program primitives


Generated Program


Co-Evolution


Further Issues


Summary

Important decisions for a genetic approach:

Wide range of application, for certain problems very good results (poor on others).

Can be computationally very expensive, but is also be rather robust, e.g. the fitness function is not necessarily invariant over time.


Further Reading    



© Manfred Kerber, 2004, Introduction to AI
24.4.2005
The URL of this page is http://www.cs.bham.ac.uk/~mmk/Teaching/AI/Teaching/AI/l5.html.
URL of module http://www.cs.bham.ac.uk/~mmk/Teaching/AI/