In computer science, evolution strategy (ES) is an optimization technique based on ideas of adaptation and evolution. It belongs to the general class of evolutionary computation or artificial evolution methodologies.
The evolution strategy optimization technique was created in the early 1960s and developed further in the 1970s and later by Ingo Rechenberg, Hans-Paul Schwefel and his co-workers.
2. Key Points:
Typically applied to:
numerical optimisation
Attributed features:
fast
good optimizer for real-valued optimisation
relatively much theory
Special:
self-adaptation of (mutation) parameters standard
Representation
Real-valued vectors
Recombination
Discrete or intermediary
Mutation
Gaussian perturbation
Parent selection
Uniform random
Survivor selection
(m,l) or (m+l)
Specialty
Self-adaptation of mutation step sizes
3. Introductory Example:
Task: minimimise f : Rnà R
Algorithm: "two-membered ES” using
Vectors from Rndirectly as chromosomes
Population size 1
Only mutation creating one child
Greedy selection
Pseudocode:
Set t = 0
Create initial point xt= áx1t,…,xntñ
REPEAT UNTIL (TERMIN.COND satisfied) DO
Draw zifrom a normal distr. for all i = 1,…,n
yit= xit + zi
IF f(xt) < f(yt) THEN xt+1= xt
ELSE xt+1= yt
FI
Set t = t+1
OD
Mutation Mechanism:
z values drawn from normal distribution N(x,s)
mean x is set to 0
variation s is called mutation step size
s is varied on the fly by the "1/5 success rule”:
This rule resets s after every k iterations by
s = s / c if ps > 1/5
s = s • c if ps < 1/5
s = s if ps = 1/5
where ps is the % of successful mutations, 0.8 £ c £ 1
Illustration Of Normal Distribution:
4. Representation:
Chromosomes consist of three parts:
Object variables: x1,…,xn
Strategy parameters:
Mutation step sizes: s1,…,sns
Rotation angles: a1,…, ana
Not every component is always present
Full size: á x1,…,xn,s1,…,sn,a1,…, akñ
where k = n(n-1)/2 (no. of i,j pairs)
5. Mutation:
Main Mechanism: changing value by adding random noise drawn from normal distribution
x’i= xi+ N(0,s)
Key Idea:
s is part of the chromosome áx1,…,xn,sñ
s is also mutated into s’
Thus: mutation step sizes is co-evolving with the solution x
6. Recombination:
Creates one child
Acts per variable / position by either
Averaging parental values, or
Selecting one of the parental values
From two or more parents by either:
Using two selected parents to make a child
Selecting two parents for each position a new
Names Of Recombinations:
Two fixed parents
Two parents selected for each i
zi=(xi+ yi)/2
Local intermediary
Global intermediary
ziis xior yichosen randomly
Local
discrete
Global
discrete
7. Parent Selection:
Parents are selected by uniform random distribution whenever an operator needs one/some
Thus: ES parent selection is unbiased - every individual has the same probability to be selected
Note that in ES "parent” means a population member (in GA’s: a population member selected to undergo variation)
8. Survivor Selection:
Applied after creating p children from the m parents by mutation and recombination
Deterministically chops off the "bad stuff”
Basis of selection is either:
The set of children only: (m,p)-selection
The set of parents and children: (m+p)-selection
(m+p)-selection is an elitist strategy
(m,p)-selection can "forget”
Often (m,p)-selection is preferred for:
Better in leaving local optima
Better in following moving optima
Using the + strategy bad m values can survive in áx,mñ too long if their host x is very fit
Selective pressure in ES is very high (p » 7 • m is the common setting)
9. Self-Adaptation Illustrated:
Given a dynamically changing fitness landscape (optimum location shifted every 200 generations)
Self-adaptive ES is able to
follow the optimum and
adjust the mutation step size after every shift !
Prerequisites For Self-Adaptation:
m 1 to carry different strategies
p > m to generate offspring surplus
Not "too” strong selection, e.g., p » 7•m
(m,p)-selection to get rid of misadapted s‘s
Mixing strategy parameters by (intermediary) recombination on them
