Lecture 2:
Canonical Genetic
Algorithms
Suggested reading: D. E. Goldberg, Genetic Algorithm in Search, Optimization, and
Machine Learning, Addison Wesley Publishing Company, January 1989
What Are Genetic Algorithms?
Genetic algorithms are optimization algorithm
inspired from natural selection and genetics
A candidate solution is referred to as an individual
Process
Parent individuals generate offspring individuals
The resultant offspring are evaluated for their
fitness
The fittest offspring individuals survive and
become parents
The process is repeated
2
History of Genetic Algorithms
In 1960’s
Rechenberg: “evolution strategies”
Optimization method for real-valued parameters
Fogel, Owens, and Walsh: “evolutionary programming”
Real-valued parameters evolve using random mutation
In 1970’s
John Holland and his colleagues at University of Michigan
developed “genetic algorithms (GA)”
Holland’s1975 book “Adaptation in Natural and Artificial
Systems” is the beginning of the GA
Holland introduced “schemas,” the framework of most
theoretical analysis of GAs. 3
In 1990’s
John Koza: “genetic programming” used genetic
algorithms to evolve programs for solving certain tasks
It is generally accepted to call these techniques as evolutionary
computation
Strong interaction among the different evolutionary
computation methods makes it hard to make strict distinction
among GAs, evolution strategies, evolutionary programming
and other evolutionary techniques
4
Differences Between GAs and
Traditional Methods
GAs operate on encodings of the parameters values,
not necessarily the actual parameter values
GAs operate on a population of solutions, not a
single solution
GAs only use the fitness values based on the
objective functions
GAs use probabilistic computations, not
deterministic computations
GAs are efficient in handling problems with a
discrete or mixed search spaces
5
The Canonical GA
Canonical GA
The canonical genetic algorithm refers to the GA
proposed by John Holland in 1965
START
Initialization
Fitness evaluation
Selection
Crossover
Mutation
STOP?
END
7
Gene Representation
Parameter values are encoded into binary strings of
fixed and finite length
Gene: each bit of the binary string
Chromosome: a binary string
Individual: a set of one or multiple chromosomes, a
prospective solution to the given problem
Population: a group of individuals
Longer string lengths
Improve resolution
Requires more computation time
8
Binary Representation
Suppose we wish to maximize f (x)
Where [
x ∈ Ω; Ω = xmin, xmax ]
Binary representation xbinary ∈ [bl bl −1 L b2 b1 ]
[
We map xmin, xmax ] to [0 , 2 l
−1 ]
x max − x min l
i −1
Thus x = x min + ∑ i
b 2
2l − 1 i =1
9
Example
Let l = 5, Ω = [-5, 20]
Then
xbinary = [ 0 0 0 0 0 ] ⇒ x = −5
xbinary = [ 1 1 1 1 1 ] ⇒ x = 20
20 − (−5)
xbinary = [ 1 0 0 1 1 ] ⇒ x = −5 + (2 4 + 21 + 2 0 ) = 10.3226
2 −1
5
10
Fitness Evaluation
Each individual x is assigned with a fitness value
f(x) as the measure of performance
It is assumed that the fitness value is positive and
the better the individual as a solution, the fitness
value is more positive
The objective function can be the fitness function
itself if it is properly defined
11
Example 1
Consider the problem
max g(x) = -x2 + 4x, x ∈ [1, 5]
A fitness function
f(x) =-g(x)+100= -x2 + 4x + 100
12
Example 2
Consider the problem
min g(x) = x2, x ∈ [-10, 10]
A fitness function
f(x) = 1/(g(x) + 0.1) = 1/(x2 + 0.1)
13
Selection
Chooses individuals from the current population to
constitute a mating pool for reproduction
Fitness proportional selection methods
Each individual x is selected and copied in the
mating pool with the probability proportional to
fitness (f(x) / Σf(x))
14
Roulette Wheel Selection
Individuals with
fitness values Mating pool
19
76
Winner
44
27 Assign a piece
8 proportional to the
53 fitness value
31
76
15
Crossover
Single-point crossover is assumed
Two parent individuals are selected from mating pool
Crossover operation is executed with the probability pc
Crossover point is randomly chosen and the strings are
swapped with respect the crossover point between the
two parents
16
Single Point Crossover
Crossover point
Parent 1 1 0 1 0 0 1 1 0 Child 1 1 0 1 0 1 0 1 1
Parent 2 1 1 0 0 1 0 1 1 Child 2 1 1 0 0 0 1 1 0
17
Mutation
Mutation operator is applied gene-wise, that is, each
gene undergoes mutation with the probability pm
When the mutation operation occurs to a gene, its
gene value is flipped
1 0
0 1
Mutation points
1 1 0 0 1 0 1 1 1 0 0 0 1 1 1 1
18
Overview of Canonical GA
Initial
population Fitness
Evaluation
19
76
44
f (x) 27
8
53
31
76
Selection
Mutation Crossover Mating pool
19
Summary of Canonical GA
Binary representation
Fixed string length
Fitness proportional selection operator
Single-point crossover operator
Gene-wise mutation operator
20
A Manual Example
Using Canonical GAs
Problem Description
Consider the following maximization problem
max f(x) = x2
where x is an integer between 0 and 31
1000
900
800
700
600
f(x)
500
400
300
200
100
0
0 5 10 15 20 25 30
x
f(x) = x2 has its maximum value 961 at x = 31 22
Gene Representation
Before applying GA, a representation method must be
defined
Use unsigned binary integer of length 5
10110 1⋅24 + 0⋅23 + 1⋅22 + 1⋅21 + 0⋅20 = 22
A five-bit unsigned binary integer can have values
between 0(0000) and 31(11111)
23
Canonical GA Execution Flow
START
Initialization
Fitness evaluation
Selection
Crossover
Mutation
STOP?
END
24
Initialization
Initial populations are randomly generated
Suppose that the population size is 4
An example initial population
Individual Initial x value
No. population
1 01101 13
2 11000 24
3 01000 8
4 10011 19 25
Fitness Evaluation
Evaluate the fitness of initial population
The objective function f(x) is used as the fitness
function
Each individual is decoded to integer and the fitness
function value is calculated
26
Fitness Evaluation
Decoding
01000 Decode x=8 Evaluation f(8) = 82 = 64
Results
Individual No. Initial population x value f(x) fi / Σf Expected
number
1 01101 13 169 0.14 0.56
2 11000 24 576 0.49 1.96
3 01000 8 64 0.06 0.24
4 10011 19 361 0.31 1.24
27
Selection
Select individuals to the mating pool
Selection probability is proportional to the fitness
value of the individual
Roulette wheel selection method is used
Individual Initial population x value f(x) fi / Σf Expected
No. number
1 01101 13 169 0.14 0.56
2 11000 24 576 0.49 1.96
3 01000 8 64 0.06 0.24
4 10011 19 361 0.31 1.24
28
Selection
1
Roulette wheel 2
3
4
Outcome of Roulette wheel is 1, 2, 2, and 4
Resulting mating pool
No. Mating pool
1 01101
2 11000
3 11000
4 10011
29
Crossover
Two individuals are randomly chosen from mating pool
Crossover occurs with the probability of pc = 1
Crossover point is chosen randomly
Mating pool Crossover New x f(x)
point population
0110 1 01100 12 144
4
1100 0 11001 25 625
11 000 11011 27 729
2
10 011 10000 16 256
30
Mutation
Applied on a bit-by-bit basis
Each gene mutated with probability of pm = 0.001
Before After x f(x)
Mutation Mutation
01100 01100 12 144
11001 11001 25 625
11011 11011 27 729
10000 10010 18 324
31
Fitness Evaluation
Fitness values of the new population are calculated
Old x f(x) New x f(x)
population population
01101 13 169 01100 12 144
11000 24 576 11001 25 625
01000 8 64 11011 27 729
10011 19 361 10010 18 324
sum 1170 sum 1756
avg 293 avg 439
max 576 max 729
32
