5.1.1 Kriterien der Systematisierung

5.1.2 Daten zur Visualisierung

5.1.3 Schema der Systematisierung

5.1 Systematisierung

Eine Klassifizierung der Visualisierung Evolutionärer Algorithmen läßt sich auf verschiedenen Ebenen vornehmen. Im folgenden wird eine Unterteilung nach mehreren Kriterien vorgenommen, die in ihrer Kombination eine feine Systematisierung erlauben. Wenn Methoden von der Repräsentation der Werte abhängig sind, wird dies bei der ausführlichen Erläuterung der einzelnen Techniken in den folgenden Abschnitten erwähnt. Wenn möglich, wird für die gebräuchlichsten Repräsentationen eine praktische Realisierungsmöglichkeit aufgezeigt.

Zu Beginn erfolgt eine Aufstellung aller Kriterien, die für die weitere Systematisierung in Betracht gezogen werden müssen bzw. als Kriterien für eine Unterteilung herangezogen werden können. Aus der Kombination der einzelnen Unterpunkte der Kriterien ergeben sich im weiteren die zu charakterisierenden Bereiche. Für jeden dieser Bereiche können Techniken der Visualisierung abgeleitet bzw. entwickelt werden.

5.1.1 Kriterien der Systematisierung

Eine erste Unterteilung wird entsprechend dem Zeitintervall der verwendeten Daten vorgenommen:

• einzelne Individuen (individuelle Daten und Eigenschaften),
• eine/aktuelle Generation; augenblicklicher Zustand (lokale Daten und Eigenschaften),
• alle Generationen eines Optimierungslaufs (globale Daten und Eigenschaften) und
• mehrere Optimierungsläufe (Vergleich globaler Daten und Eigenschaften).

Die zweite Unterteilung bezieht sich auf die Anzahl der Individuen, für die gleichzeitig Werte dargestellt werden und dient einer gezielten Verfeinerung der ersten Unterteilung:

• einzelne Individuen,
• alle Individuen einer (Unter-)Population und
• Individuen mehrerer (Unter-)Populationen.

Eine dritte Unterteilung kann danach vorgenommen werden, ob:

• der Verlauf bzw. die Arbeit eines Evolutionären Algorithmus dargestellt oder
• ob Einblick in verschiedene Eigenschaften der Zielfunktion gegeben werden soll. (Diese sind im engeren Sinne nicht speziell auf Evolutionäre Algorithmen abgestimmt, werden aber bei der Arbeit mit Evolutionären Algorithmen oft benötigt. Erst mit etwas Wissen über die Zielfunktion kann oftmals der richtige bzw. ein gut geeigneter Evolutionärer Algorithmus ausgewählt werden.)

Zusätzlich spielt die Repräsentation der Variablen des Problems eine wichtige Rolle. Je nach Typ der Variablen und je nachdem ob ein Individuum eine konstante oder veränderliche Anzahl von Variablen hat, müssen bei einigen Visualisierungstechniken verschiedene Darstellungsformen angewendet werden. Manche Varianten sind nur für einzelne dieser Repräsentationen berechenbar bzw. sinnvoll. Deutlich komplizierter wird eine Visualisierung von Werten (z.B. Variablen der Individuen), wenn diese nicht als ein- oder mehrdimensionaler Vektor, sondern als komplexere Struktur (Baum o.ä.) vorliegen. Im folgenden wird davon ausgegangen, daß die Werte in einer Matrixstruktur vorliegen.

5.1.2 Daten zur Visualisierung

Für die Visualisierung werden zwei Arten von Daten verwendet:

1. direkte Werte der Individuen bzw. Populationen (mit diesen arbeitet der Evolutionäre Algorithmus bzw. liefert sie als Ergebnis) und
2. abgeleitete Werte für Individuen bzw. Populationen (diese werden aus den direkt verfügbaren Werten berechnet und charakterisieren Eigenschaften oder Zustände).

direkte Werte	abgeleitete Werte
Variablen der Individuen, Zielfunktionswerte (Güte) der Individuen, Anzahl der Individuen pro (Unter-) Population, Anzahl der Generationen, Parameter des Evolutionären Algorithmus, erfolgreicher Abschluß eines Laufs.	Veränderung der Zielfunktionswerte (Ableitung, Differenz), Verteilung oder Standardabweichung der Zielfunktionswerte, Abstände der Individuen voneinander (Distanz), Verteilung der Abstände/Distanzen zwischen den Individuen.

Tabelle 5-1: Arten der Daten, die zur Visualisierung verwendet werden

5.1.3 Schema der Systematisierung

Mit den aufgestellten Kriterien und den zur Verfügung stehenden Daten zur Visualisierung kann ein Schema aufgestellt werden, das eine Zuordnung der entsprechenden Werte bzw. Verfahren vornimmt. In Tabelle 5-2 ist dieses Schema vorgestellt.

	direkte Werte			abgeleitete Werte
	einzelne Individ.	Unterpopulationen	Population	Population
eine/aktuelle Generation	· Variablen des besten Individuums	· Größe bzw. Ordnung der Unterpopulationen	· Variablen der Individuen · ZFW der Individuen	· Distanzverteilung · Distanzkarten · Fitneß-Allel-Teppich
mehrere Generationen	· ZFW des jeweils besten Individuums	· Größe bzw. Ordnung der Unterpopulationen	· Konvergenz: ZFW des besten Individuums	· Konvergenz: mittlerer ZFW, Standardabweichung der ZFW · Statistik: Diversität, Fixierung, Inzucht, Klassen
mehrere Läufe	· bester ZFW je Lauf · bestes Individuum je Lauf	· beste Unterpopulation / Strategie je Lauf	· Anzahl Generationen / Zielfunktionsaufrufe bis Optimum je Lauf · Anzahl erfolgreicher Läufe	· Abhängigkeit des Erfolgs von veränderten Parametern

Tabelle 5-2: Systematisierung der Visualisierungsmöglichkeiten für Verlauf, Zustand oder Abschluß eines Evolutionären Algorithmus

Eine systematische Darstellung der Visualisierungsmöglichkeiten Evolutionärer Algorithmen ist bisher nur von Schwehm [Swm96] bekannt. Er unterscheidet nach der Detailliertheit der Darstellung ([Swm96], S.92):

• Gesamtverhalten einer Konfiguration:

• Vergleich verschiedener Konfigurationen bzw. Läufe,

• globales Verhalten der Population:

• Eigenschaften der gesamten Population über mehrere Generationen,
• globale Maße; Konvergenz und Populationsstatistik,

• lokales Verhalten der Population:

• Eigenschaften lokaler Nachbarschaften,
• lokale Maße,

• spezielle Eigenschaften einzelner Individuen:

• Genotyp und Phänotyp einzelner Individuen.

Diese Systematisierung ist im Ansatz gut und entspricht der in Unterabschnitt 5.1.1, S. vorgenommenen Unterteilung nach dem Zeitintervall der verwendeten Daten. Die Begriffe dieser Systematisierung wurden deshalb dort mit aufgeführt und werden im folgenden an den entsprechenden Stellen zusätzlich verwendet. In der alleinigen Anwendung hat sich diese Systematisierung allerdings als zu grob erwiesen. Von Schwehm wurden außerdem nur Verfahren für die binäre Repräsentation von Variablen betrachtet. Einige der dort untersuchten Verfahren lassen sich nicht auf eine andere Repräsentation anwenden.

Von Collins ([Col93], [Col97a], [Col97b]) und Routen ([RC93], [Rou94]) wurden verschiedene Möglichkeiten zur Visualisierung Evolutionärer Algorithmen vorgestellt. Allerdings wurde keine Systematisierung der verschiedenen Möglichkeiten gegeben oder versucht. Routen und Collins nennen eine Anzahl von Aufgaben, welche die Visualisierung erfüllen sollte ([RC93], S.278):

• Darstellung, ob die Fitneß (gemeint sind die Güte bzw. der Zielfunktionswert) der Population (noch) steigt und wie stark sich die Fitneß ändert,
• Auswirkungen der Einstellungen der Parameter verstehen,
• Verschiedenartigkeit (diversity) innerhalb der Population erkennen,
• welche Allele innerhalb eines Individuums werden bevorzugt und an welchen Stellen liegen diese Allele,
• Auftreten und Auswirkungen des Mutationsoperators erkennen und
• werden zwei oder mehrere mögliche Lösungen vom Evolutionären Algorithmus bevorzugt (deutet auf multimodale Zielfunktion hin)?

Alle diese Aufgaben (und einige weitere) lassen sich durch die in den folgenden Abschnitten vorgestellten Verfahren erfüllen. Eine eindeutige Zuordnung eines Verfahrens zu einer Aufgabe ist aber nicht möglich. Viele Verfahren liefern Informationen, die zur Erfüllung mehrerer dieser Aufgaben beitragen können. Bei der Erläuterung jedes Verfahrens werden die Informationen genannt, die aus der Darstellung gewonnen werden können. Dabei erfolgt auch eine Bewertung der von Collins und/bzw. Routen vorgeschlagenen Methoden.

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