Transcript Genetic Algorithm

Genetic Algorithm
Yu-Chi Ho
Jonathan T. Lee
Harvard University
Sep. 7, 2000
1
Outline
Intuition
 The Algorithm
 Issues
 References

2
First Genetic Algorithm
3
Intuition

Based on the theory of evolution:
survival of the fittest, “good”
parents produce “good” children

First introduced by John Holland
(1975)
4
Brief Description
Code the designs as chromosomes
 A population-based model that
produces new designs through
“reproduction”
 A simulated “evolution”

N
5
Example

Traveling Salesman Problem

A design/chromosome, the traveling
order of the cities:
[a b c d f e]
a
b
f
c
e
N
d
6
The Algorithm
Step 0: Randomly generate an initial
population.
Step 1: Select parents and “reproduce” the
next generation
Step 2: Evaluate the fitness of the new
generation
Step 3: Replace the old generation with the
new generation
Step 4: Repeat step 1 though 3 till iteration
T
N
7
Selection

Designs with a better fitness value
have a better chance to be chosen
as a parent

N
To insure that the good “information”
from the good parents is being passed
onto the next generation
8
Reproduction

Cross-over
Pick the parents
[a b c d e f] and [b c d a f e]
 Pick the cross-over point
[a b c d | e f] and [b c d a | f e]
 Reproduce
[a b c d
e f]  [b c d a e f]
[b c d a
f e]  [a b c d f e]
 Correction if necessary

N
9
Reproduction (cont.)

Mutation
Pick the parent
[a b c d e f]
 Pick the mutation point and value
[a b c d e f]: e  c
 Reproduce
[a b c d e f]  [a b c d c f]
 Correction if necessary
[a b c d c f]  [a b e d c f]

N
10
Issues

Pros:


Cons:


Robust
What is the best way to encode the
designs?
Requirement:

Evaluation function must be relatively
fast
11
References



Whitley, D., “A Genetic Algorithm Tutorial,”
Statistics and Computing, Volume 4, pp.
65-85, 1994.
Holland, J., Adaptation in Natural and
Artificial Systems, University of Michigan
Press, 1975.
Heitkötter, J. and D. Beasley (Eds.), The
Hitch-Hiker's Guide to Evolutionary
Computation,
<http://alife.santafe.edu/~joke/encore/w
ww/Q1_1.htm>
12