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”:http://www.amazon.de/gp/product/3423344784?ie=UTF8&tag=disra-21&linkCode=as2&camp=1638&creative=19454&creativeASIN=3423344784 / “sb”:http://shop.scienceblogs.de/der-blinde-uhrmacher,oD72RtJm4cyTNWqX,i) 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”:http://www.activestate.com/activepython/.

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:

# Der Zielstring
# Die Größe der Population
# Die Crossover-Wahrscheinlichkeit
# Die Mutationswahrscheinlichkeit (pro Gen!)
# 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)21. 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!

Kommentare (10)

  1. #1 Christian A.
    01/15/2010

    Der Eintrag gefällt mir 🙂

    Evolutionäre Algorithmen sind schon ziemlich cool. Es begeistert mich einfach, dass man inspiriert von der Beobachtung der Lebewesen Algorithmen ableiten kann, die so einiges schaffen. Mir ist da letztes Jahr ein Artikel untergekommen
    Schmidt, M. and Lipson, H. : Distilling Free-Form Natural Laws from Experimental Data (2009), Science 324
    Wo die Autoren einen evolutionären Algorithmus geschrieben haben, um die Gesetze/Formeln zu generieren, die Beobachtungen in Form von Zeitreihen erzeugen. Ist schon ziemlich cool, wenn mir der Algo die Formel für ein Doppelpendel ausspuckt 🙂

  2. #2 matthias
    01/15/2010

    Ich würde das eigentlich gar nicht so eng sehen, dass man in diesem Algorithmus – im Gegensatz zur Natur – das Ziel schon vorgegeben hat. Denn eigentlich ist das ja auch hier eine Ausnahme. Normalerweiße kennt man das Ziel ja gerade nicht, wenn man einen Algorithmus schreibt, der irgendwas berechnen soll, sagen wir mal die Nullstellen irgendeiner Funktion (sonst ist das ja eigentlich sinnlos).
    Aber das könnte man ja ganz ähnlich lösen. (ein x ist umso fitter, je kleiner |f(x)|, und Papa x und Mutter y brüten ein Kind z = a*x+(1-a)*y aus, mit einem zufälligen a (0

  3. #3 Odysseus
    01/15/2010

    Schön, dass du deine kleine Pythonserie nicht ganz vergessen hast. Hier gibt es Dawkins, und sein Programm (ab 4:40, aber das ganze Video ist sehenswert) sieht ganz ähnlich aus wie deins.

  4. #4 Christian A.
    01/15/2010

    @matthias: Da würde man wohl leicht mal in einem lokalen Minimum landen, da dürfte man gut draufrauschen müssen, um das zu umgehen 🙂

  5. #5 matthias
    01/17/2010

    @Christian A
    Für die lokalen Minima gibts ja noch eine (nicht zu kleine) Mutationsrate 😉 Und manchmal verheddert sich die Evolution halt in einer Sackgasse, und eine Art stirbt aus :-
    Aber man müsste schon wirklich Pech haben, dass die ganze Population in einem lokalen Minimum gefangen bleibt (und OK, zur Nullstellensuche verwendet man wohl im Normalfall eher keinen genetischen Algorithmus…). Jedenfalls braucht man das Ziel gar nicht explizit vorgeben.

  6. #6 KMic
    01/18/2010

    Schöner Eintrag, vielen Dank!

  7. #7 Chupacabra
    01/21/2010

    Ich finde genetische Algorithmen nicht so toll. Sie lassen sich nur in den einfachsten Fällen analysieren. Ich meine damit, dass man zur Zeit lediglich für einfachste bis triviale Probleme zeigen kann, dass ein gen. Algorithmus mit einer bestimmten Wahrscheinlichkeit eine Lösung findet, oder dass er dafür durchschnittlich eine bestimmte Zeit braucht. Im allgemeinen kann man bestenfalls über einen konkreten gen. Algorithmus sagen, dass er sich in einem konkreten Einsatz in der Praxis bewährt hat (woran man das auch immer festmacht).

    Was mich persönlich auch ein wenig ärgert ist, wenn man sich erst gar nicht die Mühe macht, für ein bestimmtes Optimierungsproblem nach einem effizienten Algorithmus (sei es auch ein Approximationsalg.) zu suchen, sondern sofort auf irgendwelche Heuristiken, wie genet. Verfahren, zurückgreift.

    Zu der Analogie der Evolutionstheorie: Wie gesagt, für gen. Algorithmen können wir nur in den einfachsten Fällen sagen, was »hinten rauskommt« und »wie schnell« das sein wird. Unter diesem Aspekt finde ich es daher fast lächerlich, wenn (wie ich finde) behauptet wird, die Evolutionstheorie sei zum größten Teil verstanden. Und noch merkwürdiger finde ich es, wenn so getan wird, als ob jeder Mensch durch ein wenig Überlegung sofort einsehen müsste, dass die ET stimmt.

  8. #8 Jörg
    01/21/2010

    @Chupacabra:

    In der Realität ist eine Methode die sich bewährt wunderbar. Die wenigstens Anwendungen werden hingehen und spezielle Algorithmen entwickeln sondern auf bestehende Methoden anwenden. GAs kenn ich jetzt nicht, aber ich kann mir nicht vorstellen dass man da nicht auch Allgemeines zum Konvergenzverhalten beweisen kann. Und die Realität sieht eben so aus, dass man ein Optimierungsproblem dann eben mal loslaufen lässt und schaut was rauskommt. Da geht keiner hin und beweist vorher das Laufzeitverhalten. Ich denke, dass sich wesentlich schlimmere Argumente gegen GAs finden lassen, wie die Schwierigkeiten die korrekten Varianten für alle Mechanismen auszuwählen.

    Ich habe im Artikel auch mehrfach drauf hingewiesen, dass GAs nicht direkt mit der Evolution verglichen werden dürfen, sondern nur Mechanismen borgen. Sehr wohl kann man damit aber die Argumente bezüglich Wahrscheinlichkeiten der Kreationisten widerlegen.
    Ich habe vor allem mehrmals darauf hingewiesen, dass Evolution ungerichtet ist. Argumente bezüglich Laufzeitverhalten und Ergebnis sind 100% irrelevant für den Erfolg der Evolutionstheorie.
    Ich weiß auch nicht was es heißen soll, dass die Evolutionstheorie verstanden ist. Wenn überhaupt, kann nur die Evolution verstanden sein. Die Theorie, die diese erklärt, ist höchst erfolgreich und von begnadeter Schönheit und Faszination. Die Evolutionstheorie ist die Große Vereinheitlichte Theorie. Ich hoffe, dass eines Tages in der Physik eine GUT gefunden werden kann, die an Schönheit und Eleganz an die Evolutionstheorie heranreicht. I

  9. #9 Chupacabra
    01/21/2010

    Die wenigstens Anwendungen werden hingehen und spezielle Algorithmen entwickeln sondern auf bestehende Methoden anwenden.

    Ich habe nicht das Gegenteil »gefordert«. Heuristiken bzw. GA sind aber i. A. die schlechteste Methode. Eine Schlussfolgerung der Art »Heute ging’s gut, also wird es morgen vermutlich auch so sein.« kann für bestimmte Zwecke ausreichend sein. Für andere Zwecke ist es aber wichtig zu verstehen, was der Algorithmus berechnet und insbesondere wann er versagt, und welche Ressourcen er verbraucht. Und genau das kann man für GA praktisch nicht angeben.

    GAs kenn ich jetzt nicht, aber ich kann mir nicht vorstellen dass man da nicht auch Allgemeines zum Konvergenzverhalten beweisen kann.

    Wie gesagt, soweit ich weiß, nur für Trivialfälle.

    Und die Realität sieht eben so aus, dass man ein Optimierungsproblem dann eben mal loslaufen lässt und schaut was rauskommt. Da geht keiner hin und beweist vorher das Laufzeitverhalten.

    Mit Realität meinst du sicherlich den praktischen Einsatz. Zu meiner Realität zähle ich aber auch die wissenschaftliche Arbeit der theoretischen Informatik, die sich mit Optimierungsproblemen beschäftigt. Und da wird eben nicht mal so geschaut, was rauskommt.

    Ich weiß, dass in der Praxis häufig schnell Heuristiken eingesetzt werden, anstatt das Problem genauer zu analysieren. Das ist es ja, was mich persönlich ein wenig ärgert. Denn oft lässt sich nämlich ein konkretes praktisches Problem auf ein allgemeines reduzieren, für das es effiziente Algorithmen gibt. Aber es würde mich nicht wundern, wenn ein ausgebildeter Informatiker auf die Idee kommen würde, ein Navigationsgerät zu entwerfen, dass die kürzeste Route mit Hilfe genetischer Algorithmen berechnet.

    Zur ET: Ich gebe zu, ich habe mich missverständlich ausgedrückt. Mit »…wenn (wie ich finde) behauptet wird« meinte ich nicht deinen Beitrag, sondern so was wie den gesellschaftlichen Konsens, wie ich ihn wahrnehme.

    Ich weiß auch nicht was es heißen soll, dass die Evolutionstheorie verstanden ist. Wenn überhaupt, kann nur die Evolution verstanden sein.

    Mit »die Evolutionstheorie verstehen« meine ich quasi-logisch begründen können, dass Evolution zu höheren Wesen führt. Ich finde, dass oft so getan wird, als ob das möglich ist. Als Nichtbiologe wundert mich das, weil wir Informatiker eben nicht mal für einfachste genetische Algorithmen Aussagen logisch ableiten können.

  10. #10 Ralf
    10/04/2010

    Ich finde das Beispiel nicht sonderlich gelungen, da die Fitnesfunktion sehr zielsicher zum gewünschten Ergebnis führt. Es gibt ja in jeder Dimension (Position in der Zeichenkette) nur genau einen wert der Volle Punktzahl gibt. Es gibt also gar keine lokalen Extremwerte, da es zu jeder Zeit möglich ist eine Dimension zu finden bei der man durch Änderung in den Nachbarwert die gleiche oder eine bessere Fitness erhält.

    Besser wäre m.E nur Punkte für korrekte Silben o.ä. zu vergeben. Oder wird zumindest richtig aus den jeweiligen Teilmengen Konsonanten und Volkale gewählt, so gibt es für die Position die Hälfte der Punkte.

    Jedenfalls irgendeinen Einfluss in der Bewertungsfunktion, der dazu führt, dass es wirklich lokale maxima gibt.