GENETIC ALGORITHM
EXAMPLE
Artificial Intelligence
GA Example
• Maximize the function f(x) = x2 over the range of integers from 0 to
31 (x is between 0 and 31). Assume that the population size is 4.
Initial Selection/ Crossover/ Mutation/
population Reproduction Recombine Mutate
2
GA Example
Initial Selection/ Crossover/ Mutation/
population Reproduction Recombine Mutate
[1,0,0,1,0]
[1,1,0,1,1]
[1,0,1,1,1]
[0,1,1,1,0]
3
GA Example
Initial Selection/ Crossover/ Mutation/
population Reproduction Recombine Mutate
Initial x x2 Probability Bin
population
[1,0,0,1,0] 18 324 324/1778=0.18 0.01 – 0.18
[1,1,0,1,1] 27 729 729/1778 0.19 – 0.59
=0.41
[1,0,1,1,1] 23 529 529/1778 0.60 – 0.89
=0.30
[0,1,1,1,0] 14 196 196/1778 0.90 – 1
=0.11
4
total 1778 1.0
GA Example
Initial Selection/ Crossover/ Mutation/
population Reproduction Recombine Mutate
Selecting Parent 1: 0.12
Initial x x2 Probability Bin [1,0,0,1,0]
population
Selecting Parent 2: 0.25
[1,0,0,1,0] 18 324 324/1778=0.18 0.01 – 0.18
[1,1,0,1,1] 27 729 729/1778 0.19 – 0.59 [1,1,0,1,1]
=0.41 Selecting Parent 3: 0.55
[1,0,1,1,1] 23 529 529/1778 0.60 – 0.89
=0.30 [1,1,0,1,1]
[0,1,1,1,0] 14 196 196/1778 0.90 – 1 Selecting Parent 4: 0.95
=0.11
[0,1,1,1,0] 5
total 1778
GA Example
Initial Selection/ Crossover/ Mutation/
population Reproduction Recombine Mutate
[1,0,0,1,0] [1,0,0,1,0]
[1,1,0,1,1] [1,1,0,1,1]
[1,0,1,1,1] [1,1,0,1,1]
[0,1,1,1,0] [0,1,1,1,0]
6
GA Example
Initial Selection/ Crossover/ Mutation/
population Reproduction Recombine Mutate
[1,0,0,1,0] [1,0,0,1,0] [1,0,0,1,1]
[1,1,0,1,0]
[1,1,0,1,1] [1,1,0,1,1]
[1,1,1,1,0]
[0,1,0,1,1]
[1,0,1,1,1] [1,1,0,1,1]
[0,1,1,1,0] [0,1,1,1,0]
7
GA Example
Initial Selection/ Crossover/ Mutation/
population Reproduction Recombine Mutate
[1,0,0,1,0] [1,0,0,1,0] [1,0,0,1,1] [1,0,0,1,1]
[1,1,0,1,0]
[1,1,0,1,1] [1,1,0,1,1] [1,1,0,1,0]
[1,1,1,1,0]
[1,1,1,1,0]
[0,1,0,1,1]
[1,0,1,1,1] [1,1,0,1,1]
[1,1,0,1,1]
[0,1,1,1,0] [0,1,1,1,0]
8
All Together Selecting Parent 1: 0.12
[1,0,0,1,0]
Initial x x2 Probability Bin Selecting Parent 2: 0.25
population [1,1,0,1,1]
[1,0,0,1,0] 18 324 324/1778=0.18 0.01 – 0.18
Selecting Parent 3: 0.55
[1,1,0,1,1] 27 729 729/1778 0.19 – 0.59 [1,1,0,1,1]
=0.41
Selecting Parent 4: 0.95
[1,0,1,1,1] 23 529 529/1778 0.60 – 0.89
=0.30 [0,1,1,1,0]
[0,1,1,1,0] 14 196 196/1778 0.90 – 1
[1,0,0,1,0] [1,0,0,1,0] =0.11 [1,0,0,1,1] [1,0,0,1,1]
total 1778 1.0
[1,1,0,1,0]
[1,1,0,1,1] [1,1,0,1,1] [1,1,0,1,0]
[1,1,1,1,0]
[1,1,1,1,0]
[0,1,0,1,1]
[1,0,1,1,1]
Initial [1,1,0,1,1]
Selection Crossover Mutation 9
population [1,1,0,1,1]
Questions?
10
