Startseite  
     
  Ingo Rechenberg

Zur 1. Vorlesung Evolutionsstrategie I:  Das ES-Kalkül und die "Insel der Krebse"

  A u f   d e m   W e g   z u   e i n e r   e v o l u t i o n s s t r a t e g i s c h e n   A l g e b r a
 

Verbale Beschreibung

Schreibweise im ES-Kalkül

  Am Anfang steht das Verfahren von "Versuch und Irrtum" (Trial-and-Error-Verfahren): Ein momentaner Zustand wird zufällig abgeändert. Bei Erfolg wird er beibehalten, bei Misserfolg zurückgenommen.
     
 

Das Trial-and-Error-Verfahren lässt sich evolutionsbiologisch deuten: Ein Elter erzeugt einen mutierten Nachkommen. Nachkomme plus Elter gelangen in eine Selektionsurne. Das bessere Individuum überlebt und wird Elter der neuen Generation.

(1 + 1) - ES

     
  1. Schritt zur genaueren Evolutionsnachbildung: Es gibt m Eltern, von denen ein zufällig gewählter einen Nachkommen erzeugt. Nachkomme plus Eltern gelangen in die Selektionsurne. Die m besten Individuen werden selektiert und zu Eltern der neuen Generation.

( m + 1) - ES

     
  2. Schritt zur genaueren Evolutionsnachbildung: Die m  Eltern erzeugen in zufälliger Folge l  Nachkommen. Aus der Vereinigungsmenge werden die m besten Individuen ausgelesen und zu Eltern der neuen Generation erklärt.

( m + l) - ES

     
  3. Schritt zur genaueren Evolutionsnachbildung: Die Eltern haben eine begrenzte Lebenszeit und gelangen nicht in die Selektionsurne (Komma statt Plus). Die m Besten der l Nachkommen werden zu Eltern der neuen Generation erklärt.

( m , l) - ES        (l > m )

     
  4. Schritt zur genaueren Evolutionsnachbildung: Durch sexuelle Fortpflanzung wird nur ein r-tel der Erbinformation auf einen Nachkommen übertragen. Ist r = 2 (Biologie), müssen 2 Eltern aus dem Pool gezogen werden um einen Nachkommen zu erzeugen.

( m /r , l) - ES

     
  Ein Exponent g an der runden Klammer kennzeichnet, wie oft der Evolutionszug durchgeführt werden soll. Man beachte, dass die in einer Klammer selektierten Individuen als Eltern zu Beginn der nachfolgenden Klammer erscheinen. Damit besteht die Möglichkeit, in der ausgeschriebenen Form Populationswellen zu erzeugen.

( m , l) g - ES

(2 , 6)4 = (2 , 6) (2 , 6) (2 , 6) (2 , 6)

     
  Der Faktor l' vor der runden Klammer besagt, dass die Runde-Klammer-Operation l' mal durchgeführt wird. Im rechten Beispiel laufen 3 Evolutionen 9 Generationen lang parallel. Das ergibt einen Sinn, wenn am Ende z.B. die 2 besten Populationen (Klammern) ausgelesen werden und zu Elternpopulationen erklärt werden.

l' ( m , l) g - ES

3 (2 , 8)9 = (2 , 8)9 + (2 , 8)9 + (2 , 8)9

     
  Die Auslese von m' Eltern-Populationen, die wieder l' Nachkommen-Populationen (Gründerpopulationen) erzeugen, führt zur geschachtelten Evolutionsstrategie. Die algebraische Schreibweise zeigt eine Strategie in einer Strategie. Die geschachtelte ES ist die zurzeit leistungsfähigste Form einer Evolutionsstrategie.

[m' , l' ( m , l) g ] g'- ES

     
  Tatsache ist, dass die biologische Evolution eine ähnliche hierarchisch geschachtelte Struktur erkennen lässt.

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

     
  Die Science-Fiction-Erzählung "Insel der Krebse" von Anatolij Dnjeprow aus dem Jahre 1958 inspirierte die Entwicklung der Evolutionsstrategie in der simplen Form der (1 + 1)-ES. Nach 40 Jahren hat sich aus dem Schema "Jeder gegen Jeden" der Algorithmus der geschachtelten Evolutionsstrategie entwickelt. Die in der Erzählung geschilderte Entwicklung "hin zu einem Riesenkrebs, der seinen Schöpfer umbringt" könnte bei einer geschachtelten ES nicht passieren.

Anatolij Dnjeprow: Insel der Krebse

     
 
 

 

Ingo Rechenberg

Zur 2. Vorlesung Evolutionsstrategie I:  Logik der Experimentierens  -  Starke Kausalität

   

  

  Wir experimentieren, weil uns das Verhalten der Welt nicht a priori durchsichtig ist. Die Kybernetik beschreibt die Situation bildhaft durch einen "Schwarzen Kasten": An Aktionspolen (rote Punkte) handeln wir, an Reaktionspolen (gelbe Punkte) beobachten wir das Ergebnis. Aktionspole sind Schalter, Schiebevorrichtungen, Drehlager, Variable in einem Computerprogramm usw.

   

 

  Die Dreiteilung des Versuchsobjekts "Schwarzer Kasten" in Aktionspole, unsichtbare innere Struktur und Reaktionspole enthält drei mögliche Fragestellungen des Experimentators an das Versuchsobjekt.

 

   

    

 

1. Frage an das Versuchsobjekt:

WAS Ist die Reaktion auf eine vorgegebene Aktion? Forschungsziel ist die Sammlung von Daten über das Objektverhalten. Die Frage: "Was kann man in Erfahrung bringen" steht am Anfang einer jeden empirischen Forschung im wissenschaftlichen wie im technischen Bereich.

   

 

 

2. Frage an das Versuchsobjekt:

WARUM ist die Reaktion auf eine Aktion in der beobachteten Weise erfolgt? Forschungsziel ist, eine erklärende Beschreibung des Aktions-Reaktions-Mechanismus. Der Forscher sucht nach einem Modell, das die innere Struktur des schwarzen Kastens gut simuliert. Die Frage: "Warum kommt dieses oder jenes Phänomen vor" ist Ausgangspunkt der wissenschaftlichen Grundlagenforschung.

   

         

 

3. Frage an das Versuchsobjekt:

WOMIT (durch welche Aktion) kann eine vorgegebene Reaktion erhalten werden? Forschungsziel ist in diesem Fall, das Versuchsobjekt derart zu verändern, dass eine gewünschte Wirkung erreicht wird. Die Frage: "Womit kann man eine bestimmte Wirkung erzielen" ist das Hauptproblem der technischen Entwicklung.

   

 

  Der Experimentator glaubt an ein "vernünftiges" Verhalten des Versuchsobjekts. Unvernünftig wäre, wenn bei derselben Aktion stets eine andere Reaktion aufträte. Kein Experiment ließe sich verifizieren: Das Kausalitätsprinzip "gleiche Ursache, gleiche Wirkung" wäre verletzt. Unvernünftig wäre aber auch ein Verhalten, bei dem die kleinste Änderung der Ursache zu einer riesigen Wirkung führt. So zeigt das Säulendiagramm rechts, dass in der Nachbarschaft einer x-y-Einstellung die Reaktion (Säulenhöhe) völlig willkürlich ist. Das Kausalitätsprinzip ist zwar erfüllt, aber es ist wenig wert. Das im Säulendiagramm  gezeigte Eingangs-Ausgangs-Verhalten wird deshalb schwach kausal genannt.

     
  Vernünftiges Eingangs-Ausgangs-Verhalten wird starke Kausalität genannt. Eine kleine Änderung der Ursache führt zu einer kleinen Änderung der Wirkung. Im Säulendiagramm: Säulen ähnlicher Höhe ballen sich zusammen. Das ist ein Normverhalten der Welt. Wer sich ein Tasse Kaffee eingießt baut auf dieses Normverhalten: Die Kanne etwas mehr geneigt und der Kaffeestrom erhöht sich etwas und umgekehrt.

     
  In einer nicht kausalen oder schwach kausalen Welt lässt sich nicht vernünftig agieren. Strategien (so auch die Evolutionsstrategie) arbeiten auf einer Weltordnung. Eine universelle Weltordnung ist die starke Kausalität.

   

 

 
 

 
 

Ingo Rechenberg

Zur 3. Vorlesung Evolutionsstrategie I:  Vier elementare Suchstrategien

   

 

  Gegeben ist ein abgegrenztes x-y-Suchfeld. Ein Experimentator stochert mit einer gelben Stange nach der optimalen Lösung; das ist der für ihn unsichtbare Berggipfel. Nachfolgend werden vier elementare Gipfelsuchstrategien beschrieben.

   

 

 

1. Globale deterministische Suche

Der Experimentator teilt die x- und y-Achse in m diskrete Abschnitte. Dann durchwandert er systematisch die m mal m Felder. Jede Verbesserung (Stangenverlängerung) wird als x-y-Position neu notiert. Der Experimentator benötigt zum Finden des Optimums:

          Für 2 Dimensionen     G = m 2   Versuche

          Für n Dimensionen     G = m n  Versuche

   

 

 

2. Globale stochastische Suche

Der Experimentator erinnert sich an die Mutationstheorie von Darwin und erwürfelt die zu vermessenden diskreten Einstellungen.

1  Versuch:    Ziel getroffen  w = 1/m 2

1  Versuch:    Ziel nicht getroffen  w = 1 - 1/m 2

2  Versuche:  Ziel nicht getroffen  w = (1 - 1/m 2) 2

G Versuche: Ziel nicht getroffen  w = (1 - 1/m 2) G

G Versuche: Ziel getroffen  w = 1 - (1 - 1/m 2) G

Nach G aufgelöst (m >> 1): G = - m 2 ln(1 - w)

Um das Ziel mit einer Wahrscheinlichkeit von w = 0,95 zu treffen benötigt der Experimentator:

     Für 2 Dimensionen     G » 3 m 2   Versuche

     Für n Dimensionen     G » 3 m n   Versuche

     
 

3. Lokale deterministische Suche

Der Experimentator besitze drei gleich lange Stangen. Die 1. Stange steckt er am momentanen Standpunkt in den Boden, die 2. Stange einen Schritt nach x und die 3. Stange einen Schritt nach y versetzt. Auf die drei Stangen legt er eine Platte. Sind die Schritte klein, zeigt die Platte, in welche Richtung der Berg maximal ansteigt. In diese Gradientenrichtung bewegt er sich um den Linearitätsradius d  bergan.

Wir definieren für die lokale Suche eine lokale strategische Güte, die Fortschrittsgeschwindigkeit j:

  Für 2 Dimensionen   jgrad = d / 3

  Für n Dimensionen   jgrad = d / (n + 1)

     
 

3. Lokale stochastische Suche

.  .  . 

   

                                   

 
 

 
 

Ingo Rechenberg

Zur 4. Vorlesung Evolutionsstrategie I:  xxx

 

 

 

 

 

 

 
 

 

 
   

---------

     
   

 

     
 

     
   

 

     
   

 

     
   

 

 

 

Ingo Rechenberg

Zur 5. Vorlesung Evolutionsstrategie I:  xxx

   

   

     
   

 

     
 

 

 

 
 

 
 

Ingo Rechenberg

Zur 6. Vorlesung Evolutionsstrategie I:  xxx

   

 

     
 

 

 

   

 

 

 

 

   
 
 
 

 

 

 
 

 
 

Ingo Rechenberg

Zur 7. Vorlesung Evolutionsstrategie I:  xxx