5.4 Eigenschaften der Zielfunktion

Previous PageTable Of ContentsNext Page

Die in den vorangegangenen Abschnitten vorgestellten Verfahren dienten der Darstellung von Daten, die während eines Laufs zur Verfügung stehen und standen in direktem Zusammenhang mit der Arbeit des Evolutionären Algorithmus.

In diesem Abschnitt werden Verfahren vorgestellt, die zur direkten Visualisierung von Eigenschaften der Zielfunktion dienen. Damit sind diese Verfahren nicht nur auf die Arbeit mit Evolutionären Algorithmen anwendbar, sondern können auch im Zusammenhang mit anderen Optimierungsverfahren eingesetzt werden. Weiterhin können diese Verfahren zum tiefergehenden Kennenlernen der Zielfunktion verwendet werden.


5.4.1 Direkte Darstellung der Zielfunktion

Previous SectionTop Of PageNext Section

Eine der einfachsten Methoden zum Erlangen von zusätzlichem Wissen ist die direkte Darstellung der Zielfunktion. Dazu wird diese mit einem engem Gitter abgetastet, die Zielfunktionswerte der zugehörigen Punkte werden berechnet und die Ergebnisse dargestellt. Leider hören an dieser Stelle die einfachen Dinge auf. Für die direkte Darstellung stehen nur drei Dimensionen zur Verfügung, so daß nur Zielfunktionen mit 2 Variablen (Dimensionen) dargestellt werden können.

Obwohl die direkte Darstellung auf die gleichzeitige Darstellung von 2 Variablen beschränkt ist, kann damit für viele Funktionen ein gutes Verständnis der Struktur erreicht werden. Für Funktionen, bei denen die Variablen untereinander vertauschbar sind, ohne daß sich die Zielfunktion ändert (dies trifft für viele der gebräuchlichen skalierbaren Testfunktionen zu), kann durch eine zweidimensionale Darstellung ein gutes Verständnis des Aussehens der hochdimensionalen Zielfunktion gewonnen werden.

Auch wenn die direkte Darstellung der Zielfunktion bei vielen praktischen Problemen nicht vollständig realisierbar ist, kann ein Blick auf die direkte Darstellung eines Ausschnittes des Suchraumes einige neue Informationen bringen. Damit kann abgeschätzt werden, ob und wie stark die Funktion verrauscht ist, ob Unstetigkeiten enthalten sind bzw. ob lokale Minima zu erwarten sind.

In Abbildung 5-15 sind Beispiele für einige bekannte Testfunktionen gegeben. Die Darstellungen sind Gittergrafiken mit darunterliegender Konturgrafik (mesh plot mit contour plot). Ein Teil der Funktionen ist für zwei verschiedene Bereiche der Variablen dargestellt, wodurch die unterschiedliche Charakteristik dieser Funktionen in Abhängigkeit des Bereiches der Variablen deutlich sichtbar wird. Unter Nutzung dieser Darstellungen ist ein gutes Verständnis des Aussehens dieser Funktionen möglich.

Wenn die Zielfunktion mehr als zwei Variablen hat und die Variablen untereinander nicht austauschbar sind, müssen andere Möglichkeiten der Darstellung dieser hochdimensionalen Daten gefunden werden. Möglichkeiten der multidimensionalen Skalierung bzw. hochdimensionalen Visualisierung werden in Abschnitt 5.5, ab S., genauer behandelt. Unter Nutzung des dort angegebenen Verfahrens ist es möglich, einen Schnitt durch die hochdimensionale Funktion darzustellen.

Abbildung 5-15: Direkte Darstellung der Zielfunktion für zwei Variablen


5.4.2 Fitneß-Distanz-Verteilung

Previous SectionTop Of PageNext Section

Von Routen und Collins wurde in [RC93] eine Veranschaulichung der Ähnlichkeit eines Individuums zu einem anderen (meist dem besten bis dahin bekannten Individuum) und der Fitneß (Güte, Zielfunktionswert) vorgeschlagen. Als Ähnlichkeitsmaß bietet sich die Distanz zwischen den Individuen an. In [RC93] wird diese Methode zur Visualisierung des augenblicklichen Zustandes einer Population verwendet.

Wenn statt der aktuellen Population eine größere Anzahl von Individuen verwendet wird, ergibt sich ein Abbild der Ähnlichkeit zwischen allen verwendeten Individuen. Dadurch kann ein abstrahiertes Abbild der Zielfunktion gewonnen werden.

Jones und Forrest stellten in [JF95] eine identische Methode vor, wobei ihr Anliegen vordergründig in eine andere Richtung zielte. Sie wollten einen Meßwert finden, der einen Ausdruck für die Schwierigkeiten bildet, die eine Zielfunktion einem Genetischen Algorithmus bei der Optimierung bereitet. Frühere Vorschläge für ein solches Maß (deceptive problems, u.a. [Gol87]; rugged fitness landscapes, u.a. [HG95]; epistatic interactions, [Dav91b]) ,,funktionierten" zwar am Beispiel einiger Funktionen, aber es ließen sich immer wieder Gegenbeispiele finden. Damit wurde deutlich, daß diese Vorschläge manchmal etwas mit der Schwere einer Funktion zu tun haben, aber nicht die entscheidende Antwort liefern konnten.

In [JF95] wurde eine Bewertung des Zusammenhanges zwischen der Fitneß (gemeint ist die Güte bzw. der Zielfunktionswert) einer Lösung (eines Individuums) und seinem Abstand (Distanz) zur besten Lösung (globales Optimum) als Meßwert für die Schwere einer Funktion vorgeschlagen und untersucht. Als Maß wurde die Fitneß-Distanz-Korrelation (fitness distance correlation - FDC) als ein Zusammenhang vorgeschlagen.

Eine Möglichkeit der Berechnung des FDC-Koeffizienten besteht darin, eine Anzahl von Individuen zu nehmen, von diesen den Zielfunktionswert (hier als Fit bezeichnet) zu berechnen und zusammen mit der Distanz Dist daraus nach Gleichung 5-1 den FDC-Koeffizienten zu bilden:

Die Berechnung der Distanz ist abhängig von der Repräsentation des Problems. Für eine binäre Repräsentation kann die Hammingdistanz verwendet werden, für ganzzahlige und reelle Repräsentationen der euklidische Abstand als leicht zugängliches Maß. Für andere Repräsentationen ist die Definition des Abstandes etwas komplizierter bzw. problemspezifisch. Anstatt die Distanz einfach durch den Abstand zu berechnen, wäre es günstiger, die Distanz als Anzahl der nötigen Anwendungen der evolutionären Operatoren zu berechnen. Dies würde bessere Vorhersagen für den Abstand zweier Individuen voneinander ergeben. Allerdings ist diese Vorgehensweise deutlich komplizierter und nur selten anwendbar.

Für die Stellen, an denen FDC als einzelnes Maß zu einfach ist, um den Zusammenhang zwischen Fitneß und Distanz vollständig wiederzugeben, wurde von Jones und Forrest die visuelle Bewertung der Fitneß-Distanz-Verteilung in einem 2-D Punktdiagramm (scatter plot) vorgeschlagen. In [JF95] wurde die Fitneß-Distanz-Korrelation für verschiedene Standardfunktionen untersucht. Dabei wurde ausschließlich mit einer binären Repräsentation der Variablen gearbeitet. Einige der Testfunktionen zeigten für eine unterschiedliche binäre Kodierung (Länge der binären Sequenzen, normal oder gray codiert) unterschiedliche Ergebnisse.


Abbildung 5-16: Fitneß-Distanz-Verteilung in einem 2-D Punktdiagramm ausgewählter zweidimensionaler Testfunktionen

In den Abbildungen 5-16 und 5-17 werden die Fitneß-Distanz-Verteilung und die Fitneß-Distanz-Korrelation einiger bekannter Standardtestfunktionen gezeigt. Dabei wird ausschließlich mit einer reellen Repräsentation gearbeitet. Alle Grafiken enthalten in der Titelzeile den Namen der untersuchten Testfunktion, die Fitneß-Distanz-Korrelation und die Anzahl der verwendeten Dimensionen der Zielfunktionen. In Abbildung 5-16 sind Beispiele für zweidimensionale Funktionen gezeigt; Abbildung 5-17 zeigt dieselben Funktionen, diesmal wurden 10 Dimensionen verwendet.

Abbildung 5-17: Fitneß-Distanz-Verteilung in einem 2-D Punktdiagramm der Testfunktionen aus Abbildung 5-16 in 10 Dimensionen

Bei einer reellen Repräsentation ist der Suchraum nicht vordergründig endlich, wie dies bei einer binären Kodierung der Fall ist. Erst durch die Festlegung einer minimalen Rasterweite bzw. der Anzahl von Punkten je Dimension zur Abtastung der Zielfunktion kann die Größe des Suchraums angegeben bzw. die Genauigkeit der Berechnungen beeinflußt werden. In diesem Unterabschnitt wurden 3000 Testpunkte für die Berechnung der Fitneß-Distanz-Korrelation und zur grafischen Darstellung verwendet (eine Erhöhung der Anzahl der Testpunkte auf 20000 zeigte in der grafischen Darstellung keine anderen Ergebnisse; durch die sehr hohe Zahl an Punkten wurde nur die Darstellung unübersichtlicher). Wenn die Zielfunktion mit bis zu 6 Dimensionen bzw. Variablen verwendet wurde, erfolgte eine gleichmäßige Abtastung des Wertebereiches. Bei höheren Dimensionen ist nur noch eine gleichmäßig zufällige Verteilung der Testpunkte möglich, da eine Rasterung in dem Sinne nicht mehr möglich ist (4 Punkte je Dimension bei 7 Dimensionen ergibt 47=16384 Testpunkte).

Die Darstellung der Fitneß-Distanz-Verteilung in einem 2-D Punktdiagramm und die Berechnung der Fitneß-Distanz-Korrelation sind ein weiteres Hilfsmittel zur Analyse einer Zielfunktion. Zusammen können damit Einblicke in die Schwere einer Zielfunktion gewonnen werden, die sonst nur schwer bzw. gefühlsmäßig zugänglich sind. Für höherdimensionale Zielfunktionen (mehr als 20 Variablen) werden die Interpretation der Darstellung und der Aussagewert der Fitneß-Distanz-Korrelation allerdings immer schwieriger.


5.4.3 Visualisierung problemspezifischer Daten und Ergebnisse

Previous SectionTop Of PageNext Section

In allen bisherigen Verfahren zur Visualisierung wurde davon ausgegangen, daß die Variablen eines Individuums die kleinste bzw. genaueste Einheit der zur Verfügung stehenden Daten ist. Aus der Sicht des Evolutionären Algorithmus ist dies auch richtig. Der Evolutionäre Algorithmus arbeitet auf diesen Variablen, mehr ,,sieht" der Algorithmus vom zu lösenden Problem nicht.

Für den Anwender stellen die Variablen, die vom Evolutionären Algorithmus bearbeitet werden, nur bei den einfachsten Problemen eine vollständige Beschreibung des zu bearbeitenden Systems dar. In fast allen praktischen Aufgaben sind die Variablen eine Abstraktion bzw. repräsentieren nur einen kleinen Teil des Problems:

Für den Anwender ist es für eine genaue Bewertung der Güte einer Lösung bzw. den Vergleich ähnlicher Lösungen unerläßlich, daß nicht nur die Variablen verglichen werden, sondern auch der Verlauf der Simulation mit einer weitergehenden Darstellung des Verlaufs der Zustands- und Ausgangsgrößen der Simulation.

Für diese Darstellungen können keine allgemeinen Hinweise gegeben werden, für jedes zu lösende Problem fallen sie unterschiedlich aus. Da sie aber direkt bei der Lösung des Problems helfen, sollte einige Aufmerksamkeit in eine umfassende und leicht verständliche Darstellung aller zur Verfügung stehenden Informationen verwendet werden.

In der Anwendung dieser problemspezifischen Darstellungen lassen sich die folgenden Bereiche benennen:

Der zweite und dritte Punkt stehen in direktem Zusammenhang. Oftmals kommt der Hinweis, daß eine Lösung mit einem schlechteren Zielfunktionswert doch eigentlich besser sei. An der Stelle muß dann die Zielfunktion so verändert werden, daß die bessere Lösung auch den besseren Zielfunktionswert hat. Dieser Prozeß kann mehrere Wiederholungen erfordern, bis die Zielfunktion eine Lösung so bewertet, wie es der Anwender erwartet. Ohne eine ausführliche und übersichtliche Visualisierung ist dies nicht zu erreichen.

Bei der Vorstellung von Anwendungen Evolutionärer Algorithmen auf praktische Probleme in Kapitel 7, ab S., wird ausgiebig Gebrauch von der problemspezifischen Visualisierung gemacht. In diesen und allen weiteren bisher bearbeiteten Anwendungen wurden mit Hilfe der problemspezifischen Visualisierung Mängel der Zielfunktion bzw. der darunterliegenden Simulation aufgedeckt. Die Änderungen konnten nachfolgend komfortabel überprüft 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).