(SS09-03) Projektdokumentation

Aus Verteilte Systeme - Wiki
Zur Navigation springen Zur Suche springen

Grundlagen

Bevor wir uns tiefer mit der Parallelisierung von genetischen Algorithmen beschäftigen, sollen die grundliegenden Begrifflichkeiten und Zusammenhänge darstellen werden.

Verfahren genetischer Algorithmen

Genetische Algorithmen arbeiten nach einem Verfahren, das an die biologischen Evolution angelehnt ist. In der Biologie stellen Chromosome die Baupläne für Individuen dar. Sie beinhalten mehreren Genen, die gewisse Eigenschaften des Individuums repräsentieren. Bezieht man dies auf den Reisenden, dann ist ein Chromosom eine Reise und die Gene die Städte, die auf dieser angesteuert werden. Die Reihenfolge entspricht dabei der Anordnungsfolge der Gene auf dem Chromosom (im Prinzip an welcher Stelle im Array sich das Gen befindet).

Wir nehmen im Folgenden zur Vereinfachung an, dass ein Chromosom auch gleichzeitig ein Individuum ist.

Zusammenhänge

Wie auch in der Biologie wird bei den genetischen Algorithmen eine Generation an Individuen durch Evolution erzeugt. Dabei werden die besten Individuen der aktuelle Generation, also der Menge an Chromosomen, die bei der Initialisierung zufällig bestimmt oder durch eine vorherige Evolution erzeugt wurden, ausgewählt. Diesen Vorgang nennt man Selektion. Zur Bewertung eines Chromosoms wird eine Fitness-Funktion definiert, die durch domänenspezifische Berechungen einen Wert bestimmt. In unserem Szenario hat der Reisende dazu eine Funktion implementiert, die die Entfernung zwischen allen Städten (Atome) berechnet und durch deren Anzahl auf der gesamten Reise teilt. Je geringer dieser Wert ist, desto näher sind wir der Lösung des Problems.

Die selektierten Chromosome bilden die nächste Generation. Auf diese werden nun die genetischen Operationen angewendt. Bei der Rekombination werden zufällige Gene zweier Chromosome zu einem neuen Chromosom kombiniert. Die Mutation ändert einfach zufällige Atome eines Chromosoms. Bei beiden Operationen ist natürlich darauf zu achten, dass sich zwar die Reihenfolge der Atome ändert, aber trotzdem keine doppelt vorkommen oder ganz raus fallen. Dies würde sich auf die Route unseres Reisenden auswirken, so dass er nicht mehr alle Städte besucht oder einige doppelt.

Die prinzipielle Parallelisierbarkeit der Evolutionären Algorithmen (EA)

Die EA bieten auf der Ebene der Individuen, als auch auf der Ebene der Populationen diverse Möglichkeiten der Parallelisierung. In diesem Abschnitt sollen die Abläufe und Prozesse innerhalb einer Population betrachtet werden, also auf der Ebene der Individuen.

  • Erzeugung einer Individuenmenge als Ausgangspunkt der Evolution (Startpopulation) und Berechnung der Fitness der Individuen

Bei der Erzeugung der Ausgangspopulation gibt es keine Einschränkung der Parallelisierbarkeit. Jedes Individuum kann für sich selbst und unabhängig von den anderen Individuen der Population erzeugt werden. (z.B. jeweils auf einem eigenen Prozessor oder von parallel und unabhängig arbeitenden Prozessoren). Bei der Berechnung der Fitness kann jedes Individuum einzeln auf seine Tauglichkeit und Güte geprüft werden. Dieser Schritt ist ebenfalls ohne Probleme und Einschränkungen parallelisierbar.

Man sollte bei der Berechnung der Fitness jedoch beachten, das es Individuen gibt die mit anderen Individuen kooperieren müssen, um ihren Zweck zu erfüllen und zu überleben. In diesen Fällen muss die Fitness anderer Individuen bei der Berechnung der eigenen Fitness mit berücksichtigt werden. Dies ist z.B. bei Parasiten und ihren Wirten der Fall. Auch gibt es Anwendungen der EA bei denen die Fitness eines Individuums erst durch die Fitness seiner Nachkommen berechnet werden kann. Dies ist bei neutraler Mutation relevant.

  • Berechnung der Abbruchbedingung

Es gibt mehrere Möglichkeiten der Berechnung der Abbruchbedingungen. Diese hängt meist von den Abbruchkriterien der EA ab, ist meist eine Funktion der Fitneß und setzt damit die Kenntnis der Fitneß aller Individuen voraus. Die Abbruch - Prüfung stellt eine zentrale Steuerungsfunktion der Algorithmen dar und ist in der Regel nicht parallelisierbar. Man könnte die Berechnung der Abbruchbedingung auch als „Flaschenhals“ der EA bezeichnen.

  • Auswahl der zu rekombinierenden Individuen

Die Auswahl der zu rekombinierenden Individuen kann im Regelfall nicht oder nur ungenügend parallelisiert werden. Dies ist insbesondere dann der Fall , wenn die Selektion der Individuen proportional zur Fitneß der Individuen (Roulette Wheel) vorgenommen werden soll oder in irgendeiner anderen Weise von der Fitneß der Gesamtpopulation abhängt.

  • Crossover

Wesentlich besser ist die Situation beim Kreuzen (Crossover) der selektierten Individuen. Der Crossover-Prozess selektierter Individuen (meist Pärchen) kann hochgradig parallelisiert werden, da die Berechnung der vollkommen unabhängig voneinander durchgeführt werden können. Dies kann zu einem enormen Speed-Up führen der um so stärker ausfällt, je rechenintensiver der eingesetzte Crossover-Mechanismus ist.

  • Mutation

Die Mutationen sind in der Regel ebenfalls hochgradig parallelisierbar, da sie nur lokal auf die einzelnen Individuen wirken. Bei den Evolutionsstrategien ist die adaptive Schrittweitenregelung der Mutationen zu beachten. Bei diesem Mechanismus werden den Nachkommen unterschiedliche Mutationsraten mitgegeben. Ein bestimmter Prozentsatz erhält die Mutationsschrittweite des Elternteils oder der Eltern, ein anderer Teil der Nachkommen erhält eine größere und der dritte Teil eine kleinere Schrittweite. Die Nachkommen müssen deshalb als Gesamtheit betrachtet werden und können nicht völlig unabhängig voneiander mutiert werden.

  • Selektion

Um die Populationsgröße konstant zu halten und um evtl. Eliten zu berücksichtigen müssen die tauglichsten nach einem Selektionskriterium ausgesondert werden. Dies erfordert die Kenntnis der Fitness aller Individuen und stellt einen zentralen Steuerungsmechanismus dar, der praktisch nicht parallelisiert werden kann. Parallelisierung der Selektion ist nur möglich, wenn man die Individuen zu Populationen zusammenfaßt und in diesen lokal selektiert.

Evolutionsmodelle

Bei der Umsetzung des Frameworks können verschiedene Modelle implementiert werden, die jeweils ihr Stärken und Schwächen aufweisen. Es werden abstrakte Mechanismen bereit gestellt, um Probleme mit verschiedenen dieser Modellen zu bearbeiten. Die folgende Betrachtung liefert einen Überblick über die wichtigsten Modelle.

  • Insel-Modell

In diesem Modell können beliebig viele Populationen betrachtet werden, die jede für sich einen Evolutionsprozess durchführt. Die einzelnen Populationen sind voneinander getrennt und entwickeln sich völlig unabhängig und isoliert voneinander.

Mit diesem Modell können mehrere Evolutionsläufe parallel durchgeführt werden, indem mehrere Inseln gleichzeitig eingesetzt werden. Am Ende können das oder die besten Individuen aus allen Insel - Populationen als Lösung bzw. als Optimum bestimmt werden.

Damit können die auf einem seriellen Rechner nur sequentiell durchführbaren Simulationen der EA parallelisiert werden. Eine Kommunikation der Prozesse, der Inseln, untereinander findet nicht statt. Deswegen brauchen die Prozesse untereinander nicht synchronisiert zu werden und jeder kann seine Rechenzeit optimal nutzen. Der Speed-Up ist beim Insel-Modell direkt proportional zu der Anzahl der simulierten Inseln, also der parallel entwickelten Populationen.

Ein Nachteil des Insel-Modells ist das die einzelnen Inseln nicht kommunizieren können. Die einzelnen Populationen können sich nur auf der Basis des genetischen Erbgutes entwickeln, das auf der Insel in der Anfangspopulation verfügbar ist. Sind die Populationen auf den Inseln klein und die Mutationsrate niedrig, so kann dies sehr schnell zu sehr homogenen und anfälligen, nicht mehr adaptionsfähigen, quasi inzestuösen Populationen führen (Inzucht).

  • Das Netzwerk-Modell

Um die Nachteile des Insel-Modells zu beseitigen, kann es zu einem Netzwerk-Modell erweitert werden. Dieses besteht ebenfalls aus einer Menge voneinander abgegrenzter unabhängiger Populationen. Im Gegensatz zum Insel-Modell tauschen die einzelnen Populationen hier Informationen (d.h. einzelne Individuen) untereinander aus. Das Netzwerk-Modell das realistischeres Modell, da es keine absolute Isolation von Populationen auf unterschiedlichen Inseln gibt und die Individuen auf irgendeine Art zwischen den Populationen hin und her wandern damit neues Erbgut in die Populationen gebracht wird. Im Netzwerk-Modell sind die Populationen über feststehende Kommunikationskanäle (Wanderungswege) miteinander verbunden.

Durch die Vermaschung der Populationen wird das Modell schwieriger zu steuern und langsamer als das Insel-Modell. Der Zeitverlust wird häufig dadurch wieder wettgemacht, daß die Populationen durch das ständige Ein- und Auswandern von Individuen wesentlich langsamer stagnieren. Meistens, jedoch nicht immer, besitzt das global beste Individuum eines Netzwerk-Modells eine höhere Fitness als das beste Individuum aller Inseln des Insel-Modells.

Die Individuen können synchron oder asynchron ausgetauscht werden. Beide Ansätze sind im wesentlichen grundverschieden. Beim synchronen Vorgehen geschieht der Austausch der Individuen gleichzeitig. Anders bei der asynchronen Kommunikation. Hier tauschen die Populationen unabhängig voneinander zu verschiedenen Zeitpunkten Informationen aus.

  • Das Migrations-Modell

Das Migrationen-Modell orientiert sich an Populationen aktiver, weitgehend selbstständiger und wanderungsfähiger Individuen und damit sehr stark an der Realität.

Im Migrations-Modell sind die Verbindungen nicht wie im Netzwerk-Modell statisch, sondern dynamisch. Je nach lokalen Verhältnissen innerhalb der einzelnen Populationen werden Verbindungen zu anderen Populationen auch über mehrere fremde Populationen aufgebaut.

Nicht nur die Kommunikationspfade werden dynamisch aufgebaut, auch die Kommunikationsraten werden dynamisch ermittelt. Bei einem hohen Selektionsdruck wandern mehr Individuen aus, als bei einem niedrigeren. Populationen mit einem niedrigeren Selektionsdruck wirken wie ein Magnet auf die Populationen mit einem höheren Selektionsdruck. Dies wird simuliert, indem die Wanderwege zu Populationen mit niedrigem Selektionsdruck mit höherer Wahrscheinlichkeit frequentiert werden.

Ein großer Nachteil des Migrations-Modells ist seine Komplexität. Es kann und wird sehr leicht zu Rückkopplungen unter den Populationen kommen. Dies bedeutet, wandern Individuen aus einer Population mit hohem Selektionsdruck aus, wird dort der Selektionsdruck erniedrigt. In der Population mit niedrigem Selektionsdruck erhöhen diese Individuen den Selektionsdruck. Das System der Wanderungsbewegungen kann sich völlig chaotisch verhalten.

Der größte Nachteil dieses Modells ist, das es nur auf einem MIMD-Rechner mit variablen, frei programmierbaren Kommunikationskanälen zwischen den Prozessoren effizient läuft, da die Kommunikationspfade während der Laufzeit aus der Software heraus von den EA aufgebaut und abgebaut werden müssen. Ein solches System ist meist unerschwinglich.

  • Das Pollen-Modell

Auch das Pollen-Modell ist eine Variante des Netzwerk-Modells. Es orientiert sich im Gegensatz zum komplexen Migrations-Modell an der Pflanzenwelt. In der Pflanzenwelt ist die Dynamik der Bewegungen und die räumliche Isolation wesentlich eingeschränkter. Pflanzen können sich über weite Entfernungen ausbreiten und stark variierende Artmerkmale entwickeln. Eine Methode zur räumlichen Verteilung des Erbgutes aus dem Pflanzenreich ist der Pollenflug.

Das Pollen-Modell besteht aus einer starren Anordnung von räumlich verteilten Populationen. Der Migrationsprozess und der Austausch von Information wird durch ein Modell des Pollenfluges simuliert. Es wird ein "Wind" definiert, der den Pollen (die Erbinformation) mit einer gewissen, zeitlich variablen Stärke in eine zufällig bestimmte Richtung treibt.

  • Das Nachbarschafts-Modell

Das Nachbarschafts-Modell ist ebenfalls eine Variante des Netzwerk-Modells. Die Populationen werden räumlich fix angeordnet. Die Anordnung kann ein - oder mehrdimensional sein.

Die Populationen werden nach einem festen Schema einer Nachbarschaft von Populationen zugeordnet. Die Nachbarschaften haben in der Regel eine für alle Populationen gleiche Gestalt und Ausdehnung. Um Randpopulationen nicht zu vernachlässigen, werden häufig Torusartige Anordnungen der Populationen gewählt. Dies bewirkt bei einer planaren Anordnung, dass die am äußersten linken Rand befindlichen Populationen per Definition direkte Nachbarn der am rechten Rand liegenden Population sind.

  • Das Kommunen-Modell

In diesem Modell wird eine Population als Kommune betrachtet, die in ihrem inneren noch feiner strukturiert ist. Als Vorbild dienen menschliche Kommunen (Städte).

Jede Kommune besteht aus einer limitierten Anzahl von Häusern, in denen die Individuen leben und Nachkommen erzeugen. Weiterhin besteht die Kommune aus einem „Stadtkern“ mit allen Individuen zugänglichen „sozialen“ Einrichtungen. Die Nachkommen treffen sich ab einem bestimmten Alter (abhängig von der Fitness oder der Generation) in einer „Single-Bar“ oder einem „Heiratsinstitut“ im Stadtkern. Dort suchen sie sich einen Partner (dieser kann nach dem gewöhnlichen Roulette-Wheel Verfahren gesucht werden). Haben sie einen Partner gefunden, benötigen sie im nachfolgenden Schritt ein Haus zur Erzeugung der Nachkommen. Da die Häuser limitiert sind, müssen die Paare sich über einen „Makler“ im Stadtkern um ein Haus streiten. Paare die kein Haus finden konnten, begeben sich zum Busbahnhof im Stadtkern um in einer anderen Gemeinde (Kommune) ihr Glück zu versuchen.

Das Kommunen-Modell benötigt einen relativ hohen Kommunikationsaufwand innerhalb einer Population und viele zentrale Steuerungsfunktionen wie den Stadtkern mit Makler und Single-Bar, die Verwaltung der Häuser usw.. Dieses sehr komplexe Modell ist nur auf wenigen Plattformen effizient simulierbar.

Projekt

Wir planen ein Framework, mit dem verschiedene Szenarien durch evolutionäre Algorithmen behandelt werden können. Zuerst haben wir eine Evaluation bestehender Frameworks durchgeführt, die wir um zusätzliche Parallelisierung erweitern wollten. Dabei stellte sich allerdings heraus, dass die gefundenen professionellen Tools bereits parallelisiert sind. Das freie und nicht parallel arbeitende n-genes, das aber schon seit einigen Jahren nicht gepflegt wird, wurde näher untersucht. Leider entspricht es nicht unseren Ansprüchen, da Individuuen die jeweils aus einer Permutation gegebener Gene bestehen nicht realisiert werden konnten. Dies ist z.B. nötig, möchte man das TSP-Szenario umsetzten und der Reisende soll jede Stadt nur einmal auf seiner Tour ansteuern. Wir haben uns deswegen für einen eigenen Entwurf entschieden.

Entwurf

Grob kann unser Tool in einen ersten Framework-artigen - und einen problemspezifischen Bereich aufgeteilt werden. Ersterer beschäftigt sich mit der Infrastruktur, also die verschiedene Probleme übertragbaren Elemente, wie zum Beispiel die genetischen Operationen oder verschiedene Abbruchkriterien, und das eingesetzte Modell. Der zweite Bereich definiert einige Schnittstellen, mit deren Hilfe ein konkretes Problem auf der besagten Infrastruktur bearbeitet werden kann. Diese umfassen zum Beispiel die Berechnung der Fitness von Individuen oder speziell angepasste Gene.

Infrastruktur

Zusammenhänge: EvolutionModel

Zur Bearbeitung eines Problems durch genetische Algorithmen ist eine grundliegende Voraussetzung eine Implementierung eines der Modelle, die bereits in den letzten Abschnitten erwähnt wurde. Das Framework bietet dazu die abstrakte Klasse EvolutionModel an, von der konkrete Modelle erben und das bereits Statistik-, Steuerungs-, Observations und Parallelisierungsmechanismen zu Verfügung stellt. Während der Entwicklung stellte sich heraus, das es sinnvoll ist diese Funktionalität zu abstrahieren, da sie zur Implementierung eines Modells nötig sind.

Zum einen bietet werden Methoden zum Starten und Stoppen des Evolutionsprozesses bereit gestellt. Damit fungiert EvolutionModel als Schnittstelle für jede Steuerung durch eine SW-Komponente oder den Benutzer.

Zudem wird Funktionalität bereit gestellt, die allgemein für die Realisierung von Modellen, genetischen Operationen und Szenarien benötigt wird. So wird z.B. das aktuell beste Individuum aller beteiligten Inseln festgehalten. Wird ein neues gefunden, so wird über das implementierte Observer Patter möglichen allen registrierten Objekten ein Event gesendet, das eine Änderung am Zustand des Models signalisiert. Entsprechende Objekte müssen dazu lediglich die Schnittstelle IModelObserver anbieten und sich als Observer registriet haben.

Um eine globale parallele Ausführung von unterschiedlichen Aufgaben zu ermöglichen, hält das EvolutionModel einen ExecuterService und bietet Methoden um diesem Aufgaben (Callable und Runnable) zur Ausführung zu übergeben. Durch die zentrale Verwaltung ist es möglich alle parallelen ablaufenden Aufgaben mit nur einem Thread-Pool pro Model abzuwickeln, was den Overhead zum Erzeugen und Verwalten eigenständiger Pools in spezielleren Bausteinen einspart. Die im Framework integrierten genetischen Operationen verwenden diesen Executorservice beispielsweise, um eine parallelisierte Ausführung zu ermöglichen.

Individuen und Lebensräume

Wie im einleitenden Abschnitt beschrieben wird eine Menge Individuen für die evolutionäre Entwicklung verwendet. Diese Menge wir im Framework durch die Klasse Population repräsentiert, die beliebig viele Individuals aufnimmt, verwaltet und zugriff auf sie gewährt. Ein Individuum besteht aus beliebig vielen Genes, die je nach dem bearbeiteten Problem alles möglich sein können. In dem von uns behandelten Szenario wird die Klasse noch spezialisiert und mit Koordinaten sowie einem optionalen Namen versehen.

Beim Erzeugen der Individuen und bei allen anderen Operationen die direkt auf Genen operieren, muss auf eine Factory zurückgegriffen werden. Ein solche kann durch die Implementierung der IGeneFactory Schnittstelle in das Framework eingebunden werden. Die darin definierten Methoden erlauben den gezielten und zufälligen Zugriff auf die Gene, die für die Bearbeitung eines Szenarios zur Verfügung stehen. Die Factory ist insbesondere dafür zuständig diese Gene aus einer Datei, Benutzungsoberfläche oder ein anderes Medium zu laden.

Während der Entwicklung sind mehrere dieser Factories entstanden. Die SpringBackedGeneFactory läd Gene aus dem IOC-Container von Spring. Diese Implementierung eignet sich gut zum ersten Kontakt mit dem Framework, da im Prinzip beliebige Klassen als Gene geladen werden können, ohne dass sich diese direkt auf ein Problem beziehen. Die folgende Definition zeigt ein solches Gen, das als Bean über seine id ansprechbar ist und die angegebenen Eigenschaften hat.

</bean>
    <bean id="gene9" class="de.fh.wiesbaden.puva.gen.scenario.tsp.TSPGene">
    <property name="id" value="9" />
    <property name="name" value="Köln" />
    <property name="XPos" value="800.0" />
    <property name="YPos" value="50.0" />
</bean>

Nach der Anwendung der genetischen Operationen kann ein Individuum für ein spezielles Szenario unbrauchbar sein, da es wichtige Einschränkungen nicht mehr einhält. Dies ist zum Beispiel der Fall, wenn man mit Permutationen einer Menge von Genen arbeitet, die in einem Individuum nicht mehrmals enthalten sein dürfen. Darum kann für jedes Individuum eine Verifikation sowie ggf. seine Reparatur durchgeführt werden. Beides ist voll abhängig vom Szenario und muss bei Bedarf bereitgestellt werden. Mit Hilfe der IPopulationTools Schnittstelle können diese Vorgänge implementiert und über den Kontext in den Ablauf der Evolution integriert werden.

Durch die Realisierung der IFitness Schnittstelle wird dem Framework eine Methode zur Verfügung gestellt, mit deren Rückgabewert eine Aussage über die Güte eines Individuums getroffen werden können. Die sogenannte Fitness-Funktion wird bei vielen genetischen Operationen, wie z.B. der Selektion, und der Auswahl des am Besten angepassten Individuums verwendet. Da es sich bei der Bestimmung der Fitness, abhängig von der Anzahl der Gene und der Methode mit man dann den Wert berechnet, um einen sehr aufwändigen Prozess handelt und der selbe Wert auf mehrmals benötigt wird, kann ein Individual diesen Wert speichern und dann immer wieder verwenden. Werden seine Gene verändert, ist der Wert natürlich nicht mehr gültig und muss neu berechnet werden. Wird trotzdem versucht den Wert abzurufen, so wird eine Exception geworfen die den ungültigen Wert bemängelt.

Möchte man Individuen vergleichen, um eine Aussage darüber treffen zu können, welches besser an das Problem angepasst ist, kann man sich fragen ob ein höherer oder geringerer Fitness-Wert der bessere ist. Da wir im Laufe der Implementierung feststellen mussten, das diese Entscheidung sehr stark vom Problem und der eingesetzten Methode zur Berechnung des Wertes abhängt, entschieden wir uns eine Methode in die IPopulationTools Schnittstelle aufzunehmen. Damit kann (und muss) die Berechnung und der Vergleich der Fitness-Werte für jedes Szenario implementiert und in das Framework eingebaut werden.

Genetische Operationen

Die genetischen Operationen sind ein weiterer wichtiger Bestandteile des Frameworks. Da sie ebenso wie das Model zunächst unabhängig vom Problem sind das bearbeitet wird, können sie völlig unabhängig implementiert werden. Es werden drei Schnittstellen bereitgestellt, die die Implementierung und den flexiblen Einsatz unterschiedlicher Operationen ermöglicht.

  • ISelection - Selektionsalgorithmus zur Auswahl der am Besten angepassten Individuen
  • ICrossover - Kreuzen zweier Individuen einer Population
  • IMutator - Mutation eines Individuums.

Beim Implementieren eines Modells muss der Entwickler die Verwaltung der Operationen selbst in die Hand nehmen. An dieser Stelle wurde bewusst eine Entscheidung gegen Abstraktion gewählt, da der Einsatz sehr stark vom Vorgehen innerhalb des Modells abhängt. So kann man zum Beispiel einen konkreten IMutator für alle Mutationen im Modell verwendet, oder man teilt die Evolution auf verschiedene Inseln auf und arbeitet auf jeder mit einem anderen. Selbiges gilt auch für ICrossover und ISelection und gewährt höchst mögliche Flexibilität bei der Umsetzung.

IContext hält wichtige Objekte für den Ablauf der Evolution bereit

Kontext

Neben den Grundbausteinen für den evolutionären Prozess sind auch weitere Operationen nötig, die der IContext zur Verfügung stellt. Das EvolutionModel hält eine Instanz des Kontextes und reicht diese den meisten genetischen Operationen beim Aufruf weiter. Da nur eine Instanz verwendet wird, ist ganz besonders darauf zu achten, dass der eingesetzte Code auf jeden Fall Thread-Safe ist.

Bei wird vor allem auf den eingesetzten Zufallszahlengenerator IRandom zurück gegriffen, der eine Voraussetzung für z.B. die Mutation ist. Da der im JRE integrierte Generator zu schlechte Ergebnisse liefert (häufig die selben Werte), haben wir einige seiner Methoden in die Schnittstelle übernommen und so den flexiblen Einsatz fortgeschrittener Implementierungen ermöglicht. Das Framework stellt als erste Verbesserung einen MarsenneTwister bereit.

Parallelisierung der Evolutionsmodelle

Kern der Anwendung ist das Evolutionsmodell. In der Referenzimplementierung haben wir uns für das einige Variationen des Insel-Modells entschieden. Eine Insel beherbergt dabei eine Population von Individuen, die von Generation zu Generation durch die genetischen Operationen weiterentwickelt werden. Die ausgesuchten Variationen lassen sich sehr gut parallelisieren, indem man z.B. die Inseln parallel evolutionieren lässt. Dies wird mit dem Planet-Modell umgesetzt, bei dem nicht nur mehrere Inseln parallel Populationen entwickeln, sondern auch die genetischen Operationen parallelisiert wurden. Beim zusätzlich erweiterten Nachbarschafts-Modell werden die Individuen von einer Insel auf alle anderen Inseln zufällig übertragen. Dadurch profitieren alle Inseln von den Fortschritten der einzelnen.

  • Insel-Modell

Jeder Insel wird als selbständiger Thread gestartet. Die Oberklasse "PlanetModell" ist sowie Starter als auch ein Verwalter von den Inseln, d.h. intern wird ein "Worker" gestartet, der die besten Inviduen aus einer Queue konsumiert. Jeweiliger Insel von seiner Seite stellt sein bestes Individuum bei jedem Durchlauf für PlanetModel bereit, indem er das Individuum in die Queue platziert.

  • Nachbarschafts-Modell

Obwohl ein paralleles Insel-Modell bereits zu einer erheblichen Verbesserung des Ergebnisses einer Berechnung führt, werden verschiedene Populationen noch isoliert voneinander entwickelt. Die einzelnen Populationen kommunizieren nicht und profitieren also nicht von den parallel laufenden Entwicklungen. Diesen Schwachpunkt versucht das Nachbarschafts-Modell zu lösen, indem Individuen der Populationen untereinander getauscht werden.

Integration des Nachbarschaftsmodells in in das Framework

Zur Realisierung wird dabei mit den spezialisierten NeighborhoodIslands gearbeitet, die einen isolierten Lebensraum für je eine Population darstellen. Das NeightborhoodModel verfügt über einen dedizierten Thread, der die besten Individuen einer Insel auf alle anderen Insel transportiert und diesen Prozess zyklisch mit den anderen Inseln wiederholt. Der Evolutionsprozess einer NeighborhoodIsland wurde um das Einfügen der übertragenen Individuen in die aktuelle Population erweitert.

Durch die zusätzliche Kommunikation entsteht ein beträchtlicher Overhead, sowohl für das Auswählen und Übertragen der Individuen, aber auch die dazu nötige Synchronisation. Da jede Insel in einem eigenen Thread läuft und auch für die Evolutionären-Operationen teilweise mehrere Threads eingesetzt werden, ist dies ein besonders wichtiger Punkt, denn es muss sichergestellt werden, dass neue Individuen den Ablauf nicht stören. Dazu hat jede Insel eine Queue, in die eine List mit transferierten Individuen eingefügt werden kann. Auch beim bestimmen der Individuen einer Insel, die zu den anderen übertragen werden, ist Synchronisation nötig, denn nur wenn ein exklusiver Zugriff auf eine Population gegeben ist, kann dieser Vorgang erfolgreich und konsistent abgeschlossen werden.

Problemspezifische Erweiterungen

Um nun mit den beschriebenen Mechanismen der genetischen Algorithmen ein Problem zu bearbeiten, müssen folgende Schnittstellen bereitgestellt werden:

  • IGeneFactory
  • IPopulationTools
  • IFittness

Eine genaue Beschreibung findet sich in den vorherigen Abschnitten und in der Beschreibung zur Realisierung des TSP Szenarios.

Konfiguration

Das Modell und die verwendeten Algorithmen werden durch das Dependency Injection Framework Spring zu einer Anwendung zusammen gebaut. Dies ermöglicht den leichten Austausch einzelner Komponenten durch Anpassug einer Konfigurationsdatei. So wird die geforderte Flexibilität bezüglich der Anpassbarkeit an neue Probleme erreicht.

Im folgendenm Abschnitt wird der Aufbau der XML-Konfigurationsdatei am Beispiel des TSP beschrieben.

Zuerst wird Arbeitsfläche instanziert, die der Nutzer implementiert hat. Dabei werden Gen-Factory und Evoluionsmodell angebunden.

	<bean id="mapView" class="de.fh.wiesbaden.puva.gen.scenario.tsp.ui.MapViewUi">
		<property name="geneFactory" ref="mapViewGeneFactory" />
		<property name="evolutionModel" ref="planet0" />
	</bean>

GenFactory wird instanziert.

	<bean id="mapViewGeneFactory"
		class="de.fh.wiesbaden.puva.gen.scenario.tsp.ui.TSPMapViewGeneFactory" />

Ein Observer wird registriert. Dieser Observer, in diesem Fall ein Console Observer, bekommt immer die besten Individuen im Laufe der ganze Evolution. Die Abhängigkeiten sind: Model und Context

	<bean id="BestIndividualObserver"
		class="de.fh.wiesbaden.puva.gen.ui.console.BestIndividualObserver">
		<property name="model" ref="planet0" />
		<property name="contex" ref="context" />
	</bean>

Ein Evolutionsmodell wird instanziert. In diesem Fall ein Inselmodell. Dieses Modell benötigt eine "queueSize" Variable. Diese Variable legt die Queue-Größe für den internen Consument an. Je mehr Inseln man hat, desto größer muss die Queue sein. Weitere Abhängigket ist Context.

	<bean id="planet0" class="de.fh.wiesbaden.puva.gen.islandmodell.PlanetModell"
		init-method="init">
		<property name="queueSize" value="20" />
		<property name="context" ref="context" />
	</bean>

Weiter müssen auch die Insel instanziert werden, die alle dann an den Modell angehängt werden. Bei der instanzierung müssen mehrere wichtige Werte gesetzt werden.

context
Der Context muss registriert werden.
name
Es muss ein Name für den Insel festgelegt werden.
planetModell
Das zugehörige Evolutionsmodell
everyGenerationBestIndToTake
Mit dieser Variable legt man fest, wie oft der beste Individuen an das Modell von den Insel geschickt wird. In diesem Fall bei jeder 30. Generation. Um unnötigen Overhead zu vermeiden, soll man diesen Wert nicht zu klein halten.
populationSize
Diese Eigenschaft legt fest, wie groß die Population maximal werden darf. Damit wird Überbevolkerung von Inviduen vermiden.
selection
Hier wird der Selektionsverfahren festgelegt.
individualsToSelect
Wieviele Individuen nach der Selektion übrig bleiben dürfen.
populationCrossoverReturner
An dieser Stelle wird Crossover festgelegt.
populationMutateReturner
An dieser Stelle wird Mutation festgelegt.
termination
Und schließlich die Termination.

So kann man beliebig viele Inseln instanzieren, die dann parallel abgearbeitet werden.

	<bean id="island0" scope="prototype" class="de.fh.wiesbaden.puva.gen.islandmodell.IslandConc">
		<property name="context" ref="context" />
		<property name="name" value="island0" />
		<property name="planetModell" ref="planet0" />
		<property name="everyGenerationBestIndToTake" value="30" />
		<property name="populationSize" value="100" />
		<property name="selection" ref="kTournament" />
		<property name="individualsToSelect" value="20" />
		<property name="populationCrossoverReturner" ref="childrenAndParentsCrossoverReturner" />
		<property name="populationMutateReturner" ref="populationMutateReturner0" />
		<property name="termination" ref="terminator0" />
	</bean>

Weiterer Bean, der instanziert werden muss, ist CrossoverReturner. Er beinhaltet einen beliebigen Crossover. Threads Variable legt Anzahl der Threads fest. So wird Crossover immer parallel abgearbeitet.

<bean id="childrenAndParentsCrossoverReturner" scope="prototype" class="de.fh.wiesbaden.puva.gen.model.operations.crossover.population.ChildrenAndParentsCrossoverReturner">
		<property name="ctx" ref="context" />
		<property name="crossover" ref="doubleOffspringCrossover" />		
                <property name="threads" value="2"></property>
	</bean>

Desweiteren wird die Temmination festgelegt. Dabei besteht die Termination selbst aus mehreren Terminatoren, die jeder Zeit nachgerüstet werden können.

TerminationByTime
Der Insel wird nach angegebene Zeit terminiert.
TerminationByMaxGeneration
Der Insel wird terminiert, nachdem die angegebene Generationsanzahl erreicht wurde.
TerminationByInbreeding
Der Insel terminiert, wenn Inzucht in der Population festgestellt wird.
TerminationByBestFitness
Der Insel wird terminiert, wenn der angegebene Fitnesswert erreicht wird.
TerminationByFitnessDifference
Der Insel wird terminiert, wenn es zu kleine Differenz zwischen besten Individuen festgestellt wird.
<bean id="terminator0" scope="prototype" class="de.fh.wiesbaden.puva.gen.model.operations.termination.Termination">
	<property name="terminations">
		<list>
			<bean class="de.fh.wiesbaden.puva.gen.model.operations.termination.TerminationByTime">
				<property name="seconds" value="60" />
			</bean>
			<bean class="de.fh.wiesbaden.puva.gen.model.operations.termination.TerminationByMaxGeneration">
				<property name="generations" value="50000"></property>
			</bean>
			<bean class="de.fh.wiesbaden.puva.gen.model.operations.termination.TerminationByInbreeding" />
			<bean class="de.fh.wiesbaden.puva.gen.model.operations.termination.TerminationByBestFitness">
				<property name="context" ref="context" />
				<property name="bestFitness" value="0"></property>
			</bean>
			<bean class="de.fh.wiesbaden.puva.gen.model.operations.termination.TerminationByFitnessDifference">
				<property name="fitnessDifference" value="3"></property>
			</bean>
		</list>
	</property>
</bean>	

Population-Bean beinhaltet Context und PopulationTools.

	<bean id="population" scope="prototype"	class="de.fh.wiesbaden.puva.gen.model.population.Population">
		<property name="context" ref="context" />
		<property name="tools" ref="populationTools" />
	</bean>

PopualtionTools

        <bean id="populationTools" class="de.fh.wiesbaden.puva.gen.scenario.tsp.TSPPopulationTools" />

MutatorWrapper benötigt Context, einen beliebigen Mutator, Wahrscheinlichkeitwert für die Mutation und Anzahl der Threads.

	<bean id="populationMutateReturner0" scope="prototype" 
        class="de.fh.wiesbaden.puva.gen.model.operations.mutator.ConcurrentMutatorWrapper">
		<property name="context" ref="context" />
		<property name="mutator" ref="nRandomGenesMutator"></property>
		<property name="probability" value="0.05"></property>
		<property name="threads" value="2"></property>
	</bean>

Der passende Mutator.

	<bean id="nRandomGenesMutator" scope="prototype"
        class="de.fh.wiesbaden.puva.gen.model.operations.mutator.NRandomGenesMutator">
		<property name="n" value="1"></property>	
	</bean>

Die passende Selektion.

	<bean id="kTournament" scope="prototype" class="de.fh.wiesbaden.puva.gen.model.operations.selection.KTournamentSelection" >
		<property name="k" value="10" />	
	</bean>

Der passender Crossover.

	<bean id="doubleOffspringCrossover" scope="prototype" 
        class="de.fh.wiesbaden.puva.gen.model.operations.crossover.DoubleOffspringCrossover" />

An dieser Stelle wird der Context festgelegt. Der beinhaltet Fitness, Random Generator, Gen Factory und Verweis auf Evolutionsmodell.

	<bean id="context" class="de.fh.wiesbaden.puva.gen.model.Context">
		<property name="fitness" ref="fitness" />
		<property name="random" ref="randomGenerator" />
		<property name="geneFactory" ref="mapViewGeneFactory" />
		<property name="evolutionModel" ref="planet0" />
	</bean>

Fitness:

	
    <bean id="fitness" class="de.fh.wiesbaden.puva.gen.scenario.tsp.TSPFitness" />

Random Generator:

    <bean id="randomGenerator" class="de.fh.wiesbaden.puva.gen.tools.MersenneRandom" />

Parallelisierung

Insel/Nachbarschaft Modell

Jeder Insel wird parallel gestartet. Im Falle von Insel Modell werden die Inseln isoliert voneinander abgearbeitet, das führt dazu, dass wenn ein Insel in die "falsche" Richtung sich evolutioniert hast, gibt es keine Möglichkeit die Evolution ggf. zu verbessern. Bei Nachbarschaft Modell kontaktieren die Inseln miteinander, indem jeder Insel ihre besten Individuen an die andere weitergibt. Somit erzielt dieses Modell meistens bessere Resultaten. Tests haben gezeigt, dass Einsatz von Modellen viel bessere und vorallem schnellere Resultaten liefert.

Crossover

Crossover wird parallelisiert indem einen Wrapper einsetzt. Dieser Warapper hantiert mit Populationen deren Individuen mit einander gecrosst werden sollen. Die Crossover selbst können nur mit Individuen-Paar arbeiten. Sowie bei Wrappern als auch bei Crossover können so verschiedene Implementierungen eingesetzt werden.

Mutation

Mutation wird ebenfalls hochgrädig parallelisiert. In Wrapper bekommen die Threads jeweils ihre Equivalenzklassen von Population erteilt, die sie parallel abarbeiten.

Verifikation

Verifikation wurde auch parallelisiert. Funktioniert nachdem gleichen Prinzip wie Mutation. Allerdings ist ganze Funktionalität in Klasse Population untergbracht wurde, somit kann die Population sich selber parallel verifizieren.

Szenario

Um das im Projekt entwickelte Framework praktisch zu erproben, wurde ein Problem gesucht, das mit deterministischen Algorithmen nur mit sehr hohem Aufwand gelöst werden kann. Mit dem Traveling Salesman Problem (TSP) haben wir ein solches zur Bearbeitung gefunden.

Ziel ist die kürzeste Strecke zwischen verschiedenen Städten auf der Handelsroute eins Händlers zu finden. Nähere Informationen finden sich z.B. in der Wikipedia oder auf den Webpräsenzen der vielen Forschungsprojekten auf dem Bereich der theoretischen Informatik.

Integration in das Framework

Erweiterungen zur Implementierung des TSP Szenarios

Das nebenstehende Bild zeigt die Erweiterung des Frameworks, mit der das TSP integriert wurde. Andere Probleme lassen sich ganz ähnlich übertragen, denn konzeptionell sind lediglich die dargestellten Interfaces/Klassen abhängig vom Szenario.

Mit TSPFitness wird die Fitnessfunktion bereitgestellt, die in diesem Fall die Distanz zwischen den Städten aufsummiert und zurück gibt. Die TSPPopulationTools bietet dann eine Methode an, mit der verschieden Individuen verglichen werden können. In diesem Fall ist das mit dem geringsten Fitness-Wert das bessere, da die Distanz zwischen den Strecken dann offensichtlich kürzer ist. Des weiteren wird über diese Klasse eine Methode zur Reparatur von Individuen angeboten. Dabei werden doppelte Städte innerhalb einer Route gesucht und eine davon durch eine bisher nicht verwendete Stadt ersetzt.

Wie bereits zuvor erwähnt ist das TSPGene ein spezialisiertes Gene, dass die Koordinaten der repräsentierten Stadt enthält. Da mit der TSPMapView eine grafische Benutzungsoberfläche eingesetzt wird, über die der Benutzer auf einer Karte selbst die Städte definiert, verwendet die abgebildete TSPGeneFactory diese Eingabe und erzeugt daraus die Gene. In der TSPFileGeneFactory Implementierung werden Dateien des TSPLIB-Projektes der Uni Heidelberg als Eingabe verwendet.

Die angeschlossene GUI implementiert IModelObserver und bekommt darüber immer dann ein Ereignis signalisiert, wenn ein neues bestes Individuum gefunden wurde, eine konfigurierbare Anzahl an Generationen vergangen ist oder der Prozess terminierte. Darauf wird mit dem Zeichnen der aktuell besten Route sowie Anzeige der aktuellen Generation reagiert.

Grafische Oberfläche

Eingabe des Benutzer ist nicht in optimaler Reihenfolge

Um die Arbeit des Frameworks und das Szenario in einer Abschlusspräsentation vorführen zu können, wurde eine GUI implementiert, die dem Benutzer eine Karte anzeigt. Auf dieser kann er nach belieben Wegpunkte der Route setzen, die dann durch das Framework optimiert wird. Zur Darstellung wird dabei auf das Kartenmaterial des OpenStreetMap-Projektes zurück gegriffen.

Zum starten der Anwendung kann die Klasse TSPMapView verwendet werden, die als Übergabeparameter ein Konfiguration für den Spring IOC-Container erwartet. Folgende Konfigurationen wurden während der Entwicklung entworfen (Order conf/):

  • TSP_MapView.xml – Einfaches nicht parallelisiertes Inselmodel
  • P2_TSP_MapView.xml – Parallelisiertes Inselmodel (PlantModel)
  • P3_TSP_MapView.xml – Nachbarschaftsmodel

Diese Dateien können beliebig verwendet und bei Bedarf angepasst werden.

Die Route wurde durch die genetischen Operationen optimiert

Performance-Analyse

Abschließend werden an dieser Stelle noch einige Daten zu unseren Untersuchungen bezüglich der Beschleunigung durch die vorgenommene Parallelisierung präsentiert. Alle Tests wurden auf einem Server mit 4 Quad-Core Opteron CPUs und 20 GB Arbeitsspeicher ausgeführt. Für die im folgenden beschriebene Analyse kam die Datei a280 von dem TSPLIB-Projekt der Uni Heidelberg zum Einsatz. Es umfasst eine Rundreise mit 280 Städten, für die ein optimale Route mit einem Fitness-Wert von 2579 bereits berechnet wurde.

Der Fitness-Wert dieser optimalen Route wurde als eines der Abbruchbedingungen verwendet. Da wir das Framework nicht endlos lang nach der Lösung suchen lassen konnten, haben wir zudem ein Zeitlimit von 10 Minuten und eine Obergrenze von 1.000.000 Generationen als weitere Kriterien verwendet. Letzter Grenzwert wurde allerdings in keinem Test erreicht.

Insgesamt wurden für jede Konfiguration und jedem Model fünf Testläuft durchgeführt, da genetische Algorithmen nicht deterministisch im Ablauf sind, hätte ein Durchgang allein nicht ausgesagt. Als Kriterium wurde der Fitness-Wert der besten Route eines Testlaufes verwendet (geringer = besser). Bei den parallelisierten Modellen wurden mehrere Durchläufe mit unterschiedlicher Anzahl an Threads zur Anwendung der genetischen Operationen durchgeführt.

Damit die Testläufe nachvollzogen und die Einstellungen genauer studiert werden können, befinden sich die Spring Konfiguration im Umfang des Quellcodes. Der Name gibt jeweils Auskunft darüber, wieviele Inseln (i) und Threads für Mutation (m) und Corssover (c) zum Einsatz kamen. In P2_TSP_noGUI_2i_2m_2c.xml zum Beispiel wurde jeder der genannten Parameter mit 2 belegt.

Bei den nun folgenden Diagrammen sybolisiert ein Punkt je einen Durchlauf, der nach den obern beschriebenen Kriterien beendet wurde. Auf der X-Achse findet sich die Anzahl der dabei erzeugten Generationen. Auf der Y-Achse der Fitness-Wert des besten gefundenen Individuums.

Nicht parallelisiertes Inselmodel (SimpleIslandModel)

Nicht-parallel.gif

Wie man sieht wurden sehr viele Generationen während dem Ablauf der Evolution erzeugt. Die erreichten Fitness-Werte liegen im Bereich zwischen 5500 und 6050, was sehr weit von der optimalen Route entfernt ist.

Paralleles Inselmodel (PlanetModel)

Bei diesem Model wurden immer zwei simultan arbeitenden Inseln eingesetzt. Die genetischen Operationen wurden mit 2, 4 und 8 Threads ausgeführt.

Dia parallel.gif

Konfigurationen:

  • P2_TSP_noGUI_2i_2m_2c.xml
  • P2_TSP_noGUI_2i_4m_4c.xml
  • P2_TSP_noGUI_2i_8m_8c.xml

Nachbarschaftsmodel

Auch bei diesem Model wurden zwei simultan arbeitenden Inseln eingesetzt. Die genetischen Operationen wurden mit 2, 4 und 8 Threads ausgeführt.

Dia nachbarschaftsmodel.gif

Die Fitness-Werte der jeweils besten gefunden Routen liegen zwischen 3739,23 und 4410,32. Damit konnte nochmals eine Verbesserung im Ergebnis erreicht werden. Da dieses Model neben den genetischen Operationen noch die Kommunikation zwischen den Inseln realisiert, wird ein etwas höherer Aufwand erbracht, als bei den vorangegangen Modellen. Die Abweichung bei der Konfiguration mit 8 Threads für Mutation und Crossover lässt sich mit der kleinen Population erklären. Wir haben in den Tests lediglich 100 Individuen je Population zugelassen, womit die Kosten für Synchronisation und Aufteilung der Aufgaben vermutlich zu hoch sind. Im abschließenden Test wird auf diesen Punkt eingegange.

Konfigurationen:

  • P3_TSP_noGUI_2i_2m_2c.xml
  • P3_TSP_noGUI_2i_4m_4c.xml
  • P3_TSP_noGUI_2i_8m_8c.xml

Weitere Testläufe mit veränderter Konfigration

Bei der genauen Analyse der in den letzten Abschnitten vorgestellte Messungen viel auf, dass wir immer mit sehr kleinen Populationen gearbeitet hatten. Die folgende Tabelle zeigt die Auswertung der Daten des Nachbarschaftsmodells mit eine Populationsgröße von 1000/2000 Individuen, wobei jeweils 450/600 in die nächste Generation übernommen wurden.

Dia weitere.gif

Es zeigt sich, dass nicht nur die resultierenden Fitness-Werte besser sind, sondern auch die Parallelisierung anhand der Anzahl der bearbeiteten Generationen sichtbar wird. Auf der X-Achse befinden sich die Anzahl der Generationen, die während dem Prozess der Evolution erzeugt wurden. Auf der Y-Achse findet sich der beste erzielte Fitness-Wert.

Beispiel zur Deutung der Beschriftung:

20m,20c,1000p – Jeweils 20 Threads für Mutation und Crossover, Population mit 1000 Individuen

Die Konfigurationsdateien mit der entsprechenden Benennung befinden sich beim Source-Code.

Download

Die folgenden Downloads sind nur intern über das Netz der Fachhochschule erreichbar.

Quellcode
Ausführbares JAR