Transcript cee6410GeneticAlgorithms_JHS

Genetic (Evolutionary)
Algorithms
CEE 6410
Guest : Jim Stagge
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 benefits and 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
Gene
Decision variable
Population
Set of alternatives
CEE 6410
Chromosome
Alternative (array of
decision variables)
Fitness
Objection function value
David Rosenberg
6
Trivial Example
• Max Z = f(x,y) = 2x + 1y
s.t.
x+y=5
• What is the most efficient way to get all one color?
CEE 6410
David Rosenberg
7
GA Solution Process
Selection
parents
stopping criteria
initiate &
evaluate
Population
evaluated offspring
Reproduction
modified
offspring
Evaluation
deleted
members
Discard
CEE 6410
David Rosenberg
8
1. Generate the Population
Population
• Encode decision variables
• Generate randomly within constraints
• Genes can represent :
–
–
–
–
–
Bit strings
Real numbers
Permutations of element
Lists of rules
... any data structure ...
CEE 6410
1 0 1 0 1 1 1 1 1
43.2 -33.1 6.5 ... 0.0 15.2
1 5 2 3 5 1 4 1
R1 R2 R3 ... R22 R23
David Rosenberg
9
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
10
3. Selection
parents
Selection
Population
• Select 2 parents from current population
• Selection based on fitness:
– Likelihood proportional to fitness value
f (i )
– Individual i will have a
probability to be chosen  f (i)
i
CEE 6410
3
4
2
1
David Rosenberg
11
4. Reproduction: 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)
pc : Probability of crossover (0 ≤ pc ≤ 1)
CEE 6410
David Rosenberg
12
4. Reproduction: Mutation Operator
Chromosome
Before
Mutation
Chromosome
After
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
...
...
pm : Probability of mutation (0 ≤ pm ≤ 1)
CEE 6410
David Rosenberg
13
5. Evaluate and Discard
modified offspring
evaluated offspring
Evaluation
deleted members
Discard
• Return to original population size
• Elitism operator - retain the fittest parent
individuals (alternatives) in the next generation
• Why?
CEE 6410
David Rosenberg
14
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
15
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
16
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
17
Ex 2. Which GA Simulation
Parameters are missing in Excel?
CEE 6410
David Rosenberg
18
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
19
GA Benefits
• Successful in large or complex search space
– Many decision variables
– Non-linear objectives
– Combinatorial problems (decision variables combined
effect)
• Robust
– Can handle local optima (mutation operator)
– Handles all types of decision variables, simulations
• Multi-objective versions
CEE 6410
David Rosenberg
20
GA Limitations
• Optimal solution not guaranteed (approximate
solution)
• Can be slow
• Population tradeoff, larger population increases:
– Likelihood to find optimal solution
– Computation effort
• Mutation tradeoff, higher mutation probability:
– Avoids getting stuck in a local optimum
– Increases the tendency for solutions to wander
• Parameter settings specific to the problem
CEE 6410
David Rosenberg
21
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
22