Verteilte, evolutionäre Optimierung von Schwärmen

Diese Seite beschreibt kurz meine Diplomarbeit und bietet diese zum Download an.

• Diplomarbeit, 8.5MB PDF, 141 Seiten

Die hier downloadbare Diplomarbeitsversion entspricht nicht exakt der Abgabe (z.B. habe ich die Danksagung und Selbstständigkeitserklärung hier weggelassen und die Typographie verbessert).

Kurz gesagt: Ich wollte nicht nur mal Schwarmverhalten simulieren, ich wollte auch eine riesige Evolution drumherum durchführen, so dass das Verhalten von selbst entsteht. Künstlichem Leben beim entstehen zusehen, sozusagen. Das Ganze ist im Grunde eine schöne, bunte, wissenschaftlich angehauchte Techdemo.

Im Rahmen der Diplomarbeit wurde eine universelle Softwareinfrastruktur für die Durchführung von Experimenten zur Schwarmevolution implementiert. Diese Softwareinfrastruktur evolviert Schwarmverhalten nicht nur auf einem Rechner, sondern parallelisiert den Aufwand effizient und robust auf Rechnercluster. Dies ermöglicht große und vielseitige Experimente. Da ich damals noch meinem „alles selbst hinkriegen“-Komplex frönte wurde hierfür ein eigenes Netzwerkprotokoll implementiert.

Gegenüber anderen wissenschaftlichen Experimenten wurde darauf geachtet, die Entstehung biologischen Verhaltens deutlich weniger zu beschränken (z.B. durch Evolution von Aspekten der Sensorik und Aktorik von Schwärmern, freiere Evolution der Kontrollstrukturen und umfangreiche Evolutionen).

Die für die Diplomarbeit geschriebene Software umfasst grob drei Teile (allesamt geschrieben in JAVA), die ich kurz vorstelle:

1. Eine allgemeine Evolutionssoftware mit effizienter Netzwerkverteilung auf viele Rechner
2. Eine Schwarmsimulationsengine, die auf ein Physikframework aufbaut
3. Ein strukturevolvierbares Neuronales Netz.

Zunächst ist festzustellen, dass das Evolutionsframework komplett generalisiert geschrieben wurde. Prinzipiell ist also egal, was genau man evolviert. Dass ich damit danach ganze Schwärme von Lebewesen evolviert habe, ist also nur ein möglicher Einsatzbereich gewesen und ich setze das Framework auch hin und wieder für andere Zwecke ein.

• Es gibt eine einfach bedienbare GUI (Bild rechts).
• Verschiedenste Evolutionsstrategien und Parameter waren zur Laufzeit wähl- und veränderbar.
• Von Haus aus wurde die Verteilung von Evaluation, Mutation und Crossover der einzelnen Lösungskandidaten auf mehrere CPUs unterstützt.

Für große Evolutionen wie die in meiner Diplomarbeit habe ich dann einen eigenes TCP-basiertes Verteilungsprotokoll mit Steuerung durch eigene GUI implementiert (wieder Bild rechts). Die Topologie ist hier zentralisiert: Ein Evolutionsserver und viele Clients.

• Clients konnten sich selbst am Evolutionsserver updaten, damit ich das Protokoll erweitern konnte, ohne alle Clients zu besuchen.
• Jeder Client benchmarkt sich selbst, meldet sich beim Server an, lädt sich JAVA-Klassen des zu evolvierenden Problems herunter und bindet sie ein (der Client weiß ja nicht vorher, was genau evolviert werden wird).
• Der Server stellt diese Klassen zur Verfügung und verteilt „Chunks“ von „Rechenjobs“ an Clients, die entweder Mutationen, Crossovers, oder Evaluationen darstellen konnten.
• Für alle diese Job-Arten wird die durchschnittliche Berechnungsdauer kontinuierlich nachgehalten, bereinigt um die Geschwindigkeiten der Clients.
• Anhand der durchschnittlichen Berechnungsdauer, der Clientgeschwindigkeit, der Geschwindigkeit der Client-Anbindung an den Server und der Latenz der Anbindung des Clients zum Server wird nun entschieden, wie viele Jobs ein Client zugewiesen bekommt. Beispiel: Ein schneller Client mit langsamer Anbindung bekommt viele Jobs auf einmal, um nicht so oft senden zu müssen.
• Das ganze ist natürlich problemanfällig: Clients können ausfallen, einzelne langsame Clients könnten alle anderen warten lassen („Staggers“). Dazu wird nachgehalten, welcher Client gerade was berechnet und wie lange schon, so dass Jobs ggfs. aufgrund von Ausfall oder annormaler Bearbeitungsdauer mehrfach vergeben werden.
• Client-Intern wird eine weitere Verteilung auf mehrere Kerne vorgenommen, falls vorhanden.
• Da Jobs und Rückgabewerte hochrepetitiv sind, wurden diese Daten selbstverständlich direkt im Protokoll komprimiert.

Die Parallelisierung der Evolution war hierbei zu ca. 85%-90% effizient, es wurde also dieser Anteil der zur Verfügung gestellten Rechenkraft tatsächlich genutzt. Hier muss man noch einberechnen, dass der Evolutionsserver relativ schlecht und über eine Standard-Internetverbindung angebunden war (ich musste ihn nehmen, weil ich seine Verfügbarkeit garantieren konnte). Gerade in diesem Zusammenhang ist dieser Wert nicht übel.

Der Schwarmsimulator ist ebenso abstrakt gehalten, so dass verschiedenste Experimente darauf realisiert werden konnten.

• Konkret habe ich einen Aufsatz auf das Physikframework Phys2D geschrieben (heute würde ich ein Framework nehmen, das besser gewartet wird, wie z.B. das verwandte http://www.jbox2d.org/JBox2D). Deswegen sieht es in den Videos so aus, als ob die Schwärmer „schlittschuhlaufen“ . Nichtsdestotrotz hat es aber gut funktioniert.
• Phys2D nutzt intern eine QuadTree-basierte Kollisionsdetektion, die ich für bessere Performance noch leicht angepasst habe. Die Sensorik konnte ich auch einfach auf Kollisionen von „Emittern“ mit „Sensorbereichen“ zurückführen, Occlusions habe ich hier nicht berechnet.

Fehlt noch das strukturevolvierbare Neuronale Netz – das Gehirn der Schwärmer und gleichzeitig das Element, was hauptsächlich durch die Evolution angepasst wurde. Eingaben in das Neuronale Netz sind sensorische Wahrnehmungen der Schwärmer, Ausgaben dann Bewegung, Kommunikationsäußerung, und viel mehr. Alles dazwischen wurde evolviert. Gestartet wird mit einem zufälligen Gehirn.

• Um einfach Synapsen und Neurone hinzufügen, verändern und löschen zu können und jede beliebige Topologie realisieren zu können, habe ich das Neuronale Netz als Adjazenzmatrix repräsentiert.
• Während der Propagierung von Daten kam eine zusätzliche connectivity cache zum einsatz, so dass nicht die ganze Matrix nicht im laufenden Betrieb bemüht werden musste.

Siehe hierzu aber den Abschnitt „Lessons learned“ .

Nach der Implementierungsphase wurde eine Familie von verschiedenen naturinspirierten Evolutionsexperimenten mit Schwärmern und variierenden Umwelten durchgeführt. Evolvierte Schwärme wurden mit Hilfe einer automatisierten Test-Suite einer Vor-Auswertung unterzogen. So konnte vorab entschieden werden, welche evolvierten Schwärmer für die weitere Betrachtung mittels visualisierter Simulation besonders interessant sind und in der Diplomarbeit weiter betrachtet und analysiert wurden. Wie eine Evolution grundsätzlich abläuft und Verhalten entsteht, wird in folgendem Youtube-Video sichtbar.

Im Rahmen der Diplomarbeit wurden zehn Experimente mit insgesamt 100 Evolutionen (10 Evolutionsdurchläufe pro Experiment) durchgeführt und so dargestellt, wie vielfältig Verhaltensweisen sein können, die durch weniger beschränkte Schwarmevolutionen entstehen. Einige davon wurden ausführlich in Text, Bild und Video dokumentiert und analysiert.

Es ist festzuhalten, dass kooperative Mechanismen unter gleichartigen Individuen bei den gegebenen Modellen recht einfach evolvierbar zu sein schienen: In jedem Experiment (sogar vereinzelt in denjenigen Testexperimenten, bei welchen offensichtlich reines Individualverhalten zur Zielerreichung ausreichte) waren Fertigkeiten wichtig für den Schwarm, welche auf Individualebene keinen Sinn machen.

Über die verschiedenen Evolutionen ist eine Fülle an kooperativen Verhaltensweisen entstanden:

• Geburtenkontrolle zum Zwecke der Rationierung vorhandenen Futters,
• ausgeprägtes Markierungs-,
• Aggregations-
• und Explorationsverhalten
• Kommunikationsmechanismen, welche einfacher Art, jedoch für die Funktion des Gesamtschwarms unerlässlich waren

Das sind Verhaltensmerkmale, die in der Natur allerorten beobachtet werden können. Die gezeigten – mithilfe des einfachen, exemplarischen Lebewesens- und Umweltmodells evolutionär entstandenen – Verhaltensweisen stellen das Potential von Experimenten mit freien, umfangreichen Evolutionen eindrucksvoll dar, wie auch folgender Vortragstrailer auf YouTube zeigt.

Zur Evaluation eines jeden Schwarmgenoms wurde eine Simulation mit 70.000 Simulationsschritten eingesetzt. In einer solchen Simulation „lebten“ durchschnittlich ca. 10 bis 50 Schwärmer gleichzeitig in der Schwarmwelt, zuzüglich ggf. tausender passiver Objekte (Futter, Pheromone). Da ein Schwärmerleben nur ca. 10.000 Schritte dauert, wurden während einer Evaluation verschiedene Generationen der Schwärmerpopulation durchlaufen. Pro Evolution wurden 25.000 solcher Evaluationen, also 1,75 * 10^9 Simulationsschritte durchgeführt. Je nach Experiment und vorhandener Anzahl an beteiligten Computern dauerte ein Zehnfachdurchlauf an Evolutionen (also ein Experiment) mit insgesamt 1,75 * 10^10 Simulationsschritten zwischen 12 Stunden und 4 Tagen. Dies entspricht einer effektiven Simulationsgeschwindigkeit zwischen ca. 50.000 und 400.000 durchgeführten Simulationsschritten pro Sekunde – jeweils unter Berücksichtigung physikalischer Gesetze. Zu Spitzenzeiten wurden so um die 100 CPUs gleichzeitig genutzt.

• Mach nicht alles selbst! In Zukunft würde ich das Evolutionsframework, die Parallelisierung auf heterogene Cluster, und vielleicht auch andere Bestandteile vorgefertigt nehmen, und dafür gewisse Kernbereiche, insbesondere effiziente Datenstrukturen, maßschneidern. Aber: Der Weg ist das Ziel, ich habe viel gelernt und meinen Dickkopf ausleben können.
• Algorithmik und Datenstrukturanalyse sind dein Freund! Beispielsweise kam ein nicht zu unterschätzender Anteil des Rechenaufwandes von den Neuronalen Netzen. Darum habe ich für weitergehende Experimente SNIPE gebaut, das by design deutlich besser skaliert. Auf dem Weg dorthin habe ich festgestellt, dass mir die Algorithmik und die Datenstrukturen selbst sehr viel Spaß machen und habe dann das Feld gewechselt. Jetzt mache ich Schwarmverhalten und klassische Algorithmik.
• Die Evolutionsoperatoren waren meiner Meinung nach nicht sehr sophisticated, heute würde ich andere Operatoren und ein anderes Evolutionsverfahren nehmen. Um so überraschender, wie komplex das entstandene Verhalten dennoch ist.
• Wenn es keiner Physik bedarf, kann man einfachere Weltmodelle wählen, z.B. eine Zellenwelt. Das könnte nochmal einen guten Performanceboost geben.