10.3.4 Eleks
Das Konzept der genetischen Algorithmen wurde in den 60er Jahren von John M. Holland an der Universität von Michigan entwickelt und hat in der Informatik eine gewisse Bedeutung bei der näherungsweisen Lösung von ansonsten nur schwer oder gar nicht lösbaren Problemen erlangt. Dabei wird eine Menge von zunächst völlig ungeeigneten Lösungen auf ein Problem angesetzt. Neue Lösungen züchtet man durch Verpaaren der besten alten Lösungen und durch kleine Veränderungen in den bestehenden Lösungen (Mutationen).  Früher oder später tauchen Lösungen auf, die besser sind als ihre Vorgänger; diese werden dann bevorzugt weitergezüchtet.
Diese Aufgabe befasst sich mit einem sehr einfachen Problem, das aber schon einen recht guten Einblick in die Vorgehensweise bei der Problemlösung durch genetische Algorithmen liefert.  Man stelle sich eine Art Ur­Ozean vor, die Ursuppe, in der eine Zahl primitiver Lebewesen, Eleks genannt, lebt. Die Lebensbedingungen in der Ursuppe sind ständigen (aber periodisch wiederkehrenden) Veränderungen unterworfen, die die Eleks möglichst gut vorhersagen müssen, wenn sie überleben wollen.
In dieser Ursuppe werden die sich ändernden Lebensbedingungen durch eine Folge von Nullen und Einsen symbolisiert.  Die Chromosomen der Eleks stellen einen endlichen Automaten dar, der auf die Eingaben aus der Ursuppe reagiert und Ausgaben produziert, die ebenfalls aus Nullen und Einsen bestehen.  Stimmt nun eine Ausgabe mit der darauffolgenden Eingabe aus der Ursuppe überein, so hat das Elek eine Änderung der Lebensbedingungen korrekt vorhergesagt. Die Eingaben aus der Ursuppe wiederholen sich periodisch (z. B. alle sechs Zyklen).  Kann ein Elek eine Folge von einhundert Eingabesymbolen richtig vorhersagen, ist es ein perfekter Hellseher und die Evolution (oder Zucht) der Eleks hat ihren Höhepunkt erreicht.
Wie arbeitet nun der endliche Automat eines jeden Eleks? Ein endlicher Automat besitzt eine endliche Zahl verschiedener Zustände. Ein Eingabesignal bewirkt, daß er in einen anderen Zustand übergeht.  Unsere Elek­Automaten erzeugen außerdem bei jeder Eingabe ein Ausgabesymbol. Endliche Automaten lassen sich auf verschiedene Arten darstellen, z. B. als Übergangstabelle oder als Übergangsdiagramm.  Die Übergangstabelle für einen endlichen Automaten mit den drei möglichen Zuständen A, B und C, der mit Nullen und Einsen als Signalen arbeitet, paßt gerade in eine Tabelle vom Format drei mal vier.  Zu jedem Zustand des Automaten und zu jedem möglichen Eingabesymbol gibt es zwei Einträge.  Der erste ist das entsprechende Ausgabesymbol, der zweite der Zustand, in den der Automat übergeht:

Zustand
Eingabesymbole
 
0
1
0
1
 
Vorhersage
Folgezustand
Vorhersage
Folgezustand
A
1
B
1
C
B
0
C
0
B
C
1
A
0
A

Ein Beispiel: Wenn sich der durch diese Tabelle repräsentierte Automat gerade im Zustand C befindet und eine Eins empfängt, so wird er eine Null vorhersagen und in den Zustand A übergehen.
Die Darstellung der Eleks als "Genmuster" ist eine Verkettung der Felder. Also für das Beispiel: "1B1C0C0B1A0A".
Wenn nun das eben beschriebene Elek (ausgehend vom Zustand A) auf eine Ursuppe mit der Eingabefolge 0111000010110 angesetzt wird, reagiert es mit der Ausgabe 1000011001000. Dabei gibt jedes Ausgabesymbol an, welche Eingabe das Elek als nächstes erwartet.  Die Trefferquote in diesem Beispiel liegt bei 50%, ist also nicht höher als bei einfachem Raten.  Sehr viel besser schneidet es allerdings ab, wenn die Ursuppe eine sich ständig wiederholende Folge von 010011 liefert. 
Je größer die Zahl der Zustände eines Eleks, desto länger darf die sich wiederholende Sequenz von Eingabesymbolen sein, die irgendwann einmal vorhersagbar ist. So ist für eine Menge von Eleks mit vier Zuständen eine Eingabefolge der Periode vier oder sechs gar kein Problem, während es bei einer Periode der Länge acht schon sehr lange dauern kann, bis ein perfekter Hellseher auftaucht. Mit steigender Zahl der Zustände wird die Zahl der möglichen verschiedenen Eleks immer größer und die Wahrscheinlichkeit immer geringer, daß der perfekte Hellseher schon bald auftritt.
Nun zum Aufbau des Programms Ursuppe.
  • Es wird eine Klasse "Elek" definiert.
  • Bei jedem Zyklus durchläuft jedes Elek eine Folge von 100 Umweltsymbolen einer bestimmten Periode.  Die sich immer wiederholende Folge der Symbole wird beim Programmstart per Zufall oder durch Tastatureingabe festgelegt. Beim Durchlaufen der 100 Symbole wird jedes Symbol mit der letzten Ausgabe des Eleks verglichen und bei einem Treffer ein Zähler für das betreffende Elek erhöht.
  • Hat irgendwann eines der Eleks einen Zählerwert von 100, bricht das Programm ab; der perfekte Hellseher ist gefunden.
  • Nach jedem Test aller vorhandenen Eleks werden das beste und das schlechteste Elek bestimmt.
  • Anschließend kommt es zu einer Mutation. Das sieht so aus, daß an Hand zweier Zufallszahlen zwei beliebige Eleks ausgewählt und verändert werden. An Hand einer Zufallszahl b wird der mutierte Teil des Gens gewählt. Ist b gerade (Vorhersage), wird zum Gen 1 addiert, das Ergebnis modulo 2 genommen und wieder an der ausgewählten Stelle gespeichert. Ist b ungerade (Folgezustand), d.h. zum Gen wird 1 addiert und das Ergebnis modulo der Zahl der möglichen Zustände genommen.
  • Zuletzt wird noch bestimmt, ob eine Paarung zweier Eleks stattfinden soll.  Das sollte nicht zu oft geschehen, da sonst das beste Elek rasch die gesamte Population mit seinen Genen überschwemmt und die Evolution weitgehend zum Stillstand kommt. Am besten nimmt man hier wieder eine Zufallszahl und stellt fest, ob sie unterhalb einer bestimmten Grenze liegt, durch eine bestimmte Zahl teilbar ist oder ähnliches. Wahrscheinlichkeiten von 1:5 bis 1:25 für die Paarung sind gute Richtwerte; der Experimentierfreudigkeit sind hier aber keine Grenzen gesetzt. Die Paarung selbst läuft so ab, daß zunächst zufällig ein Elek ausgewählt wird, das nicht das beste und nicht das schlechteste sein darf. Nun wird durch zwei Zufallszahlen, die Indizes in die Gensequenz darstellen sollen, ein Chromosomenstück des besten Eleks ausgewählt.  Eine Kopie dieses Stückes wird einer Kopie des ausgewählten Eleks an der gleichen Stelle eingesetzt (Crossing­Over). Das neu entstandene Elek ersetzt nun das bisher schlechteste Elek.
  • * Das Programm soll alle n Zyklen die Nummer, die Trefferquote und die Chromosomen des gerade besten Eleks ausgeben.  Dadurch läßt sich der Fortgang der Evolution gut verfolgen. Zum Austesten des Programms sollte man zu Beginn n=1 setzen und eventuell alle Eleks ausgeben.  Die Zahl der Eleks, die Anzahl der Zustände, die Länge der Periode und optional noch die Paarungsrate sollen dem Programm als Parameter auf der Kommandozeile übergeben werden.  Es darf davon ausgegangen werden, daß maximal 100 Eleks, zehn Zustände und 20 sich wiederholenden Eingabesymbole verlangt werden.  (Bei vier Zuständen und einer Periode von vier oder sechs, mit denen man das Programm testen sollte, reichen zehn Eleks.)