5.3 Eigenschaften einer Population in einer Generation (Lokale Eigenschaften)

Previous PageTable Of ContentsNext Page

Die in diesem Kapitel beschriebenen Methoden dienen einer schnellen und übersichtlichen Darstellung der Eigenschaften der Individuen einer Generation, z.B. der aktuellen Population.


5.3.1 Variablen aller Individuen einer Generation

Previous SectionTop Of PageNext Section

Die Variablen aller Individuen einer Population stehen immer zur Verfügung und können einfach und direkt dargestellt werden. Die Darstellung aller Variablen der Individuen einer Population gibt ein momentanes Abbild des Phänotyps der Individuen der Population.

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

  1. 2-D Liniendiagramm, direkte Darstellung; jedes Individuum wird durch eine Linie repräsentiert, die den Wert der Variablen über der Nummer der Variablen darstellt, siehe Abbildung 5-8, oben,
  2. 2-D Liniendiagramm, indirekte Darstellung; Darstellung des besten und durchschnittlichen Individuums zusammen mit der Standardabweichung der Variablen vom Mittelwert der Variablen, siehe Abbildung 5-8, unten,
  3. 3-D Liniendiagramm; jedes Individuum wird durch eine Linie repräsentiert, die den Wert der Variablen über der Nummer der Variablen darstellt, siehe Abbildung 5-9, oben, oder
  4. 2-D Farbenteppich; die Individuen werden über den Generationen aufgetragen und die jedem Individuum pro Generation zugeordnete Fläche erhält die Farbe, die mit dem entsprechenden Variablenwert auf einer Farbskala korrespondiert, siehe Abbildung 5-9, unten.

Für eine reelle oder diskrete Repräsentation der Variablen ist die erste Darstellungsmethode gut geeignet und liefert Ergebnisse, die leicht zu interpretieren sind. Die zweite Möglichkeit ergibt besonders bei einer hohen Anzahl von Individuen eine übersichtlichere Darstellung. Die dritte und vierte Variante bieten die Möglichkeit der Zuordnung der Variablenwerte zu den einzelnen Individuen, was insbesondere bei der Anwendung des regionalen und lokalen Modells von Vorteil ist. Außerdem geben sie ein besseres Bild, wieviele Individuen ähnliche Variablenwerte haben.

In Abbildung 5-8 sind beide Varianten dargestellt. Zur Veranschaulichung der Aussagekraft einer solchen Grafik sind jeweils Grafiken von Beginn, Mitte und Ende eines Laufs dargestellt. Zu Beginn des Laufs (jeweils linke Grafik) ist die Vielfalt in der Population hoch. Die Variablen der Individuen unterscheiden sich stark voneinander, es gibt kaum identische Individuen. Entsprechend hoch ist die Standardabweichung für jede der Variablen (linke untere Grafik). Im weiteren Verlauf (jeweils mittlere Grafik) nimmt die Vielfalt in der Population deutlich ab, viele Individuen sind zu anderen Individuen sehr ähnlich. Die Standardabweichung ist deutlich kleiner als zu Beginn des Laufs. Am Ende des Laufs (jeweils rechte Grafik) sind fast alle Individuen sehr ähnlich. Dies zeigt sich auch an der sehr kleinen Standardabweichung für alle Variablen. Eine Ausnahme bildet zu diesem Zeitpunkt noch Variable 13: Erst wenige Individuen haben für diese Variable einen Wert von null, die meisten Individuen arbeiten noch mit einem Wert von eins.


Abbildung 5-8: Variablen aller Individuen einer Population; oben: 2-D Liniengrafik aller Individuen, unten: 2-D Liniengrafik des besten (dicke Linie) und des durchschnittlichen Individuums sowie der Standardabweichung der Variablen; links: Beginn eines Laufs, Mitte: während eines Laufs, rechts: Ende eines Laufs

Die Verwendung eines 3-D Liniendiagramms ermöglicht eine Zuordnung der einzelnen Variablenwerte zu den Individuen, siehe Abbildung 5-9, oben. Diese zusätzliche Information erhöht auf der einen Seite die aus der Grafik zu entnehmende Information, gleichzeitig verringert sich dadurch aber die Übersichtlichkeit deutlich. Gerade bei vielen verschiedenen Variablenwerten bzw. unterschiedlichen Individuen ist das 3-D Liniendiagramm nur schwer zu überblicken. Nur bei der Verwendung weniger Individuen oder weniger Variablen pro Individuum kann das 3-D Liniendiagramm seine Vorteile zur Geltung bringen. In Abbildung 5-9, oben, ist gut zu sehen, wie erst ab der Mitte des Laufs (mittlere Grafik) etwas aus der Darstellung zu entnehmen ist. Am Ende des Laufs (rechte Grafik), wenn alle Individuen sehr ähnlich sind, läßt sich aus dem 3-D Liniendiagramm gut erkennen, daß einige Individuen schon alle Variablen um 0 haben, während die anderen Individuen an Position 13 noch eine 1 stehen haben.

Den Vorteil des 3-D Linendiagramms, die Zuordnung der Variablenwerte zu den Individuen, kombiniert mit einer guten Übersichtlichkeit, bietet die Darstellung der Variablenwerte in einem 2-D Farbenteppich, siehe Abbildung 5-9, unten. Auf einen Blick ist zu erkennen, wie die Variablenwerte an den einzelnen Positionen und in der Population verteilt sind, ob bestimmte Variablenpositionen bei allen Individuen gleich sind, an welchen Positionen große Unterschiede auftreten und welches Individuum an welcher Position welchen Wert hat. In Abbildung 5-9, unten, ist sehr gut zu erkennen, wie sich vom Beginn des Laufs (linke Grafik), in dem die Variablen noch sehr unterschiedlich sind, im weiteren Verlauf die Unterschiede verringern (mittlere Grafik), bis am Ende (rechte Grafik) die Individuen in allen Variablen bis auf eine gleich sind.


Abbildung 5-9: Variablen aller Individuen einer Population; oben: 3-D Liniendiagramm, unten: 2-D Farbenteppich; links: Beginn eines Laufs, Mitte: während eines Laufs, rechts: Ende eines Laufs (die dargestellten Daten korrespondieren mit Abbildung 5-8)

Die Darstellung mit einem 2-D Farbenteppich ist für alle Repräsentationen der Variablen geeignet (reell, ganzzahlig, diskret, binär). Je nach Mannigfaltigkeit der möglichen Werte jeder Variablen müssen bestimmten Wertebereichen gleiche Farben zugeordnet oder die Anzahl der verwendeten Farben beschränkt werden. So würden z.B. bei einer binären Repräsentation nur 2 Farben verwendet werden.

Zusammenfassend können aus diesen Grafiken die folgenden Dinge herausgelesen werden:

Wenn sich mehrere Bereiche herausbilden, kann dies ein Indikator dafür sein, daß die Zielfunktion multimodal ist. Oder umgekehrt, bei einer multimodalen Funktion werden sich während des Laufs verschiedene Bereiche (cluster) herausbilden. Durch die sich ständig verringernde Verschiedenartigkeit bleibt am Ende meist nur ein Bereich übrig (Ausnahme: Verwendung von mehrkriterieller (multiobjective) Selektion, niching und sharing).

Es erfordert etwas Übung bzw. Vertrautheit mit dem Problem, damit aus dieser Darstellung der Variablen aller Individuen die oben angegebenen Informationen herausgelesen werden können. Weiterhin sind die möglichen Ergebnisse stark von der Repräsentation der Variablen abhängig. Trotzdem ist dieses Diagramm eines der aufschlußreichsten für den aktuellen Zustand der Population und sollte bei keiner Visualisierung fehlen.

Die Visualisierung der Variablen aller Individuen wird in [RC93] in zwei Varianten erwähnt. Die erste entspricht dem hier vorgestellten Farbenteppich, die zweite der 2-D Liniengrafik. Für die 2-D Liniengrafik, als `Überlagerung der Repräsentation eines jeden Chromosoms' bezeichnet, wird der Hinweis gegeben, daß damit die Positionen erkannt werden können, an denen die Diversität innerhalb der Population nicht mehr vorhanden ist.


5.3.2 Zielfunktionswerte aller Individuen einer Generation

Previous SectionTop Of PageNext Section

Die Zielfunktionswerte der Individuen einer Population stehen direkt zur Verfügung und bieten sich somit zu einer Visualisierung an. Die Darstellung aller Zielfunktionswerte ergibt ein weiteres detailliertes Abbild des Zustandes der Population.

Für eine Darstellung werden die Zielfunktionswerte über den einzelnen Individuen in einem 2-D Diagramm aufgetragen. Hierfür bieten sich Punkt- oder ausgefüllte Treppendiagramme an. Abbildung 5-10 zeigt die 2 Möglichkeiten für dieselbe Population von Individuen.

Abbildung 5-10: Zielfunktionswerte aller Individuen einer Generation; links: 2-D Punktdiagramm; rechts: ausgefülltes 2-D Treppendiagramm

In Abbildung 5-10 erfolgt die Anordnung der Individuen entsprechend ihrer Position in der Population, wobei nur eine eindimensionale Struktur betrachtet wurde. Eine weitere Möglichkeit besteht darin, die Individuen der Population nach ihrer Fitneß zu sortieren und dann die Zielfunktionswerte darzustellen. Diese Darstellung gibt ein direktes Bild der Verteilung der absoluten Werte der Zielfunktionswerte. Auf einen Blick ist zu erkennen, ob viele Individuen gleichwertige Zielfunktionswerte aufweisen, ob nur wenig gute oder nur wenig schlechte Individuen in der Population vertreten sind.

Wesentlich interessanter wird die Darstellung der Zielfunktionswerte aller Individuen einer Population bei der Verwendung von Unterpopulationen. Dabei darf die Population nicht entsprechend der Fitneß sortiert sein, sondern muß in der Reihenfolge dargestellt sein, wie die Individuen in den Unterpopulationen angeordnet sind. Außerdem müssen im Diagramm die Grenzen zwischen den Unterpopulationen eingezeichnet werden. In Abbildung 5-10 sind die Grenzen zwischen den Unterpopulationen als senkrechte gestrichelte Linien eingezeichnet. Damit kann auf einfache Weise das unterschiedliche Verhalten der Unterpopulationen beobachtet werden.

Noch wichtiger wird diese Darstellung bei der Verwendung unterschiedlicher Strategien für die einzelnen Unterpopulationen. In jeder Generation ist die Unterpopulation zu erkennen, deren Strategie im Moment den besten Fortschritt erbringt. Genauso ist zu erkennen, wenn eine Unterpopulation keinerlei gute Individuen produziert. Werden miteinander konkurrierende Unterpopulationen verwendet, so ist durch die eingezeichneten Grenzen zwischen den Unterpopulationen gleichzeitig die Größe jeder Unterpopulation dem Diagramm zu entnehmen.

Die bisher gemachten Aussagen gelten ganz allgemein für die Darstellung der Zielfunktionswerte. Für den Fall einer ein- oder zweidimensionalen Nachbarschaft unter den Individuen (Verwendung des lokalen Modells, siehe Abschnitt 4.4, ab S.) läßt sich aber noch mehr Information aus dieser Darstellung gewinnen. Für eine eindimensionale Nachbarschaft können dieselben Diagramme wie in Abbildung 5-10 verwendet werden. Für eine zweidimensionale Nachbarschaft bietet sich der 2-D Farbenteppich (Farbe entspricht dem Zielfunktionswert des entsprechenden Individuums), siehe Abbildung 5-11, und das 3-D Oberflächendiagramm an. Da die Zielfunktionswerte entsprechend der räumlichen Anordnung der Individuen dargestellt sind (x-Achse: Position in Dimension 1, y-Achse: Position in Dimension 2), lassen sich räumliche Bereiche ähnlicher Zielfunktionswerte gut erkennen. Diese Darstellungen geben einen Einblick in die räumliche Verteilung der Zielfunktionswerte.

Abbildung 5-11: Zielfunktionswerte aller Individuen einer Generation, Anordnung der Individuen in einem zweidimensionalen Gitter - lokales Modell, 2-D Farbenteppich; links: Beginn eines Laufs, Mitte: während eines Laufs, rechts: Ende eines Laufs

In Abbildung 5-11 läßt sich gut die Bildung von Bereichen verfolgen. Zu Beginn des Laufs (linke Grafik) sind die Zielfunktionswerte der Individuen sehr unterschiedlich. Im Verlauf der nächsten Generationen werden die Unterschiede zwischen benachbarten Zielfunktionswerten immer kleiner, es kommt zur Ausbildung kleiner Bereiche von ähnlichen Zielfunktionswerten. Gegen Ende des Laufs werden die Bereiche guter (niedriger) Zielfunktionswerte immer größer und verdrängen dadurch die schlechten Zielfunktionswerte. In der rechten Grafik dominiert ein großer Bereich guter Zielfunktionswerte deutlich die Population.

Allerdings läßt sich aus der Verteilung der Zielfunktionswerte nicht eindeutig erkennen, ob verschiedene Bereiche der Population mit gleichen Zielfunktionswerten gleiche oder unterschiedliche Bereiche des Suchraumes durchmustern. An dieser Stelle sei darauf hingewiesen, daß zwei Individuen mit demselben Zielfunktionswert nicht unbedingt auch dieselben Variablenwerte (denselben Phänotyp) besitzen müssen. Die Unterschiede zwischen den Individuen lassen sich aus der Darstellung der Zielfunktionswerte nur bei einigen Problemen ablesen. Besser geeignet zur Erkennung der Unterschiede zwischen den Individuen ist die Darstellung der Variablenwerte selbst, siehe Unterabschnitt 5.3.1, S., bzw. die Darstellung der Distanz zwischen Individuen in Distanzkarten, siehe Unterabschnitt 5.3.3, S..

Schwehm beschrieb und verwendete in [Swm96] die Darstellung der Zielfunktionswerte zur Visualisierung der räumlichen Verteilung der Qualität der Individuen und nannte diese Darstellung Qualitätskarten. Routen und Collins beschrieben in [RC93] zwei Varianten zur Darstellung der Zielfunktionswerte einer Population einer Generation: 2-D Balkendiagramm (sortiert nach Nummer des Individuums, Fitneß der Individuen oder Distanz zum besten Individuum) und `radial fitness plot'.


5.3.3 Distanzverteilung und Distanzkarten der Individuen einer Generation

Previous SectionTop Of PageNext Section

Die Individuen einer Population arbeiten während eines Laufs alle in demselben Suchraum, jedoch meist in unterschiedlichen Bereichen. Dies wird auch als parallele Durchmusterung des Suchraums bezeichnet. Eine wichtige Eigenschaft ist die Distanz zwischen den Individuen. Die Distanz gibt an, wie weit die Individuen während des Laufs voneinander entfernt sind. Die Distanz ist eine abgeleitete Größe, sie steht nicht auf Grund der Arbeit des Evolutionären Algorithmus zur Verfügung.

Die Nutzung der Distanz zwischen den Individuen kann in zwei Anwendungsbereiche unterteilt werden bzw. kann Aussagen über zwei verschiedene Eigenschaften machen:

Je nachdem, welcher der beschriebenen Anwendungsfälle betrachtet werden soll, kommen zwei verschiedene Darstellungsformen zum Einsatz:

Die Berechnung der Distanz ist abhängig von der Repräsentation der Variablen der Individuen. Für die binäre Repräsentation kann die Hammingdistanz verwendet werden, für die ganzzahlige oder reelle Repräsentation der euklidische Abstand.

Distanzverteilung

Die Distanzverteilung stellt die Verteilung der Abstände zwischen den Individuen einer Population dar. Zuerst werden die Distanzen zwischen allen Individuen einer Population berechnet. Anschließend wird ermittelt, wie häufig Distanzen in bestimmte Distanzintervalle fallen (Ermittlung der Verteilungsdichte der Distanzen). Diese Verteilungsdichte wird in einem Histogramm dargestellt, siehe Abbildung 5-12.

Abbildung 5-12: Distanzverteilung der Individuen einer Generation: 2-D Treppendiagramm; links: Beginn eines Laufs, Mitte: während eines Laufs, rechts: Ende eines Laufs

Das Distanzverteilungsdiagramm gibt ein Bild der Diversität der Population. Zu Beginn eines Laufs sind die Individuen im Suchraum verteilt. Dadurch existieren viele verschiedene Distanzen zwischen den einzelnen Individuen (große Abstände zwischen den Individuen, viele verschiedene Abstände). Je weiter der Lauf fortschreitet, um so stärker nähern sich die Individuen einander an und die Abstände zwischen den Individuen werden immer kleiner. Wenn sich alle Individuen einem Punkt annähern, werden die Abstände fast auf Null absinken. In Abbildung 5-12 ist dieser Fall dargestellt. Es ist gut zu erkennen, wie die absoluten Abstände während des Laufs kleiner werden und die Abstände immer weniger verteilt sind.

Außerdem kann aus der Distanzverteilung die Bildung von Clustern erkannt werden. Im Diagramm zeigt sich dies durch die Herausbildung von mehreren sogenannten Bergen. Wenn die Individuen größtenteils zu z.B. zwei verschiedenen Clustern gehören, dann sind die Abstände der Individuen in den Clustern untereinander nahe Null, die Abstände zwischen Individuen unterschiedlicher Cluster aber deutlich größer, jedoch in der Gesamtheit auch wieder sehr ähnlich. Im Diagramm zeigt sich dies durch zwei Bereiche, ein Bereich nahe Null, der andere im Bereich des Abstandes der Zentren der beiden Cluster.

In Abbildung 5-12, Mitte ist ein Beispiel mit mehreren Bereichen zu erkennen. Ein großer Teil der Abstände liegt um 0.15. Weiterhin treten viele Abstände mit Werten um Null auf. Eine noch kleinere Anzahl von Abständen hat Werte um 0.05. Am Ende sind die verschiedenen Bereiche verschwunden, alle Individuen liegen sehr dicht beieinander.

Diese Analyse kann auch für mehr als zwei oder drei Cluster durchgeführt werden. Allerdings können sich dann die einzelnen Bereiche so stark überdecken, daß eine Clusterung in dem Sinne nicht mehr erkennbar ist. Hier zeigen sich die Grenzen des Distanzverteilungsdiagramms. Eine Lösung für den Fall des Auftretens mehrerer Cluster bieten die Distanzkarten.

Die Visualisierung der Distanzverteilung wurde von Routen in [Rou94] vorgeschlagen.

Distanzkarten

Bei den Distanzkarten geht es weniger um die Darstellung der Häufigkeit, mit der Distanzen zwischen allen Individuen auftreten. Distanzkarten dienen vor allem der Darstellung der Distanz zwischen Individuen in ihrer räumlichen Anordnung. Zum Einsatz kommen Distanzkarten überall dort, wo eine räumlich beschränkte Interaktion zwischen den Individuen einer Population stattfindet (lokales Modell, siehe Abschnitt 4.4, S.).

Für die Visualisierung wird die Distanz eines Individuums zu seinen Nachbarn berechnet und anschließend in dieser Nachbarschaft dargestellt. Je nach Struktur der Nachbarschaft kommen unterschiedliche Diagramme zum Einsatz. Für eine eindimensionale (lineare) Nachbarschaft können die Distanzen in einem einfachen 2-D Treppendiagramm dargestellt werden, siehe Abbildung 5-13.

Abbildung 5-13: Distanzkarte einer Population in eindimensionaler Nachbarschaft als 2-D Treppendiagramm; links: Beginn eines Laufs, Mitte: während eines Laufs, rechts: Ende eines Laufs

Bei einer zweidimensionalen Nachbarschaft bietet sich zum einen die Verwendung eines Farbenteppichs an, bei dem das jedem Individuum zugeordnete Rechteck eine Farbe entsprechend der Distanz zu seinen Nachbarn erhält. Eine weitere Möglichkeit ist die Verwendung eines 3-D Oberflächendiagramms, bei dem die Distanz direkt in die Höhe der 3. Koordinate umgesetzt wird. Beide Varianten sind in Abbildung 5-14 dargestellt.


Abbildung 5-14: Distanzkarte einer Population in zweidimensionaler Nachbarschaft; oben: 2-D Farbenteppich, unten: 3-D Oberflächendiagramm; links: Beginn eines Laufs, Mitte: während eines Laufs, rechts: Ende eines Laufs (die dargestellten Daten korrespondieren mit Abbildung 5-11)

Distanzkarten zeigen Eigenschaften von Nachbarschaften innerhalb der Population. Ähnlich wie bei der Distanzverteilung, läßt sich einmal die Diversität der Population erkennen. Zu Beginn ist die Distanz zwischen benachbarten Individuen hoch. Durch die lokalen Nachbarschaften (lokale evolutionäre Operationen) bilden sich recht schnell räumliche Bereiche mit ähnlichen Individuen. Dies wird durch große Bereiche mit geringen Distanzen zwischen den Individuen deutlich. Die Anzahl von Individuen mit großen Distanzen wird gegen Ende des Laufs immer kleiner.

Die Bildung von unterschiedlichen Clustern als zweite zu erkennende Eigenschaft läßt sich aus den Distanzkarten wesentlich leichter ablesen, als dies aus der Distanzverteilung möglich ist. Da die Distanzen entsprechend der räumlichen Verteilung der Individuen dargestellt werden, können Bereiche, in denen die Distanzen zwischen den Individuen sehr klein sind, leicht als Bereiche mit ähnlichen Individuen erkannt werden. An der Grenze von Bereichen gibt es einen Sprung in der Distanz eines Individuums zu seinen Nachbarn. Die Grenzen von Clustern sind damit an den Individuen mit einer hohen Distanz zu erkennen. Deutlich ist dies in Abbildung 5-13, rechts zu erkennen. Bei einer zweidimensionalen Nachbarschaft zeigt sich dies in einer anderen Farbe im Farbenteppich oder durch große Sprünge im 3-D Oberflächendiagramm, siehe Abbildung 5-14.

Wenn zwischen den Individuen eine eindimensionale Nachbarschaft besteht, so kann mit einer Distanzkarte nicht nur die Entwicklung und Veränderung der Distanzen zwischen den benachbarten Individuen in einer Generation dargestellt, sondern über alle Generationen beobachtet werden. Sehr anschaulich dafür ist die Verwendung eines Farbenteppichs. Jede Zeile repräsentiert die Individuen einer Generation, wobei die Farbe jedes Individuums wiederum dessen Distanz zu seinen Nachbarn symbolisiert. Durch die geschlossene farbige Darstellung lassen sich leicht die Bereiche der Population erkennen, in denen sich gleichartige Individuen befinden bzw. es läßt sich erkennen, wie sich die Grenzen zwischen Clustern von ähnlichen Individuen im Verlaufe der Generationen verändern. Allerdings sollte nicht verschwiegen werden, daß für diese Darstellung die Variablen aller Individuen aller Generationen gespeichert werden müssen. Dies führt für viele Probleme realistischer Größe heute zu einem unverhältnismäßig hohen Aufwand bzw. bringt die Programmsysteme an den Rand ihrer Leistungsfähigkeit. Aber in einigen Jahren oder mit speziell auf die Verwendung des lokalen Modells zugeschnittenen Programmen ist die Verwendung dieser Darstellung sehr zu empfehlen.

Distanzkarten zur Visualisierung der Eigenschaften von Nachbarschaften werden u.a. von Schwehm in [Swm96] beschrieben und verwendet. Schwehm beschränkte sich aber auf die Darstellung der Hammingdistanz zwischen den Individuen. Wie die obigen Beispiele zeigen, können bei einer Verwendung anderer Abstandsmaße (z.B. euklidischer Abstand) Distanzkarten für alle Repräsentationen der Variablen verwendet werden.


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