Beweggründe

Im Laufe meines Studiums habe ich mich mit verschiedenen Bereichen der Informatik beschäftigt. Insbesondere in den Wahlpflichtveranstaltungen wurde es mir ermöglicht, mir einen Einblick in die unterschiedlichsten Teilgebiete aus den Bereichen der graphischen Datenverarbeitung, der Bioinformatik und der Programmiersprachen (Compilerbau) zu verschaffen. Unter anderem gehörten auch die Fächer Neuronale Netze und Evolutionsalgorithmen zu den von mir besuchten Lehrveranstaltungen.

Diese Lehrveranstaltungen haben mein Interesse an Evolutionsstrategien und Genetischen Algorithmen geweckt. Speziell die Simulation – insbesondere die Simulation auf verteilten Systemen – dieser Verfahren zur Lösung von Problemstellungen der Informatik haben mich ganz besonders gereizt.

Aus diesem Interesse heraus entstand dann auch die Idee, meine Diplomarbeit über eben dieses Thema zu schreiben und dabei eine Bibliothek zu entwickeln, die eine solche Simulation auf einfache Art und Weise ermöglicht.

Zielsetzung

Das Ziel dieser Diplomarbeit war die Entwicklung eines Frameworks, welches zur Implementierung von Optimierungsprogrammen für Optimierungsprobleme jeglicher Art dienen soll. Die dabei entstandene Bibliothek sollte eine Sammlung von Klassen beinhalten, die allgemeine Funktionalitäten zur Verarbeitung von Algorithmen nach dem Vorbild der biologischen Evolution bereit stellt. Sie stellt lediglich ein Grundgerüst für die Verarbeitung dar. Individuen werden als abstrakte Klassen definiert und müssen für das jeweils zu lösende Problem implementiert werden. Das heißt, dass die Spezialisierung eines Individuums unter anderem Methoden zur Initialisierung, Bewertung, Mutation und unter Umständen auch zur Rekombination eines Individuums implementieren muss.

Die Bibliothek wurde in der Programmiersprache C++ unter Verwendung der Standard Template Library entwickelt. Als Entwicklungssystem diente ein Rechner, der unter dem Betriebssystem Linux lief und mit einem GNU C++-Compiler in der Version 2.95.3 ausgerüstet war. Zur Erzeugung der Klassendokumentation wurde Doxygen, ein Dokumentationswerkzeug welches Javadoc ähnelt, verwendet. Die Dokumentation wird dabei in Form von speziellen Kommentaren in den Header-Dateien der verschiedenen Klassen eingefügt. Aus den dort definierten Dokumentationseinträgen werden die von Doxygen definierten Tags ausgelesen und in eine im HTML-Format gespeicherte Dokumentationsstruktur gebracht. Diese Dokumentation kann dann in einem beliebigen Browser dargestellt werden.

Neben der Verarbeitung von einfachen Populationen auf einem einzelnen System besteht die Möglichkeit, verteilte Populationen unter Verwendung der Parallel Virtual Machine (PVM) als Message Passing System, auf verschiedenen Rechnern unterschiedlichster Architektur zu verarbeiten. Ein auf diese Weise konfigurierter Optimierungslauf besteht aus einem Master- und n Slave-Prozessen, die untereinander Informationen austauschen können. Als Schnittstelle zu PVM wurde die C++-Bibliothek CPPVM verwendet, die eine objektorientierte Kapselung von PVM vornimmt und somit auf einfache Art das Versenden von Nachrichten und die Verteilung der Prozesse ermöglicht.

Die computergestützte Simulation von Evolutionsprozessen ist äußerst rechenaufwendig und durch die Parallelisierung der Populationen auf verteilten Systemen kann deren Verarbeitung erheblich beschleunigt werden. Unter Verwendung von Rechen-Clustern kann auf vergleichsweise günstige Art und Weise eine beträchtliche Rechenleistung aufgebracht werden.