Entwurfsdetails zu GaFrame

Bewusst haben wir in dieser Dokumentation auf theoretische Details zu GA verzichtet, da hierzu genügend Literatur verfügbar ist. Dennoch muss auch hier kurz das Grundschema eines GA aufgezeigt werden, um anschließend direkt das Softwaredesign ableiten zu können.

Population erzeugen Hier muss eine Grundpopulation erzeugt werden, mit der der GA arbeiten kann. Hierfür kann man verschiedene Ideen entwickeln, die wir als Stategie bezeichnen. Ein Beispiel für eine solche Strategie wäre: doppelte Anzahl von Individuen mit zufälliger Chromosomenbelegung erzeugen Berechnung der Fitness jedes dieser Individuen Übernahme der "fittesten" Individuen in die Grundpopulation Selektion Bei der Selektion handelt es sich um ein Auswahlverfahren, welches die Individuen bestimmt, die in den sogenannten Heiratspool aufgenommen werden. Auch hier sind unterschiedliche Verfahren, also Strategien (z.B. paarweise zufällig auswählen) möglich. Rekombination In dieser Phase werden sogenannte genetische Operatoren auf die Phänotypen der Individuen im Heiratspool angewendet, um Kinder zu erzeugen, die im Laufe des Evolutionsprozesses immer bessere (Problemlösungs-) Eigenschaften entwickeln sollen. Hier sind wieder verschiedene Operatoren möglich, die auch als Strategie bezeichnet werden sollen. Ersetzung Da die Individuen im Allgemeinen nicht altern und sie somit bis zum Ende der Evolution in der Population vorhanden wären, muss man ein Verfahren wählen, welches die Population nach dem Erzeugen von Kindern wieder auf ein gewisses Maß reduziert. Der Einfachheit halber wird man wohl festlegen (wie wir dies auch getan haben), dass die Anzahl der Individuen einer Population konstant ist. Auch hier bestehen wieder mehrere Verfahren, dieses Ersetzungschema zu bewerkstelligen. Weiterhin wird nach diesem Schritt noch eine Mutation vorgenommen. Die Mutation ist ebenfalls ein genetischer Operator, welcher zufällig ausgewählte Gene manipuliert, um "neue Wege" in der Evolution einschlagen zu können. Die Mutation trägt also maßgeblich zur Entwicklung der Population über Generationen hinweg bei. Ende? Es wird stets geprüft, ob die maximale Anzahl an Durchläufen erreicht ist oder die maximal benötigte Fitness erreicht wurde. In beiden Fällen wird der GA abgebrochen und das beste Individuum ausgegeben

Wie man sich leicht vorstellen kann, benötigt man evtl. an einigen Stellen die Fitness der Individuen, je nachdem welche Verfahren/Strategien zur Anwendung kommen. Im Grundschema ist die Berechnung der Fitness, also das "Konvertieren" der Phänotypen in (hoffentlich) lebensfähige Individuen, an einer Stelle festgeschrieben. Da wir aber aus praktischen Gründen an verschiedenen Stellen diese Berechnung anstoßen, haben wir im Grundschema die Fitnessberechnung weggelassen (siehe auch nächster Abschnitt).

Nachdem wir nun mit dem Ablaufschema eines GA vertraut sind, können wir diesen Prozess direkt als Sequenzdiagramm abbilden. Der hier aufgeführte Ablauf ist so tatsächlich in GaFrame implementiert.

Wie man sieht, ist der komplette Ablauf des GA in einer Methode untergebracht, der run()-Methode, die von außen aufgerufen werden muss, um den GA in Gang zu setzen.

Die einzelnen Teilschritte sind nochmals in eigene Methoden gekapselt, um Übersichtlichkeit und gute Lesbarkeit zu erreichen. In den jeweiligen Teilschritten werden schließlich Methoden von austauschbaren Strategien aufgerufen, die die entsprechenede Implementierung enthalten. Details hierfür finden sich im Abschnitt zur Softwarearchitektur.

Klassendiagramm

Das oben dargestellte Klassendiagramm enthält grundsätzlich alle Klassen, die das GaFrame beinhaltet. Lediglich einige Util-Klassen und der RMI-Server sind hier aus Platzgründen nicht mit aufgeführt. Wenn Sie sich für diese Util-Klassen interessieren, sollten Sie einen Blick in die javadoc-Dokumentation werfen und unter de.htwdd.ga.util nachschlagen. Auch das vollständige Klassendiagramm ist im Javadoc enthalten. In den folgenden Kapiteln werden einige Informationen zur verteilten Verarbeitung und RMI folgen, weswegen hier nur der Hinweis darauf erfolgt.

Wie man im Klassendiagramm sehr schön erkennen kann, ist GaFrame modular aufgebaut. Das bedeutet, dass es sich ohne Eingriffe in die bisherige Implementierung erweitern und anpassen lässt. Hiermit haben wir unseren definierten Anforderungen Rechnung getragen und konnten dies in parallel laufenden Belegen testen. Das Konzept hat sich in unseren Augen bewährt und lässt sich einfach handhaben.

Austauschbare Komponenten

Designziel war es, neben Effizienz des genetischen Prozesses, das System flexibel und allgemeingültig zu entwerfen. Um dies zu gewährleisten, haben wir eine einfache Form eines Extensionpoint-Mechanismus vorgesehen, der es gestattet, das System massiv zu beeinflussen, ohne nur eine Zeile Quellcode des eigentlichen GaFrame-Paketes ändern zu müssen.

Gelöst haben wir das Problem so, dass in den verschiedenen Phasen der run()-Methode verschiedene Aufgaben an verschiedene Objekte delegiert werden. Dieses Vorgehen ist im Sequenzdiagramm deutlich abzulesen.

Für den Austausch von Komponenten verfügt ein Objekt des Typs GeneticAlgorithm über Setter-Methoden um, die entsprechenden Objekte zu setzen. Wie aus dem Klassendiagramm ersichtlich, muss hierzu die gewünschte Schnittstelle genutzt und die Funktionalität ausprogrammiert werden. Im folgenden wird auf die einzelnen Bestandteile eingegangen.

Fitnessfunktion

Für jedes Problem muss eine individuelle Fitnessfunktion zur Verfügung gestellt werden. Hierzu haben wir das Interface FitnessFunction vorgesehen, welches die Methode double computeFitness(BitSet chromosome) vorschreibt. Hierbei verfügt jedes Individuum über eine eigene Fitnessfunktion, was nötig ist, um die parallele Nutzung zu gewährleisten.

Gesetzt wird die Fitnessfunktion über den Setter public void setFitnessFunction(Class fitnessFunction). Da hier nur ein Class-Objekt übergeben wird, ist es uns möglich, mittels Reflection beliebig viele Instanzen der Fitnessfunktion zu erzeugen.

Initialisierungsfunktion und Mutation

Wir haben bereits zwei Implementierungen einer Initialisierungsfunktion dem Paket beigefügt. Nähere Informationen unter Verfahren.

Oft ist es nötig, für konkrete Anwendungsfälle spezielle Initialisierungsverfahren zu nutzen, um die Konvergenz des genetischen Prozesses zu beschleunigen oder sogar erst zu ermöglichen. Um eigene Implementierungen in GaFrame nutzen zu können, verfügt die Klasse GeneticAlgorithm über die Setter-Methode void setInitializationFunction(InitializationFunction initializationFunction). Hiermit ist es möglich eine eigene, die Klasse InitializationFunction ableitende, Klasse zu nutzen.

Weiterhin sei erwähnt, dass es eigentlich nicht vorgesehen ist, die Klasse Individual zu verändern. Sollte dies unbedingt nötig sein, um zum Beispiel die Mutation grundsätzlich anders zu implementieren, dann können Sie in einer eigenen Initialisierungsfunktion Objekte Ihrer eigenen Idividuum-Klasse erzeugen. Bitte achten Sie hier allerdings darauf, dass das Individuum ein zentrales Element des Genetischen Algorithmus ist und Änderungen hier schnell dazu führen können, dass andere Verfahren nicht mehr ordungsgemäß auf den Individual-Objekten arbeiten können. Erweitern Sie also bitte die Individual-Klasse nur, wenn Sie mit den Interna von GaFrame absolut vertraut sind!

Selektionsverfahren

Die drei letzten Komponenten, die man austauschen kann, werden alle nach dem oben beschriebenen Schema eingehängt. Weiterhin ist hierfür jeweils ein Interface vorgesehen, um die Schnittstelle zu GaFrame zu definieren. Wir werden also die Beschreibung verkürzen und nur noch den Namen des Interfaces und der Setter-Methode nennen, um die entsprechende Strategieimplementierung in GaFrame einzuhängen.

Interface:

SelectionStrategy

Setter in GeneticAlgorithm:

void setSelectionStrategy(SelectionStrategy selectionStrategy)

Rekombinationsverfahren

Interface:

CrossoverMethod

Setter in GeneticAlgorithm:

void setCrossoverMethod(CrossoverMethod crossoverMethod)

Ersetzungsstrategie

Interface:

ReplacementStrategy

Setter in GeneticAlgorithm:

void setReplacementStrategy(ReplacementStrategy replacementStrategy)