Ingo Rechenberg

PowerPoint-Folien zur 2. Vorlesung „Evolutionsstrategie II“

Der ES-Fortschritt im Quadrikgebirge und

Kalkül der geschachtelten Evolutionsstrategien

Weiterverwendung nur unter Angabe der Quelle gestattet

Klettern bei starker Kausalität

Experimentator

Suchfeld

Klettern bei linearer starker Kausalität

Experimentator

Suchfeld

(1 + 1)-ES

DARWINs Theorie in maximaler Abstraktion

Lokales Klettern der Evolutionsstrategie

linear

n

21

Lokales Klettern der Evolutionsstrategie

nichtlinear

(1 , )-ES

ES mit mehr als einem Nachkommen

= 6

Die Grundidee (in einer Dimension)

Satz von Funktionen

)sin(xxe

)log(x)arctan(x

)cosh(x)(erf x

432

241

61

21

1e xxxxx

8642

403201

7201

241

21

1)cos( xxxxx

Alle Funktionen haben dieselbe Form

9753

91

71

51

31

)arctan( xxxxxx

33

32

2

2 )0(!3

1)0(!2

1)0(!1

1)0()0( x

dx

fdx

dx

fdx

dxdf

fxf

)sinh(ar x

TAYLOR Potenzreihenentwicklung in der MACLAURINschen Form:

!

nichtlinear für welches Gebirge ?

)0(!2

1)0(!1

1)0()0(1 1

2

1

ji

n

i

n

j jii

n

i ixx

xxfx

xfff

x

TAYLOR-Entwicklungin n Dimensionen (MACLAURIN Reihe)

1 11

0 ji

n

i

n

j

jii

n

i

i xxbxaQQ

Vektor

Hauptachsentransformation =Drehung des Koordinatensystems derart, dass die Kreuzterme wegfallen

2

110 k

n

ikk

n

kk ydycQQ

ji

n

i

n

jjii

n

ii xxbxaQQ

1 11

0

x2

x1

y2

y1

Minus-Zeichen und alle d k > 0, um lokal konvexe Höhenlinien zu erhalten !

Die Hauptachsentransformation ist erlaubt, weil die Mutationen rotationssymmetrisch erzeugt werden

Konvergenzmaß „Erfolgswahrscheinlichkeit“

n

kkk

n

kkk ydycQQQQQ

1

2

10ENΔ

eiltnormalvert),0(

n

kkc

1

2 mit

n

kkd

1

2

2

110 k

n

ikk

n

kk ydycQQ

Text Text

eiltnormalvert),0( ky

Konstante für n >> 1

Mutativen Änderungen des Nachkommen

n

kkdzQ

1

2Δ

n

kkk

n

kkk ydycQ

1

2

1

Δ

eiltnormalvert),0( z

n

kkc

1

2 mit

Konstante für n >> 1

n

kkdzQ

1

2Δ

n

kkd

1

2

222

1

e2

1)(

zzw

22

12

2 erf1)()(2

e

k

kk c

ddzzwdzwW

kd

Erfolgswahrscheinlichkeit

z*

Konvergenzmaß „Fortschrittsgeschwindigkeit“

N11

N2

2

Fortschritt als Höhenlinienprojektion der Nachkommen auf den Gradienten des Elters

Universelle Fortschrittsdefinition

E

gradE

E tan

Q

2

11k

n

kkk

n

kk ydycQ

0 tan 21

22

2

2

1

n

nyyy

yQ

yQ

yQ

2tan kc

N

Q

2

22

k

k

k c

d

c

z

kdzQ 2Δ Die mutativen Q-Änderungen

Ergeben die Fortschritte

2

2

k

k

c

dz

(0, ) - normalverteilte Zufallszahlen

Konstante

- normalverteilte Zufallszahlen

2,0 kc

tan

Q

2

2

k

k

c

dz

(0, ) - normalverteilte Zufallszahlen

KonstanteBei der Erzeugung von Nachkommen wird die größte Zufallzahl z selektiert

,1c

2

2,1,1

k

k

c

dc

Aus Vorlesung ES1

2

2,1,1

k

k

c

dc

= Komplexität

2,1,1 c

2,1 c 2

,1

c

22,1

2

,12,1

ccc

2

Zentrales Fortschrittsgesetz

-5 -3 -1 310

0,2

0,1

0,3

1 01 01 01 010

2

Evolution Window

nicht so

sondern so

Ließe sich das Vorhandensein eines zusammengesetzten Organs nachweisen, das nicht durch zahlreiche aufeinander folgende geringe Abänderungen entstehen könnte, so müsste meine Theorie zusammenbrechen. Aber ich kenne keinen solchen Fall.

Charles Darwin

rn

c

d

k

k

22

r

2,1 2

r

nc

2,1,1 c Komplexität für

das Kugelmodell

Demonstration der Notwendigkeit einer Schrittweitenregelung

2erf1

21 ,1

ec

W

221

2erf1e

k

k

cdW

Erfolgswahrscheinlichkeit

Nachkommender Anzahl Gesamte

Elterder alsbesser Nachkommender Zahl e W

2erf1

21 ,1

ec

W

Schrittweitenadaption über die Erfolgswahrscheinlichkeit

0.227

2 0.25

0.20

0.15

0.10

0.05

0.1 0.2 0.3 0.4 0.5

= 10

We

50 20 60.25

0.20

0.15

0.10

0.05

0.1 0.2 0.3 0.4 0.5

= 10

We

1 / 5

Entwicklung der 1/5-Erfolgsregel

We > 1/5We < 1/5Mutationen

Biologisch unmöglichKosmische Strahlung

? ? ?

ich bin Spitze

Einschätzung des Kletterstils

im Solo- und im Gruppenklettern

Mutation

Duplikator

DNA

Hat Kopie hergestelltrer

Mutation der Mutabilität undVererbbarkeit der Mutabilität

„Knackpunkt“ der Evolutionsstrategie

Algorithmus der (1, ) – Evolutionstrategie mit MSR

11NE1Ng zxx gg

22NE2N zxx ggg

zxx gg gNEN

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

ggNBE

1 xx )(),(),()( N2NNNB 1minmax/ gggg QQQQ xxxx

ggNBE

1

1E1N gg

2E2N gg

ggEN

eiltnormalvert schlogarithmi5,1/1

5,1 :6für oder

654

321

Entwicklung der Evolutionsstrategie

ES-]),/(,/[

' = Zahl der Eltern-Populationen

' = Zahl der Nachkommen-Populationen

= Zahl der Eltern-Individuen= Zahl der Nachkommen-Individuen = Generationen der Isolation

'= Zahl der Populations-Generationen

' = Mischungszahl Populationen

= Mischungszahl Individuen

Darwin Mendel

Wright Haldane Fisher

Populationsgegentiker

wVariablensatz

Population

Zufallswahl

Duplikation

Mutation

Spielzeichen für Evolutionsstrategien (1)

Rekombination

Q

Bewertung

Realisation

Isolation

Spielzeichen für Evolutionsstrategien (2)

QSelektion

Q

Q

Kartenspiel: ( 1 + 1 ) - ES

Q Q QQ Q

Q

Kartenspiel: ( 1 + 5 ) ] - ES

Q Q QQ Q

Q

Kartenspiel: ( 1 , 5 ) - ES

Q Q Q Q Q Q Q

Q

w

Kartenspiel: ( 3 , 7 ) - ES

Q

w

w w w w w w

Q Q Q Q Q Q

Kartenspiel: ( 3 / 2 , 6 ) - ES

Q Q

Q

1 7

Q Q

Q

1 7

Q Q

Q

1 7

Q

1w

2 3w w w

Q

Kartenspiel: [ 2 , 3 ( 4 , 7 ) ] - ES

Q Q

Q

1 7

Q

30

Q Q

Q

1 7

30

w w

Q

Kartenspiel: [ 1 , 2 ( 4 , 7 )30 ] - ES

w1

w

6

w

w

w

w

Q Q

Q

w

w

w

Q Q

Q

Q

Q

Kartenspiel: [ 4 / 3 , 6 ( 5 / 2 , 7 ) ] - ES

(1 + 1)-ES

DARWINs Theorie inmaximaler Abstraktion

(1 , )-ES

ES mit mehr als einem Nachkommen

= 6

( , )-ES

ES mit mehrerenEltern und Nachkommen

= 7

= 2

( , )-ES

ES mit Mischung der

Variablen (Erbanlagen)

= 8

= 2 = 2

ES]),(,[

12154

Neue Gründerpopulationen

Die geschachtelte Evolutionsstrategie

Auf dem Weg zu einemAuf dem Weg zu einem

evolutionsstrategischen Kalkülevolutionsstrategischen Kalkül

1 +1( )2 - gliedrige Wettkampfsituation - ES ,+,

Auf dem Weg zu einem evolutionsstrategischen Kalkül

( ) - ES +,

Auf dem Weg zu einem evolutionsstrategischen Kalkül

/

Beispiel = 2

( ) - ES +,/ 2

Elter liefert nur die Hälfte der Erbinformation

Multirekombination: =

( ) - ES +,/ dominant

Zu kompliziert in der Natur aber auf dem Computer möglich

( ) - ES +,/ intermediär

( ) - ES +, intermediär (Abkürzung)

( ) - ES +,

Auf dem Weg zu einem evolutionsstrategischen Kalkül

Beispiel:

(1+ 6)4 = (1+ 6) (1+ 6) (1+ 6) (1+ 6)(1+ 6)4 = (1+ 6) (1+ 6) (1+ 6) (1+ 6) - ES

Die Zahl der Eltern wird fett geschrieben !

Zur Kennzeichnung der Eltern in fetter Schrift

(1+ 9) = (1+3+3+3)

(1+3+3+3) = (10) Unsinn !

Trennung von Eltern und Nachkommen !(1+3+3+3) = (1+9)1 1

(1+3+3+3) = (1+3+3+3)1 1

= 4 = 6 = 9

( ) - ES +,

Auf dem Weg zu einem evolutionsstrategischen Kalkül

Erweiterung: Populationswelle

(1+ 6) (2+ 6) (3+ 6) (2+ 6) (1+ 6) - ES

( ) - ES +,

Auf dem Weg zu einem evolutionsstrategischen Kalkül

ES mit Drift-Phase

(1, 7)(1, 7)(1, 7)(1, 7)(7, 7)(7, 7)(7, 7)

= (1,7)4 (7,7)3 - ES

starke Selektion schwache Selektion

( ) - ES +,

Auf dem Weg zu einem evolutionsstrategischen Kalkül

ES mit Gründer-Phase

(1, 4)(4, 16)(16, 64)(64, 256)(256, 1024) - ES

( ) - ES +,

Auf dem Weg zu einer evolutionsstrategischen Algebra

Beispiel:

= (1, 6)8 + (1, 6)8

+ (1, 6)8 + (1, 6)84 (1, 6)8

2 ,

Beste Population

Zweitbeste Population

Selektion der besten Populationen

,

( ) - ES +,

Auf dem Weg zu einem evolutionsstrategischen Kalkül

+,[ ]

' = Zahl der Eltern-Populationen' = Zahl der Nachkommen-Populationen

= Zahl der Eltern-Individuen = Zahl der Nachkommen-Individuen = Generationen der Isolation

'= Zahl der Populations-Generationen

21,1

1,1

Zwei unterschiedliche Strategien

Beispiel für eine algebraische Operation in einer geschachtelten ES

Biologische Entsprechung der Strategie-Schachtelung

| Familie Gattung { Art [ Varietät ( Individuum ) ] } |

Ende

www.bionik.tu-berlin.de

eiltnormalvert*),0(1

n

kkkzc

n

kkc

1

2* mit

Additionstheorem für (0, )-normalverteilte Zufallszahlen zk

Chiquadrat-Gesetz für n >> 1

Für große n gilt, dass n quadrierte

(0, 1) -normalverteilte Zufallszahlen

summiert wiederum normalverteilte

Zufallszahlen ergeben mit dem

Mittelwert n und der Streuung .n2

In Erweiterung gilt für den Mittelwert:

n

kk

n

kkk dzd

1

2

1

2 eiltnormalvert-mit ),0( kz

n =

Wird immer kleiner im Verlältnis zu n