Transcript BUGBUG: FORMAT SLIDE – BACKGROUND – PERHAPS TAKE

RAJ ASHAR
CAS/GRS COMPUTER SCIENCE
CS 591: ALGORITHMS FOR THE
NEW AGE
DECEMBER 9 , 2002
Instructor: Prof. Shang-Hua Teng
Evolutionary Algorithms
Opaque means to clearly-good solutions
Agenda
 Background
 General Evolutionary Algorithm (EA)
 Evolutionary Operators
 EA classes
 Ants Demo
Evolution from a CS Perspective:
Part I
 Population’s individuals compete for an environment’s
finite resources
 Genetic composition determines success
 Goal: Be a
 Survival: black-box objective function
 Environment dictates black-box’s inner workings
 Surprise: Evolution itself requires diversity
Evolution from a CS Perspective:
Part II
 NOT a purely-stochastic event
 1017 seconds to winnow through ~1019,500,000
possible genotypes
 Extremely unlikely that random search would
optimize survival functions
 Nature adapts, not optimizes, but …
 Optima do exist
 Nature’s success piques CS curiosity
Why Evolution?
 Process complements traditional search and
optimization techniques
 Copes well with noisy, inaccurate, incomplete
data
 Highly-parallelized
 Potentially multiple solutions to same problem
 Does not require in-depth problem knowledge
 Awesome proof of concept
Computation, Meet Evolution
 Evolutionary computation
 Evolutionary Algorithms (EAs)
EA Basics
 Seek high-”fitness” structures
 Each structure encoded as a chromosome
 Genes make up chromosome
 Each gene represents value for some parameter
EA Flowchart
General EA Pseudocode
 Generate [P(0)]
t=0
WHILE NOT Termination_Criterion [P(t)]
DO Evaluate [P(t)]
P' (t) = Select [P(t)]
P''(t) = ApplyReproductionOperators [P'(t)]
P(t+1) = Replace [P(t), P''(t)]
t = t + 1 END
RETURN Best_Solution
Evolutionary Operators
 Selection
 Recombination
 Mutation
 Reinsertion
Selection Operation
 Selection Idea:
 Compute each individual’s fitness level
 Rank-based methods only: weight each individual’s
reproduction probability by rank
 Select which individuals shall mate
 Several selection methods exist
 Concerns
 Maintain Population Diversity
 Improve Overall Fitness
 Spread
Tournament Selection
 For Nind iterations:
 Randomly choose Tour number of individuals
from the population for a group G.
 Select the objectively-fittest individual from G
for reproduction.
 Tour may range from [2, Nind]
 Generates “uniform at random offspring,”
 Attempts to mimic “stags rut to vie for the
privilege of mating with a herd of hinds.”
Truncation Selection
 Pick top Trunc percent of population to reproduce
 Produces uniform at random offspring
 Artificial selection method
Ranking Methods
 Compare individuals’ fitness
 Proportional fitness assignment
 Assigns each individual I ’s reproduction
probability proportionally to I ’s fitness, and
normalizes all probabilities to the unity
 Scales poorly
 Rank-based fitness assignment
 Sorts population according to individual fitness
 More robust than proportional fitness
assignment
Rank-Based Selection
 Pos = individual’s ranked position
 SP = selective pressure
 Two weighting formulae:
 Linear ranking: Fitness(Pos) = 2 - SP + 2·(SP - 1)·(Pos 1) / (Nind - 1)
 SP may assume a value in [1.0, 2.0].
 non-linear ranking: Fitness(Pos) = Nind·X(Pos - 1) /
Σ(X(i - 1)); i = 1:Nind
 X stands for the root of the polynomial
0 = (SP - 1)·X(Nind - 1) + SP·X(Nind - 2) + ... + SP·X + SP
Comparing Ranking Formulae
 Read right to left (position vs. fitness assignment)
 Nonlinear increases weight more quickly with
position
 Better for smaller populations
Roulette wheel selection
 Roulette wheel selection
 Map each individual to segments of a continuous line
“such that each individual's segment is equal in size to its
fitness” by rank
 Highest-ranked individual enjoys the largest line
segment
 Lowest-ranked individual occupies no line segment.
 MatingPopulation, the number of individuals to
reproduce:
 For MatingPopulation iterations:
 Generate a random number from independent sampling
and a uniform distribution.
 Select for reproduction “individual whose segment spans
the random number”.
Stochastic universal sampling
 Like Roulette wheel sampling, but differs slightly
 NPointer = number of individuals to select
 Place NPointer equally-spaced pointers over the line
 Each pointer at 1/NPointer distance from another pointer.
 Randomly generate number r within the range [0,
1/NPointer],
 Place first pointer at r and every pointer thereafter at
1/NPointer distance from the previous pointer
 Select for reproduction each individual whose line
segment receives a pointer.
 Zero bias and minimum spread
Recombination
 Two categories
 Real-valued recombination
 Binary recombination
 Discrete recombination algorithm
 Applies to both categories
 Exchanges gene values between individuals
parent 1
parent 2
mask 1
mask 2
12
123
25
4
5
34
2
1
2
2
1
1
offspring 1
offspring 2
123
12
4
4
5
5
Real-valued recombination
 Intermediate-value recombination
 Set offspring value according to
offspring = parent 1 + α(parent 2 - parent 1)
 α = scaling factor chosen uniformly at random
over an interval [-d, 1 + d]
 α differs for each gene
 d = 0.25 represents a good choice.
parent 1
12 25
5
parent 2 123
4 34
sample 1
0.5 1.1 -0.1
sample 2
0.1 0.8 0.5
offspring 1
offspring 2
67.5 1.9 2.1
23.1 8.2 19.5
Discrete recombination
 Single-point crossover
 Randomly choose a gene at which to juxtapose
two chromosomes
parent 1
parent 2
0 1 1 1 0 0 1 1 0 1 0
1 0 1 0 1 1 0 0 1 0 1
crossover position
5
offspring 1
offspring 2
0 1 1 1 0| 1 0 0 1 0 1
1 0 1 0 1| 0 1 1 0 1 0
Mutation
 Adds “small random values,” bounded by a
mutation step value, to randomly chosen
genes
 Probability of chromosomal mutation
inversely proportional to the number of
genes
 Again, two categories
 Real-valued recombination
 Binary recombination
Reinsertion
 Introducing offspring to population
 Questions
 Add all offspring, or just fittest offspring
 Replace all parents, least-fit parents, randomlychosen parents
 Two categories based on selection methods
 Local reinsertion
 Global reinsertion
Genetic Algorithms
 Fixed-size chromosome encodes parameter values
 Genetic operations and fitness measures improve
population
 At each iteration,
 GA evaluates fitness of each individual
 Creates new population by performing operations such
as crossover, fitness-proportionate reproduction and
mutation measured
 Replaces entirely the previous population with the
offspring.
 Useful in solving multidimensional optimization
problems
 Maximize low-orbit satellite Earth coverage
Genetic Programming
 Extends genetic learning to programming
 Population consists of variable-length programs
 Represented as parse trees
 When executed, solve the given problem
 Crossover involves exchanging random subtrees
 Mutation generally does not take place
 Already, “human competitive” results
 Among others, “Creation of a cellular automata rule for the majority
classification problem that is better than the Gacs-Kurdyumov-Levin
(GKL) rule and all other known rules written by humans”
Evolutionary Strategies
 Capable of solving high dimensional, multimodal, nonlinear
problems subject to linear and/or nonlinear constraints.
 Objective function can also be the result of a simulation, and does
not have to be given in a closed form.
 Two strategies:
 plus strategy: reinserts parents and children based on fitness. Plus
strategy departs from reality in theoretically allowing an individual
to remain within the population for perpetuity.
 comma strategy: perform only selection on the offspring, and replace
all parents with the selected offspring.
 Individual
 Object variables
 Strategy variables
 Requires knowledge of probability theory and applied
statistics
Evolutionary Programming
 Strategy for stochastic optimization
 No constraint on representation
 Perturbs offspring chromosomes during
reproduction
 Does not use crossover
 Degree of mutation depends on degree of
functional change imposed by parents
 Stochastic tournament to determine reinsertion
 Open questions?
 Complexity
 Why do these methods work?
Ants!
 Genetic algorithm
 Can alter parameters
 Proof of concept for systems?