Eprobots JS Dokumentation

Dokumentation

Einleitung

Eprobots JS ist die Simulation einer zweidimensionalen Welt, die von Individuen bevölkert ist (Eprobots), welche sich bewegen, Nahrung aufnehmen, sich fortpflanzen und sterben. In der Welt wird kontinuierlich Energie, bzw. Nahrung verteilt. Pro Simulationsschritt können sich die Eprobots einen Schritt in eine von acht Richtungen bewegen oder stehen bleiben.

Diese Steuerung kann auf unterschiedliche Weise realisiert werden, zum Beispiel durch einen Zufallszahlengenerator. Bei Eprobots JS erfolgt die Verhaltenssteuerung über interne sogenannte OISC-Programme die in jedem Simulationsschritt ausgeführt werden. Dieses Programm stellt das Genom dar und wird von Generation zu Generation mit einem Mutationsfaktor weitergegeben. Initial bzw. wenn keine Individuen mehr vorhanden sind, werden neue Individuen mit zufällig generierten Programmen erzeugt.

OISC

Für die genetische Programmierung kam die Frage nach der „Programmiersprache“. Nach Recherchen bin ich auf den OISC (One Instruction Set Computer) gestoßen. Es ist ein Computermodell, das nur einen einzigen Befehl mit drei Parametern kennt, damit allerdings alle Fähigkeiten eines „normalen“ Computers hat, also Turing-vollständig ist. In den Programmen müssen so keine Befehle kodiert werden, sie brauchen nur Adressen und Werte zu enthalten. Außerdem kann ein Interpreter für solche Programme mit ein paar Codezeilen auskommen. Um mehr valide Programme, bzw. Programme erzeugen zu können, die tatsächlich etwas tun und nicht sofort abbrechen, werden nicht-negative Adresswerte in jedem Fall auf eine vorhandene Adresse gemappt (mittels Modulo mit der festen Programmlänge).

Es gibt verschiedene Implementierungsvarianten. Ich habe mich für diese entschieden: subleq (Subtract and branch if less than or equal to zero). Der OISC ist mächtig genug, dass man theoretisch mit ihm alle anderen „höheren“ Befehle, zum Beispiel Multiplikation, zusammenbauen kann. Dies geschieht natürlich auf Kosten der Anzahl der Befehle und somit auch der Laufzeit/Effizienz der Programme. Es gibt auch einen C-Compiler, der OISC-Code erzeugen kann (A Simple Multi-Processor Computer Based on Subleq).

Evolutionäre Programmierung

Mit Computerprogrammen kann man Lösungen für Probleme finden. Man kann mit dem beschriebenen Interpreter und einem gegebenen Problem aber auch versuchen Programme zu finden, die das Problem lösen.

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

Zusammenfassung:

• Programme zufällig initialisieren
• Fitness bewerten (Testmethode die aussagt wie gut das Programm das Problem löst)
• Die besten dürfen sich reproduzieren (alternativ: die besten dürfen sich mit höherer Wahrscheinlichkeit reproduzieren)
  • Kind erhält Kopie des Elternprogrammes mit Mutation einzelner Speicherzellen
• zurück zum Punkt „Fitness bewerten“ mit den Individuen der neuen Generation oder Abbruch, wenn ein bestimmter Fitnesswert erreicht wurde

Beispielproblem: Programm mit Schrittlänge 300

Erzeuge ein Programm, welches nach 300 Schritten terminiert. Ein subleq-Programm terminiert, 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. Beim meinen Versuchen kamen nach ein paar Generationen tatsächlich Programme, die z.B. 300 Programmschritte „lang“ sind.

Beispielspielproblem mit Ein- und Ausgabe: Zahlen quadrieren

Möchte man Programme haben die zum Beispiel Zahlen quadrieren, dann braucht man dafür Ein- und Ausgabe. Ein-/Ausgabe kann man realisieren, indem man einfach Speicherzellen als Eingabespeicher und/oder Ausgabespeicher definiert.

Beispielsweise verwendet man die gleiche Zelle für die Eingabe wie auch die Ausgabe. Zu Berechnung des Fitnesswertes müssen verschiedene Eingaben „angelegt“ werden, damit sichergestellt ist, dass die Eingabe auch tatsächlich mit der Ausgabe korreliert und im Testbereich korrekt ist. Zum Berechnen der Fitness wird das Programm dafür zum Beispiel zehn mal ausgeführt, wobei in die Eingabezelle vor jeder Ausführung die aktuell zu testende Zahl geschrieben wird (0 bis 9). Nach jeder Ausführung wird getestet, ob 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 im Testbereich „quadrieren“ konnten. Es war nur leider keine allgemeine Lösung: Das Ganze funktionierte über eine Tabelle mit Konstanten, auf die indirekt adressiert wurde. Die Konstante wurde dann zum Eingabewert dazu addiert und fertig war das Quadrat.

Eprobots JS

Modell/Simulation

Wie in der Einleitung beschrieben wird eine zweidimensionale Welt simuliert, in der Individuen mit einem Lebenszyklus leben und kontinuierlich Nahrung verteilt wird. Die Simulation soll gut visualisiert werden können und möglichst in „Echtzeit“ ausführbar sein. Die Welt ist torusförmig, man kann sich unendlich lange in eine Richtung bewegen. In dieser simulierten Welt ist die Evolution offen, es gibt keine genau vorgegebenen Fitnesskriterien, außer zu überleben. Erfolgreiches Verhalten setzt sich durch.

Jeder Eprobot hat in jedem Simulationschritt die Wahl entweder stehen zu bleiben, oder in eine der acht Richtungen zu gehen, sofern dies das Feld begehbar ist. Individuen gleicher Art nehmen sich gegenseitig als Hindernis war. Geht ein Eprobot auf ein Feld auf dem sich ein Energieobjekt befindet, nimmt der Eprobot das Energieobjekt auf und versucht umgehend sich fortzupflanzen, bzw. sich zu „teilen“. Das funktioniert nur, wenn sich neben dem Eprobot mindestens ein freies Feld befindet.

Nahrungsverteilung

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.

Steuerung mit OISC

Zur Steuerung werden die oben beschriebenen OISC-Programme eingesetz und ausgeführt. In jedem Simulationsschritt wird das OISC-Programm eines Eprobots ausgeführt und der Wert der letzten Speicherzelle wird als Steuerwert verwendet. Es gibt neun Möglichkeiten der Bewegung (inklusive „nichts tun“). Um mehr Programme zu erhalten, die etwas tun, wird der Wert modulo 9 genommen.

Fortpflanzung/Mutation

Anfangs werden Programme erzeugt, die den oben erwähnten Steuerwert nicht verändern. Das führt dazu, dass die Individuen sich nicht oder nur stur in eine Richtung bewegen, also auch keine oder wenig Nahrung aufnehmen, sich also auch nicht fortpflanzen und sterben. Irgendwann wird ein Individuum mit einem Programm erzeugt, welches ein komplexeres Bewegungsmuster generiert und mit dem es mit höherer Wahrscheinlichkeit auf Energieobjekte trifft. Es kann sich fortpflanzen und vererbt sein Programm an seine Nachkommen. Somit setzt sich dieses Verhalten/Bewegungsmuster durch, wobei es durch Mutationen evt. weiter optimiert wird.

Fossilien

Nach der aktiven Phase werden die Eprobots zu „Fossilien“. Die Fossilien sind einfache Hindernisse für die aktiven Eprobots. Die aktiven Eprobots sind rot. In der Darstellung erhalten die Fossilien eine andere Farbe und verändern diese in Wert und Helligkeit mit fortschreitender Zeit. Nach einer einstellbaren Zeit verschwinden auch die Fossilien. Letztendlich verändern die Eprobots so ihre Umwelt durch ihr eigenes Verhalten indirekt selbst.

App

Mit dem Button „Start“ wird die Simulation gestartet und gestoppt. Um eine Welt mit anderen Dimensionen zu initialisieren kann der Button „Reset simulation“ verwendet werden.

Settings

Durch die Einstellung „sleeptime“ wird die maximale Anzeigedauer eines Simulationsschrittes bestimmt, wodurch eine konstante Framerate erreicht werden kann.

Die Oberfläche stellt Controls für die Settings bereit, die während der Simulationslaufzeit geändert werden können. Es gibt Parameter wie Lebenszeit der Eprobots (lifetime), Aufenthaltsdauer der Fossilien (Fossiltime), Gesamtenergiemenge (Object_count).