6. Vorlesung Evolutionsstrategie I

1/n

1/ n

Gradientenstrategie

kontra

Evolutionsstrategie

Der Dumme, der einfach losgeht, kommt weiter als der Schlaue, der sitzen bleibt und sich vor lauter Nachdenken nicht entscheiden kann.

Motto des Evolutionsstrategen

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

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

Kein zufälliges Stochern,

sondern gerichtete Diffusion

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

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

rn

rnr

n

882erf1

2

Kugel8e

882

**8** erf1

2*

Kugel e

folgt und mit **rn

rn

1

211

2Korr

n

b

1

211

2

n

bn

nn

bn

bn

n

n

nbn

2e

11

21lim

bn

bn

bn

2

1

e2

1 *

Korr

21

** e2

1

Quasikonstante für opt

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