Post on 05-Apr-2015
transcript
Ingo Rechenberg
PowerPoint-Folien zur 5. Vorlesung „Evolutionsstrategie I“
Korridormodell, Kugelmodell und die 1/5 - Erfolgsregel
Folgen eines zum Gipfel ausgerollten Ariadnefadens
Vernünftige Strategien folgen Wegen zum Optimum
zurückgelegter WegZahl der Nachkommen
ggg zxx EN
Algorithmus der (1 + 1) - ES
1gEx
)() ( für gggENN xQxx Q
sonst gEx{
nn 1
2)(
evo
E nde der L inearität G loba le stochastische Suche
evo
Suche nach dem maximalen Fortschritt
Wo ist das Optimum ???
Nichtlineare Modelle
Weitab vom Optimum
Nahe am Optimum
Parabelgrat
Kreiskuppe
Modellfunktion Rechteckgrat (Korridormodell)
2-dimensional 3-dimensional
Q steigt longitudinal monoton an
Modellfunktion Kreiskuppe (Kugelmodell)
2-dimensional 3-dimensional
Q steigt radial monoton an
)(213 2
322
212
e21)(
zzz
t PPw
P
P
Zur Trefferwahrscheinlichkeitsdichte
Ursprung der z-KoordinatenP
P
P
P
P
P
P
R+
Ry1
y2,...n
P '
Lokaler Fortschritt der (1 + 1)-ES am Korridormodell
3
P
3
2erf
2erf
21
2erf
2erf
21
222 nn ybybybyb
n
R
t yywyy PP dd 111 )()(
…
122/e1
212erf
22)(
Korr
n
b
bb
y1y2,...n
2b
122/e1
212erf
22)(
Korr
n
b
bb
Mitueu
u2
11)(erf
für u
>>1
folgt
1
211
2Korr
n
b
1
211
2Korr
n
b
Wir suchen das Maximum von
durch Nullsetzen der 1. Ableitung: 0dd
nb 2opt
nbe
max!
Wir erinnern uns:
zurückgelegter Weg
Zahl der Nachkommen
Wir konstruieren ein zweites Konvergenzmaß
erfolgreiche Nachkommen
Gesamtzahl der NachkommenWe
We nennen wir die Erfolgswahrscheinlichkeit
n
R
t yywyy PP dd 111 )()(
…
Es galt:
n
R
t yyw PPW dd 1)(1e
…
Wir setzen die Fortschrittsbewertung = 1
bW
211
21
e für / b << 1
11opt 11
21
211
21 e
nn
nbW
opt
e21 e W opt ( = 1 :
5,4 )für n >> 1
ggg zxx EN
Algorithmus der (1 + 1) – ES mit Erfolgsregel
1gEx
)() ( für gggENN xQxx Q
sonst gEx{
vergrößern für We > 1 /
2e verkleinern für We < 1 /
2e
!
Korridormodell und optimale
Mutationsschrittweite
Modellfunktion Kreiskuppe (Kugelmodell)
2-dimensional 3-dimensional
Q steigt monoton an
y2,...n
1y
P’
R+
PP
P
Fortschrittsbewertung am Kugelmodell
zurückgelegter Weg als RadiendifferenzZahl der NachkommenKugel
n
R
tn yywyyyr PP dd 122
221 )()(Kugel
…
zurückgelegter Weg als RadiendifferenzZahl der NachkommenKugel
rn
rnr
n
882erf1
2
Kugel8e
rnW8
erf121
Kugele 1 für r
n
Korridor Kugel
nb
e nr202,0
nb2
nr224,1
max
opt
opteWe21 270,0
Ergebnisse der nichtlinearen Theorie
0
0,1
0,2
0,3
0,4
0 0,1 0,2 0,3 0,4 0,5W e
* Korridorm odell
Kugelm odell
(1 + 1) - Evolutionsstrategie: 1 / 5 - Erfolgsregel
1/6 1/5 1/4
ggg zxx EN
Algorithmus der (1 + 1) – ES mit 1/5-Erfolgsregel
1gEx
)() ( für gggENN xQxQx
sonst gEx{
vergrößern für We > 1 /
5 verkleinern für We < 1 /
5
normiert 1 Länge die auf gz
Zur 1/5-Erfolgsregel
Der Futurologe Stanislaw Lem schrieb in einem Essay im Spiegel:
Die Menschheit hat bis jetzt 10 hoch 15 Bits an Information gespeichert. Bis zum Jahr 2000 wird sich die Menge etwa verdoppeln. Dabei gilt für die Infosintflut Folgendes: Etwa drei Fünftel sind Unsinn und vermischter Unsinn; den ich „Trübkunde“ nenne; ein Fünftel ist zwar sinnvoll, aber vergängliche Info, und kaum ein Fünftel besteht aus ernsten Denkfrüchten. Sogar die Forschungsanstalten werden in der Flut versinken, weil sie nicht Information, sondern Selektion benötigen, um weiter agieren zu können.
Ende