« vorheriger Beitrag  · nächster Beitrag »

15.01.10 · 16:20 Uhr

Ein genetischer Algorithmus in Python

Kategorie: Naturwissenschaften  ·  Kommentare: 10

Viele Probleme die man in der Wissenschaft lösen muss, sind so schwierig, dass man sie nicht analytisch in annehmbarer Zeit ausrechnen kann. An dieser Stelle kommen dann oft zufallsbasierte Methoden zum Einsatz. Dazu gehören die Monte-Carlo-Methoden, aber auch eine Klasse von Algorithmen die sich Prinzipien der Evolution zum Vorbild genommen haben. Die bekannteste Art evolutionsbasierter Algorithmen sind die Genetischen Algorithmen. Ich möchte ein einfaches Beispiel für einen Genetischen Algorithmus (GA) zeigen. Diese lassen sich vor allem für Optimierungsprobleme einsetzen, ich habe also immer irgendein Maß des Erfolges meiner Parameter, und möchte dieses möglichst groß machen. Ein einfaches Beispiel wäre es, einen Parameter zu finden, z.B. eine Geschwindigkeit, der die bestmögliche Modellierung einer Messung erlaubt. Dies ist eine sehr häufige Problemklasse, die man mit vielen verschiedenen Mitteln angeht, von denen Genetische Algorithmen nur eine spezielle sind.
Umgekehrt kann man mit Hilfe von Genetischen Algorithmen auch Missverständnisse in der Evolutionstheorie beleuchten, nämlich das Vorurteil dass Zufall alleine keine komplexen Lebensformen hervorbringen kann. Dieses Missverständnis beruht darauf, dass zwar die Mutation in den Genen zufällig ist, aber durch den Selektionsdruck die best-angepassten Individuen überleben. Diese beiden Prinzipien liefern auch die Grundlage für Genetische Algorithmen. Richard Dawkins hat einen GA in seinem Buch "Der blinde Uhrmacher" (ama / sb) verwendet, auch mit einem Beispiel wie ich es hier bringe. Das Buch habe ich aber nicht gelesen, daher weiß ich nicht wie sehr mein Beispiel seinem ähnelt.
Ich habe den Code in Python implementiert, wenn ihr ihn selbst ausführen wollt, ladet ihn hier herunter und führt ihn in der Kommandozeile aus. Für WIndows müsst ihr euch ein Python installieren, z.B. von ActiveState.

Man führt das Programm dann aus mit

python ga.py DIESISTDERSZIELSTRING 500 0.65 0.035 500

Die Eingaben werden jetzt klar, ich benenne nur erst die Parameter:

1. Der Zielstring
2. Die Größe der Population
3. Die Crossover-Wahrscheinlichkeit
4. Die Mutationswahrscheinlichkeit (pro Gen!)
5. Die Anzahl Generationen

Ich will keine Code-Fragmente einfügen, dann lässt sich der Hintergrund besser erzählen. Ich hoffe, der Code ist einigermaßen verständlich geschrieben. Ich werde aber in Klammer Zeilennummern in den Text einfügen. Der Code erzeugt neben Bildschirmausgaben auch noch eine Datei "logging.out" mit viel mehr Informationen, z.B. den Chromosomen aus jedem Lauf und den Crossover-Vorgängen und Mutationen.

Aufgabe

Aber zunächst definieren die Aufgabe für den Algorithmus: Er soll einen Text erraten. Nehmen wir vereinfachend an, dass er nur die Buchstaben a-z enthält und keine Leerzeichen oder Umlaute oder Ziffern. Ignorieren wir weiterhin Groß- und Kleinschreibung. Das ist alles nur zur Vereinfachung und könnte leicht auch berücksichtigt werden.
Den Text, der erraten werden soll, nennen wir den Zielstring, z.B.:
KREATIONISTENSINDDOOF

Was wäre die einfachste Methode, die wir uns denken können? Wir würden zufällig Buchstaben aneinandersetzen, und dann gucken ob wir den richtigen Text haben. Das wäre jetzt das typische Kreationistenverständnis von Evolution: Man würfelt solange bis man genau sein Ergebnis hat. Man sich sich leicht vorstellen, dass das sehr lange dauern kann. Für den obigen Text KREATIONISTENSINDDOOF z.B. wäre die Wahrscheinlichkeit, sie mit einem Wurf zu erhalten (1/26)²¹. Denn einen einzelnen Buchstaben trifft man mit Wahrscheinlichkeit 1:26. Man muss aber 21 Buchstaben auf einmal treffen, also multipliziert man die Wahrscheinlichkeiten. Vergessen wir aber nicht den Selektionsdruck, der die Gene weiterleben lässt, die die beste Anpassung an die Umwelt erlauben. Dieser Schritt wird uns erlauben, schneller zum Ziel zu kommen.

Zwischenbemerkung

Bei diesen Vergleichen zur Evolution darf man einen sehr wichtigen Unterschied zur Natur nicht vergessen: Wenn wir einen Algorithmus ausführen, haben wir eine Richtung. Wir wollen, dass das Ergebnis zu einem bestimmten Ziel führt. Die Natur ist aber nicht zielgerichtet. Es gibt keinen Drang hin zu mehr Komplexität oder eine Leiter der Evolution auf der oben die Menschen stehen. In den Genetischen Algorithmen verwenden man lediglich die Mechanismen der natürlichen Evolution, aber man richtet sie auf ein Ziel. Vergesst diesen Unterschied nicht!

Populationen, Gene, Chromosome, Fitness

Wenn wir schon bei der Evolution abkupfern, formulieren wir doch auch unsere Fachbegriffe in diese Richtung. Ein Chromosom ist eine mögliche Lösung. In unserem Fall ist es die Sammlung von 21 Buchstaben, oder wie lange man den Zielstring auch immer wählt. Jeder der 21 Buchstaben ist ein Gen. Wir beginnen unseren Algorithmus, indem wir völlig zufällige Texte erstellen (Z. 146-161). Wir reihen dazu einfach wahllos Buchstaben aneinander. Soweit liegen wir noch auf der Linie der Kreationisten, aber wir machen das nicht beliebig oft. Wir nehmen nur eine bestimmte, definierte Menge an Chromosomen und nennen das unsere Population. Das ist der zweite Parameter im Programmaufruf. Für jedes Chromosom müssen wir eine Fitness festlegen. Abweichend von der Natur haben wir eine klare Richtung - die Fitness soll maximal werden. Wir können daher ein einfaches Maß für die Fitness finden (Z. 58-72): Wenn ein Buchstabe in einem Chromosom an der richtigen Stelle im Zielstring genauso auftritt, erhöhen wir die Fitness um 1. Die maximale Fitness ist also gleich der Länge des Zielstrings. Im allgemeinen hat man bei Problemen keine klare Vorstellung, wann die Fitness maximal ist. Man kann aber schauen, wie sehr sie sich noch verändert, und wenn sie lange gleich bleibt oder nur wenig besser wird kann man mit einem guten Ergebnis rechnen.

Generationen

Jetzt möchten wir unsere Population von Chromosomen, also einen Zoo von Zufallstexten, von denen manche mehr, manche weniger gut zum Ziel passen, so selektieren dass die besseren eher überleben. Wie in der Natur erzeugen wir neue Generationen von Populationen nach bestimmten Regeln. Dazu "paaren" wir unsere Chromosomen. Dazu brauchen wir zunächst eine Selektion der "Eltern". Es gibt viele Wege für jede dieser Methoden, ich habe die folgende gewählt (Z. 171-180):
Diese Methode funktioniert ganz gut, weil die Fitness ganze Zahlen annimmt. Ich erstelle eine Liste möglicher Eltern, in dem ich zunächst jedes Chromosom einmal in die Liste stecke (jeder soll eine Chance bekommen) und dann noch eine Kopie von jedem Chromosom PRO FITNESS des Chromosoms. Dann wird also ein Chromosom mit Fitness 10 insgesamt 11mal in der Liste stehen. Ein unfittes wird weniger oft drinstehen. Wenn ich jetzt zufällig zwei aus der Liste picke, ist die Wahrscheinlichkeit höher fittere Individuen zu erwischen. Aber trotzdem haben auch die unfitteren noch eine Chance, ihre Gene weiter zu bringen. Das ist ziemlich wichtig, um aus "lokalen Minima" herauszukommen. In unserem Fall kann man einfach sagen: Vielleicht stimmt bei einem Chromosom nur der erste Buchstabe. Wenn aber alle anderen Chromosomen in der Population den ersten Buchstaben falsch haben, ist es trotzdem gut dass eine Chance besteht dass der richtige weitergetragen wird.
Außerdem ist es sehr wichtig für die Weiterverbreitung, den beiden fittesten Chromosomen eine green card zu geben und ihnen einfach Plätze in der nächsten Generation zu reservieren (Z. 182-197).

Crossover

Hat man zwei Eltern gewählt, dann brüten diese zwei Kinder aus (Z. 203). Mit einer Wahrscheinlichkeit, die man als dritten Parameter angibt, kommt es dabei zum Crossover (Z. 205-222). Ich habe in One-Point-Crossover gewählt. Dabei zerschneidet man beiden Chromosomen an einer zufälligen Stelle - aber beide an der gleichen, und setzt dann die Strings neu zusammen, z.B.:

AAAAA|AAAAAAAA Vater
BBBBB|BBBBBBBB Mutter
AAAAA|BBBBBBBB Kind 1
BBBBB|AAAAAAAA Kind 2

Hat der Zufall kein Crossover bestimmt, kopiert man einfach Vater und Mutter in die nächste Generation.

Mutation

Jetzt kommt der Schritt der zufälligen Mutation, der praktisch "frisches Blut" oder vielmehr frische Buchstaben in die Population bringt (Z. 224-245). Der vierte Parameter für das Programm ist die Wahrscheinlichkeit, mit der ein Gen mutiert. Hier verstehen wir unter einer Mutation, dass an einer Stelle zufällig ein neuer Buchstabe eingesetzt wird. Und zwar völlig unabhängig davon, ob dieser Buchstabe eigentlich korrekt war. Hier mag das etwas ineffektiv erscheinen, da man genau das Ziel kennt. Bei allgemeinen Problemen ist der Vergleich mit dem Ziel aber wesentlich schwieriger, daher kann man dort im Allgemeinen gar keine Aussage treffen, ob ein Gen "richtig" ist.
Man geht also für jedes Kind die Gene im Chromosom durch und würfelt einmal eine Zahl zwischen 0 und 1. Ist diese kleiner als die Mutationswahrscheinlichkeit, ersetzt man dieses Gen durch einen zufälligen Buchstaben.
Im Logfile findet man Crossover und Mutation aufgeführt:

DEBUG ## ZXYRPXZWDSNNWLBFSLKGG and OXMOBUCLVJSMPEGHVMEKF breeded ZXYRPXZW|VJSMPEGHVMEKF
DEBUG ## ZXYRPXZWDSNNWLBFSLKGG and OXMOBUCLVJSMPEGHVMEKF breeded OXMOBUCL|DSNNWLBFSLKGG
DEBUG ## Child mutated to ZXYRPXZWVJSMPEGHVMEKF (0 Mutations)
DEBUG ## Child mutated to CXMOQUCLDGNNWLBFSLKGG (3 Mutations)

Auf diese Art brütet man so lange Kinder aus, bis die nächste Generation so viele Mitglieder hat wie die vorhergehende. Auch hier sei wieder bemerkt, dass es alle möglichen Varianten von GA gibt, verschiedene Methoden für Selektion, Crossover, Mutation und Populationsgröße sind beschrieben.

Durchführung

Jetzt haben wir schon alles beisammen, um das Spiel zu starten. Als letzten Parameter sagen wir noch, wie viele Generationen maximal durchlaufen werden. Das Programm läuft entweder so lange, oder bis der Zielstring gefunden wurde. Die Population sollte nicht zu klein gewählt werden, bei einem String von Länge 21 dürfen es ruhig 500 sein. Die richtigen Zahlen zu finden, ist dann die Kunst des Modellierers. Als Crossover-Rate nehmen wir 0.65 (etwas mehr als die Hälfte) und als Mutationsrate 0.035. Diese darf nicht zu groß und nicht zu niedrig sein - ein paar Prozent sind ok.
Schauen wir mal, wieviele Generationen es braucht, um KREATIONISTENSINDDOOF zu finden. Ich könnte jetzt zum Vergleich einen pur zufallsbasierten Algorithmus nehmen und würfeln, bis ich den String habe. Das würde vielleicht Tage dauern - ich hoffe ihr seht ein dass der GA schneller ist.
Von einer initialen Population, die Strings enthielt wie:

KQWHAGQSLQSZDTGPNJXIG
HIVGXYPQDGPAPHNGFXTXW
IQHJIELJRDMJHRYWBHHUJ
MWSAXQGDVOTTCWIUDIFPP

wobei der letzte die beste Fitness hatte - 4 - danach brauchte es 146 Generationen, um den korrekten String zu erhalten. Das Programm gibt für jede Generation eine Info aus:

INFO ## Generation 19:
INFO ## Fittest individual (Values 14/21/7.172000): LREALIONRETEZSINDCOYF
INFO ## Generation 20:
INFO ## Fittest individual (Values 14/21/7.472000): KDEAZIQNITTEZSINDCOYF
INFO ## Generation 21:
INFO ## Fittest individual (Values 14/21/7.508000): KKEXIIONISTHVSINDCOYF
INFO ## Generation 22:
INFO ## Fittest individual (Values 14/21/7.828000): KKEXIIONISTHVSINDCOYF

in der man den fittesten Text sieht. Die Werte sind als erstes die Fitness des besten Text, dahinter die Länge des Textes, also die Zielfitness, und dann die durchschnittliche Fitness der Population, diese sollte im Laufe der Zeit im Schnitt steigen.
Am Schluss dauert es länger - klar, hier muss zufällig der richtige Buchstabe an 1 oder 2 Stellen kommen und dann noch in den "guten" String reinrutschen. Würden wir nicht immer die zwei besten Chromosomen weitergeben, würde das sehr lange dauern.
Schließlich war er erfolgreich:

INFO ## Generation 146:
INFO ## Fittest individual (Values 21/21/12.964000): KREATIONISTENSINDDOOF
INFO ## Success!

Viel Spaß beim Ausprobieren!

Autor: Jörg· 10 Kommentare· Permalink· Trackback-URL

Tags: evolution· genetische algorithmen· informatik· kreationismus· methoden· optimierung· programmierung· python