Ingo Rechenberg
PowerPoint-Folien zur 7. Vorlesung „Evolutionsstrategie I“
Von der (1 + 1) - ES mit 1/5 - Erfolgsregel zur
(1, l ) - ES mit mutativer Schrittweitenregelung
Weiterverwendung nur unter
Angabe der Quelle gestattet
Algorithmus der (1+1)–ES mit 1/5-Erfolgsregel
in der originalen Form
g
g
xN  xE   z
xEg 1 
g
z
g
(0, 1/ n )- normalverteilt
xNg für Q (xNg )  Q (xEg )
xEg sonst
Nach jeweils
n Generationen
   1,5 für We > 1 / 5
   / 1,5 für We < 1 / 5
Versagen der 1/5-Erfolgsregel
am spitzen Grat
Erfolgsgebiet
kleiner als 1/5 Kreisumfang
We < 1/5
   /1,5
Elter
We < 1/5
…
Optimierung mit Randbedingung
Versagen der 1/5-Erfolgsregel !
Nicht erlaubter Bereich
E
Ideale Funktion in der
mathematischen Welt
Rauher Berg in der
experimentellen Welt
Versagen der 1/5-Erfolgsregel !
Fehlmessung
bei Störungen
Erfolgsgebiet
Q= 2
3
4
5
7
6
8
9
We < 1/5
E
Fehlerhafte Messung:
~
Q = 6 statt Q = 4
   /1,5
We < 1/5
…
Die (1 + 1)-ES kann an Unstetigkeiten versagen
… und sie ist unbiologisch !
We >
< 1/5
We ?
Kosmische
Biologisch unmöglich
Mutationen
Strahlung
Von der
(1 + 1)-ES
DARWINs Theorie in
maximaler Abstraktion
zur
(1 , l)-ES
l=6
ES mit mehr als
einem Nachkommen
Basis-Algorithmus der (1, l ) - Evolutionsstrategie
Kopiervorgang
xNg1  xEg    z1
g
g
xN2  xE    z2
z1 , z2 ,  zn  (0, 1/ n )  normalverteilt

xNgl  xEg    zl
g
xEg 1  xNB


g
Q( xNB
)  max/min Q( xNg1 ), Q( xNg2 ), Q( xNgl )
Technischer und
biologischer Kopierer
DNA
DNA Polymerase
Erzeugung fehlerhafter Kopien
Ein Lebewesen kopiert sich selbst !
Wenn ich mich nicht an
meinem eigenen Schopfe
herausgezogen hätte
Baron von Münchhausen
DNA-Kopierer
DNA
Genetische Individualität
der Mutabilität
Text
Basis-Algorithmus der (1, l ) - Evolutionsstrategie
xNg1  xEg    z1
g
g
xN2  xE    z2
z1 , z2 ,  zn  (0, 1/ n )  normalverteilt

xNgl  xEg    zl
g
xEg 1  xNB


g
Q( xNB
)  max/min Q( xNg1 ), Q( xNg2 ), Q( xNgl )
Basis-Algorithmus der (1, l ) - Evolutionsstrategie
xNg1  xEg  Ng1  z1
g
g
g
xN2  xE   N2  z2
z1 , z2 ,  zn  (0, 1/ n )  normalverteilt

xNgl  xEg  Ngl  zl
g
xEg 1  xNB


g
Q( xNB
)  max/min Q( xNg1 ), Q( xNg2 ), Q( xNgl )
DNA-Kopierer
DNA
Vererbbarkeit der Mutabilität
Text
Basis-Algorithmus der (1, l ) - Evolutionsstrategie
xNg1  xEg   Ng1  z1
g
xN2 
g
xE  Ng2
 z2
z1 , z2 ,  zn  (0, 1/ n )  normalverteilt

xNgl  xEg  Ngl  zl
Vererbung der Mutabilität
g
 Eg 1   NB
g 1
g
xE  xNB


g
Q( xNB
)  max/min Q( xNg1 ), Q( xNg2 ), Q( xNgl )
DNA-Kopierer
DNA
Vererbbarkeit der Mutabilität
und Mutation der Mutabilität
„Knackpunkt“ der Evolutionsstrategie
Text
Algorithmus der (1, l ) – Evolutionsstrategie mit MSR
 Ng1   Eg  1
xNg1  xEg  Ng1  z1
z1 , z2 ,  zn  (0, 1/ n )  normalverteilt
  logarithmisch normalverteilt
Ng2  Eg  2
xNg 2  xEg   Ng2  z2
Mutation der Mutabilität

Ngl   Eg  l
g
g
g
xNl  xE  Nl  zl
g 1
g
 E   NB
g 1
g
xE  xNB
Vererbung der Mutabilität


g
Q( xNB
)  max/min Q( xNg1 ), Q( xNg2 ), Q( xNgl )
Mutative Schrittweiten-Regelung
(1, l ) - ES mit MSR
l 8
ich bin Spitze
? ? ?
Einschätzung des Kletterstils
im Solo- und im Gruppenklettern
Lineare Theorie der (1, l ) - ES
x
y
E
Q steigt monoton in x-Richtung an
= Linienfortschritt
Q ändert sich nicht in y-Richtung
y-Mutationen sind also neutral;
sie tragen nicht zum Fortschritt bei
1
Größte von l
normalverteilten
Zufallszahlen
x2
1
2
wt ( x ) 
e 2
2 
u
u  Du
u+Du
x
l 1



W1  wt ( x ) dx 
wt ( x ) dx   W2  W3  Wl


x u
 x 

u


 u
 so
und
derfort
alle
anderen
2. Nachkomme
liegen hier


 l  wt ( x ) dx 
wt ( x ) dx

und der 3., 4., … Nachkomme hier
x u
 x 

u  Du
W1, 2,l
Der l2.
Nachkomme liegt
liegt hier
hier
1.1Nachkomme


 u

 l  wt ( x ) dx   wt ( x ) dx 


x u
 x 

u  Du
W1, 2,l

l 1

Übergang zur Wahrscheinlichkeitsdichte
w1, 2,l
1
 l  lim
Du  0 D u


wt ( x ) dx   wt ( x ) dx 


x u
 x 

u  Du

 u

wl (u)  l wt (u )  wt ( x ) dx 


 x 


u

l 1
l 1
1,0
wl (u)
0,8

10
l
5
0,6
 1, l 
20
 u  w (u) du
l
u  


 1l  u  wl (u) du
0,4
u 0
0,2
u
-2
-1
0
1
2
3
4
5
Häufigkeitsverteilung für die Größte von l normalverteilten Zufallszahlen
wl (u) 
l
 2
e
 1 u2 
1
2 2
l 1

 u  
 
 2 1  erf 
  2  
 
Lineare Fortschrittsgeschwindigkeit


 1, l 

u  wl (u) du

 1l  u  wl (u) du
u 0
u  
 1 , l 
l
 2

 ue
u  0
l 1
2
 1 2u 
1
2

 u  
  du
 2 1  erf 
  2  
 
 1, l  c1 , l   mit c 1, l 
2 l
 2 l 1

z e
z 0
z2
1  erf(z )
l 1
dz
Die Fortschrittsbeiwerte der Komma-Strategie (exakte Werte)
c1,1  0
c1,2
1, l
1

 0,5642

c1,3 
c1,4 
c1,5 
3
2 
6
 
lin
 c1, l  
11 lin  0,40  
 0,8463
 
arctan 2  1,0294
 

5 6
arctan
2

1
 1,1630


2  

1/ 2
Die Fortschrittsbeiwerte der Plus-Strategie (exakte Werte)
c11 
1
 0,3989
2
c12 
1 
1 
1


  0,6810
2 
2
 
c13

1 3 1 1
2


arctan 2   0,8881
 

2 2  2
2

c14
1 1 3 

 
  1,0458
2  2
2
Fortschrittsvergleiche der linearen Theorie
 1,1  0   11
 1, 2  0,828   12
1, 3  0,953   1 3
 1, 4  0,984   1 4

 1, l   1l für l  4
1 3 
 1 4   
   1 1  2,621   1 1
2
2
Parallele und serielle Fortschrittsgeschwindigkeit
parallel
seriell
zurückgele gter Weg

Zahl der Generation en
zurückgele gter Weg

Zahl der Nachkommen
seriell  parallel / l
 14 seriell  1,046  / 4  0,262  
 11 seriell
1

 / 1  0,3989  
2
Text
Ende
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-Polymerase) wird von dem Lebewesen selbst hergestellt. Die Bauanweisung steht irgendwo 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, l)-ES jedem Nachkommen eine andere Kopiergenauigkeit, 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 übertragen. 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ändert 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 Strategievariable  einer Mutation unterworfen wird. Mutationsschrittweiten müssen multiplikativ 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 Aufwand, wenn in einem gegebenen Lebensraum statt mit einem Individuum mit Tausenden von ihnen experimentiert wird. In der Evolution zählt der Fortschritt pro
Generation (parallele Fortschrittsgeschwindigkeit). Ganz anders ist es bei der Anwendung der Evolutionsstrategie auf einem gewöhnliche Computer. Hier müssen
die Nachkommen einzeln nacheinander durchgerechnet werden. Für die Computeranwendung muss die Fortschrittsgeschwindigkeit auf die Zahl der Nachkommen
bezogen werden. Diese serielle Fortschrittsgeschwindigkeit ergibt sich, indem die
parallele Fortschrittsgeschwindigkeit zusätzlich durch l dividiert wird. Nur wenn in
der Zukunft sich die Parallelrechner durchsetzen, ist die biologische Bewertung des
Fortschritts auch bei der Computeranwendung der Evolutionsstrategie richtig.

E1-05Fo7