HTW Dresden > GaFrame
 

Parallelisierung

Um einen Genetischen Algorithmus nutzbringend einsetzen zu können, ist es oft erforderlich, den Evolutionsprozess über einen relativ langen Zeitraum (eine große Anzahl von Zyklen) durchzuführen. Der Rechenaufwand zur Durchführung eines Genetischen Algorithmus kann sich dabei durch folgende Faktoren erhöhen:

Da inzwischen viele PCs mit mehreren Prozessoren oder mit Mehrkernprozessoren ausgestattet sind, lag es nahe, für GaFrame direkt die Möglichkeit der Parallelverarbeitung vorzusehen.

Parallelisierung in GaFrame

Um im Ablaufmodell von GaFrame parallele Verarbeitung effektiv nutzen zu können, musste zuerst ein geeigneter Erweiterungspunkt in der Architektur gefunden werden.

Die eigentlichen "genetischen Operationen" im Genetischen Algorithmus (Selektion, Rekombination, Mutation, Ersetzung) zeichnen sich durch konstanten Aufwand aus, der für die meisten mittels Genetischer Algorithmen zu lösenden Probleme etwa gleich sein sollte. Die Berechnung der Fitness eines Individuums ist aber bei jedem Problem individuell, hier können durchaus auch aufwändige Funktionen genutzt werden. Dies ist z.B. in den Belegen der Autoren der Fall. Aus diesem Grund entschieden wir uns, die Fitnessberechnung parallelisierbar zu gestalten. Sobald innerhalb des Genetischen Algorithums die Fitness einer Population zu berechnen ist (siehe Design), kann dies bei entsprechender Konfiguration auf mehrere Prozessoren bzw. Kerne verteilt werden. GaFrame nutzt hierbei pro Prozessor/Kern einen eigenständigen Thread, sodass die Kapazitäten der Maschine optimal ausgenutzt werden.

Das folgende Objektdiagramm zeigt nochmals den Zusammenhang: GeneticAlgorithm füllt, sobald eine Fitnessberechnung notwendig ist, die entsprechenden Individuen in eine Warteschlange. Die Threads, die die eigentliche Fitnessberechnung durchführen, werden benachrichtigt, nehmen die Individuen aus der Warteschlange und berechnen ihre Fitness.

Objektdiagramm Multithreading

Das hier erläuterte Verfahren bildet auch die Basis für die im nächsten Abschnitt erläuterte verteilte Verarbeitung.