4.6 Konkurrierende Unterpopulationen
4.6.1 Erfolg der Unterpopulationen
4.6.2 Aufteilung der Ressourcen
4.6.3 Umsetzung der Verteilung der Ressourcen
4.6.4 Beispiel des Einsatzes konkurrierender Unterpopulationen
4.6 Konkurrierende Unterpopulationen |
|
Eine logische Erweiterung des regionalen Modells mit unterschiedlichen Strategien für die einzelnen Unterpopulationen ist das Prinzip der miteinander konkurrierenden Unterpopulationen (engl. competing subpopulations). Bei der Anwendung unterschiedlicher Strategien innerhalb des regionalen Modells blieb die Größe jeder Unterpopulation (Anzahl der Individuen in einer Unterpopulation) während eines Laufs konstant. Auch wenn eine Strategie nicht erfolgreich ist, standen dieser Strategie weiterhin dieselben Ressourcen zur Verfügung.
Von dieser Konstanz der Ressourcen wird bei der Anwendung des Prinzips miteinander konkurrierender Unterpopulationen abgegangen. Statt dessen wird die Größe jeder Unterpopulation davon abhängig gemacht, ob die von ihr angewendete Strategie im Moment erfolgreich ist. Eine erfolgreiche Unterpopulation bekommt mehr Ressourcen zur Verfügung gestellt, eine erfolglose Unterpopulation muß Ressourcen an andere Unterpopulationen abgeben.
Eine Entsprechung dieses Prinzips in der natürlichen Evolution liegt auf der Hand. Eine Unterpopulation, die erfolgreich ist, hat mehr Ressourcen zur Verfügung und kann sich dadurch meist besser fortpflanzen und entwickeln. Dieses Prinzip ist eines der grundlegenden in der Natur und läßt sich in den verschiedensten Bereichen beobachten.
Jedesmal, wenn ein Wettbewerb zwischen konkurrierenden Unterpopulationen durchgeführt wird, müssen die folgenden Schritte durchlaufen werden:
Die Anwendung der miteinander konkurrierenden Unterpopulationen ermöglicht eine effektive Verteilung der Ressourcen. Die Unterpopulationen, die am erfolgreichsten sind, erhalten mehr Ressourcen (Individuen) und damit mehr Rechenressourcen. Durch eine geeignete Adaption werden diese Ressourcen effektiv umverteilt, sobald es eine Verschiebung innerhalb des Erfolges der Unterpopulationen gibt.
Durch eine geeignete Wahl der Parameter können verschiedene Eigenschaften für das Verhalten der miteinander konkurrierenden Unterpopulationen definiert werden und damit die Stärke der Konkurrenz bzw. Unterdrückung erfolgloser Unterpopulationen durch erfolgreiche Unterpopulationen beeinflußt werden.
4.6.1 Erfolg der Unterpopulationen |
|
Die Berechnung des Erfolgs der Unterpopulationen wurde bereits im Abschnitt zur Anwendung verschiedener Strategien, Abschnitt 4.5, ab S., behandelt, die dortigen Ergebnisse werden hier verwendet. Der Erfolg der Unterpopulationen wird in einer Ordnung der Unterpopulationen ausgedrückt, die wie in Unterabschnitt 4.5.1, S. ermittelt wird. Um ein zu starkes Schwanken der Ordnung der Unterpopulationen zu verhindern, wird für den Erfolg der Unterpopulationen dieselbe Gewichtung (Gleichung 4-9) angewendet, wie für die Darstellung der Ordnung der Unterpopulationen.
4.6.2 Aufteilung der Ressourcen |
|
Bei jedem Wettbewerb zwischen den Unterpopulationen werden die zur Verfügung stehenden Ressourcen neu aufgeteilt. Dies kann einmal durch die Bestimmung von erfolgreichen und erfolglosen Unterpopulationen geschehen, andererseits aber durch eine gewichtete Aufteilung der Ressourcen.
Für die Bestimmung erfolgreicher und erfolgloser Unterpopulationen dient die gewichtete Ordnung der Unterpopulationen als Grundlage. Dadurch wird festgelegt, welche Unterpopulationen zusätzliche Ressourcen bekommen und welche Unterpopulationen Ressourcen abgegeben müssen.
Die einfachste Variante dafür ist, daß nur die beste Unterpopulation erfolgreich ist und Ressourcen erhält, alle anderen Unterpopulationen müssen Ressourcen abgeben. Dies würde während eines Laufs dazu führen, daß immer nur eine Unterpopulation viele Individuen enthält, alle anderen Unterpopulationen haben die minimale Anzahl an Individuen. Zu einer Koexistenz von zwei oder mehr Unterpopulationen kann es nicht kommen.
Etwas umfassender ist der Ansatz, daß ein Teil der Unterpopulationen als erfolgreich eingestuft wird, der Rest als erfolglos. Zum Beispiel können 25% der besten Unterpopulationen als erfolgreich eingestuft werden (Erfolgsrate = 0.25) und erhalten zusätzliche Ressourcen, die anderen 75% müssen Ressourcen abgeben. Dadurch können neben der besten Strategie auch solche Strategien mit einem größeren Teil der Ressourcen arbeiten, die zwar gut sind, aber nicht führend.
Bei einer genaueren Betrachtung dieses Prozesses der Aufteilung von Ressourcen finden sich Gemeinsamkeiten zur Fitneßzuweisung, siehe Unterabschnitt 3.2.1, ab S.. Bei der Fitneßzuweisung geht es darum, jedem Individuum aus seinem Zielfunktionswert, im Vergleich zu den Zielfunktionswerten der anderen Individuen des Selektionspools, eine Fortpflanzungswahrscheinlichkeit und damit die Anzahl möglicher Nachkommen zuzuweisen. Die Güte eines Individuums wird umgerechnet in die Ressourcen, die dem Individuum zur Produktion von Nachkommen zur Verfügung stehen.
Genau um denselben Sachverhalt geht es hier, nur auf einer höheren Ebene. Die zur Verfügung stehenden Ressourcen sollen auf die Unterpopulationen aufgeteilt werden. Die Erkenntnisse aus der Fitneßzuweisung können direkt auf die Verteilung der Ressourcen bei konkurrierenden Unterpopulationen angewendet werden und führen zur gewichteten Aufteilung der Ressourcen. Bei der Fitneßzuweisung wurde gezeigt, daß Verfahren auf der Basis der Reihenfolge der Individuen (ranking) am robustesten arbeiten. Die im Unterabschnitt 4.5.1, S., berechnete gewichtete Ordnung der Unterpopulationen, Gleichung 4-9, dient deshalb als Grundlage für die Verteilung der Ressourcen.
Im nächsten Schritt wird jeder Unterpopulation auf der Grundlage ihres Ranges ein Anteil an den insgesamt zur Verfügung stehenden Ressourcen zugewiesen. Aus dem Bereich der Fitneßzuweisung sind die beiden Verfahren lineares Ranking und nichtlineares Ranking bekannt. Parameter dieser Verfahren ist der Selektionsdruck SP. In Analogie dazu wird hier der Parameter des Verteilungsdrucks VP definiert. Dieser bestimmt, wie die Ressourcen verteilt werden. Für einen niedrigen Verteilungsdruck ist der Unterschied im Anteil der Ressourcen jeder Unterpopulation nur gering. Für einen hohen Verteilungsdruck, besonders bei Anwendung des nichtlinearen Ranking, hat die beste Unterpopulation einen sehr hohen Anteil an den Ressourcen, für die anderen Unterpopulationen ist der Anteil deutlich geringer. Die weiteren guten Unterpopulationen erhalten aber trotzdem einen höheren Anteil an Ressourcen als die schlechten Unterpopulationen.
In Abbildung 4-12 ist die Verteilung der Ressourcen auf acht Unterpopulationen für unterschiedliche Werte des Verteilungsdruckes dargestellt. Dabei wurde ein Minimum an Ressourcen (Unterpopulationsminimum, hier 1%), das jeder Unterpopulation zum Überleben zur Verfügung stehen muß, berücksichtigt.
Mit einem linearen Ranking ist nur ein maximaler Verteilungsdruck von 2 einstellbar. Da die beste Unterpopulation meist stärker bevorzugt werden soll, muß ein nichtlineares Ranking angewendet werden. Damit können Werte für den Verteilungsdruck bis zu Anzahl der Unterpopulation-2 verwendet werden.
Abbildung 4-12: Verteilung der Ressourcen auf die Unterpopulationen für lineares und nichtlineares Ranking und verschiedene Werte des Verteilungsdrucks
4.6.3 Umsetzung der Verteilung der Ressourcen |
|
Für die Umsetzung der berechneten Aufteilung der Ressourcen werden die folgenden Verfahren und Parameter benutzt bzw. müssen definiert werden:
Bisher wurde nur von den Ressourcen gesprochen. Es fehlte aber jede Umsetzung auf die vom Evolutionären Algorithmus benutzte Größe der Individuen. Diese wird durch den Ressourcenverbrauch definiert, der angibt, wieviele Ressourcen jedes Individuum benötigt.
Die einfachste Variante ist, daß jede Ressourceneinheit einem Individuum entspricht. Damit wird angenommen, daß die Individuen aller Strategien denselben Ressourcenverbrauch haben.
Es ist jedoch viel wahrscheinlicher, daß Individuen verschiedener Strategien einen unterschiedlichen Ressourcenverbrauch haben. Diese Annahme ermöglicht eine deutlich realistischere Modellierung der Konkurrenz zwischen Unterpopulationen bzw. verschiedenen Strategien. Eine Strategie kann z.B. mit 10 Ressourceneinheiten 10 Individuen versorgen, eine zweite Strategie nur 2 Individuen, eine dritte aber sogar 100 Individuen.
Der Parameter des Ressourcenverbrauchs bestimmt damit umgekehrt proportional, wie stark eine Unterpopulation wächst (neue Individuen bekommt), wenn sie zusätzliche Ressourcen zugewiesen bekommt. Gleichzeitig kann über den Ressourcenverbrauch einer Strategie gesteuert werden, ob eine Strategie mit einer kleinen Individuenzahl (hoher Ressourcenverbrauch) oder eher mit einer hohen Individuenzahl (niedriger Ressourcenverbrauch) arbeitet.
Das Konkurrenzintervall gibt an, zu welchen Zeitpunkten ein Wettbewerb zwischen den Unterpopulationen und damit eine Umverteilung der Ressourcen zwischen den Unterpopulationen stattfindet. Damit wird definiert, wie lange die Unterpopulationen ohne Veränderung der ihnen zur Verfügung stehenden Ressourcen existieren bzw. wie lange sie Zeit haben, bevor sie im Vergleich zu den anderen Unterpopulationen ihre Ergebnisse zeigen müssen.
Das Konkurrenzintervall kann als eine fest definierte Zahl von Generationen gegeben sein. Der Wert kann zwischen 1 und einer größeren Zahl von Generationen gewählt werden. Der Zeitpunkt für einen Wettbewerb kann aber auch in Abhängigkeit von anderen Dingen als der Anzahl vergangener Generationen definiert werden. Eine Möglichkeit besteht zum Beispiel darin, immer dann einen Wettbewerb durchzuführen, wenn in einer Unterpopulation ein deutlicher Fortschritt zu verzeichnen war.
Die Unterpopulationen, die bei einem Wettbewerb als erfolglos eingestuft wurden bzw. die Unterpopulationen, deren bisheriger Anteil an den Gesamtressourcen höher ist, als er sich aus der neuen Verteilung der Ressourcen ergab, müssen Ressourcen abgeben. Der maximale Umfang an Ressourcen, der in einem Wettbewerb abgegeben werden kann, wird durch die Konkurrenzrate festgelegt.
Die Konkurrenzrate wird als Anteil der Ressourcen der Unterpopulation, und nicht als fester Wert, angegeben. Dadurch wird gewährleistet, daß Unterpopulationen mit wenigen Ressourcen im Vergleich zu Unterpopulationen mit vielen Ressourcen einen absolut gesehen kleineren Betrag abgeben müssen. Die Konkurrenzrate sollte immer nur einen Teil der Ressourcen einer Unterpopulation umfassen.
Im folgenden werden Richtwerte für Konkurrenzintervall und Konkurrenzrate aufgeführt, die sich als gute Startwerte erwiesen haben.
Konkurrenzintervall (abhängig von der durchschnittlichen oder anfänglichen Anzahl der Individuen pro Unterpopulation):
(4-10)
Konkurrenzrate:
(4-11)
Konkurrenzintervall und Konkurrenzrate zusammen ergeben die Geschwindigkeit, mit der eine Umverteilung der Ressourcen zwischen den Unterpopulationen stattfindet.
Aus den oben genannten Richtwerten ergibt sich eine Umverteilungsgeschwindigkeit von:
(4-12)
Bei einem sehr kleinen Wert für das Konkurrenzintervall (< 6 Generationen) sollte die Konkurrenzrate auch sehr klein sein, da sonst eine zu schnelle Umverteilung der Ressourcen zwischen den Unterpopulationen stattfindet. Ist die Konkurrenzrate höher gewählt (> 10%), sollte auch das Konkurrenzintervall größer gewählt werden. Die Umverteilungsgeschwindigkeit ermöglicht einen einfachen Vergleich verschiedener Werte für beide Parameter.
Die Konkurrenzauswahl gibt an, wie die Individuen ausgewählt werden, die von einer Unterpopulation abgegeben werden müssen.
Für die Auswahl der Individuen gibt es verschiedene Möglichkeiten:
Für die Auswahl der schlechtesten Individuen spricht, daß dadurch die erfolglosen Unterpopulationen nicht noch zusätzliche Nachteile im Wettbewerb haben. Bei der Abgabe der besten Individuen würden die erfolglosen Unterpopulationen noch weiter benachteiligt, als dies durch die Verringerung der Individuenzahl ohnehin schon geschieht. Von der Wertigkeit genau dazwischen liegt eine zufällig verteilte Auswahl der Individuen.
Die Auswahl der besten oder schlechtesten Individuen kann unter Verwendung eines der vorgestellten Selektionsverfahren, siehe Abschnitt 3.2, ab S., erfolgen.
Um zu verhindern, daß eine erfolglose Unterpopulation vollständig verschwindet, muß eine minimale Unterpopulationsgröße bzw. ein minimaler Anteil an Ressourcen festgelegt werden, der jeder Unterpopulation immer erhalten bleibt. Nur bis zum Erreichen dieses Minimums können Ressourcen abgegeben werden, danach bleibt ihre Größe konstant (bis diese Unterpopulation vielleicht wieder einmal erfolgreich wird).
Das Unterpopulationsminimum kann angegeben werden als:
Die Angabe als Anteil der Unterpopulationsgröße hat, gegenüber einer festen Individuenzahl, den Vorteil der besseren Vergleichbarkeit zwischen unterschiedlich großen Unterpopulationen. Oftmals ist aber bekannt, wie groß eine Unterpopulation mindestens sein muß, um noch arbeiten zu können. Die flexibelste Angabe ist die Definition als Anteil der insgesamt zur Verfügung stehenden Ressourcen. In Gleichung 4-13 werden Richtwerte aufgeführt, die sich als sinnvolle Werte erwiesen haben.
Wenn das Unterpopulationsminimum sehr klein gesetzt wird (4-6 Individuen), ist die Funktion der meisten Evolutionären Algorithmen in einer Unterpopulation mit so wenigen Individuen kaum noch gewährleistet. Ein Erfolg dieser sehr kleinen Unterpopulation gegenüber anderen größeren Unterpopulationen tritt dann nur noch ein, wenn die anderen Unterpopulationen mit ihren Strategien deutlich schlechter sind.
Bei einem Unterpopulationsminimum von 10% der Gesamtressourcen, 5 Unterpopulationen und einer erfolgreichen Unterpopulation erhält die erfolgreiche Unterpopulation nach einigen Wettbewerben 60% der Gesamtressourcen. Die erfolglosen 4 Unterpopulationen dagegen haben jede nur 10% der Gesamtressourcen zur Verfügung. Dies entspricht einem Verhältnis von 6:1 (erfolgreiche zu erfolgloser Unterpopulation) bzw. 3:2 (erfolgreiche Unterpopulation zu allen erfolglosen Unterpopulationen). Bei einer weiteren Verringerung des Unterpopulationsminimums würde sich dieses Verhältnis weiter verschieben. Wenn eine gewichtete Verteilung der Ressourcen auf die Unterpopulationen gewählt wird, kann das Unterpopulationsminimum, im Vergleich zur Verwendung einer einzigen erfolgreichen Unterpopulation, kleiner gewählt werden. Bei einer gewichteten Verteilung erreichen nur die wirklich schlechtesten Unterpopulationen das Unterpopulationsminimum, die anderen bekommen einen höheren Anteil der Ressourcen zur Verfügung gestellt.
4.6.4 Beispiel des Einsatzes konkurrierender Unterpopulationen |
|
In diesem Unterabschnitt soll der Einsatz konkurrierender Unterpopulationen demonstriert werden. Das Beispiel benutzt dieselbe Testfunktion, die bei der Demonstration des Einsatzes unterschiedlicher Strategien verwendet wurde (DeJong's Funktion 1 oder Hypersphäre). Die Optimierung wurde mit denselben Parametern und Strategien durchgeführt. Jede der 5 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: große und mittlere 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). Zu Beginn des Laufs hatten alle Unterpopulationen eine Größe von 15 Individuen. Alle 40 Generationen fand Migration zwischen den Unterpopulationen statt. Dabei wanderten die besten Individuen in einer vollständigen Netzstruktur.
Die Parameter der Konkurrenz waren wie folgt eingestellt: nur die beste Unterpopulation erhält Ressourcen, Ressourcenverbrauch für alle Individuen 1, Konkurrenzintervall von 4 Generationen, die schlechtesten Individuen einer Unterpopulation wurden abgegeben, Unterpopulationsminimum von 5 Individuen. Dieses Beispiel stellt damit eine der einfachsten Varianten konkurrierender Unterpopulationen dar, die gleichzeitig gut zu überblicken ist. Der Verlauf und die Ergebnisse eines solchen Optimierungslaufs sind in den Abbildungen 4-13 und 4-14 dargestellt.
Abbildung 4-13: Einsatz konkurrierender Unterpopulationen; links: Größe der Unterpopulationen, Mitte und rechts: bester Zielfunktionswert je Unterpopulation (Mitte: Beginn, rechts: gesamter Lauf)
Einen guten Überblick über den Verlauf der Konkurrenz zwischen den Unterpopulationen gibt Abbildung 4-13, links. Die Grafik zeigt die relative Größe der einzelnen Unterpopulationen im Verlauf der Optimierung. Die Anzahl der Individuen einer Unterpopulation ergibt sich aus der Differenz zwischen zwei Linien. (Im Gegensatz zur Darstellung der Größe der Unterpopulationen kann aus dieser Darstellung auch die Zuordnung der Größe einer Unterpopulation zur Nummer der Unterpopulation erfolgen.) Zu Beginn des Laufs steigt die Größe von Unterpopulation 1 (große Mutationsschritte) kurz an. Etwa ab Generation 50 wächst Unterpopulation 5 (große und mittlere Mutationsschritte). Erst nach Generation 320 wird Unterpopulation 2 besser (mittlere Mutationsschritte), ab Generation 400 erhält Unterpopulation 3 (kleine Mutationsschritte) mehr Individuen. Die letzten knapp 200 Generationen ist Unterpopulation 4 (winzige Mutationsschritte) am erfolgreichsten und hat die meisten Individuen. Die erfolglosen Unterpopulationen verfügen zu jedem Zeitpunkt nur über einen geringen Anteil der Individuen der Gesamtpopulation.
In Abbildung 4-13, Mitte und rechts ist der Verlauf der besten Zielfunktionswerte für jede Unterpopulation dargestellt. Beide Grafiken zeigen, daß zu jedem Zeitpunkt einige der Unterpopulationen keine Verbesserung erreichen. Erst nach einer Migration verbessert sich der Wert des besten Zielfunktionswertes dieser Unterpopulationen. Im Verlauf der Optimierung sind es aber immer unterschiedliche Unterpopulationen, die keine Verbesserung mit ihrer Strategie erreichen bzw. aus einer erfolglosen Unterpopulation wird im Verlauf der Optimierung eine erfolgreiche Unterpopulation und umgekehrt. Besonders in der rechten Grafik sind die Übergänge von einer Strategie zur nächsten gut zu erkennen (um Generation 440 und Generation 600). Die sich verlangsamende Konvergenz kann durch die neue Strategie wieder beschleunigt werden. Über den gesamten Lauf gesehen wird eine gleichmäßige Konvergenzgeschwindigkeit erreicht.
Abbildung 4-14: Einsatz konkurrierender Unterpopulationen - Zielfunktionswerte aller Individuen; links: Beginn des Laufs, Mitte: Mitte des Laufs, rechts: Ende des Laufs
Einen tieferen Einblick in den Verlauf der Optimierung zeigt Abbildung 4-14. Alle Grafiken zeigen die Zielfunktionswerte aller Individuen der Population über mehrere Generationen (die Individuen mit den niedrigsten Nummern bilden Unterpopulation 1; die Individuen mit den höchsten Nummern Unterpopulation 5; dazwischen liegen die anderen Unterpopulationen). Die Trennung zwischen den Unterpopulationen ist deutlich zu erkennen. Dadurch kann auch indirekt die Größe der einzelnen Unterpopulationen abgelesen werden. Für die Darstellung wurden Zeiträume ausgewählt, die den Übergang von einer Strategie zur nächsten zeigen. Die linke Grafik zeigt den Beginn des Laufs, in dem Unterpopulation 1 erfolgreich war und in der Größe anwuchs. In der Grafik ist der Grund für diesen Erfolg zu erkennen: in Unterpopulation 1 findet die größte Verbesserung in den Zielfunktionswerten statt. In Unterpopulation 2, 3 und 4 dagegen gibt es kaum Verbesserung, nur Unterpopulation 5 kann in den ersten 40 Generationen eine sichtbare Verbesserung der Zielfunktionswerte erreichen. Mit der Migration in Generation 40 erfolgt eine Angleichung der Zielfunktionswerte zwischen den Unterpopulationen, ein Effekt, der auch in Abbildung 4-13, Mitte abzulesen ist.
Nach der Migration in Generation 40 verändert sich das Bild. Ab Generation 60 (Abbildung 4-14, Mitte) steigt die Größe von Unterpopulation 5 an. Die Zielfunktionswerte dieser Unterpopulation zeigen die stärkste Verbesserung. Unterpopulation 1 kann zwar auch noch die Zielfunktionswerte verbessern, allerdings nicht so stark wie Unterpopulation 5. Die Unterpopulationen 2, 3 und 4 zeigen weiterhin keine Verbesserung der Zielfunktionswerte, außer der Angleichung durch die Migration in Generation 80.
In Abbildung 4-14, rechts ist ein weiterer Übergang zwischen den Strategien dargestellt. Unterpopulation 2 wächst noch bis Generation 400. Danach wird Unterpopulation 3 am erfolgreichsten. Dies ist an der gleichmäßigen Verbesserung der Zielfunktionswerte zu erkennen, die ab Generation 420 mit einer Zunahme der Unterpopulationsgröße verbunden ist. Unterpopulation 2 kann zwar auch gute Zielfunktionswerte erreichen, daneben sind in Unterpopulation 2 aber auch viele deutlich schlechtere Individuen enthalten.
Die Auswertung eines Laufs mit Konkurrenz zwischen Unterpopulationen mit verschiedenen Strategien liefert dem Anwender Informationen über die Verteilung der Ressourcen, wann welche Strategie erfolgreich ist und wie sich die Zielfunktionswerte verändern. Durch die Kombination der hier vorgestellten 3 Visualisierungsmethoden (Abbildung 4-13, links, Abbildung 4-13, Mitte und rechts sowie Abbildung 4-14) lassen sich diese Informationen einerseits leicht erfassen, andererseits kann durch Auswahl der Methoden die Menge bzw. Tiefe an Information bestimmt werden, die zur Verfügung steht bzw. verwendet werden soll. Die Größe der Unterpopulationen zeigt direkt die Verteilung der Ressourcen und gibt damit ein Abbild des Erfolgs der Unterpopulationen. Die Darstellung des besten Zielfunktionswertes je Unterpopulation gibt eine erste direkte Maßzahl für den Erfolg einer Unterpopulation. Mit der Darstellung aller Zielfunktionswerte werden alle Daten veranschaulicht, die für die Berechnung des Erfolgs der Unterpopulationen verwendet werden. Diese Grafik (Abbildung 4-14) gibt den tiefsten Einblick in den Zustand der Unterpopulationen und läßt detaillierte Rückschlüsse über den Erfolg einer Suchstrategie zu.
4.6.5 Analyse der konkurrierenden Unterpopulationen |
|
Der Einsatz miteinander konkurrierender Unterpopulationen hat zwei Vorteile gegenüber der Anwendung eines normalen regionalen Modells: erstens werden zur gleichen Zeit verschiedene Strategien angewendet und zweitens wird denjenigen Strategien, die im Moment die besten Ergebnisse erzielen, ein größerer Teil der Ressourcen zur Verfügung gestellt. Auf diesem Weg findet eine effektive Verteilung der Ressourcen auf die vom Anwender vorgegebenen Strategien während des gesamten Laufs statt. Es ist nicht notwendig, für die Verteilung der Ressourcen einen Plan von außen vorzugeben bzw. die Veränderung von Strategieparametern zu Beginn eines Laufs festzulegen.
Die Vorteile konkurrierender Unterpopulationen eröffnen in der praktischen Anwendung in mehreren Bereichen ein neues bzw. verändertes Vorgehen. Bei der Bearbeitung eines Problems mit einem Evolutionären Algorithmus muß man sich nicht auf einen Satz von Parametern beschränken, sondern es können mehrere gleichzeitig angewendet werden. In der Auswertung dieser Läufe kann ermittelt werden, welche Strategien keinen oder einen sehr geringen Beitrag zur Lösung des Problems beitragen. Diese Information liefert oftmals neue Erkenntnisse über den Typ des Problems und damit ein erweitertes Verständnis. Dasselbe gilt für die Informationen, die aus dem Erfolg einer Strategie gezogen werden können. Bei der weiteren Bearbeitung dieses Problems können die erfolglosen Strategien durch neue Strategien ersetzt werden, die entweder auf den bisher erfolgreichen Strategien beruhen oder auf Grund der neuen Informationen über das Problem als vielversprechend eingeschätzt werden. Innerhalb einer vernünftigen Anzahl von Läufen läßt sich damit aus einem Repertoire vorhandener Strategien die für ein konkretes Problem erfolgreichste Strategie bzw. erfolgreiche Kombination von Strategien ermitteln.
Bisher wurden erst wenige Arbeiten zur Beschreibung und Anwendung konkurrierender Unterpopulationen veröffentlicht.
In [SVM94] wurde eine einfache Variante konkurrierender Unterpopulationen zur Strategieanpassung vorgestellt. Es wurde ein Ressourcenverbrauch von 1, ein Konkurrenzintervall von 4 Generationen, eine Konkurrenzrate von 1/8 und ein Unterpopulationsminimum von 4 Individuen benutzt. Eine Ordnung der Unterpopulationen wurde nicht berechnet, sondern es wurde nur die beste Unterpopulation ermittelt. Alle Unterpopulationen außer der besten mußten Individuen abgeben, die Konkurrenzauswahl erfolgte zufällig und die beste Unterpopulation erhielt alle freien Ressourcen. Eine Migration fand alle 16 Generationen statt. Während einer Migration wanderte das global beste Individuum in alle anderen Unterpopulationen, die beste Unterpopulation erhielt kein neues Individuum. Andere Werte für die Parameter der miteinander konkurrierenden Unterpopulationen bzw. deren Ergebnisse wurden nicht vorgestellt. Schlierkamp-Voosen und Mühlenbein zeigten die Anwendung dieser einfachen Variante konkurrierender Unterpopulationen zur Optimierung bekannter Standardtestfunktionen (Hypersphäre, Rosenbrock's Funktion, Griewangk's Funktion).
In [SVM96] wurde das Konzept konkurrierender Unterpopulationen zur Anpassung der Individuenzahl der Gesamtpopulation erweitert (extended competition model). Der zusätzliche Parameter des Ressourcenverbrauchs, consumption factor, wurde eingeführt. Dadurch konnte die relative Größe der Unterpopulationen gesteuert werden. Diese Erweiterung des Konzepts konkurrierender Unterpopulationen zeigt ihre Vorteile, wenn Strategien zum Einsatz kommen, die am effektivsten mit stark unterschiedlichen Populationsgrößen arbeiten. Als Beispiel wurde die Konkurrenz zwischen einer Unterpopulation, deren viele Individuen (geringer Ressourcenverbrauch) nur rekombiniert werden und einer Unterpopulation, deren wenige Individuen (hoher Ressourcenverbrauch) nur mutiert werden, vorgestellt. Wie nicht anders zu erwarten, war zu Beginn des Laufs die Strategie mit der Rekombination am erfolgreichsten. Im weiteren Verlauf wurde die Mutation erfolgreicher. Als Folge sank die Gesamtzahl der Individuen im Verlauf der Optimierung deutlich ab.
Die von Schlierkamp-Voosen und Mühlenbein vorgestellte Variante konkurrierender Unterpopulationen stellt die einfachste Variante dar. Die größte Vereinfachung betrifft die Aufteilung der Ressourcen, die nur vom besten Individuum der gesamten Population abhängt. Dies hat zur Folge, daß eine Unterpopulation immer erfolglos ist, wenn in ihr nicht das global beste Individuum enthalten ist. Mit dieser Methode wird immer nur eine Strategie bevorzugt, alle anderen werden benachteiligt. Dies führt während eines Laufs, wenn die bisher beste Strategie in ihrem Suchverhalten nicht mehr so gut wie die nächstbeste ist, zu einer uneffektiven Verteilung der Ressourcen und zwar aus folgendem Grund: Wenn eine Unterpopulation mit mehr Ressourcen/Individuen arbeitet, ist die Wahrscheinlichkeit für das Finden besserer Lösungen größer. Da die beste Unterpopulation nur auf Grund des besten Individuums bestimmt wird, bleibt diese Unterpopulation solange beste Unterpopulation, bis ihre Suchstrategie wesentlich schlechter als die einer anderen Unterpopulation ist (der Nachteil der schlechteren Strategie kann durch die deutlich größeren zur Verfügung stehenden Ressourcen ausgeglichen werden). Zu einem Zeitpunkt, an dem längst eine andere Strategie erfolgreicher wäre, wenn beide Strategien mit denselben Ressourcen/derselben Individuenzahl arbeiten würden, kann sich die vorher bessere Unterpopulation noch behaupten.
Lösungen für dieses Problem wurden in diesem Abschnitt aufgezeigt. Die Einbeziehung der besten Individuen aller Unterpopulationen bzw. aller Individuen der Population ermöglicht die Bestimmung einer gewichteten Ordnung der Unterpopulationen, die eine besser abgestufte Aussage zum Erfolg der Unterpopulationen macht. Durch die zusätzliche gewichtete Aufteilung der Ressourcen auf alle Unterpopulationen wird eine Verteilung der Ressourcen erreicht, die nicht nur der besten Unterpopulation (bzw. der Unterpopulation mit dem besten Individuum) zugute kommt, sondern mehreren guten Unterpopulationen. Insbesondere beim Einsatz ähnlicher bzw. sich ergänzender Strategien führt dies zu einer "gerechteren" Verteilung der Ressourcen.
Von der Anwendung des Prinzips konkurrierender Unterpopulationen auf ein reales Problem, die automatische Generierung von Testsequenzen für digitale Schaltungen, wurde in [CPR96] berichtet. Mehrere Unterpopulationen, die alle mit demselben Parametersatz arbeiteten, wurden jeweils zu einer Gruppe zusammengefaßt. Die Ressourcen wurden nicht durch Verlagerung von Individuen zwischen erfolglosen und erfolgreichen Gruppen verteilt, sondern eine erfolglose Unterpopulation erhielt die Parameter einer erfolgreichen Unterpopulation und wechselte dadurch ihre Gruppenzugehörigkeit. Dadurch ist zwar keine so feine Verteilung der Ressourcen möglich, jedoch ist dieser Ansatz einfacher in der Anwendung auf parallelen Rechnerarchitekturen. Hinweise auf die verwendeten Parameter und deren Einstellung wurden nicht gegeben.
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).
(