Ingo Rechenberg
PowerPoint-Folien zur 10. Vorlesung „Evolutionsstrategie I“
Evolutionsstrategie bei Störungen
Optimieren mit subjektiver Bewertung
Weiterverwendung nur unter
Angabe der Quelle gestattet
(1 , l)-ES
l=5
ES mit Störung
Ideale Funktion in der
mathematischen Welt
Praxis
Rauer Berg in der
experimentellen Welt
Qualitätsfunktion mit Rauschen
~
Q  Q 
w ( ) 
Fehler

1
e
2 R
1
2
2R
2
w

+
~
Linearer Fortschritt für Q  a  x  
~
Nach einer ziemlich
aufwändigen Ableitung
~1,l  h  1,l
h
Q
x
a
( a )2   R2

mutative Q - Streuung
gesamte Q - Streuung
h wird in der Biologie Fitness-Heritabilität genannt
~1, l lin 
Beispiel:
1
  1, l lin  h  c1, l 
2
1  (R / a )
~
c1, l
R
Streuung von Q durch Rauschen

 10
a  Streuung von Q durch Mutationen
~1, l lin  0,1  1, l lin
~
c1, l  h  c1, l
Formale Erweiterung auf ( , l ) - ES
~
c , l  h  c , l
?
~
c , l  h  c , l
!
Fortschrittsbeiwerte bei Rauschen
h=1
h = 1/10
h = 1/100
c1, 10  1,54
c5, 10  0,90
~
c1, 10  0,154
~
c2,10  0,242
~
c
 0,293
~
c1, 10  0,015
~
c2,10  0,025
~
c
 0,037
c1, 100  2,51
~
c1, 100  0,251
c5, 100  2,16
~
c5,100  0,635
~
c20, 100  0,773
~
c1, 100  0,025
~
c5,100  0,095
~
c
 0,206
c2, 10  1,35
c20, 100  1,62
~
c20, 100  8,24  ~
c1,100
Das ist keine bloße
statistische Mittelung
5,10
5,10
20, 100
für h = 1/100
h  20  1  0,0457
100
~
c20, 100  0,0457 1,62  0,072
Deutung der Robustheit der (  , l ) - ES bei Störungen
 klein
 groß
Individuen-Dispersion einer (  , 10) - Evolutionsstrategie
Nichtlineare Störungstheorie für die (1, l)-ES
~
1, l kug
~
c1, l   n 
2r
2
2
n

1
c 
1, l kug 
2 1,l
2r
1  (R / a )
~
d~
 0
d
~opt
2

h
2

h
 opt


~1, l max
4
2

h
2

h
1, l max



R
2
2

1

h
2

h
a  opt

~opt
 opt
Optimale Mutationsstreuung
am verrauschten Kugelmodell
R
a  opt
Maximaler Fortschritt am
verrauschten Kugelmodell
~max
max
R
a  opt
Eine gestörte Optimierung kann nicht beliebig nahe an die
Lösung herankommen. Es bleibt ein Restzielabstand.
Für das Kugelmodell berechnet sich bei Anwendung einer (1, l ) - ES der
Stagnationsradius:
Für
R
a  opt  2
ist
c1, l r
n
rStagnation
n R

2 a c1, l
~max  0
siehe Diagramm
Robustheit der (  , l ) - ES bei Störungen
Robustheit der (  / , l ) - ES bei Störungen
Deutung der Robustheit der (  / , l ) - ES bei Störungen
/ , l
 opt
2
n

 c / , l   
2r
c / , l  r

n
Aus
d / , l
0
d
2
max
c / , l  r

2n
Für serielles Arbeiten mit der (  /, l ) - ES
gilt die Regel (s. Vorlesung ES II):
opt  0,27  l
Die  -fach vergrößerte Schrittweite lässt die Nachkommen
besser aus dem Rauschen herausragen.
Nachkommen
realisieren
ca - cw - Messung
Flexible
Bleistreifen
Neue
Generation
Eltern
eingeben
Nachkommen
bewerten
Evolution eines Spreizflügels im Windkanal
Generation
0
3
6
9
15
12
18
21
24
Evolution eines
Spreizflügels im Windkanal
27
Selektionsansicht
Entwicklung eines Quadrats
bei subjektiver Bewertung
Subjektiv gewählte (selektierte) Figur nach
Generation 0
Generation 20
Generation 40
Generation 80
Weiterentwicklung des Quadrats zum Mercedes-Stern
bei subjektiver Bewertung
Subjektiv gewählte (selektierte) Figur nach
Generation 1
Generation 20
Generation 40
Generation 60
Generation 80
Generation 100
Generation 200
Farbanpassung - Subjektive Bewertung
Subjektive Bewertung
Kaffee-Komposition mit
der Evolutionsstrategie
O1
25%
40%
13%
5%
17%
Nachkomme 1
Elter
Columbia
Sumatra
Java
Bahia
Jamaica
20%
34%
23%
5%
18%
E
N3
Subjektive
Bewertung
O2
Columbia
Nachkomme 2
O3
Sumatra
23% Columbia
Java
Nachkomme 3
O4
37% Sumatra
Bahia
25% Columbia
12% Java
Nachkomme 4
O5
Jamaica 32% Sumatra
10% Bahia
30% Columbia
15% Java
Nachkomme 5
18% Jamaica 38% Sumatra
8% Bahia
33% Columbia
8% Java
20% Jamaica 38% Sumatra
2% Bahia
9% Java
22% Jamaica
8% Bahia
12% Jamaica
M. Herdy
Evolutionsstrategische Entwicklung
einer Marken-Kaffeemischung
Schmeckt
eklig
Schmeckt
gut
Mimikry
Der Blauhäher frisst
einen Monarchen
Der bekommt dem
Vogel schlecht
Vor Übelkeit sträuben
sich die Federn
Heraus mit dem Gift
Vorüber, die Lehre
wird nicht vergessen
Subjektive Selektion in der Natur
1
2
3
4
Meilensteine in der Theorie der Evolutionsstrategie
1
Definition der Fortschrittsgeschwindigkeit 

Zurückgelegter Weg bergan
Zahl der Versuche
2
Gradienten Strategie kontra Evolutionsstrategie
Für n >> 1
Paul Guldin (1577 – 1643)
( n)
grad
 
n
1/n
Gradientenstrategie
(n)
evo

1


2 n
1/ n
Evolutionsstrategie
3
Entdeckung des Evolutionsfensters
Korridormodell
0,4
*
Korridormodell
0,3
0,2
Kugelmodell
0,1
0
-8
10
-6
10
-4
10
-2
10
0
10
2
10
4
10
*
6
10
8
10
Kugelmodell
4
Entwicklung der 1/5-Erfolgsregel
xNg  xEg   z g
zg
auf die Länge 1 normiert
g
g
g
x
für
Q
(
x
)

Q
(
x
N
N
E)
g 1
xE 
xEg sonst
 vergrößern für We > 1 / 5
 verkleinern für We < 1 / 5
5
Versagen der 1/5-Erfolgsregel am spitzen Grat
Versagen der 1/5-Erfolgsregel an Unstetigkeiten
Erfolgsgebiet
Elter
6
Mehrgliedrige
Evolutionsstrategie
(1, l ) - ES
l=6
7
Vererbbarkeit der Mutabilität und Mutation der Mutabilität
Knackpunkt der Evolutionsstrategie
DNA-Kopierer
8
Idee der Mutativen Schrittweiten Regelung (MSR)
ich bin Spitze
? ? ?
9
Von der
(1, l ) - ES
über die
(  , l ) - ES
zur
(  / , l ) - ES
10
Reduktion des vom Ziel wegführenden
Querschritts durch intermediäre Variablenmischung
x1
Geometrisches Modell
Kugelmodell
r
E
Linien Fortschritt
x2 ... xn
a
q
q
11
(  / , l ) - ES
Steigerung der optimalen Mutationsschrittweite um das  -fache
Steigerung der maximalen Fortschrittsgeschwindigkeit um das  -fache
Allerdings nur für

2 n
 1
12
ES-Optimierung mit subjektiver Bewertung
Rauschen der
Qualitätsfunktion
E
Im Mittel
Nachkommen mit vergrößerter
Mutationsschrittweite:
50% auf der positiven Seite,
50% auf der negativen Seite.
Ansteigende Ebene
Nachkommen mit verkeinerter
Mutationsschrittweite:
(kleine Schrittweite)
50% auf der positiven Seite,
50% auf der negativen Seite.
Auslese der 6 besten Nachkommen und
Mittelung ihrer Schrittweiten ergibt die
Schrittweitenänderung Null und nicht, wie
es richtig wäre, eine  -Vergrößerung.
!
Versagen der Mutativen Schrittweiten Regelung (MSR)
für eine (6/6, 12) - ES
Ende

E1-05Fo10 - Bionik TU