Ingo Rechenberg

PowerPoint-Folien zur 7. Vorlesung „Evolutionsstrategie I“

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

(1, ) - ES mit mutativer Schrittweitenregelung

Rückblick auf die letzte Vorlesung

ggg zxx EN

Algorithmus der (1 + 1) – ES mit 1/5 -Erfolgsregelin der originalen Form

1Egx )() ENN (für ggg QQ xxx

sonst Egx

1,5 für We > 1 / 5

eiltnormalvert -1,0 / )( ngz

1,5 für We < 1 / 5

Nach jeweilsn Generationen

Interpretiert als isotrope Stichprobe der Weite 1

Breite der Gaußschen Glockenkurve

Verstärkungs- oder Abschwächungsfaktor

Versagen der 1/5-Erfolgsregel am spitzen Grat

Elter

kleiner als 1/5 Kreisumfang

We < 1/5

We < 1/5

/1,5

…

Erfolgsgebiet

grad

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 !

2 3 4 57 8

69

Eine fehlerhafte Messung: Q = 6 statt Q = 4

Fehlmessung bei Störungen

We < 1/ 5 /1,5

We < 1/ 5…

Erfolgsgebiet

Q =

E

~

Die (1 + 1)-ES kann an Unstetigkeiten versagen

… und sie ist unbiologisch !

We > 1/5We < 1/5

MutationenBiologisch

unmöglich

Kosmische StrahlungWe ?

Momentaufnahme des Lebens

(1 , )-ES !

Die kann es.

(1 + 1)-ES

DARWINs Theorie in maximaler Abstraktion

Von der

(1 , )-ES

ES mit mehr als einem Nachkommen

= 6

zur

Basis-Algorithmus der (1, ) - Evolutionsstrategie

1E1N zxx gg

2E2N zxx gg

zxx ggEN

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

ggNBE

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

Kopiervorgang mit Fehlern

Bester

DNA PolymeraseDNA

Technischer und biologischer Kopierer

Insel der Krebse

Wenn ich mich nicht an meinem eigenen Schopfe

herausgezogen hätte

Baron von Münchhausen

Ein Lebewesen kopiert sich selbst ?

DNA-Kopierer

DNA

Der DNA-Kopierer ist zugleich ein Reparaturgerät. Falsche Buchstaben, z. B. durch kosmische Strahlung erzeugt, werden berichtigt!

Text

Eine nicht 100-prozentige Reparatur-leistung des DNA-Kopierers lässt Fehler (Mutationen in der DNA) übrig.

Verdopplung der Erbinformation durch Anlagerung komplementärer Buchstabenmoleküle (G,A,T,C) an die aufgetrennte DNA-Doppelhelix

DNA-Kopierer

DNA

Hat Kopierer hergestellt

Genetische Individualität der übrig gelassenen Mutationen

Text

DNA-Kopierer

DNA

Hat Kopierer hergestellt

Vererbbarkeit der Mutabilität

Text

Besser: Vererbbarkeit der Menge der nicht korrigierten Mutationen in der DNA

Mutation

DNA-Kopierer

DNA

Hat Kopierer hergestellt

Vererbbarkeit der Mutabilitätund Mutation der Mutabilität

„Knackpunkt“ der Evolutionsstrategie

Text

Reparaturfähigkeit des DNA-Kopierers

Basis-Algorithmus der (1, ) - Evolutionsstrategie

1E1N zxx gg

2E2N zxx gg

zxx ggEN

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

ggNBE

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

Schrittweiten derNachkommen gleich

Aber kann variiertund vererbt werden

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(Keimzellen eines Elters !)

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

Vererbung der Mutabilität

Algorithmus der (1, ) - Evolutionsstrategie mit MSR

11NE1N zxx ggg

22NE2N zxx ggg

zxx gggNEN

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

ggNBE

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

ggNBE

1

1E1N gg

2E2N gg

ggEN

eiltnormalvert schlogarithmi

Mutation der Mutabilität

Vererbung der Mutabilität

MSR mit ES-),1(

8

Mutative Schrittweiten-Regelung

? ? ?

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

Beklettern einer schrägen Ebene. Für die Rechnung geschickte Legung des Koordinatensystems.

u u+u x

uu

uxt xxwW d)(1

222

1e

21)(

xt xw

2W1

d)(

u

xt xxw

Größte von normalverteilten Zufallszahlen

Der 1. Nachkomme liegt hierund der 2. Nachkomme hierund der 3. Nachkomme hier

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

u

xt xxw d)(

und der 4., 5., … Nachkomme hier

WW 3

u u+u x

222

1e

21)(

xt xw

Größte von

normalverteilten Zufallszahlen

Die Wahrscheinlichkeit, dass der 1. oder der 2. oder der 3. oder… der . Nachkomme im blauen Bereich liegt

1

2121

u

xt

uu

uxt xxwxxwWWWW d)(d)(,,

Übergang zur Wahrscheinlichkeitsdichte

1

d)(d)(,2,1

u

xt

uu

uxt xxwxxwW

1

d)(d)(1lim0,2,1

u

xt

uu

uxtu

xxwxxww u

1

d)()()(

u

xtt xxwuwuw

Lösung durch Nachschauen in Integraltafeln

Wahrscheinlichkeit, dass der Beste von Nachkommen im Bereich u + Δu liegt

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

1

2erf12

12

)(2

221

e

uuw

u

-1-2 0 1 2 3 4 5

u

w

0,2

0,4

0,6

1,0

0,8

510

20u(

)duuwu

u

)(,1

duuwuu

01 )(

Mittelwertbildungen

!

duuwuu

)(,1

0d

2erf12

12

1222

1

,1 eu

uuuu

,1,1 c zzzcz

z d)erf(1e2

2 11,1

0

2

mit

duuwuu

01 )(

Lineare Fortschrittsgeschwindigkeit

Nur noch eine Funktion von

Die Fortschrittsbeiwerte der Komma-Strategie (exakte Werte)

01,1 c

5642,012,1

c

8463,02

33,1

c

0294,12arctan64,1

c

1630,112arctan62

55,1

c

,1lin,1 c

40,0lin11

21/

Die Fortschrittsbeiwerte der Plus-Strategie (exakte Werte)

3989,021

11

c

6810,02

1121

21

c

8881,02arctan22

121

23

21

31

c

0458,123

21

21

41

c

Fortschrittsvergleiche der linearen Theorie(Plus versus Komma-Strategie)

111,1 0

212,1 828,0

313,1 953,0

414,1 984,0

111141 621,223

21

4 für1,1

?

Parallele und serielle Fortschrittsgeschwindigkeit

g Weg

Nachkommenaller Zahl Weggter zurückgele

seriell

/parallelseriell

262,04046,1 /seriell 41

3989,0121 /seriell 11

Text

gWeg

enGenerationder Zahl Weggter zurückgele

parallel

Ende

www.bionik.tu-berlin.de

Fehlerhaftigkeit des DNA-Kopieres heißt nicht, dass dieser Fehler selbst erzeugt! Kopierfehler werden ursächlich durch Umwelteinflüsse (kosmische Strahlung, thermisches Rauschen, chemische Agenzien) erzeugt. Der biologische Kopierer kann aber diese Fehler erkennen und korrigieren. Je größer die Korrigierleistung des DNA-Kopierers ist, um so kleiner ist die übrig bleibende Zahl der Mutationen (Mutationsrate). Daraus folgt: Die Mutationsfreudigkeit eines Organismus kann dieser selbst kontrollieren. Die Mutationsfreudigkeit (Mutabilität) ist eine inhärente Eigenschaft des jeweiligen Lebewesens.

Der Kopierer wird nicht von außen zu Verfügung gestellt (wir kaufen uns einen Kopierer in einem Geschäft), sondern der biologische Kopierer (die DNA-Polyme-rase) wird von dem Lebewesen selbst hergestellt. Die Bauanweisung steht irgend-wo in dem lange DNA-Erbmolekül. Daraus folgt, dass jedes Lebewesen seinen individuellen Kopierer (z. B. mit unterschiedlicher Kopiergenauigkeit) besitzt, so wie jeder Mensch sich durch seine individuelle Haarfarbe auszeichnet. Deshalb ordnen wir in dem Algorithmus der (1, )-ES jedem Nachkommen eine andere Kopierge-nauigkeit, sprich eine andere Mutationsschrittweite zu.

Aus der Tatsache, dass die Bauanleitung für den DNA-Kopierer eines Lebewesens im Erbmolekül niedergeschrieben ist, folgt die Vererbbarkeit dieses Merkmals. Die individuelle DNA-Sequenz für die DNA-Polymerase wird auf die Nachkommen über-tragen. Dies bedeutet für den Evolutionsalgorithmus, dass im abschließenden Selektionsschritt einer Generation nicht nur der Objektvariablenvektor x des besten Nachkommen, sondern auch die Mutationsschrittweite des besten Nachkommen an den Elter der neuen Generation übergeben wird.

Alles, was im DNA-Molekül niedergeschrieben ist, kann durch eine Mutation verän-dert werden. Eine Mutation des Abschnitts, der die Bauanleitung für den Kopierer enthält, ändert die Arbeitsweise des Kopierers. Der Kopierer kann genauer oder ungenauer arbeiten. Er kann Fehler mehr oder weniger korrigieren. Damit wird die Mutationsfreudigkeit (sprich Mutationsschrittweite) eines Organismus mutativ ver-ändert. Im Algorithmus der Evolutionsstrategie wird der Mutationsmechanismus ergänzt, indem nicht nur der Objektvariablenvektor x, sondern auch die Strategie-variable einer Mutation unterworfen wird. Mutationsschrittweiten müssen multipli-kativ verändert werden (eine Verdopplung der Schrittweite muss genauso häufig auftreten wie eine Halbierung. Deshalb werden die Schrittweitenmutationen mit einer logarithmischen Normalverteilung erzeugt.

Die biologische Evolution arbeitet parallel. Es bedeutet keinen zusätzlichen Auf-wand, wenn in einem gegebenen Lebensraum statt mit einem Individuum mit Tau-senden von ihnen experimentiert wird. In der Evolution zählt der Fortschritt pro Generation (parallele Fortschrittsgeschwindigkeit). Ganz anders ist es bei der An-wendung der Evolutionsstrategie auf einem gewöhnliche Computer. Hier müssen die Nachkommen einzeln nacheinander durchgerechnet werden. Für die Compu-teranwendung muss die Fortschrittsgeschwindigkeit auf die Zahl der Nachkommen bezogen werden. Diese serielle Fortschrittsgeschwindigkeit ergibt sich, indem die parallele Fortschrittsgeschwindigkeit zusätzlich durch dividiert wird. Nur wenn in der Zukunft sich die Parallelrechner durchsetzen, ist die biologische Bewertung des Fortschritts auch bei der Computeranwendung der Evolutionsstrategie richtig.