Software-Projekt SW01

- - - - - - - -
Internet-basiertes, verteiltes EA-System für hybride Architekturen	Ziel dieses Software-Projektes ist der Entwurf und die Open-Source-Implementierung eines auf Internet-Technologien basierten, verteilten EA-Systems, das mit derart flexiblen Datenstrukturen ausgerüstet ist, dass eine Umsetzung einer grossen Bandbreite von Einzel-Algorithmen, Hybriden und Systemen möglich wird. Hierzu gehören neben den klassischen vier EA-Bereichen ES, EP, GA und GP die strukturell verwandten Algorithmen des Simulated Annealing SA bzw. die Varianten der Klasse der Threshold-Accepting-(TA)Verfahren. Darüber hinaus sollen auch Verfahren aus der Klasse des Tabu-Search integrierbar sein, ebenso wie Verfahren des Aktiven Lernens und SOMs. Weiterhin soll die Möglichkeit komplexer Co-Evolution sowie die Spezies-Entwicklung implementierbar sein, was durch Isolationsstrategien in einer verteilten Umgebung ermöglicht werden soll. Auf diese Weise wird die Umgebung auch geeignet, um Experimente im Bereich des Artificial Life, Ökosysteme, Artificial Societies, u.ä. durchzuführen.
Intervall-EA	Einen ersten Schwerpunkt sollen Intervall-EA (I-EA) bilden, d.h. es werden bei den EA und Hybriden nicht mehr reelle Skalare, sondern reelle Intervalle verwendet, auf die Operationen auf der Basis von Intervall-Arithmetiken zugreifen. Zum einen werden Probleme numerischer Instabilitäten, die durch eine begrenzte Auflösung reeller Maschinenzahlen und durch Rundungsoperationen verursacht werden, im Bereich der Neuronalen Netze und der EA in der Regel ignoriert. Zum anderen liegen Real-Word-Daten, insbesondere bei physikalischen Messungen, immer als Intervall vor, indem der Messwert zusammen mit einem Fehlerintervall angegeben wird, das in der Kalibrierungsphase vor den eigentlichen Messungen ermittelt wird. Aus diesen Gründen sollen Intervalle und Intervall-Arithmetiken als wesentlicher Bestandteil der Datenstruktur und der Basisfunktionen des verteilten EA-Systems verwendet werden, wobei die Flexibilität der Datenstrukturen in GENOM (s.u.) gut geeignet erscheint. Hierbei muss beachtet werden, dass verschiedene Implementierungssprachen des EA-Systems Intervalle und damit verbundene Rundungsoperationen nicht vollständig beherrschen, wie z.B. die nicht uneingeschränkte Eignung von Java für ein Scientific Computing, wie sie von Prof. Jürgen Wolff v. Gudenberg in dem Artikel "Java for Scientific Computing, Pros and Cons" beschrieben wird.
Soft-Reproduktions-Operatoren	Einen zweiten Schwerpunkt sollen Soft- oder Fuzzy-Reproduktions-Operatoren bilden, die in der Literatur hinreichend dokumentiert sind (siehe auch Bachelier (1998b:70ff)) und die gut für multimodale Zusammenhänge geeignet sind. Geprüft werden soll, ob Fuzzy-Toolboxen in der ausgewählten Entwicklungssprache genutzt werden kann, um Doppelentwicklungen zu vermeiden.
Multi-Objective- (MO) und Constraint-(C) EA	Einen dritten Schwerpunkt sollen Multi-Objective- (MO) und Constraint-(C) EA/ES sein (siehe auch die Überblickarbeit von David A. Van Veldhuizen), wobei eine Orientierung durch die Arbeiten von To Thanh Binh gegeben ist, bei denen es sich um Implementierungen spezieller MOC-ES-Varianten in der Form von Matlab-Toolboxen handelt. Eine Reihe von Vorschlägen bezüglich Pareto-ES findet sich in Bachelier (1998b), die sich insbesondere durch eine variable Populationsgrösse auszeichnen. Zu berücksichtigen sind auch Querbeziehungen zwischen diesen beiden Schwerpunkten, d.h. Erkenntnisse aus der Fuzzy-Multi-Objective-Optimierung sollen in eine Fuzzy-MOC-ES einfliessen.
Ressourcen-adaptive Multi-Populationsstrukturen	In einer verteilten Umgebung ist die Anwendung von Multi-Populationen eine effiziente Strategie, wobei in einem internet-basierten System der Ansatz ressourcen-adaptiver Multi-Populationen von besonderem Interesse ist, da dies in einer schwer vorhersagbaren, ständig veränderlichen Ressourcenumgebung eine effiziente Strategie darstellt. Dabei findet keine externe Festlegung von Populations-Parametern statt, sondern sie werden in Abhängigkeit von momentan verfügbaren, verteilten Internet-Ressourcen festgelegt. Beispielsweise werden im Internet verteilte EA-Clients einzelne Populationen für eine bestimmte Generationenanzahl (Isolation) zugeordnet. Sollte danach keine Internet-Verbindung existieren, um Ergebnisse (beste Individuen, ...) dem Server zur Verfügung zu stellen, und migrierte Individuen zu erhalten, so wird Evolution selbständig vom Client weitergeführt (ressourcen-adaptive Isolation), bis zum nächsten Mal eine Verbindung aufgebaut wird, bei der die zu diesem Zeitpunkt aktuellen Ergebnisse übergeben werden.
Induktion von Programmen	Der Hauptschwerpunkt bezüglich den Anwendungen soll jedoch in der Induktion von Programmen durch evolutionäre Verfahren bestehen, d.h. die unterschiedlichen evolutionären Verfahren, sowie die aktiv-neuronalen-evolutionären Hybride sollen verwendet werden, um Programme zu erzeugen, mit denen bestimmte Einzelprobleme bzw. Problemklassen gelöst werden. Damit wird eine konzeptuelle Erweiterung des Genetic Programming erzeugt.
Java-VM-CPG	Als Vorbild-Architektur könnte somit Distributed-GP (DGP) von Fuey Sian Chong (siehe auch Chong (1999)) herangezogen werden, wenn als Entwicklungssprache Java/Jini verwendet werden sollte. Dieses System basiert jedoch auf der Nutzung eines Java-GP-Systems, das Syntaxbäume ähnlich der Vorgehensweise von Koza verwendet. Die verteilten Clients und die Migrationsstrategien sind jedoch nicht von einer bestimmten GP-Datenstruktur abhängig, sodass ein modifizierter DGP auch auf der Basis von Binärstrings, die Maschinenbefehle repräsentieren, durchgeführt werden kann. Diese Binärstrings können im Fall von Java als Befehle für die virtuelle Java-Maschine VM betrachtet werden, im Gegensatz zu Maschinenbefehlen für die zugrundeliegende Hardware. Kann die Hardware die VM-Maschinenbefehle nicht direkt ausführen, so müssen effizienzsinkende Übersetzungsschritte zwischengeschoben werden. Dieser Nachteil ergibt sich jedoch nicht bei HW, die Java native verarbeiten kann, wie z.B. die Sun MAJC-Architektur, d.h. die Hardware kann VM-Binärcode direkt verarbeiten. Ein CGP-System, das Binärstrings derart verwendet, dass eine Java-VM diesen String direkt als Sequenz von Maschinenbefehlen verarbeiten kann, soll als Java-VM-CPG bezeichnet werden. Die Entwicklung eines solchen Ansatzes ist sinnvoll, da alle momentan im Internet verbreitete HW Java-VM-Binärcode zumindest indirekt verarbeiten kann, indem sie auf der VM verarbeitet wird, oder indem sie durch einen Just-In-Time-Compiler in Maschinenbefehle der zugrundeliegenden HW übersetzt wird. Zukünftige Internet-HW wie Sun MAJC können den Java-VM-Binärcode direkt ohne Zwischenschritte verarbeiten, sodass dies mit einer weiteren Effizienzsteigerung verbunden ist.
Java Distributed EA Library (JDEAL)	Wird Java/Jini als Entwicklungssprache anvisiert, so könnte direkt auf die Java Distributed EA-Library (JDEAL) zurückgegriffen werden, die bezüglich der speziellen Anforderungen Intervall-EA, Soft-Operatoren, MO-EA, sowie CGP und ressourcen-adaptive EA erweitert werden könnte, was durch die dokumentierten Java-Klassen gefördert wird. Von besonderer Bedeutung für die ressourcen-adaptiven EA ist die Implementierung von GA mit variablen Populationsgrössen, sowie die Implementierung von Populationsstrukturen, die durch einen Master-Slave-Prozess über das Internet verteilt werden können, wobei die Verwendung eines Blackboards ein wesentlich flexibleres Design ergeben würde, was durch die Einbeziehung von Jini möglich wäre. Weiterhin ist das Vorliegen eines Tabu-Search-Algorithmus günstig für die angestrebten hybriden Systeme, insbesondere für die Generierung von Maschinenprogrammen (siehe Software-Projekt SW02).
Verteilte Vorbild-Architekturen	Die verteilte Architektur des Datenanalyse-Projektes Seti@home oder die Monte-Carlo-Klima-Simulationen des Projektes Casino21 entsprechen den Anforderungen einer Ressourcen-Adaption. Im Gegensatz zu anderen verteilten internet-basierten Ansätzen werden durch die lokalen Clients keine Rechner mit IP-Adressen benötigt, d.h. keine Rechner, die ständig mit dem Internet verbunden sind, sondern es können alle Rechner integriert werden, die nur gelegentlich online gehen.
GENOM	Bezüglich der Datenstrukturen könnte die verteilte Variante des EA-Systems GENOM der Universität Stuttgart geprüft werden. Dies ergibt sich daraus, dass ein Merkmal dieses Systems eine maximal flexible Datenstruktur ist, und dass SA/TA-Verfahren bereits vorliegen. Es muss jedoch beachtet werden, dass die Flexibilität bei GENOM zu Lasten der Effizienz ging, was bei der Reimplementierung korrigiert werden muss. Bei der verteilten Version von GENOM von Thomas R. Schmidt (siehe Verteilte Evolutionäre Verfahren) ist eine Kommunikation von Multi-Populationen über ein Blackboard vorgesehen (jedoch nicht implementiert), was von besonderer Bedeutung für Hybride und komplexe Systeme ist, da ein Blackboard wahrscheinlich die flexibelste Möglichkeit ist, hybride und verteilte Systeme zu erzeugen. In diesem Zusammenhang ist die Hypothese zu untersuchen, ob eine Implementierung mit Java/Jini die Anforderungen erfüllen kann, die an ein solches EA-System gestellt werden, da der dort verfolgte Ansatz eines Network-Centric-Computing ein einfaches Blackboard als Kommunikationsmedium verwendet.
Graphische EA-Programmierung	Wird eine Vorbild-Architektur wie GENOM oder Distributed-GP (DGP) verwendet, so stellt sich auch die Frage, wie Probleme (Fitnessfunktionen) und EA-Parameter formuliert werden. Wird Java/Jini verwendet, so ist ein graphisches Interface sinnvoll, möglicherweise auch eine graphische Programmierumgebung, mit der EA-Experimente durch Drag-and-Drop-Operationen formuliert werden können, die in einem internet-basierten, verteilten System ausgeführt werden.
Hybride mit SOMs	Im Hinblick auf hybride Verfahren unter Einbeziehung von SOMs wäre die Verwendung von Java/Jini nicht ungeeignet, da mit dem Programm DemoGNG der Gruppe um Bernd Fritzke eine Java-Implementierung verschiedener, unüberwachter SOM-Modelle wie des Neuronen Gas, GNG-SOM, Competitive Hebb-Learning, LBG und Growing Grid bereits vorliegen. Weiterhin liegen interpolierende SOM-Modelle (I-SOMs) von Josef Göppert ebenfalls in einer Java-Implementierung vor, die in DemoGNG integriert werden könnte. Auf der Basis dieser unüberwachten Modelle liessen sich überwachte Ansätze einfach hinzu fügen. Demgegenüber existiert auch eine C++-Implementierung der SOM-Verfahren aus DemoGNG, eine Entsprechung im Bereich der I-SOMs fehlt jedoch (siehe auch Software-Projekt SW03).
- - - - - - - -
Sonstige Vorbild-Architekturen	- - - Potentiell relevante Architekturen, deren Komponenten auf eine Eignung für den Einsatz in den EA-System untersucht werden könnten sind u.a.: - - - Die Client-Server-Architektur von distributed.net. - - - Die TCP/IP-basierte Client-Server-Architektur des Rendering-Programms Cinema 4D Net mit ihren hot-swappable Clients. - - - Die Javelin-Architektur (siehe auch hierzu das Center for Research on Internet-Based Globally Distributed Computing für einen Überblick über andere verteilte Computing-Systeme auf der Basis von Internet-Technologien). - - - EA mit Java, falls eine Java/Jini/Javelin-Architektur erwogen wird: GA Playground: ein modulare General-Purpose GA Toolkit in Java von Ariel Dolan. EA mit Java: Sammlung von EA-Java-Programmen zu ES, GA, GP von Christian Jacob. - - - Reproduction Planing Language RPL2. - - - Das Datenbank- und Datenanalyse-System root, das als open-source in C++ geschrieben ist, und in Cern entwickelt wird. Bedeutend ist dieses System zum einen durch seine Skalierbarkeit, da es für die Analyse von Terra-Byte grossen Real-Word-Datenvolumen konzipiert ist. Zum anderen durch seine Maintainebility, da die Elementarteilchenbeschleuniger, welche die zu analysierenden Daten liefern, mindestens drei Jahrzente in Betrieb sein werden, sodass erwartet werden kann, dass die Analysetools in diesem Zeitraum weiterentwickelt und gewartet werden. Falls eine Java/Jini/Javelin-Architektur erwogen wird, könnte zunächst geprüft werden, in wie weit Java-Code in root integrierbar ist, oder ob ein Java-Clone sinnvoll wäre, wenn die Vorteile einer integrierten Datenbank für Populationen (von GP-Programmen) berücksichtigt werden (siehe auch Bollini & Piastra (1999)). - - - Der Linux-TurboCluster Server, als ein hochverfügbarer, ausfallsicher, fehlertoleranter Web-Server, der als open-source zur Verfügung steht. - - - Mathematik-Programme (s.a. Software-Projekt SW05), für die bereits Anwendungen im Bereich EA existieren, wie z.B. die EA-Programme, die Christian Jacob innerhalb Mathematica geschrieben hat, sowie insbesondere das Genetic Programming System Evolvica, das in der Programmiersprache von Mathematica geschrieben ist.
- - - - - - - -
Referenzen	Bollini, A.; Piastra, M.: Distributed and Persistent Evolutionary Algorithms: A Design Pattern. In: Poli et al. (1999), S. 173 - 183. Chong, Fuey Sian: A Java based distributed approach to genetic programming on the Internet. Master's thesis. Computer Science, University of Birmingham, 1998. Koza, J.R; Bennett, F.H.; Andre, D.; Keane, M.A.: Genetic Programming III. Morgan Kaufmann, 1999. Poli, R.; Nordin, P.; Langdon, W.B.; Fogarty, T.C. (eds.): Genetic Programming, Second European Workshop, EuroGP'99. Springer Verlag, LNCS 1598, S. 65 - 82, 1999.