Von Mäusen und Füchsen

Das im folgenden beschriebene Programm habe ich im Rahmen des Seminars "Künstliches Leben" an der Universität Potsdam entwickelt. Das Thema lautete:

"Genetische Algorithmen und evolutionäre Programmierung"
(oder so ähnlich)

Füchse und Mäuse krabbeln auf einem diskreten endlichen Universum (x-y-Gitter) von Punkt zu Punkt und Füchse fressen Mäuse - tragisch, aber so ist das eben.

Ziel ist es, eine (quasi-) stabile Versuchs-Population zu erzeugen. Es muß also auf lange Zeit hin ein dynamisches Gleichgewicht zwischen Füchsen und Mäusen entstehen. Genauer gesagt sollte ein Räuber-Beute-Schema entstehen - derart, daß sich die Anzahl von Mäusen und Füchsen ähnlich wie sin(x) und sin(x+pi/2) verhalten. Die unabhängige Variable x ist hier die Zeit, die in diskreten Schritten voranschreitet und im folgenden durch "Tage" umschrieben wird. Als Optimierungs-Verfahren kommt ein genetischer Algorithmus zur Anwendung, welcher nach geeigneten Spezies-Kombinationen sucht. Stirbt eine Maus- oder Fuchs-Spezies aus, gilt der Versuch als gescheitert, denn das bedeutet, dass dieses Paar an Spezies nicht gemeinsam überlebensfähig war. Die Mäuse würden zwar ohne die Füchse prima zurecht kommen - das ist aber nicht der Sinn der Sache. Eine Spezies wird über einen Parameter-Vektor verändert, der folgende Eigenschaften definiert:

• Bewegungsgeschwindigkeit
• Höhe des maximal aufnehmbaren Energievorrates
• Energiewert, den jedes Tier pro Tag verbraucht
• maximales Lebensalter
• mittlere Anzahl der Geburten pro Individuum
• mittlere Anzahl der Nachkommen pro Geburt

Ferner definiert das Programm eine Anzahl von Konstanten, die weitere Eigenschaften bestimmen. Z.B. verringert sich die Überlebenswahrscheinlchkeit von Mäusen und Füchsen in dem Maße, wie sie sich ihrem maximalen Lebensalter annähern. Speziell ist auch fest definiert, wie weit Mäuse und Füchse "sehen" können und welche Entscheidungen sie in Konflikt-Situationen treffen. Mäuse müssen z.B. häufig die Frage Fressen oder flüchten? beantworten.

Füchse können Mäuse fressen und Mäuse ernähren sich von "Pflanzen", an denen sie herumknabbern und die sich dann nach und nach wieder regenerieren. Mäuse verhungern also, wenn sie nicht ihren Aufenthaltsort ändern und zu neuen "Weiden" wandern. Ebenso verhungern Füchse, wenn sie nicht durch das Universum streifen und so die Wahrscheinlichkeit erhöhen, dass ihnen Mäuse über den Weg laufen, die sie fressen können. Jedes Tier verfügt über einen "Energievorrat", der einen bestimmten Pegel nicht unterschreiten darf. Tritt dieser Fall trotzdem ein, stirbt das Tier an Energiemangel - es verhungert. Für beide Spezies ist ein maximales Lebensalter festgelegt. Wird es erreicht, stribt das Tier. Beide Spezies können Kinder in die Welt setzen. Allerdings nur auf Punkte des Gitters in der direkten Nachbarschaft der "Mutter", die gerade unbesetzt sind.
Mäuse und Füchse können "sehen". Sie nehmen ihre direkte Nachbarschaft wahr und einen Teil der etwas weiter entfernten Gitterpunkte. Entsprechend ihrer Umwelt treffen Sie eine Entscheidung für ihren nächsten Aufenthaltsort. Wenn eine Maus einen Fuchs wahrnimmt, flüchtet Sie, auch wenn Sie gerade hungert. Eine Maus läuft vor einem Fuchs davon, indem Sie einen Sprung in die entgegengesetzte Richtung macht, aus der der Fuchs kommt. Ist der Zielpunkt besetzt, ist dieser Bewegungsversuch gescheitert und die Chance steigt für den Fuchs, in die direkte Nachbarschaft der Maus zu gelangen. Hungert eine Maus, versucht sie sich zu einer Pflanze mit höherem Energievorrat zu bewegen. Ist nichts Lohnendes für Mäuse und Füchse in Reichweite, machen sie einen Schritt in eine zufällige Richtung - der Nase nach. Frißt ein Fuchs eine Maus, erhält er deren Energievorrat, setzt aber eine Weile (50 Tage) aus, um die Maus zu verdauen. Ein mißlungener Angriff kostet einen Fuchs einen Teil seiner Energie. Jede Bewegung und jeder Bewegungsversuch kostet Energie. Nachkommen erzeugen kostet Energie und eine Ruhepause wird auch verordnet.

Der Evolutions - Algorithmus:
Zuerst muß klar zwischen zwei Populations-Begriffen unterschieden werden.
Die Versuchs-Population ist einfach die Menge der zu einem bestimmten Zeitpunkt "lebendigen" Füchse und Mäuse. Alle Füchse einer Versuchs-Population besitzen identische Eigenschaften. Gleiches gilt für die zu einem bestimmten Zeitpunkt lebendigen Mäuse.
Ein beliebiger Fuchs- und eine beliebige Maus aus der Versuchs-Population stellen gemeinsam im Sinne des Evolutions-Algorithmus ein Individuum dar. Ebenso im Sinne des Evolutions-Algorithmus' ist die Population damit die Menge der zu einem bestimmten Zeitpunkt von der Software gespeicherten Individuen - also die Menge aller Paare von Maus-Fuchs-Typen.
Aus jedem Individuum wird eine Versuchs-Population erzeugt. Die ursprüngliche Versuchs-Population für jeden dieser Versuche wird per Zufall generiert. Dabei wird eine Anzahl von Füchsen und Mäusen mit ebenfalls per Zufall ermittelten Lebensaltern in die Welt gesetzt und aufeinander losgelassen.
Solange alle Individuen scheitern, erfolgt über Selektion, Mutation und Rekombination der vorhandenen und bisher erfolglosen Individuen die Erzeugung einer neuen Population - also einer veränderten Menge von Paaren von Fuchs- und Maus-Typen.
Der Versuch gilt als erfolgreich, wenn der Algorithmus "hängt", wenn also keine der beiden Spezies der Versuchs-Population ausstirbt.
Die Fitness-Funktion ergibt sich aus der Anzahl der Tage, die ein Individuum überlebt.

Die Animationen und Diagramme im Anschluß zeigen den Überlebenskampf von zwei durch den genetischen Algorithmus gefundenen Spezies-Paaren im Zeitraffer. In den Diagrammen sind die Versuchs-Populationsstärken der beiden Spezies über der Zeit dargestellt. Dabei ist das erhoffte Räuber-Beute-Schema klar zu erkennen (auch im zweiten Diagramm: Das große Zeit-Intervall führt dort lediglich zu einer starken horizontalen Stauchung der Kurvenverläufe).
Die Darstellungen haben mit dem eigentliche Evolutionsalgorithmus nichts zu tun, denn die eigentliche Aufgabe des Programmes ist es, einen Fuchs- und einen Maus-Typ (blau und rot) mit solchen Eigenschaften zu finden, daß sich eine quasi-stabile Versuchs-Population entwickelt.
Aber schön bunt sind sie.