Evolutionäre Algorithmen

Bei evolutionären Algorithmen wird die beste Lösung wird durch eine Art „Evolution“ gewählt. Dabei gibt es mehrere „Generationen“ gleicher Größe, die jeweils immer besser entwickelte mögliche Lösungen enthalten. Um diese Lösungen erhalten zu können, muss das zu erreichende Ziel von Beginn an fest stehen. Somit kann auch eine Bewertung erfolgen, die misst, wie gut eine Loesung diesem Ziel entspricht.

Beispiel

Dieses Beispiel stammt aus dem Buch „Artificial Intelligence: A New Synthesis“ von Nils J. Nilsson.

Ziel: Ein Roboter soll in einen vorgegebenen Gelände einen Weg finden, der an der Wand entlang geht, also nur Zellen an der Wand nutzt.

  • Als Programmiersprache wird in diesem Beispiel LISP genutzt
  • Dabei gibt es die Variablen nw, n, ne, w, e, sw, s und se
  • Ausserdem sind die boolschen Funktionen AND(x,y), OR(x,y), NOT(x) und IF(x,y,z) benutzbar
  • Zur Steuerung gibt es die Aktionen north, east, south und west

Die Bewertung erfolgt durch die „Fitness“ der Lösung:

  • Das Programm wird 60 mal ausgeführt und dabei die Anzahl der besuchten Zellen nah an der Wand gezählt (Maximum: 32)
  • Dies wird zehn mal wiederholt
  • fitness = 320 - erreichbare Wandzellen

Der Evolutionsprozess

  1. Zunaechst werden 5000 mögliche, syntaktisch korrekte, Programme erstellt. Diese stellen die Generation 0 dar
  2. Wir möchten zehn Generationen erzeugen, also fuehren wir zehn mal den Algorithmus durch:
    1.Auswahl von 500 Programmen (10%) in die nächste Generation durch Wählen von sieben zufälligen Programmen und Übernahme des Besten
    2.Erzeugen der anderen 4500 Programme (90%) für die naechste Generation durch Kombination bisheriger Ergebnisse
  3. Danach: Auwahl des besten Ergebnisses

Generationen im Vergleich

Bestes Ergebnis der Generation 0: fitness = 92


Bestes Ergebnis der Generation 2: fitness = 117


Bestes Ergebnis der Generation 6: fitness = 163


Generation 10: Perfektes Ergebnis


Im Grafischen Vergleich wird die Evolution deutlich sichtbar: