Date post: | 05-Apr-2015 |
Category: |
Documents |
Upload: | ivo-anselmi |
View: | 109 times |
Download: | 0 times |
Ingo Rechenberg
PowerPoint-Folien zur 10. Vorlesung „Evolutionsstrategie I“
Evolutionsstrategie bei Störungen
Optimieren mit subjektiver Bewertung
(1 , )-ES
ES mit Störung
= 5
Ideale Funktion in der mathematischen Welt
Rauer Berg in der experimentellen Welt
Praxis
Qualitätsfunktion mit Rauschen
RQQ ~
Fehler
222
1
e21
)(R
R
R
Rw
+
w
R
Linearer Fortschritt für
Nach einer ziemlich aufwändigen Ableitung
,1,1~ h
22)( Ra
ah
Streuung- gesamteStreuung- mutative
h wird in der Biologie Fitness-Heritabilität genannt
R xaQ~
Q~
x
Beispiel: 10Mutationen durch vonStreuung Rauschen durch vonStreuung
aR
linlin ,1,1 1,0~
,1,1~ chc
,,~ chc ,,
~ chc !
,1,12,1 linlin)/(1
1~ chaR
Formale Erweiterung auf ( , ) - ES ?
,1~c
Fortschrittsbeiwerte bei Rauschen
h = 1 h = 1/10 h = 1/100
154,0~10,1 c
242,0~10,2 c
293,0~10,5 c
54,110,1 c
90,010,5 c
35,110,2 c
015,0~10,1 c
025,0~10,2 c
037,0~10,5 c
51,2100,1 c
16,2100,5 c
62,1100,20 c
251,0~100,1 c
635,0~100,5 c
773,0~100,20 c
025,0~100,1 c
095,0~100,5 c
206,0~100,20 c
100,1100,20~24,8~ cc
Das ist keine bloße statistische Mittelung
0457,0100120 h 072,062,10457,0~
100,20 c
für h = 1/100
Individuen-Dispersion einer ( , 10 ) - Evolutionsstrategie
klein
groß
Deutung der Robustheit der ( , ) - ES bei Störungen
Größere Q-Unterschiede,zuverlässigere Selektion
Nichtlineare Störungstheorie für die (1, )-ES
rnc2
~~2
,1,1 kug
rnc
aR2)/(1
1~2
,12,1 kug
0d
~d
2
opt
opt 2~
hh 24
,1
,1 2~
max
max hh
22
opt21 hha
R
Hilfsvariable
opt
opt~
opt
aR
max
max~
opt
aR
Optimale Mutationsstreuung am verrauschten Kugelmodell
Maximaler Fortschritt am verrauschten Kugelmodell
Stagnationsradius:
2opt
aRFür ist 0~
max
nrc ,1
,12Stagnation ca
nr R
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, ) - ES der
siehe Diagramm
Robustheit der ( / , ) - ES bei Störungen
Robustheit der ( , ) - ES bei Störungen
Min2
221
RxaxQn
kk
Deutung der Robustheit der ( , ) - ES bei Störungen
Die -fach vergrößerte Schrittweite lässt die Nachkommen besser aus dem Rauschen herausragen.
nrc
,/opt
Aus 0d
d ,/
nrc
2
2,/
max
rnc 2
2
,/,/
Für serielles Arbeiten mit der ( /, ) - ES gilt die Regel (s. Vorlesung ES II):
27,0opt
Multirekombination
NeueGeneration
Nachkommenrealisieren
FlexibleBleistreifen
Messungc ca w--
Nachkommenbewerten
Elterneingeben
Evolution eines Spreizflügels im Windkanal
Generation
0
9
1215
18
21
24
27
Evolution eines Spreizflügels im Windkanal
6
3
Selektionsansicht
Subjektiv gewählte (selektierte) Figur nachGeneration 0 Generation 20 Generation 40 Generation 80
Entwicklung eines Quadrats bei subjektiver Bewertung
Die x-y-Koordinaten der 6 Ecken der Figur werden mutiert
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 mitder Evolutionsstrategie
Elter25% Columbia
40% Sumatra
13% Java
5% Bahia
17% Jamaica
Nachkomme 120% Columbia
34% Sumatra
23% Java
5% Bahia
18% Jamaica
Nachkomme 223% Columbia
37% Sumatra
12% Java
10% Bahia
18% Jamaica
Nachkomme 325% Columbia
32% Sumatra
15% Java
8% Bahia
20% Jamaica
Nachkomme 430% Columbia
38% Sumatra
8% Java
2% Bahia
22% Jamaica
Nachkomme 533% Columbia
38% Sumatra
9% Java
8% Bahia
12% Jamaica
O 1
O 2
O 3
O 4
O 5
Subjektive Bewertung
E
N 3
Evolutionsstrategische Entwicklungeiner Marken-Kaffeemischung
M. Herdy
MimikrySchmeckt eklig
Schmeckt gut
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
Meilensteine in der Theorie der Evolutionsstrategie
12
3
4
1
Definition der Fortschrittsgeschwindigkeit
Zurückgelegter Weg berganZahl der Versuche
2
Gradienten Strategie kontra Evolutionsstrategie
Für n >> 1
nn
21)(
evonn )(
grad
1/ n
Evolutionsstrategie
1/n
Gradientenstrategie
Paul Guldin (1577 – 1643)
Guldinsche Regeln
3
Entdeckung des Evolutionsfensters
Kugelmodell
Korridormodell
10010-210-410-610-8
102 104 106 1080
0,4
0,3
0,2
0,1
*
*
Korridormodell Kugelmodell
4
Entwicklung der 1/5-Erfolgsregel
gggEN zxx
1gEx
)() (für gggENN QQ xxx
sonst gEx
vergrößern für We > 1 / 5
verkleinern für We < 1 / 5
gz auf die Länge 1 normiert
5
Elter
Erfolgs-gebiet
Versagen der 1/5-Erfolgsregel am spitzen Grat
Versagen der 1/5-Erfolgsregel an Unstetigkeiten
6Mehrgliedrige
Evolutionsstrategie
ES -),1(
= 6
7Vererbbarkeit der Mutabilität und Mutation der Mutabilität
Mutation
DNA-Kopierer
Hat Kopierer hergestellt
Knackpunkt der Evolutionsstrategie
? ? ?
8
ich bin Spitze
Idee der Mutativen Schrittweiten Regelung (MSR)
9Von der
ES-),1(
über die
ES-),(
zur
ES-),/(
10
Kugelmodell
E
r
.. .x x2 n
x1
a
q
a
a
Linien Fortschritt
Reduktion des vom Ziel wegführenden
Querschritts durch intermediäre Variablenmischung
q
Geometrisches Modell
11
Steigerung der optimalen Mutationsschrittweite um das -fache
Steigerung der maximalen Fortschrittsgeschwindigkeit um das -fache
ES-),/(
Allerdings nur für 12
n
12 ES-Optimierung mit subjektiver Bewertung
Rauschen der Qualitätsfunktion
Versagen der Mutativen Schrittweiten Regelung (MSR)
für eine ( 6/6, 12 ) - ES
Nachkommen mit vergrößerter Mutationsschrittweite:
50% auf der positiven Seite, 50% auf der negativen Seite.
Nachkommen mit verkeinerter Mutationsschrittweite:
50% auf der positiven Seite, 50% auf der negativen Seite.
E
!
Ansteigende Ebene
(kleine Schrittweite)
Auslese der 6 besten Nachkommen und Mittelung ihrer Schrittweiten ergibt die Schrittweitenänderung Null und nicht, wie es richtig wäre, eine -Vergrößerung.
Im Mittel
Ende
www.bionik.tu-berlin.de