5.2 Eigenschaften einer Population über mehrere Generationen (Globale Eigenschaften)

Previous PageTable Of ContentsNext Page

Die in diesem Kapitel beschriebenen Methoden dienen einer schnellen und übersichtlichen Darstellung von Veränderungen der Population im Verlauf der Generationen, die durch die Wirkungsweise des verwendeten Evolutionären Algorithmus entstehen. Dies entspricht dem globalen Verhalten der Population.


5.2.1 Zielfunktionswert des besten Individuums der Population (Konvergenzdiagramm)

Previous SectionTop Of PageNext Section

Die wohl bekannteste und fast immer genutzte Visualisierung ist die Darstellung der Konvergenz der Population. Dazu wird der Zielfunktionswert des besten Individuums über die vergangenen Generationen dargestellt. Dies gibt einen guten Überblick, wie schnell bessere Lösungen durch den verwendeten Algorithmus gefunden werden und wie groß der Fortschritt zwischen den einzelnen Generationen war. Diese Darstellung kann mit dem Mittelwert der Zielfunktionswerte aller Individuen der Population sowie deren Standardabweichung ergänzt werden.

Abbildung 5-1 zeigt verschiedene Darstellungen des Verlaufs des besten und des durchschnittlichen Zielfunktionswertes als Liniengrafik. Die Zielfunktionswerte einer Anzahl zurückliegender Generationen werden über den entsprechenden Generationen aufgetragen.

Bei der Anwendung des regionalen Modells können außer dem besten Zielfunktionswert der gesamten Population auch die jeweils besten Zielfunktionswerte der einzelnen Unterpopulationen angezeigt werden. Ein Beispiel dafür ist in Abbildung 4-13, S. gegeben.

Abbildung 5-1: Konvergenzdiagramm; links: Zielfunktionswert des besten Individuums über mehrere Generationen; Mitte: zusätzlich durchschnittlicher Zielfunktionswert aller Individuen und Standardabweichung der Zielfunktionswerte als Fehlergraph; rechts: wie links mit logarithmischer Skalierung

Bei der Darstellung sollten folgende Probleme beachtet werden:

Die hier geschilderten Probleme lassen sich durch einen vernünftigen Entwurf der Zielfunktion verringern oder sogar umgehen.


5.2.2 Variablen des jeweils besten Individuums einer Population

Previous SectionTop Of PageNext Section

Mittels Darstellung der Variablen des jeweils besten Individuums über die bisherigen Generationen wird die Möglichkeit einer tieferen Einsicht in die Vorgänge während der Optimierung gegeben. Bei der oben beschriebenen Konvergenzdarstellung wird nur ein Wert pro Generation dargestellt. Ein Überblick, wie die einzelnen Individuen aussehen, die diesen Zielfunktionswert jeweils produzieren, ist aber damit nicht gegeben. Mit der Visualisierung aller Variablen des jeweils besten Individuums läßt sich auf einen Blick erkennen, ob im Verlauf der Optimierung große Sprünge in den Variablen auftreten oder nur kleine Änderungen, ob mehrere Individuen mit ähnlichem Zielfunktionswert, aber deutlich unterschiedlichen Variablenwerten auftreten. Außerdem gibt diese Darstellung zusammen mit der Konvergenzdarstellung einen guten Einblick in den Zusammenhang zwischen der Größe der Veränderung der Zielfunktionswerte und der korrespondierenden Veränderung der Variablenwerte. Dies ist besonders bei einer Verlangsamung der Konvergenz wichtig: Durch einen Blick auf die Veränderung der Variablen der besten Individuen kann schnell eingeschätzt werden, ob die Optimierung festgefahren ist oder nicht.

Für die Visualisierung sollte die Anzahl der Variablen konstant sein (da sonst die Interpretation der Anzeige erschwert wird) und der Typ der Variablen berücksichtigt werden. Bei mehrwertigen Variablen (reelle, ganzzahlige oder diskrete Repräsentation) kann die Visualisierung als 2-D (Abbildung 5-2) oder 3-D Liniengrafik (Abbildung 5-3, links) erfolgen, wobei jede Linie den Verlauf einer Variablen über die Generationen darstellt. Für jede Art von Variablen ist eine zweite Variante geeignet, die Darstellung als 2-D Farbenteppich, auch als image plot bezeichnet (Abbildung 5-3, rechts). Der Wert jeder Variablen ist hier als Farbe des zugehörigen Bereichs der Grafik kodiert (für binäre Variablen würden hier entsprechend nur zwei Farben zur Darstellung verwendet werden).

Abbildung 5-2: Variablen des besten Individuums über mehrere Generationen: 2-D Liniengrafik; links: Rosenbrock's Funktion, rechts: Rastrigin's Funktion

Zwei Beispiele der Darstellung des besten Individuums jeder Generation in einer 2-D Liniengrafik sind in Abbildung 5-2 links und rechts dargestellt. Die linke Grafik zeigt eine Funktion (Rosenbrock's Funktion), bei der die Variablen untereinander korrelieren. Es gibt nur einen schmalen Weg zum Optimum, Sprünge zwischen den besten Individuen treten nicht auf, die Veränderungen sind kontinuierlich und gleichzeitig bei allen Variablen.

Ganz anders ist das Bild des zweiten Beispiels (Rastrigin's Funktion), Abbildung 5-2 rechts. Es gibt immer wieder starke Sprünge zwischen den Variablen, was darauf hindeutet, daß sich die jeweils besten Individuen von Generation zu Generation in mehreren Variablen unterscheiden. Dies tritt besonders nach einer Migration verstärkt auf (gut zu erkennen nach Generation 60, 80 und 100). Außerdem sind sehr gut die lokalen Minima für Variablenwerte bei Vielfachen von eins zu erkennen. Nur durch einen Sprung in einem Variablenwert um annähernd eins kann ein besserer Zielfunktionswert erreicht werden. Wie schwierig es ist, die letzte Variable auf den richtigen Wert zu bekommen, zeigt sich daran, daß dafür um die 40 Generationen benötigt werden.

In Abbildung 5-3 wird derselbe Lauf wie in Abbildung 5-2, links, mit zwei weiteren Verfahren dargestellt. Die linke Grafik verwendet eine 3-D Liniengrafik. Diese hat den Vorteil gegenüber der 2-D Liniengrafik, daß zusätzlich die Information entnommen werden kann, welche Variable wann welchen Wert hat. Diese Information läßt sich in einer 2-D Liniengrafik nur durch eine zusätzliche Legende gewinnen, die aber bei einer größeren Anzahl von Variablen nicht anwendbar ist. Wenn dagegen die Zuordnung der Variablenwerte zu den Variablen nicht notwendig ist, ist die 2-D Liniengrafik schneller zu erfassen. Eine weitere Variante der Darstellung der Variablen der besten Individuen zeigt Abbildung 5-3, rechts. Die Verwendung eines Farbenteppichs ermöglicht die schnelle Erfassung der Informationen, einschließlich der Zuordnung der Variablenwerte zur Nummer einer Variablen. Je nach Anzahl der verwendeten Farben ist eine exakte Bestimmung des Variablenwertes möglich. Die Anwendung des Farbenteppichs ist aber mehr im Bereich des schnellen Überblicks über die Veränderungen der Variablenwerte von Generation zu Generation und die Unterschiede zwischen den Variablen von Vorteil.

Abbildung 5-3: Variablen des besten Individuums über mehrere Generationen; links: 3-D Liniengrafik, rechts: 2-D Farbenteppich

Bei stark unterschiedlichen Wertebereichen der einzelnen Variablen kann eine Normierung der Variablen entsprechend des vorgegebenen Wertebereiches jeder Variablen erfolgen. Dadurch kann der Verlauf von Variablen mit kleinem Wertebereich zusammen mit Variablen mit großem Wertebereich erfolgen. Ein Nachteil ist, daß dadurch die direkte Information zu den Werten der Variablen verloren geht.


5.2.3 Zielfunktionswerte (Güte) aller Individuen über mehrere Generationen

Previous SectionTop Of PageNext Section

Die Darstellung der Zielfunktionswerte aller Individuen über mehrere Generationen gibt einen direkten Einblick in den Fortschritt der Population. Im Gegensatz zum Zielfunktionswert des besten Individuums bzw. des mittleren Zielfunktionswertes ergibt sich hier ein detaillierteres Bild. Es ist gut zu erkennen, ob es wenige gute Individuen gibt oder ob z.B. viele Individuen in bestimmten Wertebereichen liegen.

Für die grafische Darstellung bieten sich drei Möglichkeiten an:

  1. 2-D Punktdiagramm, jeder Punkt stellt einen Zielfunktionswert eines Individuums in einer Generation dar, Abbildung 5-4, links,
  2. 3-D Liniendiagramm, wobei die Zielfunktionswerte (z-Achse) der Individuen (y-Achse) über die Generationen (x-Achse) aufgetragen werden, Abbildung 5-4, Mitte oder
  3. 2-D Farbenteppich, in dem die Individuen über den Generationen aufgetragen werden und die jedem Individuum pro Generation zugeordnete Fläche die Farbe erhält, die mit dem entsprechenden Zielfunktionswert auf einer Farbskala korrespondiert, Abbildung 5-4, rechts.

Die Darstellung im Punktdiagramm gibt einen guten Überblick zur Verteilung der Zielfunktionswerte, liefert aber keine Möglichkeit der Zuordnung eines Zielfunktionswertes zu einem Individuum. Im 3-D Diagramm ist eine genauere Zuordnung der Zielfunktionswerte zu den Individuen möglich. Allerdings ist das 3-D Diagramm bei einer großen Datenmenge zu unübersichtlich. Der Farbenteppich ist leichter als das 3-D Diagramm zu erfassen und bietet dieselbe Information. Veränderungen der Zielfunktionswerte über die Generationen sind einfacher zu erkennen.

Abbildung 5-4: Zielfunktionswerte aller Individuen einer Population über mehrere Generationen; links: 2-D Punktdiagramm, Mitte: 3-D Liniendiagramm, rechts: 2-D Farbenteppich

Informationen über die Position eines Individuums sind bei der Verwendung eines regionalen oder lokalen Modells von Bedeutung. Durch die räumliche Trennung der Individuen in Unterpopulationen oder Nachbarschaften kommt es zu einer Unterteilung der Population, die auch in der Darstellung der Zielfunktionswerte erkennbar ist.

Abbildung 5-5: Zielfunktionswerte aller Individuen einer Population über mehrere Generationen bei Verwendung des regionalen Modells - 2-D Farbenteppich; links: normales regionales Modell, rechts: Verwendung konkurrierender Unterpopulationen

Für eine eindimensionale Unterteilung der Population (regionales Modell sowie lokales Modell mit eindimensionaler Nachbarschaft) sind in den Abbildungen 5-5 und 5-6 je zwei Beispiele gezeigt. Dabei kommt in allen Beispielen der 2-D Farbenteppich, siehe Abbildung 5-4, rechts, zur Anwendung. Für höherdimensionale Nachbarschaften des lokalen Modells sind die Methoden aus Abbildung 5-4 nicht anwendbar.

Abbildung 5-5 zeigt Ergebnisse bei Anwendung des regionalen Modells. Deutlich sind die Grenzen zwischen den Unterpopulationen zu erkennen. Nach jeder Migration findet eine schnelle Ausbreitung der neuen Information in der Unterpopulation statt, was an den sprunghaften Änderungen der Zielfunktionswerte alle 40 Generationen erkennbar ist. Es findet ein Heranholen der schlechteren Unterpopulationen an den Stand der besten Unterpopulation statt. In Abbildung 5-5, rechts, konkurrieren die Unterpopulationen miteinander. Sehr gut ist die sich verändernde Größe der Unterpopulationen alle 4 Generationen zu erkennen. In dieser Darstellung ist direkt ablesbar, daß die erste Unterpopulation die größten Schritte bei der Verbesserung der Zielfunktionswerte macht und deshalb als beste Unterpopulation bei jedem Wettbewerb mehr Individuen erhält.

Bei der Anwendung des regionalen Modells findet eine direkte Unterteilung der Population statt, die sich bei der grafischen Darstellung der Zielfunktionswerte gut erkennen läßt. Wird dagegen das lokale Modell verwendet, ist die Unterteilung der Population eine fließende; je weiter Individuen voneinander entfernt sind, um so stärker sind sie voneinander getrennt. Außerdem werden Nachkommen in der Nähe ihrer Eltern in die Population eingefügt. Dadurch kommt es zu einer diffusen Ausbreitung guter Individuen innerhalb der Population.

In Abbildung 5-6 sind Ergebnisse von zwei Läufen mit dem lokalen Modell dargestellt. Beide benutzen, bis auf die Größe der Nachbarschaft, dieselben Parameter. Die linke Grafik verwendet eine sehr kleine Nachbarschaft, in der rechten Grafik kam eine doppelt so große Nachbarschaft zur Anwendung. Es ist deutlich zu erkennen, daß es bei einer größeren Nachbarschaft, Abbildung 5-6, rechts, zu einer schnelleren Verbreitung guter Individuen kommt. Bei einer kleineren Nachbarschaft, Abbildung 5-6, links, können, bedingt durch die stärkere Isolation, auch Individuen länger überleben, die nicht so gut sind.

Abbildung 5-6: Zielfunktionswerte aller Individuen einer Population über mehrere Generationen in einer eindimensionalen lokalen Nachbarschaft; links: 2-D Farbenteppich mit kleiner Nachbarschaft, rechts: 2-D Farbenteppich mit größerer Nachbarschaft

Für die Skalierung der Zielfunktionswerte gelten die weiter oben gemachten Aussagen und Probleme. Folgendes Vorgehen kann einige Probleme umgehen: Für die Skalierung der Grafiken wird nur ein Teil der Zielfunktionswerte der Population (z.B. 85% der Population) verwendet, alle schlechteren Zielfunktionswerte werden auf den Maximalwert der verwendeten Zielfunktionswerte gesetzt. Bei den hier verwendeten Darstellungen wurde diese Begrenzung angewandt. In der Titelzeile wird jeweils angegeben, wieviele der Individuen zur Skalierung benutzt wurden.

Eine ähnliche Darstellung aller Gütewerte einer Population wird von Routen und Collins in [RC93] vorgeschlagen. Die Autoren benutzen ein modifiziertes Hinton-Diagramm. In diesem Diagramm ist jedem Individuum ein rechteckiger Bereich zugeordnet. Wie groß dieses Rechteck ist, hängt von der Güte des Individuums ab. Schlechte Individuen werden durch kleine Rechtecke repräsentiert, die besten Individuen durch große Rechtecke, die den jedem Individuum zur Verfügung stehenden Platz einnehmen. Durch die gleichzeitige Darstellung mehrerer Generationen kann eine Verschiebung der Fitneß in der Population beobachtet werden. Je besser die Population wird, um so größer sind die bedeckten Bereiche der Individuen. Am Ende des Laufs wird fast das gesamte Diagramm ausgefüllt sein, die Rechtecke berühren sich untereinander. Zusätzlich können die Individuen nach ihrer individuellen Fitneß sortiert werden.

Die von Routen und Collins vorgeschlagene Verwendung eines modifizierten Hinton-Diagramms hat den Nachteil, daß die Anzahl der zur Verfügung stehenden Abstufungen für die Darstellung der Fitneß eines Individuums stark begrenzt ist. Dadurch läßt sich nur ein grobes Abbild der Fitneßwerte geben. Die Verwendung des oben beschriebenen Farbenteppichs zeigt sich in der Anwendung als übersichtlicher, da durch die Verwendung von Farben feinere Abstufungen möglich sind. Die vorgeschlagene Sortierung der Population nach der individuellen Fitneß hat nur dann Vorteile, wenn es tatsächlich nur um eine Visualisierung der fortschreitenden Verbesserung der Fitneß in der Population geht. Der oben vorgeschlagene Farbenteppich kann neben der sich verändernden Fitneß der Individuen und der Population gleichzeitig noch ein Bild über die Verteilung und die Veränderung der Verteilung der Fitneßwerte innerhalb der Population bzw. der Unterpopulationen geben. Dadurch ist zusätzlich erkennbar, an welchen Stellen der Population besonders gute Individuen sind und an welchen Stellen bzw. Bereichen durch die Evolutionären Operatoren schlechte Individuen produziert werden (wichtig bzw. interessant bei der Beobachtung von Unterpopulationen mit verschiedenen Strategien, siehe Abschnitt 4.5, S. bzw. miteinander konkurrierenden Unterpopulationen, siehe Abschnitt 4.6, S.).

Einen Vorteil hat das modifizierte Hinton-Diagramm, wenn nur 2 Farben (z.B. schwarz und weiß) zur Visualisierung zur Verfügung stehen. Dann bietet die Größe des Rechtecks jedes Individuums mehr Abstufungen, als dies durch 2 Farben möglich wäre.


5.2.4 Position und Größe der Unterpopulationen

Previous SectionTop Of PageNext Section

Die bisher in diesem Abschnitt vorgestellten Verfahren waren beim Einsatz Evolutionärer Algorithmen allgemein anwendbar. Im vorigen Unterabschnitt bei der Darstellung aller Zielfunktionswerte aller Individuen über mehrere Generationen zeigte sich, daß bei Verwendung erweiterter Populationsmodelle, des regionalen und lokalen Modells, zusätzlich Informationen aus den Darstellungen abgelesen werden können.

Werden neben der Verwendung des regionalen Modells auch verschiedene Strategien je Unterpopulation verwendet, dann ist die Ordnung der Unterpopulationen der Meßwert, an dem der Erfolg der Strategien ablesbar ist. Dies wurde ausführlich in Abschnitt 4.5, ab S. erläutert. Beispiele für die Visualisierung der Ordnung der Unterpopulationen sind in Abbildung 4-11, S. gegeben.

Findet zwischen den Unterpopulationen Konkurrenz statt, so ändert sich die Größe der Unterpopulationen. Diese veränderliche Größe der Unterpopulationen läßt sich im Verlauf der Generationen darstellen und zeigt direkt die Ressourcen, die jeder Unterpopulation zur Verfügung stehen und indirekt, wie groß der Erfolg der Unterpopulationen bzw. Strategien ist.

Abbildung 5-7: Größe der Unterpopulationen, 2-D Liniengrafik; links: direkte Darstellung der Größe jeder Unterpopulation, rechts: kumulative Größe der Unterpopulationen

In Abbildung 5-7 sind zwei Varianten des Verlaufs der Größe der Unterpopulationen dargestellt. Die erste Variante, Abbildung 5-7, links, zeigt die Größe der Unterpopulationen. Bei der zweiten Variante, Abbildung 5-7, rechts, wird die kumulative (aufaddierte) Größe der Unterpopulationen dargestellt. Die zweite Variante hat den Vorteil, daß direkt die relative Verteilung der Ressourcen abgelesen werden kann. Zusätzlich kann aus dieser Grafik auch die Größe einer bestimmten Unterpopulationen (als Differenz zwischen zwei Linien) entnommen werden, ohne daß eine Legende vorhanden ist. Dies ist besonders bei einer großen Anzahl von Unterpopulationen von Vorteil.


Previous PageTable Of ContentsList Of FiguresList Of TablesNext Page

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).