Ingo Rechenberg

PowerPoint-Folien zur 5. Vorlesung „Evolutionsstrategie I“

Finale der Theorie der zweigliedrigen Evolutionsstrategie

Handlungsregeln als Ergebnis der nichtlinearen Theorie

Weiterverwendung nur unter Angabe der Quelle gestattet

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

Für maximales

Mutationsschrittweite und

Erfolgswahrscheinlichkeit

Erfolge

Erfolge

We ≈ 0,49 = 1: 2,04

We ≈ 0,16 = 1: 6,25

Höhenlinie

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

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änge22

221 nzzz

Wir dividieren durch und erhaltennzzz ,, 21

die normierten Zufallzahlen n

nz

zz

zz

z ,, 221

1

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

Normalverteilte Zufallszahlen zi für die Mutation der Variablen xi

zi

w2

22

1

e2

1)(

iz

izw

0

2

+

Wendepunkt der Kurve

)(2

13 23

22

212

e21)(

zzz

t PPw

P

P

Die Trefferwahrscheinlichkeitsdichte

Ursprung der z-KoordinatenP

P

P

P

P

P

P

‚

r

PP

Zum radialen Strecken- Erwartungswert

P

P

32123

22

21 ddd)( zzzwzzzr PPt

R3

‚Ursprung der z-Koordinaten

ntn zzzwzzzr PP ddd)( 2122

221

R

…

Für n Dimensionen

)()(

2

21

2 n

n

n für n >> 1

Zur Schwankung der Länge

2lim

2

21

nn

n

n

)()(

1

211

2Korr

n

b

rn

rnr

n

882erf1

2

Kugel8e

1

211

2Korr

n

bnn

rn

rn

nrn

882erf1

2

lKuge

8e

nn

n Wir nennen die

Mutationsschrittweite

Bisherige Formeln

Korridor Kugel

nb

e nr202,0

nb2

nr224,1

max

opt

opteWe2

1 270,0

Ergebnisse der nichtlinearen Theorie

Korridor Kugel

nb

e nr202,0

nb2

nr224,1

max

opt

opteW e21

270,0

Erweiterte Ergebnisse der nichtlinearen Theorie

optn

b2n

r224,1

ES-Suchschlauch im Korridor

für n ≈ 400

81

40022

nbopt

2 b

ES-Suchschlauch im Kugelmodell

für n ≈ 900

251

900224,1224,1

nropt

r

Text

Allgemeines Suchbild der ES für n >> 1

sondern wegenn

b 2korr opt

nr224,1

kug opt

Nicht so

so

gggEN zxx

Algorithmus der (1 + 1) - ES

1gEx

)() (für gggENN QQ xxx

sonst gEx

gz Im Mittel auf die Länge 1 normiert

Wir dividieren alle mit = 1 erzeugten n Zufallszahlen durch n

Dann ist nach der Formel n 111 nn

gggEN zxx

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

1gEx

)() (für gggENN QQ xxx

sonst gEx

gz Im Mittel auf die Länge 1 normiert

vergrößern für We > 1 /

5 verkleinern für We < 1 /

5

?Wie stark müssen wir vergrößern bzw. verkleinern?

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

enGeneration der ZahlungVerkleinerRadien

Kugel

1

)1()(

Kugel

gg rrfür g =

1

Klettern mit max)(

max Kugel202,0 grn

)()1()( 202,0

1g

ggr

nrr

nrr

g

g 202,01)(

)1(

2

)(

)1(

)1(

)2(

)(

)2( 202,01

nrr

rr

rr

g

g

g

g

g

g

nk

g

nkg

nrr

202,01)(

)(

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

kkn

k n202,0

202,0202,0

e202,01lim

Text

knk

g

nkg

nrr 202,0

)(

)(e202,01

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

kg

nkg

g

nkg

rr 202,0

)(

)(

)(

)(e

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

)1(e

g

ng

Für optimales Fortschreiten ist also nach n Generationen um

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

1,5.

→ 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

1gEx

)() (für gggENN QQ xxx

sonst gEx

gz Im Mittel auf die Länge 1 normiert

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

Nach jeweilsn Generationen

gggEN zxx

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

1gEx

)() (für gggENN QQ xxx

sonst gEx

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

Nach jeweilsn Generationen

gz Im Mittel auf die Länge 1 normiert

gggEN zxx

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

1gEx

)() (für gggENN QQ xxx

sonst gEx

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

EN xQxQ

sonst 4 3,1/ gMinimalform !

gz Im Mittel auf die Länge 1 normiert

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 !

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

rn

rnr

n

882erf1

2

Kugel8e

882

**8** erf1

2*

Kugel e

folgt und mit **rn

rn

Kugelmodell

)( **lKuge f

1

211

2Korr

n

b

1

211

2

n

bn

nbn

bn

bn

n

n

nbn

2e1

12

1lim

bn

bn

bn

2

1

e2

1 *

Korr

21

** e2

1

Quasikonstante, wenn mit opt

vorangeschritten werden soll

Korridormodell

e11lim

n

n n

, **bn

bn

),( **Korr nf

)( **orrK f

1-e11lim

n

n n

a-n

an na

1e11lim/

Kugelmodell

Korridormodell

10010-210-410-610-8

102 104 106 1080

0,4

0,3

0,2

0,1

*

*

Fortschrittsfenster der (1 + 1) - Evolutionsstrategie

Evolutionsfenster

Ende

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 ein 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.