Transcript cee6410GeneticAlgorithms

Genetic (Evolutionary)
Algorithms
CEE 6410
David Rosenberg
“Natural Selection or the Survival of the
Fittest.”
-- Charles Darwin
Learning Objectives
• Map concepts from evolutionary
biology to genetic algorithms (GAs)
• Identify parameters for running a GA
• Use a GA to solve an optimization
problem
• List limitations
CEE 6410
David Rosenberg
2
Biology - A Brief Review
Genotype
(genetic make-up)
Phenotype
(physical characteristics)
blue eyes
gene for
eye color
brown hair
gene for
hair color
{
...
chromosome
(a collection of genes)
CEE 6410
David Rosenberg
3
Darwin’s Theory of Evolution
• Genetic makeup determines an
individual’s physical characteristics
• The environment acts on individuals
to determine an individual’s
– Suitability to survive
– Likelihood to reproduce
• Individuals more fit to survive in a
particular environment:
– Pass more genetic material to their
offspring
– Their offspring are better fit to survive
CEE 6410
David Rosenberg
4
Which of the following statements comes
closest to your views on the origin and
development of human beings?
CEE 6410
David Rosenberg
5
Map Concepts
Biology
Genetic
Algorithms
Systems Analysis
Gene – sequence of nucleotides
on a DNA strand
Gene
Decision variable
value
Chromosome – group of genes
on a single strand of DNA
Chromosome
Array of decision
variables
Individual – collection of
chromosomes
Chromosome /
Individual
Alternative – array of
decision variables
Population – collection of
individuals
Population
A set of alternatives
Fitness function
Objective function
value
Fitness
CEE 6410
David Rosenberg
6
GA Solution Process
1. Generate the initial population (e.g., random)
2. Evaluate fitness of each individual
3. Test for completion
– Are our stop criteria met?
4. Generate new population (use genetic operators)
5. Return to Step #2
CEE 6410
David Rosenberg
7
1. Generate the Population
1 0 0 1 0 1 1 0 1 0 0 ...
"Binary Encoding": every chromosome
is a string of bits (i.e., either 0 or 1).
6 1 4 9 3 0 5 2 7 8 1 ...
"Permuatation Encoding": every
chromosome is a string of numbers,
each of which is a number in a
sequence.
3.145 6.259 1.476 2.847 ...
+
"Tree Encoding": every chromosome
is a tree of objects, such as functions
or commands in a programming
language.
Enter
*
CEE 6410
"Value Encoding": every chromosome
is a sequence of values.
5
%
David Rosenberg
8
2. Evaluate Fitness
"Chromosome" = set of
decision variable values, e.g.:
}
}
...
CEE 6410
}
Reservoir operating
rule parameter values
Pumping rates on
wells
others
"Fitness" is evaluated for an individual
by putting the values of the "genes" into
a simulation model to see, for example:
• how the water resources system
will behave
• what will be the total costs and
benefits that result
e.g., "fitness" = objective function value
= benefits - costs
David Rosenberg
9
3. Test for Completion
• Maximum number of iterations (generations)
reached?
• Maximum execution time reached (e.g., Excel)?
• Convergence criteria reach (e.g., in Excel,
difference in fitness between the 1st and 99th
percentile individuals)
CEE 6410
David Rosenberg
10
3. Genetic operators to generate a
new population
• Selection
– Select 2 parent individuals from current population
– Randomly select parents by their fitness
• Crossover
– Use genes from one or the other of the parents
• Mutation
– Make a random (small) change in a gene value
• Elitism
– Retain the fittest parent individuals (alternatives) in the
next generation
CEE 6410
David Rosenberg
11
The Crossover Operator
Parent A:
(3.712)
(4.681)
(0.973)
(7.818)
(6.579)
cross over point (randomly selected)
Parent B:
(8.040)
(6.721)
(5.619)
(0.011)
(2.038)
Offspring:
(3.712)
(4.681)
(0.973)
(0.011)
(2.038)
CEE 6410
David Rosenberg
12
The Mutation Operator
Chromosome
Before
Mutation
1.29
no mutation
1.29
5.68
no mutation
5.68
2.86
mutation
2.73
4.11
mutation
4.22
5.55
no mutation
5.55
...
CEE 6410
Chromosome
After
Mutation
...
David Rosenberg
13
The Elitism Operator
Parent
Population
:
CEE 6410
Fitness
Rank
Next
Generation
1
Retain
2
Retain
3
Retain
4
Retain
5
Retain
6
New
7
New
:
New
n
New
:
Selection,
crossover,
&
mutation
David Rosenberg
14
Key GA Simulation
Parameters
Symbol Description
n
Population size (#)
pc
Probability of crossover (0 ≤ pc ≤ 1)
pm
Gmax
E
CEE 6410
Probability of mutation (0 ≤ pm ≤ 1)
Maximum number of generations
Number of elite individuals
David Rosenberg
15
Ex 1. Solve the nonlinear optimization
problem with a GA
• Max Z = f(x,y) = 1000 – [(x-1)2 + (y-1)2]
• s.t.
-10 ≤ x ≤ 10
-10 ≤ y ≤ 10
• With
n = 100
pm = 0.05
Gmax = 100
pc, E = as appropriate
• Hint: Use the Evolutionary Solve method in Excel
CEE 6410
David Rosenberg
16
Ex 2. Which GA Simulation
Parameters are missing in Excel?
CEE 6410
David Rosenberg
17
GA Solution Convergence (McKee)
Example of GA Converge nce
1050
1000
Fitness
950
Minimum
Mean
Maximum
900
850
800
0
CEE 6410
25
50
Generation
75
100
David Rosenberg
18
GA Limitations
• Optimal solution not guaranteed
• Larger population increases
– Likelihood to find optimal solution
– Computation effort
• Higher mutation probability
– Avoids getting stuck in a local optimum
– Increases the tendency for solutions to wander
• Parameter settings are specific to the problem
structure
CEE 6410
David Rosenberg
19
Conclusions
• Genetic algorithms provide a flexible tool to solve
complex optimization problems
• Can embed simulation models
• Parameter settings are specific to the problem
structure
• Lots of public-domain and commercial software
available
CEE 6410
David Rosenberg
20