Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
32 слайда
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
233.00 kB
Просмотров:
87
Скачиваний:
0
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Evolution strategies
Chapter 4
№2 слайд
Содержание слайда: ES quick overview
Developed: Germany in the 1970’s
Early names: I. Rechenberg, H.-P. Schwefel
Typically applied to:
numerical optimisation
Attributed features:
fast
good optimizer for real-valued optimisation
relatively much theory
Special:
self-adaptation of (mutation) parameters standard
№3 слайд
Содержание слайда: ES technical summary tableau
№4 слайд
Содержание слайда: Introductory example
Task: minimimise f : Rn R
Algorithm: “two-membered ES” using
Vectors from Rn directly as chromosomes
Population size 1
Only mutation creating one child
Greedy selection
№5 слайд
Содержание слайда: Introductory example: pseudocde
Set t = 0
Create initial point xt = x1t,…,xnt
REPEAT UNTIL (TERMIN.COND satisfied) DO
Draw zi from 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
№6 слайд
Содержание слайда: Introductory example: mutation mechanism
z values drawn from normal distribution N(,)
mean is set to 0
variation is called mutation step size
is varied on the fly by the “1/5 success rule”:
This rule resets after every k iterations by
= / c if ps > 1/5
= • c if ps < 1/5
= if ps = 1/5
where ps is the % of successful mutations, 0.8 c 1
№7 слайд
Содержание слайда: Illustration of normal distribution
№8 слайд
Содержание слайда: Another historical example:
the jet nozzle experiment
№9 слайд
Содержание слайда: Another historical example:
the jet nozzle experiment cont’d
№10 слайд
Содержание слайда: The famous jet nozzle experiment (movie)
№11 слайд
Содержание слайда: Genetic operators: mutations (2)
№12 слайд
Содержание слайда: Representation
Chromosomes consist of three parts:
Object variables: x1,…,xn
Strategy parameters:
Mutation step sizes: 1,…,n
Rotation angles: 1,…, n
Not every component is always present
Full size: x1,…,xn, 1,…,n ,1,…, k
where k = n(n-1)/2 (no. of i,j pairs)
№13 слайд
Содержание слайда: Mutation
Main mechanism: changing value by adding random noise drawn from normal distribution
x’i = xi + N(0,)
Key idea:
is part of the chromosome x1,…,xn,
is also mutated into ’ (see later how)
Thus: mutation step size is coevolving with the solution x
№14 слайд
Содержание слайда: Mutate first
Net mutation effect: x, x’, ’
Order is important:
first ’ (see later how)
then x x’ = x + N(0,’)
Rationale: new x’ ,’ is evaluated twice
Primary: x’ is good if f(x’) is good
Secondary: ’ is good if the x’ it created is good
Reversing mutation order this would not work
№15 слайд
Содержание слайда: Mutation case 1:
Uncorrelated mutation with one
Chromosomes: x1,…,xn,
’ = • exp( • N(0,1))
x’i = xi + ’ • N(0,1)
Typically the “learning rate” 1/ n½
And we have a boundary rule ’ < 0 ’ = 0
№16 слайд
Содержание слайда: Mutants with equal likelihood
Circle: mutants having the same chance to be created
№17 слайд
Содержание слайда: Mutation case 2:
Uncorrelated mutation with n ’s
Chromosomes: x1,…,xn, 1,…, n
’i = i • exp(’ • N(0,1) + • Ni (0,1))
x’i = xi + ’i • Ni (0,1)
Two learning rate parmeters:
’ overall learning rate
coordinate wise learning rate
1/(2 n)½ and 1/(2 n½) ½
And i’ < 0 i’ = 0
№18 слайд
Содержание слайда: Mutants with equal likelihood
Ellipse: mutants having the same chance to be created
№19 слайд
Содержание слайда: Mutation case 3:
Correlated mutations
Chromosomes: x1,…,xn, 1,…, n ,1,…, k
where k = n • (n-1)/2
and the covariance matrix C is defined as:
cii = i2
cij = 0 if i and j are not correlated
cij = ½ • ( i2 - j2 ) • tan(2 ij) if i and j are correlated
Note the numbering / indices of the ‘s
№20 слайд
Содержание слайда: Correlated mutations cont’d
The mutation mechanism is then:
’i = i • exp(’ • N(0,1) + • Ni (0,1))
’j = j + • N (0,1)
x ’ = x + N(0,C’)
x stands for the vector x1,…,xn
C’ is the covariance matrix C after mutation of the values
1/(2 n)½ and 1/(2 n½) ½ and 5°
i’ < 0 i’ = 0 and
| ’j | > ’j = ’j - 2 sign(’j)
№21 слайд
Содержание слайда: Mutants with equal likelihood
Ellipse: mutants having the same chance to be created
№22 слайд
Содержание слайда: 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 anew
№23 слайд
Содержание слайда: Names of recombinations
№24 слайд
Содержание слайда: 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)
№25 слайд
Содержание слайда: Survivor selection
Applied after creating children from the parents by mutation and recombination
Deterministically chops off the “bad stuff”
Basis of selection is either:
The set of children only: (,)-selection
The set of parents and children: (+)-selection
№26 слайд
Содержание слайда: Survivor selection cont’d
(+)-selection is an elitist strategy
(,)-selection can “forget”
Often (,)-selection is preferred for:
Better in leaving local optima
Better in following moving optima
Using the + strategy bad values can survive in x, too long if their host x is very fit
Selective pressure in ES is very high ( 7 • is the common setting)
№27 слайд
Содержание слайда: 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 !
№28 слайд
Содержание слайда: Self-adaptation illustrated cont’d
№29 слайд
Содержание слайда: Prerequisites for self-adaptation
> 1 to carry different strategies
> to generate offspring surplus
Not “too” strong selection, e.g., 7 •
(,)-selection to get rid of misadapted ‘s
Mixing strategy parameters by (intermediary) recombination on them
№30 слайд
Содержание слайда: Example application:
the cherry brandy experiment
Task to create a colour mix yielding a target colour (that of a well known cherry brandy)
Ingredients: water + red, yellow, blue dye
Representation: w, r, y ,b no self-adaptation!
Values scaled to give a predefined total volume (30 ml)
Mutation: lo / med / hi values used with equal chance
Selection: (1,8) strategy
№31 слайд
Содержание слайда: Example application:
cherry brandy experiment cont’d
Fitness: students effectively making the mix and comparing it with target colour
Termination criterion: student satisfied with mixed colour
Solution is found mostly within 20 generations
Accuracy is very good
№32 слайд
Содержание слайда: Example application:
the Ackley function (Bäck et al ’93)
The Ackley function (here used with n =30):
Evolution strategy:
Representation:
-30 < xi < 30 (coincidence of 30’s!)
30 step sizes
(30,200) selection
Termination : after 200000 fitness evaluations
Results: average best solution is 7.48 • 10 –8 (very good)