4.5 Anwendung verschiedener Strategien
4.5.1 Berechnung der Ordnung der Unterpopulationen
4.5 Anwendung verschiedener Strategien |
|
Bei einer in mehrere Unterpopulationen geteilten Population (regionales Modell) sind die einzelnen Unterpopulationen unter sich in ihrer Parametrierung identisch und gehen daher bei der Suche nach derselben Strategie vor. Von der Arbeit mit unterschiedlichen Evolutionären Algorithmen ist bekannt, daß die Wahl der Operatoren und deren Parameter einen großen Einfluß auf den Verlauf und den Ausgang der Optimierung hat.
Eine logische Erweiterung des regionalen Modells eines Evolutionären Algorithmus ist die Verwendung unterschiedlicher Strategien für einige oder alle Unterpopulationen (engl. multiple strategies). Jede Unterpopulation verwendet einen eigenen Satz von Parametern, der sich von denen der anderen Unterpopulationen in einem, in mehreren oder in allen Parametern unterscheiden kann. Je nach Anwendung der zur Verfügung stehenden Operatoren bzw. deren Parametrierung kann sich das Suchverhalten der einzelnen Unterpopulationen stark oder wenig voneinander unterscheiden.
Durch die Verwendung des regionalen Modells bleiben dessen Eigenschaften erhalten. Die Unterpopulationen suchen weiterhin parallel zueinander. Von Zeit zu Zeit findet ein Austausch von Individuen zwischen den Unterpopulationen (Migration) statt. Dies führt zu einer Propagierung neuer und guter Individuen und damit zu einer Fokussierung der Suche auf vielversprechende Regionen des Suchbereiches.
Für die Anwendung verschiedener Strategien pro Unterpopulation gibt es zwei Ansatzpunkte:
Oftmals sind aus vorangegangenen Experimenten mit ähnlichen Optimierungsproblemen Erkenntnisse vorhanden, mit welchen Operatoren bzw. Parametern ein Problem gut zu lösen ist. Da diese Entscheidung nur in den seltensten Fällen eindeutig ist, bietet sich eine Anwendung verschiedener Strategien an. In einem ersten Lösungsansatz werden die aus Sicht des Anwenders vielversprechenden Operatoren und Parameter angewandt. Mittels einer einfachen Auswertung der Konvergenz der einzelnen Unterpopulationen können recht schnell die Operatoren und Parametereinstellungen verworfen werden, die keinen großen Beitrag zum Fortschritt der Optimierung geben.
4.5.1 Berechnung der Ordnung der Unterpopulationen |
|
Für die Auswertung des Einsatzes unterschiedlicher Strategien ist es notwendig, ein Maß zu finden, das es ermöglicht, den Erfolg der einzelnen Strategien zu bewerten. Als Maß für den Erfolg einer Unterpopulation wird die Position einer Unterpopulation in einer Ordnung der Unterpopulationen verwendet. Dabei ist eine niedrige Position besser als eine hohe Position. Daraus kann abgelesen werden, wie gut eine Unterpopulation zu einem bestimmten Zeitpunkt im Vergleich zu den anderen Unterpopulationen ist. Damit ist eine einfache Bewertung der Anwendung verschiedener Strategien möglich.
Zur Bildung der Ordnung der Unterpopulationen müssen die Unterpopulationen untereinander nach einem einheitlichen Kriterium sortiert werden. Da eine Unterpopulation aus einer Anzahl von Individuen besteht, ergibt sich die Güte einer Unterpopulation aus den Eigenschaften ihrer Individuen.
Das Verfahren zur Bildung der Ordnung der Unterpopulationen findet nach folgendem Schema statt:
Dieser Vorgang wird im folgenden an drei speziellen Varianten genauer erläutert.
Bewertung durch alle Individuen einer Unterpopulation:
Bewertung durch das beste Individuum jeder Unterpopulation:
Bewertung durch das beste Individuum der gesamten Population:
Die zweite und dritte Variante sind Spezialfälle der ersten Variante, die sich durch Beschränkung der Anzahl der Individuen, die zur Bewertung verwendet werden, ergeben.
Die Ordnung der Unterpopulationen gibt ein momentanes Abbild der Unterpopulationen. In Abhängigkeit der verwendeten Operatoren und Parameter kann die Ordnung innerhalb einiger Generationen stark schwanken. Dies ist im besonderen zu beobachten, wenn die Strategien der Unterpopulationen ähnlich erfolgreich sind. Für die Darstellung und Bewertung ist es daher von Vorteil, wenn die Ordnung der Unterpopulationen einer Gewichtung unterzogen wird. Dadurch wird aus dem Rang jeder Unterpopulation ein Positionswert gebildet, der einen gewichteten Mittelwert des Rangs der Unterpopulation in den zurückliegenden Generationen darstellt.
Dieser Positionswert wird für die folgenden Darstellungen verwendet. Je kleiner der Positionswert ist, um so größer ist der Erfolg einer Unterpopulation. Wenn sich der Rang einer Unterpopulation lange nicht verändert, wird der Positionswert gleich dem Rang.
4.5.2 Beispiel der Anwendung verschiedener Strategien |
|
Die Bewertung des Erfolgs einer Strategie hängt entscheidend von der verwendeten Methode zur Bestimmung der Ordnung der Unterpopulationen ab. Die Verwendung des besten Individuums der gesamten Population ist die einfachste Methode. Dafür liefert sie nur eine Aussage darüber, welche Unterpopulation die beste ist; es findet keinerlei Differenzierung zwischen den anderen Unterpopulationen statt. Eine Ordnung der Unterpopulationen kann erst durch Verwendung des besten Individuums jeder Unterpopulation ermittelt werden. Damit ist eine differenziertere Bewertung des Erfolgs der einzelnen Unterpopulationen möglich. Allerdings wird durch die ausschließliche Verwendung des jeweils besten Individuums immer noch eine beschränkte Bewertung des Erfolgs einer Unterpopulation vorgenommen.
Erst durch die Verwendung einer größeren Anzahl von Individuen der Unterpopulationen kann eine umfassendere Bewertung des Erfolgs einer Unterpopulation vorgenommen werden. Durch die größere Anzahl von Individuen wird die Verteilung der Gütewerte der Individuen mit in die Bewertung einbezogen. Damit kann eine Unterpopulation, die nicht das beste Individuum enthält, dafür aber fast nur gute Individuen, besser bewertet werden, als eine Unterpopulation mit wenigen sehr guten und vielen schlechten Individuen.
Die Verwendung der Verfahren soll an einem Beispiel illustriert werden, bei dem zwei Unterpopulationen miteinander verglichen werden sollen. Die erste Unterpopulation hat ein sehr gutes Individuum, die anderen Individuen sind schlecht. Die zweite Unterpopulation hat viele gute Individuen und nur wenige schlechte Individuen. Welche dieser beiden Unterpopulationen ist besser? Wenn die erste Unterpopulation mit dem sehr guten Individuum als beste Unterpopulation bewertet werden soll, dann kann eine der einfachen Methoden verwendet werden, die nur das beste Individuum/die besten Individuen zur Bewertung benutzen. Soll dagegen ein umfassenderes Abbild in der Ordnung der Unterpopulationen zum Ausdruck kommen, so müssen auch mehrere Individuen in die Bewertung einbezogen werden. Der Mittelwert der Fitneß der Individuen einer Unterpopulation ist eine solche Möglichkeit.
Abbildung 4-11 zeigt ein Beispiel des Verlaufs und der Ergebnisse bei der Anwendung verschiedener Strategien. Die Optimierung (hier: DeJong's Funktion 1 oder Hypersphäre) wurde mit 5 Unterpopulationen durchgeführt. Jede der Unterpopulationen verwendete eine andere Strategie, die sich in der Größe der verwendeten Mutationsschritte unterschieden (1: große Mutationsschritte; 2: mittlere Mutationsschritte; 3: kleine Mutationsschritte; 4: winzige Mutationsschritte; 5: mittlere und kleine Mutationsschritte zusammen). Je kleiner die Mutationsschritte sind, um so lokaler ist die Suche dieser Strategie. Alle Strategien verwendeten denselben Rekombinationsoperator, alle weiteren Parameter waren für alle Strategien identisch (z.B. generation gap: 0.9). Alle 40 Generationen fand eine Migration zwischen den Unterpopulationen statt. Dabei wanderten die besten Individuen in einer vollständigen Netzstruktur.
Die linke Grafik, die den Beginn des Laufs zeigt, läßt erkennen, daß am Anfang Strategie 5 am erfolgreichsten ist. Dies ändert sich erst ab Generation 200, wenn Strategie 2 besser wird und ab Generation 220 die Spitzenposition übernimmt, siehe mittlere Grafik. Ab Generation 300 wird Strategie 3 am besten und ab Generation 500 Strategie 4, siehe rechte Grafik. Strategie 1 zeigt während der ersten 50 Generationen ein gutes Verhalten, siehe linke Grafik, fällt dann aber zurück und kann nie wieder erfolgreich sein.
Abbildung 4-11: Anwendung verschiedener Strategien; oben: Ordnung der Unterpopulationen, unten: Zielfunktionswerte aller Individuen (Zielfunktionswert des besten Individuums je Unterpopulation); links: Beginn des Laufs, Mitte: Mitte des Laufs, rechts: Ende des Laufs
Bei Kenntnis der Beispielfunktion ist dieses Verhalten nicht verwunderlich. Große Mutationsschritte sind besonders zu Beginn erfolgreich, danach führen große Mutationsschritte nur noch zu Verschlechterungen. Entsprechendes gilt für die Strategien mit immer kleiner werdenden Mutationsschritten. Wenn größere Schrittweiten noch Fortschritte bringen, sind kleine Schritte zu langsam. Damit hat in diesem Beispiel jede der ersten vier Strategien ihren speziellen Einsatzbereich bzw. besten Zeitpunkt. Eine Zwischenstellung nimmt Strategie 5 mit den mittleren und kleinen Schritten ein. Es ist eindeutig aus der linken Grafik zu entnehmen, daß diese Strategie am Anfang die beste ist; ab und zu größere Schritte und meist kleinere Schritte sind eine gute Strategie. Ab Generation 200 ist dann aber eine der spezialisierteren Strategien besser, da Strategie 5 nur noch selten gute Individuen und meist schlechte Individuen produziert.
Ein Blick auf die unteren Grafiken unterstreicht diese Analyse. Strategie 5 (Unterpopulation 5 mit den Individuen 61-75) produziert von Beginn an in jeder Generation deutlich besser werdende Individuen. Bis Generation 50 kann dies auch Strategie 1 (Individuen 1-15). Danach produziert Strategie 1 nur noch schlechte Individuen, die guten Individuen kamen durch Migration in Unterpopulation 1. Bis Generation 200 hat Strategie 5 immer den größten Fortschritt zu verzeichnen. Erst dann wird Strategie 2 (Individuen 16-30) besser, siehe mittlere Grafik.
In allen unteren Grafiken ist deutlich der Effekt der Migration alle 40 Generationen zu erkennen. Neue gute Individuen von anderen Unterpopulationen werden in die Unterpopulationen eingefügt. Die Information dieser guten Individuen kann sich sehr schnell in den Unterpopulationen ausbreiten.
4.5.3 Analyse der Anwendung verschiedener Strategien |
|
Das Beispiel im vorigen Unterabschnitt verdeutlicht die Möglichkeiten, die sich aus der Anwendung verschiedener Strategien und der anschließenden grafischen Auswertung ergeben.
Zum ersten ist die Anwendung verschiedener Strategien einfacher und meist schneller als die Durchführung unabhängiger Experimente mit jeweils eigenen Parametereinstellungen. Die Ergebnisse werden in einer kompakteren Form dargeboten und sind leicht zu überschauen.
Zum zweiten ist die gleichzeitige Anwendung verschiedener Strategien in einem Lauf von großem Vorteil, da die für sich allein nicht sehr erfolgreichen Strategien in ihrer verbundenen Anwendung bessere Ergebnisse bringen als jede Strategie für sich. Es kommt z.B. recht häufig vor, daß zu Beginn eines Laufs eine andere Suchstrategie erfolgreich ist als in der Mitte oder am Ende eines Laufs (grobe Suche zu Beginn gegenüber feiner Suche am Ende, siehe Beispiel in Abbildung 4-11). Die Erzielung dieses Effekts wurde bisher durch die Adaption von Parametern der Suchstrategie versucht, was aber meist nur bei einfachen bzw. bekannten Optimierungsproblemen mit vertretbarem Aufwand zu erreichen ist.
Die Anwendung verschiedener Strategien ermöglicht damit eine höhere Stufe des Einsatzes Evolutionärer Algorithmen. Aus den angesprochenen Vorteilen sind dies im besonderen zwei Bereiche:
Ein Vorbild für die Anwendung verschiedener Strategien in der natürlichen Evolution kann leicht gefunden werden. So ist es viel wahrscheinlicher, daß sich voneinander getrennt entwickelnde Unterpopulationen auch verschiedene Strategien verwenden. Innerhalb einer Unterpopulation ist es dagegen wahrscheinlich, daß alle Individuen eine (fast) identische Strategie benutzen.
Die Anwendung verschiedener Suchstrategien für jede Unterpopulation wurde in einigen der frühen Berichte zu parallelen Evolutionären Algorithmen erwähnt. Tanese berichtete in [Tan87] von der Verwendung unterschiedlicher Mutations- und Rekombinationsraten für einige oder alle Unterpopulationen. Die Ergebnisse der Experimente wiesen darauf hin, daß das verwendete regionale Modell mit unterschiedlichen Parametern für die einzelnen Unterpopulationen robuster war, als es bei der Verwendung identischer Parameter der Fall war und die besten Werte für diese Parameter nicht bekannt sind.
Diese Dokument ist Teil der Dissertation von Hartmut Pohlheim
"Entwicklung und systemtechnische Anwendung Evolutionärer Algorithmen".
This document is part of the .
The is not free.
© Hartmut Pohlheim, All Rights Reserved,
(hartmut@pohlheim.com).
(