Ingo Rechenberg

PowerPoint-Folien zur 5. Vorlesung „Evolutionsstrategie I“

Korridormodell, Kugelmodell und die 1/5 - Erfolgsregel

Folgen eines zum Gipfel ausgerollten Ariadnefadens

Vernünftige Strategien folgen Wegen zum Optimum

zurückgelegter WegZahl der Nachkommen

ggg zxx EN

Algorithmus der (1 + 1) - ES

1gEx

)() ( für gggENN xQxx Q

sonst gEx{

nn 1

2)(

evo

E nde der L inearität G loba le stochastische Suche

evo

Suche nach dem maximalen Fortschritt

Wo ist das Optimum ???

Nichtlineare Modelle

Weitab vom Optimum

Nahe am Optimum

Parabelgrat

Kreiskuppe

Modellfunktion Rechteckgrat (Korridormodell)

2-dimensional 3-dimensional

Q steigt longitudinal monoton an

Modellfunktion Kreiskuppe (Kugelmodell)

2-dimensional 3-dimensional

Q steigt radial monoton an

)(213 2

322

212

e21)(

zzz

t PPw

P

P

Zur Trefferwahrscheinlichkeitsdichte

Ursprung der z-KoordinatenP

P

P

P

P

P

P

R+

Ry1

y2,...n

P '

Lokaler Fortschritt der (1 + 1)-ES am Korridormodell

3

P

3

2erf

2erf

21

2erf

2erf

21

222 nn ybybybyb

n

R

t yywyy PP dd 111 )()(

…

122/e1

212erf

22)(

Korr

n

b

bb

y1y2,...n

2b

122/e1

212erf

22)(

Korr

n

b

bb

Mitueu

u2

11)(erf

für u

>>1

folgt

1

211

2Korr

n

b

1

211

2Korr

n

b

Wir suchen das Maximum von

durch Nullsetzen der 1. Ableitung: 0dd

nb 2opt

nbe

max!

Wir erinnern uns:

zurückgelegter Weg

Zahl der Nachkommen

Wir konstruieren ein zweites Konvergenzmaß

erfolgreiche Nachkommen

Gesamtzahl der NachkommenWe

We nennen wir die Erfolgswahrscheinlichkeit

n

R

t yywyy PP dd 111 )()(

…

Es galt:

n

R

t yyw PPW dd 1)(1e

…

Wir setzen die Fortschrittsbewertung = 1

bW

211

21

e für / b << 1

11opt 11

21

211

21 e

nn

nbW

opt

e21 e W opt ( = 1 :

5,4 )für n >> 1

ggg zxx EN

Algorithmus der (1 + 1) – ES mit Erfolgsregel

1gEx

)() ( für gggENN xQxx Q

sonst gEx{

vergrößern für We > 1 /

2e verkleinern für We < 1 /

2e

!

Korridormodell und optimale

Mutationsschrittweite

Modellfunktion Kreiskuppe (Kugelmodell)

2-dimensional 3-dimensional

Q steigt monoton an

y2,...n

1y

P’

R+

PP

P

Fortschrittsbewertung am Kugelmodell

zurückgelegter Weg als RadiendifferenzZahl der NachkommenKugel

n

R

tn yywyyyr PP dd 122

221 )()(Kugel

…

zurückgelegter Weg als RadiendifferenzZahl der NachkommenKugel

rn

rnr

n

882erf1

2

Kugel8e

rnW8

erf121

Kugele 1 für r

n

Korridor Kugel

nb

e nr202,0

nb2

nr224,1

max

opt

opteWe21 270,0

Ergebnisse der nichtlinearen Theorie

0

0,1

0,2

0,3

0,4

0 0,1 0,2 0,3 0,4 0,5W e

* Korridorm odell

Kugelm odell

(1 + 1) - Evolutionsstrategie: 1 / 5 - Erfolgsregel

1/6 1/5 1/4

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

Zur 1/5-Erfolgsregel

Der Futurologe Stanislaw Lem schrieb in einem Essay im Spiegel:

Die Menschheit hat bis jetzt 10 hoch 15 Bits an Information gespeichert. Bis zum Jahr 2000 wird sich die Menge etwa verdoppeln. Dabei gilt für die Infosintflut Folgendes: Etwa drei Fünftel sind Unsinn und vermischter Unsinn; den ich „Trübkunde“ nenne; ein Fünftel ist zwar sinnvoll, aber vergängliche Info, und kaum ein Fünftel besteht aus ernsten Denkfrüchten. Sogar die Forschungsanstalten werden in der Flut versinken, weil sie nicht Information, sondern Selektion benötigen, um weiter agieren zu können.

Ende