View
218
Download
1
Category
Preview:
Citation preview
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.
Recommended