Home | Dokumentation | Anleitung | Galerie

Eprobots - Evolutionarily Programmed Robots

Ich habe mich wieder mit künstlicher Evolution beschäftigt, weil ich das Thema ziemlich spannend finde. Diesmal geht es aber eher um die Evolution von Verhalten. Einfaches Verhalten ist programmierbar, also habe ich mir gedacht, dass es interessant wäre Programme zu evolvieren, anstatt nur irgendwelche Parameter. Also Evolution mit Hilfe von genetischer Programmierung. Dabei herausgekommen ist eine 2D-Simulation einer Welt, die von Kreaturen bevölkert ist, welche sich aufgrund ihrer Programmierung bewegen, Nahrung aufnehmen, sich fortpflanzen und sterben. In der Welt wird Energie, bzw. Nahrung verteilt, was evt. mit Pflanzen vergleichbar ist. Die Kreaturen, bzw. "Eprobots" können auch ihre Umgebung wahrnehmen, bzw. "sehen" und haben ein "Gedächtnis". Zusätzlich wird eine Nahrungskette oder "Räuber-Beute-Beziehung" simuliert. Zuerst entstehen einfache Kreaturen, welche die Pflanzen fressen, dann aber auch Kreaturen, welche die Kreaturen fressen usw.

OISC - One Instruction Set Computer

Für die genetische Programmierung kam die Frage nach der "Programmiersprache". Nach Recherchen bin ich auf den OISC gestoßen. Es ist ein theoretischer Prozessor, der nur einen einzigen Befehl mit drei Parametern kennt. Dieser Befehl heißt subleq (subtract and branch unless positive). Dieser Prozessor kann emuliert werden, er kann subleq-Programme ausführen und Ein-/Ausgabe-Verarbeitung auf seinem Speicher durchführen. Die Programme bestehen nur aus Zahlen (z.B. Integer), wie in jedem anderen Assembler auch, aber es müssen keine Befehle kodiert werden, weil der subleq-Befehl mächtig genug ist, dass man mit ihm alle anderen einfachen Assembler-Befehle zusammenbauen kann. Sogar ein C-Compiler ist so realisierbar.

Genetische Programmierung

Das Prinzip ist jetzt, solche Programme anfangs zum Beispiel mit Hilfe eines Zufallsgenerators erzeugen zu lassen, sie auszuführen und die "Fitness" zu testen. Als "Fitness" könnte z.B. definiert sein, dass das Programm 300 Programmschritte durchlaufen soll, bis es terminiert. Terminieren tut es, wenn z.B. das Programmende erreicht ist, oder auf eine negative Speicheradresse referenziert wird. Die Programmgröße ist fest definiert. Wenn man zum Beispiel einen Speicher mit 30 Werten definiert, kann das Programm zehn Befehle enthalten. Wenn es linear durchlaufen würde, benötigte es also nur zehn Schritte, statt 300. Das heißt zur Lösung der Aufgabe bräuchte man eine Art For-Schleife.

Solche Programme lassen sich "heranzüchten", in dem man die Programme als Individuen betrachtet, von denen sich die "besten" vermehren und ihr "Erbgut", also ihre Programme auf die Nachkommen übertragen. Dabei nimmt man z.B. 100 zufällig erzeugte Anfangsindividuen, führt sie aus und bewertet sie. Die Bewertung ist umso höher, je näher die Programmschrittanzahl am Ziel liegt. Die besten 10% könnte man sich jetzt "fortpflanzen" lassen. Dabei wird eine neue Generation von Individuen erzeugt. Jetzt kommt natürlich die Evolution in's Spiel, in dem man mit einer gewissen Wahrscheinlichkeit Kopierfehler erlaubt. Das könnte so aussehen, dass man mit einer Wahrscheinlichkeit von 1% zu einem Programmwert eine Zufallszahl addiert. Dadurch entsteht zwar viel "Müll", also funktionsuntüchtigere Programme, aber auch tauglichere Exemplare. Von dieser Generation nimmt man wieder die besten 10% und nach ein paar Generationen bekommt man tatsächlich Programme, die z.B. 300 Programmschritte "lang" sind.

Ein-/Ausgabe kann man realisieren, indem man die erzeugten Programme einfach um Werte erweitert und diese Werte für einen selbst als Eingabewerte und oder Ausgabewerte deklariert. Beispielsweise erweitert man die Programme um einen Wert und schreibt in diesem Wert vor einer Ausführung die Zahlen von 0 bis 9. Man führt das Programm also zehn mal aus und testet nach jeder Ausführung, wie "gut" der Eingabewert nach der Ausführung quadriert ist. So könnte man sich ein Programm züchten, welches quadrieren kann. Durch Tests habe ich interessante Exemplare gefunden, die tatsächlich quadrieren konnten, aber nur genau die Zahlen, die ich zum Testen vorgegeben hatte :-) Das Ganze funktionierte dann ziemlich abgefahren über eine Tabelle mit Konstanten, auf die indirekt adressiert wurde. Die Konstante wurde dann zum Eingabewert dazu addiert und fertig war das Quadrat.

Eprobots

Prinzip

Um der ganzen Sache mehr Dynamik zu geben, wollte ich das ganze in einer gut visualisierbaren Simulation von "Zellen" bzw. "Robotern" verwenden, die in einer zweidimensionalen Welt "leben", eine begrenzte Lebenszeit haben und etwas "fressen" müssen, um sich fortzupflanzen. Es gibt eine Gesamtenergie, die konstant gehalten wird. Die tatsächliche Energiemenge setzt sich zusammen aus der Anzahl der Individuen und der Anzahl der Energieobjekte. Anfangs gibt es keine Individuen, also wird die Gesamtenergie in Form von Energieobjekten auf dem Feld verteilt. Später kommen Individuen dazu. Ist die aktuelle Energiemenge in einem Simulationsschritt kleiner als die definierte Gesamtenergie, z.B. wenn Energieobjekte gefressen werden, werden vor dem nächsten Simulationsschritt neue Energieobjekte verteilt. Individuen gleicher Art nehmen sich gegenseitig als Hindernis war. Die Welt ist torusförmig, man kann sich unendlich lange in eine Richtung bewegen. Sie kann aber auch durch Hindernisobjekte eingeschränkt werden. In dieser Zellularautomaten-Welt ist die Evolution so offener, es gibt keine genau vorgegebenen Fitnesskriterien, außer zu überleben.

Am Anfang werden ebenfalls zufällig generierte Individuen erzeugt. Die Individuen enthalten aber auch die oben erwähnten Programme. Das Programm wird vor jeder Ausführung mit einem Ausgabewert erweitert und ist mit "0" vorbelegt. Mit diesem Wert wird das Individuum "gesteuert". "0" bedeutet "nicht bewegen", "1" bedeutet "nach links oben bewegen" usw. (acht verschiedene Bewegungsrichtungen + "nicht bewegen"). Das Programm jedes Individuum wird in jedem Simulationsschritt ausgeführt.

Anfangs werden Programme erzeugt, die den oben erwähnten Steuerwert nicht verändern. Das führt dazu, dass die Individuen sich nicht bewegen, also auch keine Nahrung aufnehmen, sich also auch nicht fortpflanzen und sterben. Irgendwann wird ein Individuum mit einem Programm erzeugt, welches z.B. immer nach rechts geht, weil z.B. eine "5" bei jedem Simulationsschritt auf den Steuerwert kopiert wird. Dadurch bewegt sich das Individuum und mit hoher Wahrscheinlichkeit trifft es auf ein Energieobjekt, kann sich fortpflanzen und vererbt sein Programm an seine Nachkommen. Somit setzt sich dieses Verhalten durch.

Erweiterungen

Sehfeld

Ein weiterer Schritt bestand darin, dass die Programme der Individuen nicht nur "blind" Werte ausgeben, sondern auch auf Eingabe reagieren sollen. Dazu habe ich die Umgebung, also z.B. die acht Nachbarfelder ebenfalls in das Programm beim Erweitern eingeblendet. Diese Werte werden den Programmen zur Verfügung gestellt, bevor sie ausgeführt werden. Was links oben ist, steht z.B. immer an Speicherstelle x1, was oben ist an Speicherstelle x2 usw. Befindet sich an der entsprechenden Stelle nichts, steht an der Adresse eine "0", ist dort ein Hindernisobjekt befindet sich an der Adresse eine "1" usw. ("2" = Energieobjekt, "3" = Anderes Individuum). Man kann die Individuen tatsächlich beobachten, wie sie auf Ihre Umgebung reagieren, also in Abhängigkeit der Eingabewerte unterschiedliche Ausgabewerte erzeugen. So könnte wahrscheinlich auch ein Programm entstehen, was im Grunde ein künstliches neuronales Netz repräsentiert. Das Programm kann durch den Output (Bewegung in der Welt) seinen eigenen Input (aktuelle Umgebung) beeinflussen.

Gedächtnis

Die Programme werden nach jeder Ausführung wieder in ihren Ursprungszustand versetzt, falls sie z.B. ihr eigenes Programm verändert haben sollten. Es wären ja sonst auch selbstmodifizierende Programme möglich, aber ob das in diesem Fall so schlimm wäre, ist eine andere Frage. Jedenfalls werden die Programme zusätzlich zu den oben beschriebenen Erweiterungen noch um "persistent memory" erweitert. Werte die dort stehen, bleiben über die gesamte Lebensdauer des Individuums erhalten. Dieser Speicherbereich funktioniert so wie eine Art Gedächtnis. Beim Fortpflanzen des Individuums wird dagegen immer nur das Kernprogramm vererbt. Mit dem Gedächtnis könnten auch theoretisch Programme geschrieben werden, die nicht nur direkt auf Eingaben reagieren, sondern sie könnten auch Zustände speichern und so komplexeres Verhalten zeigen. Zum Beispiel könnten sich die Programme "merken", dass sie irgendwo gegen gestoßen sind und deshalb jetzt dauerhaft in die andere Richtung laufen. Viele Möglichkeiten bis zu Schwarmverhalten wären so denkbar. In der Simulation machen einige Individuen nach einigen Generationen tatsächlich Gebrauch vom Gedächtnis. Vor allem ist das interessant, weil Sie auch diese Möglichkeit erst mal "herausfinden" müssen, genau wie auch die Position der Ein-/Ausgabewerte.

Räuber-Beute-Beziehungen

Um das Ganze etwas spannender zu gestalten, habe ich noch einen weiteren Aspekt in die Simulation eingeführt. Mit einer einstellbaren Wahrscheinlichkeit wird beim Fortpflanzen nicht ein weiteres Individuum der eigenen Art erzeugt, sondern ein Individuum, welches sich von der "Elternart" ernährt. Das Individuum ist dann quasi ein "Fleischfresser" und kein "Pflanzenfresser" mehr. Die neue Art erhält eine andere Farbe. Die Fleischfresser erzeugen mit einer gewissen Wahrscheinlichkeit wieder neue Fleischfresser, die sich von den anderen Fleischfressern ernähren usw. Dies ist eine einfache Nahrungskette und kann sich theoretisch beliebig hochschaukeln. Das Ganze ist nur durch den zur Verfügung stehenden Raum und die Gesamtenergie begrenzt, kann aber auch künstlich eingeschränkt werden.