Ingo Rechenberg

PowerPoint-Folien zur 6. Vorlesung „Evolutionsstrategie I“

Handlungsregeln, die aus der

nichtlinearen Theorie der (1 + 1) - ES folgen

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

Normalverteilte Zufallszahlen zi für die Mutation der Variablen xi

zi

w2

22

1

e2

1)(

iz

izw

0

2

+

)(213 2

322

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

32

21 ddd)( zzzwzzzr PPt

R3

ntn zzzwzzzr PP ddd)( 2122

221

R

…

Für n Dimensionen

)()(

2

21

2 n

n

n für n >> 1

Zur Schwankung des Zufallsvektors

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

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

Ergebnisse der nichtlinearen Theorie

optn

b2n

r224,1

Suchbild der ES für n >> 1

sondern wegenn

b 2korr opt

nr224,1

kug opt

Nicht so

so

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

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

normiert 1 Länge die auf gz

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 >> 1 giltk

kn

k n202,0

202,0202,0

e202,01lim

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/

ggg zxx EN

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

1gEx

)() ( für gggENN xQxQx

sonst gEx{

1,5 für We > 1 / 5

normiert 1 Länge die auf gz

1,5 für We < 1 / 5

Nach jeweilsn Generationen

Computer-Versuche mit der 1/5-Erfolgsregel

ggg zxx EN

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

1gEx

)() ( für gggENN xQxQx

sonst gEx{

1,5 für We > 1 / 5

normiert 1 Länge die auf gz

1,5 für We < 1 / 5

Nach jeweilsn Generationen

ggg zxx EN

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

1gEx

)() ( für gggENN xQxQx

sonst gEx{

normiert 1 Länge die auf gz

1g { )() ( für3,1 gggEN xQxQ

sonst 4 3,1/ gMinimalform !

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

1

211

2Korr

n

b

1

211

2

n

bn

nn

bn

bn

n

n

nbn

2e1

12

1lim

bn

bn

bn

2

1

e2

1 *

Korr

21

** e2

1

Quasikonstante für opt

Korridormodell

e11lim

n

nn

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