Ingo Rechenberg

PowerPoint-Folien zur 11. Vorlesung „Evolutionsstrategie I“

Sternstunden der Theorie der EvolutionsstrategieVortrag in Jena anlässlich des 50-jährigen Jubiläums der Evolutionsstrategie

18. November 1964

Symposium 18. bis 20. November 2014 in Jena

Google Suchbegriff: „zickzack nach darwin“

Sternstunden der Theorie der Evolutionsstrategie

Eine spektakuläre Lösung der Evolution

Erg Chebbi

Cebrennus rechenbergi

„Einen Naturvorgang verstehen heißt, ihn in Mechanik zu übersetzen“

Herrmann von Helmholtz

Mechanische Evolutionsexperimente

Zickzackplatte

Start Ergebnis

Rohrkrümmer

h = 55%

h = 79%

„Ich behaupte aber, daß in jeder besonderen Naturlehre nur so viel eigentliche Wissenschaft angetroffen werden könne, als darin Mathematik anzutreffen sei“

Immanuel Kant 1786

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.

Darwins vielleicht wichtigster Ausspruch

Die starke Kausalität

Es gibt ein universelles Weltverhalten

Eingang:Neigung derKaffeekanne

Ausgang: Stärke des Kaffeestroms

Kleine Änderung der Ursache → kleine Änderung der Wirkung

Warum verhält sich die Welt normalerweise so ???

sox

y

nicht sox

y

yx

Hier gilt starke Kausalität

Hier gilt starke Kausalität

Hier gilt starke Kausalität

Hier gilt starke Kausalität

Hier gilt starke Kausalität

Hier gilt starke Kausalität

Qualität Q(x, y)

Bewegte Strecke bergaufZahl der Generationenj

=

Definition der Fortschrittsgeschwindigkeit längs des Darwinweges

j

Der Darwinweg ist nicht unbedingt der Gradientenweg

Darwinweg

Auf dem Darwinweg

Eine Strategie nutzt geschickt vorhersehbare

Verhaltensweisen des Gegners

Die Evolutionsstrategie nutzt das vorhersehbare stark kausale Verhalten

des Gegners „Natur“

Theorie der Evolutionsstrategie soll heißen:

Entwicklung von Formeln für j

für verschiedene Komplexitätsstufen einer Nachahmung der biologischen Evolution

In der Theorie der Evolutionsstrategie folgen die Komplexitätsstufen aus einer „ES-Algebra“

ES]),(,[ ES)]1( Von der zur

1+1( ) - gliedrige Evolutionsstrategie

Evolutionsstrategische Algebra

(1 + 1)-ES

DARWINs Theorie inmaximaler Abstraktion

1 +1( ) - ES ,

Evolutionsstrategische Algebra

( ) - ES +,/r

Beispiel r = 2

( ) - ES +,/ 2

Elter liefert nur die Hälfte der Erbinformation

Evolutionsstrategische Algebra

( ) - ES +,

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

Evolutionsstrategische Algebra

( ) - ES +,

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

,

Evolutionsstrategische Algebra

[ ]

ES]),(,[

1=2=1=5=4=

Neue Gründerpopulationen

Die geschachtelte Evolutionsstrategie

Theorie der Evolutionsstrategie soll heißen:

Entwicklung von Formeln für j

j

für verschiedene Komplexitätsstufen einer Nachahmung der biologischen Evolution

?]),(,[ = j

?)1( =1j?),( =j

?),/( =rj

Lokales Klettern der Evolutionsstrategie

Die Grundidee (in einer Dimension)

Satz von Funktionen

)sin(xxe)log(x

)arctan(x)cosh(x

)(erf x

= 432241

61

211e xxxxx

= 864240320

17201

241

211)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( xdxfdx

dxfdx

dxdffxf

)sinh(ar x

TAYLOR Potenzreihenentwicklung in der MACLAURINschen Form:

!

j für welches Gebirge ?

Nur die Koeffizienten sind verschieden

= 44

33

2210)( xaxaxaxaaxf

ckdk

ck

dk

ckdk

ck k

n

kxQQ

=

=1

0 ckck2

1k

n

kx

=

dk

Asym

ptotis

che T

heori

e (n

>>1)

dkdk2

2,, j =

k

k

cd

c

Lokales Klettern der Evolutionsstrategie

Ebene

22,, j =

k

k

cd

c

= lokale Komplexität

rnΩ 12 =

r

ΩIst fast eine

Konstante (1 … 3)

Mutationsstreuung

2, j = Ωc 2

,cΩ

22,

2

,2

,j

cΩ

cΩ

cΩ =

F D D= 2

Zentrales Fortschrittsgesetz

Der Evolutionsstratege

F D=D 2

-5 -3 -1 310

0,2

0,1

0,3

D

F

1 01 01 01 010

2DDF =

Evolutions Fenster

-5 -3 -1 310

0,2

0,1

0,3

D

F

1 01 01 01 010

2DDF =Französische Nationalversammlung

Die LinkenDie

Rechten

=

=n

kkxQQ

1

20

=

=n

kkxpxQ

2

21 2

1

Kuppenmodell

Gratmodell

2

2

211

1m

n

kkm x

pmxQ

=

=

m >> 1

x

x

x

1

23

Gradienten- Weg

ES-Wegfür maximalen

Fortschritt

Fortschritt am Grat

Höhen-flächen

21 DDF =Der D

arwinweg ist nich

t immer

gleich dem Gradientenweg

m >> 1

Der Evolutionsstratege

F D=D 2 21 DDF =

Darwin Mendel

Die Mischung von Erbmerkmalen (Variablenwerten)

( /r , )-ES

ES mit Mischung der Variablen (Erbanlagen)

= 8

= 2r = 2

In der Natur werden die Erbanlagen von je zwei Individuen gemischt. In der Nomenklatur der ES wäre die Mischungszahl r = 2.

( /r , ) - ES r = 2 Nur Phagen könnten bei einer Mehrfachinfektion eines Bakteriums eine Multi-

rekombination r = vollziehen. Das heißt, alle Eltern mischen ihre Erbanlagen.

( / , ) - ES r =

In der Theorie ließ sich bisher nur der unbiologische Fall r = exakt behandeln.

( / , ) = diskrete Mischung aller Variablenwerte (Theorie Thales-Rekombination) ( / , ) = kontinuierliche Mischung aller Variablenwerte

Zur Nomenklatur der Multirekombination:

2, j = Ωc

Aus

wird

2,/ j Ωc = +

24max,1max,1 2

~hh =

jj

ENENB QQQQ =

)1(optopt e 1W ),( =

)1(optopt 1 ),( =

22R

h

=

,, )(/ = /cc

)2(,1,11,1 )1( jjj =

kk ki

ki cki

ikic

=

=

=

,1

1

0

1

, 11/

Biol. Heritabilität

Bei maximalem Fortschritt verschlechtert sich die gesamte Nachkommenschaft im Mittel ebenso sehr, wie sich der Spitzen-Nachkomme verbessert

Entropiesatz der Evolutionsstrategie: (1, ) -ES

Überraschende Beziehungen zwischen der höchsten und der niedrigsten Form einer ungeschachtelten Evolutionsstrategie

Einige Sternstunden-Fo

rmeln

gestört

ungestört

)1(maxmax 1jj ),( = opt

~~

r /1

≈ 1

≈ 1

2Ω

Ivan Santibañez-Koref

2 j Ω r

21 Ω=j

=j

,c 1

,/c 2 Ω1

2/1 rj Ω

maxj Ω4/1 r

rn 12

Danke für Ihre Aufmerksamkeit

www.bionik.tu-berlin.de

Zum Praktikum / Experimentelle Übung

MATLAB-Programm der (1 + 1) ES

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

ones(m,n): Vektor/Matrix der Dimension m × n mit nur Einsen

Nur eine Spalte

MATLAB-Programm der (1, ) ES

MATLAB-Programm der (1, ) ES

v=100; kk=10; de=1; xe=ones(v,1);

Variablenzahl, Nachkommenzahl,

Startschrittweite und

Variablen-werte des Start-

Elters

MATLAB-Programm der (1, ) ES

v=100; kk=10; de=1; xe=ones(v,1);

for g=1:1000

end

Erzeugen der Generationenschleif

e

MATLAB-Programm der (1, ) ES

v=100; kk=10; de=1; xe=ones(v,1);

for g=1:1000 qb=1e+20;

end

Initialisierung der Qualität im

Bestwert-Zwischenspeicher

auf extrem schlechten Wert

(für Minimumsuche)

MATLAB-Programm der (1, ) ES

v=100; kk=10; de=1; xe=ones(v,1);

for g=1:1000 qb=1e+20; for k=1:kk

end

end

Generierung der Nachkommenschlei

fe

MATLAB-Programm der (1, ) ES

v=100; kk=10; de=1; xe=ones(v,1);

for g=1:1000 qb=1e+20; for k=1:kk if rand < 0.5 dn=de*1.3; else dn=de/1.3; end

end

end

Deterministische Variation der

Mutationsschrittweite

MATLAB-Programm der (1, ) ES

v=100; kk=10; de=1; xe=ones(v,1);

for g=1:1000 qb=1e+20; for k=1:kk if rand < 0.5 dn=de*1.3; else dn=de/1.3; end xn=xe+dn*randn(v,1)/sqrt(v);

end

end

Erzeugung eines mutierten Nachkommen

MATLAB-Programm der (1, ) ES

v=100; kk=10; de=1; xe=ones(v,1);

for g=1:1000 qb=1e+20; for k=1:kk if rand < 0.5 dn=de*1.3; else dn=de/1.3; end xn=xe+dn*randn(v,1)/sqrt(v); qn=sum(xn.^2);

end

end

Bestimmung der Qualität

des mutierten Nachkommen (Beispiel

Kugelmodell)

MATLAB-Programm der (1, ) ES

v=100; kk=10; de=1; xe=ones(v,1);

for g=1:1000 qb=1e+20; for k=1:10 if rand < 0.5 dn=de*1.3; else dn=de/1.3; end xn=xe+dn*randn(v,1)/sqrt(v); qn=sum(xn.^2); if qn < qb qb=qn; db=dn; xb=xn; end end

end

Bei Q -Verbesserung Zwischen-

speicherung der Qualität,

Schritt-weite und Variablenwerte

MATLAB-Programm der (1, ) ES

v=100; kk=10; de=1; xe=ones(v,1);

for g=1:1000 qb=1e+20; for k=1:kk if rand < 0.5 dn=de*1.3; else dn=de/1.3; end xn=xe+dn*randn(v,1)/sqrt(v); qn=sum(xn.^2); if qn < qb qb=qn; db=dn; xb=xn; end end qe=qb; de=db; xe=xb;

end

Nachkomme aus dem

Bestwert-Zwischenspeicher

wird zum Elter der nächsten

Generation

MATLAB-Programm der (1, ) ES

v=100; kk=10; de=1; xe=ones(v,1);

for g=1:1000 qb=1e+20; for k=1:kk if rand < 0.5 dn=de*1.3; else dn=de/1.3; end xn=xe+dn*randn(v,1)/sqrt(v); qn=sum(xn.^2); if qn < qb qb=qn; db=dn; xb=xn; end end qe=qb; de=db; xe=xb; semilogy(kk*g,qe,'b.') hold on; drawnow;end

Darstellung der Qualität als

Funktion des seriellen

Aufwands Kinderzahl x

Generationen

Erproben des Programms in MATLAB

Kopieren Sie das Programm der vorangegangenen Folie. Öffnen Sie MATLAB und klicken Sie in der Taskleiste auf „File/New/Script“. Fügen Sie das Programm ein und klicken Sie auf das Symbol „Save and Run“ (Speichern).

Ändern Sie die Zahl der Kinder von 10 auf 5 [kk = 5] und die Zahl der Generationen von 1000 auf 2000 [g = 1 : 2000]. Ändern Sie die Kurvenfarbe von blau auf rot [semilogy(g,qe,′r.') ]. Sie werden mit der gleichen Zahl von Funktionsaufrufen g × kk = 10000 vielleicht etwas näher an das Optimum herankommen.

Wiederholen sie die Prozedur für:

[g = 1 : 3333], [kk = 3], [semilogy(g,qe,‚g.') ][g = 1 : 500], [kk = 20], [semilogy(g,qe,‚y.') ]

Das Ergebnis: Bei 5 Nachkommen [k = 1 : 5] sollten Sie bei der seriellen Arbeitsweise des Rechners dem Optimum (Nullpunkt) am nächsten kommen.

MATLAB R2010a

Neu: Programmiersprache R

(Microsoft)

Zum Kopieren (Qualitätsfunktion = „Zigarre“ )

v=100;gg1=1000; kk1=2; xe1=ones(v,1); de1=1; aa1=1.5;gg0=50; kk0=10; xe0=ones(v,1); de0=1; aa0=1.0; oo=ones(v,1);

for g1=1:gg1 qb1=1e+20; for k1=1:kk1 dn1=de1*aa1^(2*round(rand)-1); xn1=xe1+0*randn(v,1)/sqrt(v); de0=dn1; xe0=xn1; for g0=1:gg0 qb0=1e+20; for k0=1:kk0 dn0=de0*aa0^(2*round(rand)-1); xn0=xe0+dn0*randn(v,1)/sqrt(v)+oo*randn/sqrt(v); qn0=xn0(1)^2+1000*sum(xn0(2:v).^2); if qn0 < qb0 qb0=qn0; db0=dn0; xb0=xn0; end end qe0=qb0; de0=db0; xe0=xb0; end dn1=de0; xn1=xe0; qn1=xn1(1)^2+1000*sum(xn1(2:v).^2); if qn1 < qb1 qb1=qn1; db1=dn1; xb1=xn1; end end

qe1=qb1; de1=db1; oo=xb1-xe1; xe1=xb1; semilogy(g1,qe1,'b.') hold on; drawnow;end

MATLAB-Programm einer geschachtelten (1, )-Ortho-ES

Option ExplicitDim stopp, fa

Private Sub Command1_Click() stopp = 1End Sub

Private Sub Command2_Click() EndEnd Sub

Private Sub Command3_Click()Text1 = "": Text2 = "": Text3 = "": ClsEnd Sub

Private Sub Form_Load()fa = 13End Sub

Private Sub start1_Click() myqela1End Sub

Private Sub myqela1() Dim v%, vv%, g0%, gg0%, g1%, gg1%, k0%, kk0%, k1%, kk1%, m0%, mm0%, m1%, mm1%, j% Dim qn0#, qn1#, d0#, d1#, dn0#, dn1#, aa0#, aa1#, pp#, z#, a#, w#, hh# Dim qe0#(), qb0#(), db0#(), b0#(), n0#(), e0#() Dim qe1#(), qb1#(), db1#(), b1#(), n1#(), e1#()

If fa < 1 Then fa = 13 fa = fa - 1 Randomize: stopp = 0 vv = Val(Text5): mm1 = Val(Text6): kk1 = Val(Text7): aa1 = Val(Text8) a = Val(Text15): mm0 = Val(Text9): kk0 = Val(Text10): aa0 = Val(Text11): gg0 = Val(Text12) ReDim qe0(mm0), qb0(mm0), db0(mm0), b0(vv, mm0), n0(vv), e0(vv) ReDim qe1(mm1), qb1(mm1), db1(mm1), b1(vv, mm1), n1(vv), e1(vv) d1 = 0.01: e1(1) = 1: For v = 2 To vv: e1(v) = 0: Next v 'Text14 = 2 * vv gg1 = Val(Text14)

For g1 = 1 To gg1 DoEvents: If stopp = 1 Then Exit For For m1 = 1 To mm1: qb1(m1) = -1E+20: Next m1 For k1 = 1 To kk1 If k1 = 1 Then dn1 = d1 / aa1 If k1 = 2 Then dn1 = d1 * aa1 If k1 > 2 Then If Rnd > 0.5 Then dn1 = d1 / aa1 Else dn1 = d1 * aa1 End If For v = 1 To vv 'z = Sqr(-2 * Log(1 - Rnd) / vv) * Sin(6.283185 * Rnd) n1(v) = e1(v) + 0 * z Next v d0 = dn1: e0() = n1()

For g0 = 1 To gg0 For m0 = 1 To mm0: qb0(m0) = -1E+20: Next m0 For k0 = 1 To kk0 If Rnd > 0.5 Then dn0 = d0 / aa0 Else dn0 = d0 * aa0 For v = 1 To vv z = Sqr(-2 * Log(1 - Rnd) / vv) * Sin(6.283185 * Rnd) n0(v) = e0(v) + dn0 * z Next v

qn0 = -n0(1) ^ 2: For v = 2 To vv: qn0 = qn0 - a * n0(v) ^ 2: Next v j = 1: w = qb0(1) For m0 = 2 To mm0: If qb0(m0) < w Then w = qb0(m0): j = m0 Next m0 If qn0 > qb0(j) Then qb0(j) = qn0: db0(j) = dn0 For v = 1 To vv: b0(v, j) = n0(v): Next v End If Next k0 d0 = 1: For m0 = 1 To mm0 qe0(m0) = qb0(m0): d0 = d0 * db0(m0) ^ (1 / mm0) Next m0 For v = 1 To vv e0(v) = 0: For m0 = 1 To mm0: e0(v) = e0(v) + b0(v, m0) / mm0: Next m0 Next v Next g0 dn1 = d0: n1() = e0() qn1 = -n1(1) ^ 2: For v = 2 To vv: qn1 = qn1 - a * n1(v) ^ 2: Next v

j = 1: w = qb1(1) For m1 = 2 To mm1: If qb1(m1) < w Then w = qb1(m1): j = m1 Next m1 If qn1 > qb1(j) Then qb1(j) = qn1: db1(j) = dn1 For v = 1 To vv: b1(v, j) = n1(v): Next v End If Next k1 d1 = 1: For m1 = 1 To mm1 qe1(m1) = qb1(m1): d1 = d1 * db1(m1) ^ (1 / mm1) Next m1 For v = 1 To vv e1(v) = 0: For m1 = 1 To mm1: e1(v) = e1(v) + b1(v, m1) / mm1: Next m1 Next v DoEvents: Text1 = g1 * gg0: Text2 = Format(qe1(1), "Scientific"): Text3 = Format(d1, "Scientific") hh = g1 * gg0 / vv FillStyle = 0: FillColor = QBColor(fa): Circle (5000 + 1000 * hh, 1500 - 10000 * Log(-qe1(1))), 50, QBColor(fa) If hh > 8 Then Exit For Next g1End Sub

So sieht ein Basic-Programm einer geschachtelten ( /, )-ES aus !

MATLAB-Programm der (1, ) ES

v=100; kk=10; de=1; xe=ones(v,1);

for g=1:1000 qb=1e+20; for k=1:kk if rand < 0.5 dn=de*1.3; else dn=de/1.3; end xn=xe+dn*randn(v,1)/sqrt(v); qn=sum(xn.^2); if qn < qb qb=qn; db=dn; xb=xn; end end qe=qb; de=db; xe=xb; semilogy(kk*g,qe,'b.') hold on; drawnow;end

Ersetzen Sie die Optimierungs-

funktion Kugelmodell durch

eine andere zu minimierende

Funktion

Bei Minimum-Problem umdrehen

Zum Beispiel:

Ein unregelmäßiges Sechseck, dessen Ecken (Variablenwerte) auf einem Kreis mit demDurchmesser 1 liegen, soll einen maximalen Inhalt erhalten.

Eine 1-Liter Milchtüte (Quader mit den variablen Seiten a, b, c) soll mit minimalem Material (Oberfläche) gefertigt werden.

Das Steinersche Verzweigungsproblem. 3 Punkte sollen durch Straßen miteinander verbunden werden. Wo muss die Straßenverzeigung liegen, damit die gesamte Straßen-länge minimal wird. Kann auf viele Verzweigungen (x-y-Variable) erweitert werden.

Weitere Probleme im Buch: Heinz J. Claus – ExtremwertaufgabenProbleme, ihre Geschichte, Lösungen, Methoden.