Transcript Genetic Algorithms notes

Chapter 6:
Genetic Algorithms
July 15, 2009
Rob Bilger

History & Applications

Biological Definition

Mathematical Definition

Sample problem
Overview

“Modern” Heuristics

Holland, 1960

Useful for complex objective functions

If problems are too difficult to solve using
current methods
History

p-Median Problem
◦ Chapter 6, Facility Location text

Traveling Salesman problem (TSP)

Scheduling problems
Applications

A random search technique designed to
imitate the selective breeding or evolution
of organisms

It contains chromosomes, crossover,
mutation, and the survival of the fittest
principle
Biological Definition

Initially, there is a random pool (P,
population) of solutions (chromosomes)
P=5
Chromosome
1
2
3
4
5
P = k * (n/p)

(a,b,c,d)
(1,28,15,3)
(14,9,2,4)
(13,5,7,3)
(23,8,16,19)
(9,13,5,2)
where k > 1
Each chromosome (feasible solution) is
typically encoded as a binary string
Biological Definition (cont’d)

Each of these chromosomes has a fitness
value that corresponds to the objective
function
objective min = a+2b+3c+4d
Chromosome
1
2
3
4
5

(a,b,c,d)
114
54
56
163
58
Next, two solutions (or parents) from this
pool (population) are selected for mating
to produce two new solutions (offspring)
Biological Definition (cont’d)

How the offspring are produced is the
core part of GA

Rank objective function solutions, i
probability for selection =
2i / [P(P+1)]
where i = (worst) 1, 2, 3, ……. P (best)

Parents are selected at random using
these probabilities to ensure best
Biological Definition (cont’d)

Copying parts of the parent chromosomes
to the offspring is done by identifying a
random crossover point

Chromosome sections – after crossover
point – are exchanged to create offspring
Father Chromosome
a1 | b1 ,c 1 ,d1
a1 ,b1 | c 1 ,d1
a1 ,b1 ,c 1 | d1
Mother Chromosome
a2 | b2 ,c 2 ,d2
a2 ,b2 | c 2 ,d2
a2 ,b2 ,c 2 | d2
Offspring Chromosome
a1 ,b2 ,c 2 ,d2 or a2 ,b1 ,c 1 ,d1
a1 ,b1 ,c 2 ,d2 or a2 ,b2 ,c 1 ,d1
a1 ,b1 ,c 1 ,d2 or a2 ,b2 ,c 2 ,d1
Father Chromosome
(13 | 5,7,3)
(9,13 | 5,2)
(13,5,7 | 3)
(14 | 9,2,4)
(13,5 | 7, 3)
Mother Chromosome
(1 | 28,15,3)
(14,9 | 2,4)
(9,13,5 | 2)
(9 | 13,5,2)
(9,13 | 5, 2)
Offspring Chromosome
(13,28,15,3)
(9,13,2,4)
(13,5,7,2)
(14,13,5,2)
(13,5,5,2)
Source: http://library.thinkquest.org/18242/gaexample.shtml
Biological Definition (cont’d)

Parents are replaced by the offspring to
keep the population size constant

Replacements are referred to as the new
generation

This technique can be repeated until a
stopping criteria is satisfied:
 Fixed number of generations, or
 Quality of solution discovered
Biological Definition (cont’d)

Mutation rate, M = 1% typically
◦ Done to enrich the gene pool through
diversification
◦ Randomly change one element

Invasion frequency, IR%
◦ More intense version of mutation where
randomly generated solutions replace IR% of
the population every 1/IF generations.
Biological Definition (cont’d)








P = size of initial population
G = number of generations
O = number of overlapping solutions
M = mutation rate
Ci = crossover operator I
Zj = fitness value of solution j
IF = frequency of invasions
IR = % of population replaced by invasion
Mathematical Definition

p-Median problem
◦ Locate p facilities to minimize the demand
weighted distance between each demand
node and its assigned facility
Min ΣΣ hi dij yij
s.t.
Σ xj = p
Σ yij = 1
yij - xj ≤ 0
xi {0, 1}
yij {0, 1}
Sample Problem
•p = 2
# of facilities to locate
•P = 6
population
•n = 5
elements in solution (genes)
Sample Problem

Disadvantage of GA is the number of
parameters involved:
◦
◦
◦
◦
◦
◦

Size of initial pool
Method for selecting parents for mating
The crossover operator
The number of offspring to produce
The replacement technique
The mutation rate
GA’s are best when there are a small
number of constraints (or none)
Closing

Q&A
Questions
1.
What are the different crossover methods for creating new
solution sets (offspring). Explain each.
2.
Again using the p-Median example with P=6, p=2, and n=5
create a new generation of offspring using the Template
Operator [ 1,0,1,0,1 ] and initial pool [0,1,1,0,0], [1,1,0,0,0],
[0,0,1,0,1], [0,0,1,1,0], [1,0,0,0,1], [0,1,0,0,1] with i values of
1, 2, 3, 4, 5, 6 respectively. For purposes of this exercise
assume parents for mating are randomly selected with i values
5, 6; 3, 5; and 4, 6. What problems do you notice with the
new generation?
3.
Which crossover operator did the text choose for the p-Median
problem? Why? Describe a problem that may arise from using
one of the other crossover operators.
Homework