Ingo Rechenberg PowerPoint-Folien zur 5. Vorlesung „Evolutionsstrategie I“ Finale der Theorie...

transcript

Ingo Rechenberg

PowerPoint-Folien zur 5. Vorlesung „Evolutionsstrategie I“

Finale der Theorie der zweigliedrigen Evolutionsstrategie

Handlungsregeln als Ergebnis der nichtlinearen Theorie

gggEN zxx

Algorithmus der (1 + 1) – ES mit 1/5-Erfolgsregel

)() (für gggENN QQ xxx

sonst gEx

vergrößern für We > 1 /

5 verkleinern für We < 1 /

Für maximales

Mutationsschrittweite und Erfolgswahrscheinlichkeit

Erfolge

We ≈ 0,49 = 1: 2,04

We ≈ 0,16 = 1: 6,25

Höhenlinie

gggEN zxx

sonst gEx

gz auf die Länge 1 normiert

Wie normiert man einen Zufallsvektor auf die Länge 1 ?

Wir erwürfeln die Komponenten nzzz ,, 21

und bestimmen die Länge 222

21 nzzz

Wir dividieren durch und erhaltennzzz ,, 21

die normierten Zufallzahlen n

nzzzzzz ,, 2

Dann ist 1222

21 nzzz !

Frage: Wie groß ist für viele normalverteilte Zufallsszahlen nzzz ,, 21

Viele quadrierte Zufallszahlen addiert ergeben einen repräsentativen Mittelwert

Aber für n >> 1 geht es noch viel einfacher, zu 1 zu machen

Der Zufallsschritt wird mit wachsender Variablenzahl n immer länger

Normalverteilte Zufallszahlen zi für die Mutation der Variablen xi

e21)( iz

Wendepunkt der Kurve

Werden viele Zufallszahlen mit der

Wahrscheinlichkeitsdichte

addiert, ergibt sich der Mittelwert Null.

Werden diese Zufallszahlen aber

quadriert und aufsummiert, ergibt sich

ein Mittelwert größer als Null! Die

Wurzel daraus ist die Zufallsschrittweite.

)( izw

)(213 2

Die Trefferwahrscheinlichkeitsdichte

Ursprung der z-KoordinatenP

Zum radialen Strecken- Erwartungswert

21 ddd)( zzzwzzzr PPt

‚Ursprung der z-Koordinaten

ntn zzzwzzzr PP ddd)( 2122

Für n Dimensionen

n für n >> 1

Zur Schwankung der Länge

Um also werden zu lassen, müssen wir setzen 1 n1

gggEN zxx

sonst gEx

gz auf die Länge 1 normiert eiltnormalvert -1,0 / )( n

Achtung !

Die Normierung des Zufallsvektors auf die Länge 1 gilt nur für die Anwendung des ES-Algorithmus zur Lösung eines Optimierungsproblems.

In den Formeln der Theorie der ES bleibt die Größe, welche die Mutationsschrittweite symbolisiert.

Doch einmal ersetzen wir in unseren Formeln durch

882 erf12

Kugel8e

882erf1

lKuge8e

Wir nennen die Mutationsschrittweite

Bisherige Formeln

KugelKorr

Für <<1 folgt

Hurra, das kennen wir doch (Guldin)

Korridor Kugel

e nr202,0

nr224,1

opteW e21 270,0

Ergebnisse der nichtlinearen Theorie

Korridor Kugel

e nr202,0

nr224,1

opteW e21 270,0

Erweiterte Ergebnisse der nichtlinearen Theorie

r224,1

ES-Suchschlauch im Korridor

für n ≈ 400

bopt 8

140022

ES-Suchschlauch im Kugelmodell

für n ≈ 900

ropt 25

190022412241 ,,

Allgemeines Suchbild der ES für n >> 1

sondern wegenn

b 2korr opt

nr224,1

kug opt

Nicht so

Darwin lässt grüßen !Ließe sich das Vorhandensein eines zusammengesetzten Organs nachweisen, das nicht durch zahlreiche aufeinander folgende geringe Abänderungen entstehen könnte, so müsste meine Theorie zusammenbrechen.

gggEN zxx

Algorithmus der (1 + 1) - ES mit 1/5-Erfolgsregel

sonst gEx

5? Wie stark müssen

wir vergrößern bzw. verkleinern?

eiltnormalvert -1,0 / )( n

Zum Schrittweitenänderungsfaktor der (1 + 1) - ES

enGenerationder Zahl ungVerkleinerRadien

Kugel 1

)1()(Kugel

gg rrfür g =

Klettern mit max)(

max Kugel202,0 grn

)()1()( 202,01

g 202,01)()1(

)1()2(

)()2( 202,01

202,01)()(

Für n / 0,202 >> 1 gilt

n n2020

2020202020201 ,,, e,lim

nrr 202,0

e202,01

Die Schrittweiten müssen sich so ändern wie die Radien:

rr 202,0

Für k = 1 folgt 817,0202,0)(

Für optimales Fortschreiten ist also nach n Generationen um

817,022,111 k zu verkleinern. Bewährt hat sich = 1,3 –

→ Einstellregel5/1 eW für 5,1

5/1 eW für 5,1/

gggEN zxx

Algorithmus der (1 + 1) - ES mit 1/5-Erfolgsregel

sonst gEx

1,3 für We > 1 / 5 1,3 für We < 1 / 5

Nach jeweilsn Generationen

eiltnormalvert -1,0 / )( n

gggEN zxx

sonst gEx

1,5 für We > 1 / 5 1,5 für We < 1 / 5

Nach jeweilsn Generationen

eiltnormalvert -1,0 / )( ngz

gggEN zxx

sonst gEx

1g)() ( für3,1 ggg

EN xQxQ

sonst 4 3,1/ gMinimalform !

eiltnormalvert -1,0 / )( ngz

Die Schrittweite wird nach jeder Generation verändert

Idealisierter richtiger Ablauf einer (1+ 1)-ES-Optimierung

Schrittweitenänderung

3,1 4 3,1/ 4 3,1/ 4 3,1/ 4 3,1/ 3,1 4 3,1/

Erfolg Misserfolg Erfolg

Erfolgshäufigkeit ist richtig Keine Schrittweitenänderung !

Bei mehr Erfolgen wird mehr mit 1,3 multipliziert

Bei mehr Misserfolgen wird mehr mit durch dividiert4 3,1

Ein Minimalprogramm in MATLAB

zur Minimierung der Testfunktion „Kugelmodell“

v=100; d=1; xe=ones(v,1); qe=sum(xe.^2);

for g=1:1000 xn=xe+d*randn(v,1)/sqrt(v); qn=sum(xn.^2); if qn < qe qe=qn; xe=xn; d=d*1.3; else d=d/(1.3^0.25); end semilogy(g,qe,'b.') hold on; drawnow;end

Zurück zu den Fortschrittsformeln für das Korridor- und das Kugelmodell

882 erf12

Kugel8e

882**8** erf1

Kugel e

folgt und mit **rn

Kugelmodell

)( **lKuge f

2112Korr

Korr21

** e21

Quasikonstante ≈ 1, wenn mit opt vorangeschritten werden soll

Korridormodell

e11lim

, **bn

),( **Korr nf

)( **orrK f

1-e11lim

1e11lim/

für Korridormodell

Kugelmodell

Korridormodell

10010-210-410-610-8 102 104 106 1080

Fortschrittsfenster der (1 + 1) - Evolutionsstrategie

Evolutionsfenster

www.bionik.tu-berlin.de

Genau genommen ist das gezeigte Konvergenzbild nur richtig, wenn sich die Hyper-kugel in Richtung Startelter Kugelzentrum geringfügig zu einem Ellipsoid verformt. Bei einer exakten Kugel sind die Kugelschalen selektionsneutral. Ähnlich wie beim evolutionsstrategischen Beklettern einer ansteigenden Ebene eine Seitwärtsdrift eintritt, wird bei der exakten Kugel eine Umfangsdrift stattfinden. Der Suchschlauch wird sich also spiralförmig dem Kugelzentrum nähern.

Idee der Theorie:

Es ist das Kugelmodell, das eine besonders starke Anpassung der Mutationsschritt-weite erfordert. Die Schrittweite muss sich in dem Maße verkleinern, wie der Zielab-stand während des Fortschreitens abnimmt. Wir können die Verkleinerung des Ziel-abstands pro Generation in die mathematische Form (r

(g) – r

(g+1) ) /1 bringen. Diese

mittlere Zielabstandsverkleinerung soll nun den größten Wert annehmen; das heißt wir setzen sie gleich max. Wir wiederholen die Gleichsetzung für k·n Generations-schritte (k =1, 2, ...) Wir setzen am Ende der Rechnung willkürlich k = 1. Es bedeu-tet, dass die errechnete Schrittweitenverkleinerung erst nach n Generation ausge-führt werden darf.

Der Faktor (Schittweitenänderungsfaktor genannt) gibt an, mit welchen Wert größer als 1 die Mutationsschrittweite multipliziert werden muss, wenn die Erfolgswahrscheinlichkeit größer als 1/5 ist. Umgekehrt muss durch dividiert werden, wenn die Erfolgswahrscheinlichkeit kleinen als 1/5 ist.

Ingo Rechenberg PowerPoint-Folien zur 5. Vorlesung „Evolutionsstrategie I“ Finale der Theorie...

Documents