Software-Projekt SW08

- N a v i g a t i o n - - - - - - - -

- VI-ANEC

- Über das Institut

- Software-Projekte

- Hardware-Projekte

- Best-Paper-Best-Program-Awards

- Sponsoring

- Dienste

- Kontakt

Evolutionäre Algorithmen und Zelluläre Automaten (ECA)

Zelluläre Automaten (CA) bestehen aus einer Menge von Zellen, die in einem Gitter angeordnet sind. Jede Zelle besitzt eine Nachbarschaftsmenge von anderen Zellen, sowie eine Menge von Zuständen, welche die Zelle in Abhängigkeit der Zustände der benachbarten Zellen und des eigenen Zustandes im vorangegangenen Updatezeitpunkt berechnet. Dabei verändern alle Zellen gleichzeitig in diskreten Updatezeitpunkten ihren Zustand. Uniforme CA sind dadurch charakterisiert, dass alle Zellen die gleichen Regeln bezüglich der Nachbarschaft und des Updates besitzen, wobei die Updateregeln als ein Programm betrachtet werden können. Bei non-uniformen CA können Zellen unterschiedliche Updateprogramme besitzen, wobei nicht stationäre CA einen Sonderfall darstellen, bei dem eine Zelle im Verlauf der Simulation verschiedene Updateprogramme besitzen kann. Eine CA-FAQ, eine CA-Mailinglist und ein Überblick über Cellular Automata Resources on the Web ist verfügbar. Siehe auch die Datenbank von Ariel Dolan bezüglich CA. Standardliteratur hierzu ist Toffoli & Margolus (1987) und Wolfram (1986).

Darstellungen zum Einsatz von neuen CA-Ansätzen zur Simulation physikalischer Systeme findet sich in Gerhardt & Schuster (1995). Dort zeigt sich, dass das Potential besteht, dass CA gegenüber Differenzialgleichungen einen grossen Effizienzvorteil besitzen, wobei eine hundertfache Beschleunigung in Simulationen möglich ist, um bestimmte chemische und physikalische Phänomene auf einer General-Purpose-Hardware zu simulieren. Durch die Parallelisierbarkeit der Zellen sind Special-Purpose-Implementierungen wie die CAM8 möglich, die eine konstante Ausführungskomplexität bis zu einer maximalen Gittergrösse ermöglichen, wobei eine beliebige Skalierbarkeit möglich wird. Eine maximale Beschleunigung ergibt sich, wenn neben der Parallelisierung das Updateprogramm direkt durch die Hardware ausgeführt wird, unabhängig ob es sich um ein entsprechendes ASIC oder eine FPGA handelt. Beispielsweise wird im Rahmen des CAM-Brain-Projektes von de Garis geplant, ein spezielles CA durch FPGAs zu implementieren, um damit ein vernetztes, hierarchisches System wachsender Neuronaler Netze zu erzeugen, d.h. eine Form von komplexem Gehirn zu erzeugen.

Das erste Ziel dieses ECA-Projektes ist die Integration einer Zellulären Programmiersprache (cellular programming language CPL) in die internet-basierte EA-Entwicklungsumgebung, die im Software-Projekt SW01 entwickelt wird. Ausgangsbasis soll eine Untersuchung der CPL in existierenden CA-Systemen sein, die als Source verfügbar sein müssen (siehe hierzu den Überblick "Software for CA" oder Worsch (1997)). Jedem Prozessorknoten des verteilten Systems kann eine Population oder ein einzelnes CA zugeordnet werden, das lokal den oder die Simulationsläufe durchführt, und Evaluationen durchführt. Die CPL soll so flexibel sein, dass verwandte Ansätze wie Lattice Gas Automaton (LGA), Coupled Map Lattices (CML), Continuous spatial CA (CSCA) oder Voronoi-CA (siehe MOSAIC) ebenfalls beschrieben werden können.

Die Anwendung evolutionärer Algorithmen kann in Verbindung mit einer CPL auf unterschiedlichen Ebenen erfolgen. In kontinuierlichen Modellen beispielsweise können durch ES Systemparameter optimiert werden, was ein Einsatz eines EA innerhalb der CPL darstellt. Weiterhin können CA-Beschreibungen durch ein GP- oder allgemein durch ein HP-System erzeugt werden (siehe Software-Projekt SW02), die im Bezug auf ihre Simulationseigenschaften evaluiert werden, was ein Einsatz von EA ausserhalb der CPL darstellt. Die Kombination bzw. Integration beider Ansätze ist dann möglich, wenn CA-Beschreibungen durch ein GP-System verwendet werden, in denen Parameter enthalten sind, die durch einen anderen EA spezifiziert werden.

Ein Szenario im Zusammenhang mit dem Software-Projekt SW01 besteht in der Nutzung einer GP/HP-Anwendung auf einem Server, die in einer CPL CA-Individuen erzeugt. Diese werden an lokale Clients über das Internet verteilt, auf denen Compiler die CA-Individuen auf die lokal vorhandene Hardware optimieren. Wie weiter unten noch dargestellt wird, existieren mehrere Bezüge zu dem Hardware-Projekt HW01, wobei die Compilierung für die vielen parallelen Register eines Graphikprozessors einen Kompromiss bezüglich der Effizienz und der Verfügbarkeit der Hardware darstellt. Auf dem lokalen Client werden die CA-Simulationsläufe durchgeführt, aus denen ein Evaluationswert ermittelt wird, der an den Server geliefert wird, und der damit die Selektion sel(N) zur Übernahme in die Nachfolgepopulation bzw. -populationen der CA-Individuen organisiert.

Die prinzipielle Problematik, die mit ECA verbunden ist, ist die Tatsache, dass es sich um ein Simulationsproblem handelt, d.h. zur Evaluation eines uniformen Updateprogrammes wird mindestens ein CA-Simulationslauf benötigt, d.h. es muss eine bestimmte Anzahl von globalen Updates durchgeführt werden. Im günstigsten Fall kann dann der Endzustand des CA mit einem Sollzustand verglichen werden, während in anderen Fällen die gesamte Entwicklungsgeschichte des CA in die Evaluationsfunktion einbezogen werden muss. Nicht-stationäre non-uniforme Ansätze besitzen die grösste Flexibilität, sind aber auch am schwierigsten zu handhaben, d.h. zu evaluieren, da die Entwicklungsgeschichte des CA für die Evaluation herangezogen werden muss.

In den meisten Fällen ist die Evaluation eines ECA eine sehr aufwendige Operation, was die Unterhaltung einer CA-Population zu einem sehr ressourcenintensiven Unterfangen macht. Als ein Hauptziel des ECA-Projektes sollen somit Strategien entworfen und getestet werden, wie man mit diesem Ressourcenproblem umgehen kann, wenn als Zielsetzung die Erzeugung von CAs angestrebt wird, mit denen komplexe, physikalische und chemische Phänome simuliert werden können, d.h. wenn als Aufgabe das "inverse CA-Problem" gestellt ist, bei dem lokale Updateprogramme für ein bekanntes globales Verhalten gesucht wird (siehe Worsch (1997:1)).

Werden mehrere Simulationsläufe notwendig, um ein CA-Individuum zu evaluieren, so wird durch den Simulationaufwand ein erster Ressourcen-Constraint erzeugt. Die Art der CPL ist hierbei entscheidend, da eine Interpretersprache zu langsam ist, sodass zumindest ein Compiler für die CPL vorliegen muss, der in dem internetbasierten System lokal auf den Rechnerknoten, oder zentral auf dem EA-Server liegt, und CA-Individuen in einen Maschinencode umwandelt, der auf den verteilten Rechnerknoten abgearbeitet wird. Denkbar wäre auch der Einsatz von CPG/CHP-Systemen, welche direkt Updateprogramme als Maschinencode für verteilte Rechnerknoten erzeugen.

Das wesentlich schwierigere Problem betrifft jedoch die Evaluierung der CA-Individuen in Abhängigkeit von der jeweiligen Aufgabenstellung. Grundlage hierfür ist die Beantwortung der Frage, was es bedeuten soll, wenn ein CA einen Phänomenbereich erfolgreich simulieren soll. Dies entspricht der Definition einer geeigneten Evaluationsfunktion. Wie oben erwähnt ist der Vergleich zweier Endzustände des Gitters die einfachste Definition einer solchen Evaluationsfunktion, wobei dies jedoch noch nicht die Festlegung der notwendigen Distanzmetrik zwischen den beiden Gitterzuständen beinhaltet. Komplexe Phänomenbereiche benötigen viele solche fitnes-cases, d.h. es wird eine Menge von Anfangs- und Endzuständen als Sollbeispiele definiert, die durch Messung extern ermittelt werden, oder die durch ein anderes Modell wie z.B. die numerische Lösung von Differenzialgleichungen ermittelt werden, wenn das Ziel darin besteht, ein CA zu finden, das den Phänomenbereich, der durch die Differenzialgleichungen beschrieben wird, effizienter durch ein CA zu beschreiben. Physikalische oder chemische Phänomenbereiche sind zumindest prinzipiell Messungen zugänglich, wenn man vom Problembereich der Messung in der Quantenphysik absieht, sodass hier der Bereich des Aktiven Lernens und des Optimal-Experiment-Designs eine wesentliche Rolle spielen kann, wenn eine Menge von fitnes-cases sequentiell festgelegt wird, mit denen die Evaluationsfunktion progressiv erzeugt wird. D.h. Aktives Lernen wird in diesem Zusammenhang als eine Form der progressiven Evaluationsumgebung interpretiert, mit der es gelingt, die Gesamtevaluationskosten im Generationsverlauf zu beschränken bzw. zu optimieren.

Der einfachste Ansatz einer progressiven Evaluierungsumgebung im Zusammenhang mit einer ECA ist durch die Gittergrösse zu erreichen, d.h. es wird eine wachsende Gittergrösse im Generationsverlauf erlaubt, sodass grössere und komplexere Phänomenbereiche modelliert werden können. Die Begrenzung der Anzahl der Befehle in einem Updateprogramm, sowie die schrittweise Erweiterung der erlaubten Anzahl ist ein weiterer Ansatz einer progressiven Vorgehensweise.

Dieses ECA-Projekt besitzt mehrere Bezüge zu dem Hardware-Projekt HW01, bei dem spezielle Hardware-Architekturen auf ihre Eignung zum Einsatz von EA geprüft werden. Zum einen könnten existierende CA-Hardware-Architekturen darauf geprüft werden, wie gut evolutionäre CA darauf entwickelt werden können. Z.B. ist CAM8 eine programmierbare Special-Purpose-CA-Hardware, die eine grosse Anzahl von CA-Typen modellieren kann. Andererseits sind moderne Graphikprozessoren darauf optimiert, zwei- und drei-dimensionale Operationen parallel auszuführen, sodass sich diese Architekturen zur Simulation von CA gut eignen dürften, was in besonderer Weise für SIMD-Architekturen wie FUZION 150 von PixelFusion oder C-RAM-Architekturen gilt.

Die Grundlage der analogen, elektronischen, evolutionären Hardware von Adrian Thompson besteht darin, den Taktgenerator konventioneller, d.h. digitaler FPGAs auszuschalten. In Verbindung mit programmierbarer Special-Purpose-CA-Hardware wie der CAM8 könnte geprüft werden, ob durch ein ähnliches Vorgehen ein analoges System erzeugt werden kann, das durch EA konfigurierbar ist. Sollte dies mit der Architektur von CAM8 nicht gelingen, so könnte nach alternativen CA-Architekturen gesucht werden, die mit einem Taktgenerator eine programmierbare Special-Purpose-CA-Hardware darstellen, ohne Taktgenerator aber eine analoge EHW mit einer sehr grossen Anzahl von rekonfigurierbaren Building-Blocks, da jede CA-Zelle im analogen System als Building-Block verstanden werden soll.

EHW-Verfahren können umgekehrt genutzt werden, um CA-Architekturen zu erzeugen, die auf bestimmte Anwendungsfelder optimiert sind, bzw. die Definition eines CA, die durch einen Software-EA erzeugt wurde, wird auf eine parallele Hardware-Architektur abgebildet. Eine solche nochmals spezialisierte Architektur, die nicht mehr programmierbar ist, besitzt weitere Effizienzvorteile im Vergleich zu einer programmierbaren Special-Purpose-CA-Hardware wie CAM8. Beispielsweise könnte eine CA-Hardware implementiert werden, die auf die Simulation von Luftströmungen in einem bestimmten Geschwindigkeitsintervall spezialisiert ist, sodass dieser CA zur evolutionären Optimierung von Flugzeugteilen oder Düsen eingesetzt werden kann, was als ES-Applikation Ende der 60er Jahre durch Rechenberg am Anfang der Entwicklung dieses Forschungsbereichs stand (siehe Rechenberg (1973)).

Die Implementierung der CAM-Brain-Architektur mit ihren speziellen CA-Updateregeln zum Wachstum von Neuronalen Netzen in einer FPGA-Architektur ist ein weiteres Beispiel (de Garis), wobei hier die interne Programmierbarkeit durch die Verwendung von FPGAs anstatt fest verdrahteter ASICs erhalten bleibt.

Gerhardt, Martin; Schuster, Heike: Das digitale Universum. Vieweg Verlag, 1995.

Rechenberg, Ingo: Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Stuttgart, 1973.

Sipper, Moshe: Evolution of Parallel Cellular Machines: The Cellular Programming Approach. Springer-Verlag, Heidelberg, 1997.

Toffoli,Tommaso; Margolus, Norman: Cellular Automata Machines. MIT Press, London, 1987.

Wolfram, S. (editor): Theory and Applications of Cellular Automata. World Scientific Publishing, Singapore, 1986.

Worsch, Thomas: Programming Environments for Cellular Automata. Lehrstuhl Informatik für Ingenieure und Naturwissenschaftler, Universität Karlsruhe, Mai 1997.