Ingo Rechenberg

PowerPoint-Folien zur 8. Vorlesung „Evolutionsstrategie I“

Von der (1 + 1) - ES mit 1/5-Erfolgsregel zur

(1, ) - ES mit mutativer Schrittweitenregelung

ggg zxx EN

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

in der originalen Form

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

Versagen der 1/5-Erfolgsregel

am spitzen Grat

Elter

kleiner als 1/5 Kreisumfang

We < 1/5

We > 1/5We < 1/5

Mutationen

Biologisch unmöglich

Kosmische Strahlung

Wenn ich mich nicht an meinem eigenen Schopfe herausgezogen hätte.

Baron von Münchhausen

Basis-Algorithmus der (1, ) - Evolutionsstrategie

11 EN zxx gg

2E2N zxx gg

zxx ggEN

eiltnormalvert)1,0(,, /21 nzzz n

ggNBE

1 xx )(),(),()( NNNNB 21minmax/ gggg QQQQ xxxx

Schrittweiten derNachkommen gleich

Basis-Algorithmus der (1, ) - Evolutionsstrategie

11NE1N zxx ggg

22NE2N zxx ggg

zxx gggNEN

eiltnormalvert)1,0(,, /21 nzzz n

ggNBE

1 xx )(),(),()( NNNNB 21minmax/ gggg QQQQ xxxx

Schrittweiten derNachkommen

verschieden

Vererbbarkeit der Mutabilität

DNA-Kopierer

DNA

hat Kopierer hergestellt

Basis-Algorithmus der (1, ) - Evolutionsstrategie

1g11 NEN zxx gg

22NE2N zxx ggg

zxx gggNEN

eiltnormalvert)1,0(,, /21 nzzz n

ggNBE

1 xx )(),(),()( NNNNB 21minmax/ gggg QQQQ xxxx

Basis-Algorithmus der (1, ) - Evolutionsstrategie

1g11 NEN zxx gg

22NE2N zxx ggg

zxx gggNEN

eiltnormalvert)1,0(,, /21 nzzz n

ggNBE

1 xx )(),(),()( NNNNB 21minmax/ gggg QQQQ xxxx

ggNBE

1

Mutation der Mutabilität undVererbbarkeit der Mutabilität

„Knackpunkt“ der Evolutionsstrategie

DNA-Kopierer

DNA

hat Kopierer hergestellt

Mutation

Algorithmus der (1, ) – Evolutionsstrategie mit MSR

1g11 NEN zxx gg

22NE2N zxx ggg

zxx gggNEN

eiltnormalvert)1,0(,, /21 nzzz n

ggNBE

1 xx )(),(),()( NNNNB 21minmax/ gggg QQQQ xxxx

ggNBE

1

11 EN gg

2E2N gg

ggEN

eiltnormalvert schlogarithmi

? ? ?

ich bin Spitze

Einschätzung des Kletterstils

im Solo- und im Gruppenklettern

Lineare Theorie der (1, ) - ES

Linienfortschritt

Q steigt monoton in x-Richtung an

Q ändert sich nicht in y-Richtung

y-Mutationen sind also neutral;sie tragen nicht zum Fortschritt bei

xy E

u u+u x

uu

ux

t xxwW d)(1

1

d)(d)(,2,1

u

x

t

uu

ux

t xxwxxwW

222

1

e2

1)(

x

t xw

WWW 32

1

d)(

u

x

t xxw

Größte von normalverteilten Zufallszahlen

Der 1. Nachkomme liegt hierund der 2. Nachkomme hierund der 3., 4., … Nachkomme hier

Der 2. Nachkomme liegt hierund alle anderen liegen hierund so fort

Übergang zur Wahrscheinlichkeitsdichte

1

d)(d)(,2,1

u

x

t

uu

ux

t xxwxxwW

1

d)(d)(1lim0

,2,1

u

x

t

uu

ux

tu

xxwxxwwu

1

d)()()(

u

x

tt xxwuwuw

Häufigkeitsverteilung für die Größte von normalverteilten Zufallszahlen

1

2erf1

21

2)(

222

1

e

u

uwu

-1-2 0 1 2 3 4 5

u

w

0,2

0,4

0,6

1,0

0,8

5

10

20u(

)

duuwuu

)(,1

0

d2

erf121

2

1222

1

,1 eu

u

uu

u

,1,1 c zzzcz

z d)erf(1e2

2 1

1,10

2

mit

duuwuu

01 )(

Lineare Fortschrittsgeschwindigkeit

Die Fortschrittsbeiwerte der Komma-Strategie (exakte Werte)

01,1 c

5642,01

2,1

c

8463,02

33,1

c

0294,12arctan6

4,1

c

1630,112arctan62

55,1

c

,1lin,1 c

40,0lin11

Die Fortschrittsbeiwerte der Plus-Strategie (exakte Werte)

3989,02

111

c

6810,02

11

2

121

c

8881,02arctan2

2

121

23

2

131

c

0458,12

321

2

141

c

Fortschrittsvergleiche der linearen Theorie

111,1 0

212,1 828,0

313,1 953,0

414,1 984,0

111141 621,22

321

4 für1,1

Parallele und serielle Fortschrittsgeschwindigkeit

Nachkommender Zahl Weggter zurückgele

seriell

enGenerationder Zahl Weggter zurückgele

parallel

/parallelseriell

262,04046,1 /seriell 41

3989,012

1 /seriell 11

Nicht erlaubter Bereich

Optimierung mit Randbedingung

Versagen der 1/5-Erfolgsregel !

E

Ideale Funktion in der mathematischen Welt

Rauher Berg in der experimentellen Welt

Versagen der 1/5-Erfolgsregel !

Ende