Post on 05-Apr-2015
transcript
Ingo Rechenberg
PowerPoint-Folien zur 4. Vorlesung „Evolutionsstrategie I“
Auf dem Weg zu einer nichtlinearen Theorie
Korridormodell, Kugelmodell und die 1/5 - Erfolgsregel
Weiterverwendung nur unter Angabe der Quelle gestattet
Suchstrategie: Konstruktion einer additiven Einbahnstraße zum Optimum
10 klassische Optimierungsstrategien
1. Gauß-Seidel-Strategie
2. Strategie von Hooke und Jeeves
3. Rosenbrock-Strategie
4. Strategie von Davis, Swann und Campey (DSC)
5. Simplex-Strategie von Nelder/Mead
6. Complex-Strategie von Box
7. Powell-Strategie
8. Newton-Strategie
9. Strategie von Steward
10. Strategie von Davidon, Fletcher und Powell (DFP)
Aktuell: SQP-Verfahren
(Sequential Quadradic Approximation)
x1
x2
x3
Elementare Gradientenstrategie
… Nach dem Arbeitschritt wird durch Testmessungen erneut die Richtung des steilsten Anstiegs ermittelt. In diese Richtung wird wie-derum mit der Arbeitsschritt-weite vorangegangen.
x1
x2
x3
Extrapolierende Gradientenstrategie
Nachdem die Richtung steils-ten Anstiegs ermittelt wurde wird solange mit der Arbeits-schrittweite in diese Richtung vorangeschritten, bis die Qualität sich verschlechtert. Dort wird erneut die Richtung des steilsten Anstiegs durch Testsmessungen ermittelt.
x1
x2
x3
Gauß-Seidel- oder Koordinatenstrategie
Es wird in die 1. Koordina-tenrichtung solange mit der Arbeitsschrittweite fortge-schritten, bis sich die Qua-lität verschlechtert. Dann wird die Prozedur in der 2. Koordinatenrichtung fortge-setzt usw.
x1
x2
x3
Simplex-Strategie von Nelder/Mead
12
3
4
5
6
7 Konstruktion eines gleich-seitigen Tetraeders im Variablenraum. Der Punkt niedrigster Qualität wird gestrichen. An der verblei-benden Grundfläche wird die Spitze eines neuen Tetraeders gespiegelt.
Folgen eines zum Gipfel ausgerollten Ariadnefadens
Vernünftige Strategien folgen Wegen zum Optimum
Text
100 Lose auf den Feldern der Ebene ausgelegt
Gewinn
Es gibt keinen Weg zum Gewinn, dem man folgen kann !!!
Lotterielose
0 9
9
0
zurückgelegter WegZahl der Mutationen
gggEN zxx
Algorithmus der (1 + 1) - ES
1gEx
)() (für gggENN QQ xxx
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
Einkreisen des Optimums
Voranschreiten zum Optimum
Modellfunktion Rechteckgrat (Korridormodell)
2-dimensional 3-dimensional
Q steigt longitudinal monoton an
Modellfunktion Kreiskuppe (Kugelmodell)
2-dimensional 3-dimensional
Q steigt radial monoton an
)(2
13 23
22
212
e21)(
zzz
t PPw
P
P
Zur Trefferwahrscheinlichkeitsdichte
Ursprung der z-KoordinatenP
P
P
P
P
P
P
′
Text
Gauss- oder Normalverteilung = Maß für die Länge der Mutationsschritte
Normalverteilte Zufallszahlen zi für die Mutation der Variablen xi
zi
w2
22
1
e2
1)(
iz
izw
0
2
+
Wendepunkt der Kurve
R+
Ry1
y2,...n
P '
Lokaler Fortschritt der (1 + 1)-ES am Korridormodell
6
P
Text
6
2
erf2
erf21
2erf
2erf
21
222 nn ybybybyb
n
R
t yywyy PP dd 111 )()(
…
Lange elementare Zwischenrechnung
Text
2
erf2
erf21
2erf
2erf
21
222 nn ybybybyb
Der örtliche Fortschritt im Korridor ist von der Lage des Punktes P ′ abhängig. Im Zentrum ist der Fortschritt groß, in den Ecken dagegen sehr klein. Wir müssen den Fortschritt über den Korridorquerschnitt mitteln:
b
by
n
b
by
ydyd22
2
Die lineare Mittelung ist erlaubt, weil - während des evolutiven Fortschreitens im Korridor - jede Position im Korridorquerschnitt (in der Mitte, am Rand und in der Ecke) die gleiche Aufenthaltshäufigkeit besitzt (Simulation oder lange Rechnung).
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
Dies gilt für n >> 1, wie sich später zeigen wird
n
b
211
2Korr
Wir suchen das Maximum von
durch Nullsetzen der 1. Ableitung: 0dd
nb 2opt
nbe
max!
für n >> 1
Wir erinnern uns:
zurückgelegter Weg
Zahl der Mutationen
Wir konstruieren ein zweites Konvergenzmaß
erfolgreiche Mutationen
Gesamtzahl der MutationenWe
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
1
211
21
e
n
bW für / b << 1
11opt 11
21
211
21 e
nn
nbW
opt
e21 e W opt ( = 1 :
5,4 )für n >> 1
Lange elementare Zwischenrechnung Bekannter
Grenzwert e11lim
n
nn)(
gggEN zxx
Algorithmus der (1 + 1) – ES mit Erfolgsregel
1gEx
)() (für gggENN QQ xxx
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 MutationenKugel
n
R
tn yywyyyr PP dd 122
221 )()(Kugel
…
zurückgelegter Weg als Radiendifferenz
Zahl der MutationenKugel
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
gggEN zxx
Algorithmus der (1 + 1) – ES mit 1/5-Erfolgsregel
1gEx
)() (für gggENN QQ xxx
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
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 Denk-früchten. Sogar die Forschungsanstalten werden in der Flut versinken, weil sie nicht Information, sondern Selektion benötigen, um weiter agieren zu können.
Der Futurologe Stanislaw Lem schrieb in einem Essay im Spiegel:
Ende
www.bionik.tu-berlin.de
Der Minotaurus, ein mischgestaltiges Wesen (halb Mensch, halb Stier) haust in einem Labyrinth, das Dädalus im Auftrag des kretischen Königs Minos in Knossos erbaut hat. Sieben Jungen und sieben Mädchen mussten jährlich dem Minotaurus geopfert werden. Da beschließt der athenische Held Theseus, dem Minotaurus ein Ende zu bereiten. In Knossos auf Kreta ange-kommen verliebt er sich in Ariadne, der Tochter des Königs Minos. Bevor Theseus in das Labyrinth eindringt gib Ariadne ihm auf Anraten von Dädalus ein Garnknäuel. Theseus bindet ein Ende des Fadens an das bronzene Gitter des Eingangstores. Nach langem Umherirren im Labyrinth - das Garnknäuel hinter sich abwickelnd - stößt Theseus auf den Minotaurus und erschlägt ihn in einem fürchterlichen Kampf. Mit Hilfe des ausgerollten roten Fadens der Ariadne findet Theseus problemlos den Weg in die Freiheit zurück.
Auf diesen „Ariadnefaden“ geht unser Wort „Leitfaden“ zurück.
Zur Wahrscheinlichkeitsrechnung
Diskrete Wahrscheinlichkeit:
Die Wahrscheinlichkeit eine 4 zu würfeln ist gleich 1/6.
Die Wahrscheinlichkeit eine 4 oder eine 5 zu würfeln ist gleich 1/6 1/6 = 2/6.
Die Wahrscheinlichkeit eine 3 und nochmals eine 3 zu würfeln ist gleich 1/6 1/6 = 1/36.
Kontinuierliche Wahrscheinlichkeit:
Mit dem Befehl ran in Basic wird eine Zufallszahl zwischen 0 und 1 aufgerufen. Die Wahr-scheinlichkeit genau 0,60000… (mit unendlich vielen Nullen) aufzurufen ist = 0. Sinnvoll ist nur die Frage nach der Wahrscheinlichkeit, einen Wert zwischen 0,59000… und 0,61000… zu erwürfeln.
Der Wert (hier 0,02) dividiert durch das gesamte Intervall (hier gerade = 1) ergibt die Wahrscheinlichleitsdichte.
Die Wahrscheinlichkeitsdichte w ist also ein abstrakter Zahlenwert, der mit dem Linien-, Flächen- oder Volumenelement multipliziert die reale Wahrscheinlichkeit angibt, diesen Linien-, Flächen- oder Volumenbereich zu treffen.
Wir gehen alle Punkte (hier der Ebene) durch, multiplizieren den Fortschrittspfeil (falls vor-handen) mit der Trefferwahrscheinlichkeitsdichte und addieren alle positiven Pfeillängen zusammen. Da wir mit der Wahrscheinlichkeitsdichte operieren, erübrigt sich die Division durch die Zahl der aufgesuchten Punkte, die ja Unendlich wäre.
Die Summation der unendlich vielen differentiellen Punktmultiplikationen führt zu einem Inte-gral, das im Fall von n Dimensionen ein n-dimensionales Raumintegral ist. Da positive Pfeile nur im Erfolgsgebiet R+ auftreten, erstrecken wir das Raumintegral nur über den R+-Bereich.
Die Funktion erf(x) heißt Fehlerfunktion (error function). Erf(x) ist nicht anders zu behandeln als ein Sinus, Cosinus oder Tangenshyperbolikus. Will sagen, dass der Wert für ein gegebenes Argument x aus einer Tabelle abgelesen werden muss.
Erf(x) ist definiert als das Integral
xz dzex
0
22)(erf
und hat den grafischen Verlauf
-2 -1 1 20
-1
1
x
erf( )x