What are genetic

algorithms?
(GAs)
• A class of stochastic search strategies
modeled after evolutionary mechanisms

• a popular strategy to optimize non-linear

systems with a large number of variables
3
 What are genetic
algorithms?
(GAs)
• A major difference between natural GAs
and our GAs is that we do not need to
follow the same laws observed in nature.
– Although modeled after natural processes, we
can design our own encoding of information,
our own mutations, and our own selection
criteria.
4
Why would we use genetic algorithms?
Isn’t there a simple solution we learned
in Calculus?
• A local method will only find
local extrema.
If we start our search here
We’ll end up here
8
How do we use GAs to optimize
the parameters we’re
interested in?
• Choose parameters to optimize
• Determine chromosomal representation
of parameters
• Generate initial population of individuals
(chromosomes)
• Evaluate fitness of each individual
to reproduce
• Allow selection rules and random behavior
to select next population
9
 Enter
Genetic Algorithm
Create Initial Population

Evaluate the fitness

Evaluation
of each individual

Select the parents

based on fitness Selection

Create new population Recombination

10
• Determine chromosomal representation of
parameters
• Parameters can be encoded in binary, base-4
base-10, etc.
• After you decide how to encode the parameters, you
must decide on the domain of your parameters. This
is entirely dependent on your problem. You will want
to allow your parameters to be anything physically
reasonable (if you’re solving a physical problem)

• Create an initial population with randomized

chromosomes
 Create Initial Population
• Population size is chosen (1-10 individuals/parameter
optimized for most applications)
• Parameters to be optimized are encoded.
– Binary, Base 10
– Let’s say we have 2 parameters with initial values of 32
and 13. In binary and base 10 they would look like:
 Chromosome of the
100000001101
individual

3213
encoding 22
How binary genes translate
into parameters
101011101001010111010000100110
698 349 38 You need to
understand the
system you are
optimizing in
order to determine
the proper
parameter range
• The initial population can be generated by
randomizing the genes for each chromosome of
the initial population

• You can set the parameters for a few individuals

if you want. This might speed up the process.
 Review Steps in a GA
1.Initialization of population
2. Evaluation of fitness
3. Selection
4. Recombination
5. Repeat 2-4
26
 Evaluation

• Assign a fitness value to each individual

based on the parameters derived from its
chromosome
Evaluate Fitness 27
• Each chromosome/(parameters set)/individual can
be evaluated separate from the other individuals.
– GA optimizations are typically described as
embarrassingly parallelizable

• The evaluation of the chromosomes reduces down

to a fitness value for each individual which will
be used in the next step
 Selection
• Allow selection rules and random behavior
to select next population

Selection 30
• The parents must be selected based on their
fitness.

• The individuals with a higher fitness must have

a higher probability of having offspring.

• There are several methods for selection.

Selection 31
 Roulette
Wheel
Selection
• Probability of parenthood
is proportional to fitness.
• The wheel is spun until
two parents are selected.
• The two parents create Fit(#1)

one offspring. Fit(#2)

Fit(#3)
• The process is repeated to Fit(#4)
Fit(#5)
create a new population
for the next generation.

Selection 32
• Roulette wheel selection has problems if
the fitness changes by orders of magnitude.
• If two individuals have a much higher
fitness, they could be the parents for
every child in the next generation.
 Fit(#1)
Fit(#2)
Fit(#3)
Fit(#4)
Fit(#5)

Selection 33
Another Reason Not to Use
the Roulette Wheel
• If the fitness value for all
individuals is very close,
the parents will be chosen Fit(#1)
Fit(#2)
with equal probability, Fit(#3)

and the function will Fit(#4)

Fit(#5)

cease to optimize.
• Roulette selection is very
sensitive to the form of
the fitness function and
generally requires
modifications to work at
all.

Selection 34
Rank Selection
Fit(#1)
Fit(#2)

• All individuals in Fit(#3)

Fit(#4)

the population are 1 Fit(#5)

ranked according
to fitness
rank
• Each individual is
assigned a weight Fit(#1)

inversely Fit(#2)
Fit(#3)
Fit(#4)

proportional to the 1 Fit(#5)

1.7
rank (or other rank
similar scheme).

Selection 35
 Tournament Selection
• 4 individuals (A,B,C,D) are randomly selected from
the population. Two are eliminated and two become
the parents of a child in the next generation

A
A
Fitness(A) > Fitness(B) B

C
D
Fitness(D) > Fitness(C) D

Selection 36
Tournament Selection
• Selection of parents continues until a new
population is completed.
• Individuals might be the parent to several children,
or no children.

A
A
Fitness(A) > Fitness(B) B

C
D
Fitness(D) > Fitness(C) D

Selection 37
Similarities Between
Tournament
and Rank Selection
 Fraction of
• Tournament Fitness
selection is very population
similar to rank 9 Both parents were
selection in the 16 above the median
limit of a large
population when 6 One parent was

we assign a 16 above the median

weight of 1/rank.
1 Neither parent was
above the median
Selection
16 38
 Recombination
• Using the chromosomes of the parents, we
create the chromosome of the child

Recombination 39
Recombination with crossover
points
• We can choose a Parent 1
number of Parent 2
crossover points child

A a A In this case, the parameters

Param. 1 B b B remained intact, and the
(eyes) C c C child inherited the same eyes
D d D as parent1 and the same
e nose as parent2.
E e
f
Param. 2 F f
g
(nose) G g
H h h

Recombination 40
crossover point occurs within a
parameter
parent1
parent2
child

A a A
Param. 1 B b B
In this case the child will have
(eyes) C c C
a new nose that is not the same
D d D
E e E as parent1 or parent2.
Param. 2 F f F
(nose) G g g
H h h
Recombination 41
representation of parameters becomes important.
parent1
parent2 Not possible if
child we used base 10
encoding
 1 1 1
Param. 1 1 0 1 1 1 1
1 1 1 5 0 5
1 0 1
0
0 1 0 0 1 0
Param. 2 0 1
1 0 5 3
0 1
0 1 1

Recombination 42
 Recombination – Uniform Crossover
• Uniform crossover
– No limit to crossover points
A a a
B b B Allows more variation in offspring
C c c and decreases need for random
D d D mutations
E e e
F f f
G g g
H h H

Recombination 43
 parent1
• Mutations can
parent2
be applied after
child
recombination
A a A A
Param. 1 B b B B
C c C C
D d D D A random mutation
E e e e has been applied to
Param. 2 F f f f the child
G g g g
H h h h
Random
44
mutations
• Creep mutations are a special
type of random mutation. Possible creep
• Creep mutations cause a mutations for
parameter to change by a small param. 1
amount, rather than randomizing
any one element.
 1 1 1 1 1
Param. 1 1 1 1 1 1
1 1 1 0 1
0 1 0 1 1
0 1 1 1 OR 1
Param. 2 0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

Random
45
mutations
• The desirable frequency of mutations depends
greatly on the other GA options chosen.

A a A A
Param. 1 B b B B
C c C C
D d D D
E e e e
Param. 2 F f f f
G g g g
H h h H

Random
46
mutations
 Other Operators for Recombination
• Other rearrangements of
information are possible
• Swap entire genes
• Swap locus 0 2
4 4 0 5
2 0 4 9
8 8 2 0
5 5 8 3
9 9 5 0
0 0 9 4
3 3 0 2
3 8
Random
47
mutations
 Micro-GA
• Small population size of 1 individual per
parameter optimized.
• No random mutations.
• When the genetic variance is below a
certain threshold (~5%), the most fit
individual goes on, while the chromosomes
of all other individuals are randomized
• Cycle this process
50
Overview of a micro-GA
Create initial population

Evaluate the fitness

of each individual

Select the parents

based on fitness

Recombine parents to
create new population

Is the variance in genes

< than 5% No

Randomize the chromosomes

for all but the most fit individual Yes
51
 Micro-GA Pros and Cons
• Tends to be very efficient in terms of total
CPU time.
• Robust algorithm with no need to tinker
with random mutation parameters

• It uses a smaller population,

and therefore has less potential
for parallelization.
52
 Review
Evaluation of the fitness
is the time-consuming
Create Initial Population portion

Evaluate the fitness

Evaluation
of each individual

Select the parents

based on fitness Selection

53
Create new population Recombination
 How do you know if
you’ve found the absolute
maximum?
• You don’t
• Even GAs are not a “black-box” optimizer
for any function
• You can gain confidence by running
several optimizations with different starting
parameters, different algorithm options,
and different parameter ranges.
54
Which GA options are good picks
for my system?
• Start with robust algorithms
– Micro-GA
– Binary encoding
– Tournament selection
– Uniform crossover at gene boundaries

• If you are unsatisfied with the progress you

can change a couple options
– Allow crossover everywhere to introduce more
variety between each generation.
• Change to base-10 encoding as well, so it isn’t too random
– Use rank selection with a weight of 1/rank 3 to heavily
favor the best individuals.