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.
|