1 Einleitung
1 Einleitung |
|
Überall in seiner Umgebung und bei der Arbeit begegnet man Problemen bzw. Systemen, die von einer Anzahl von Entscheidungen bzw. variablen Größen abhängen. Diese Entscheidungen oder Variablen können mehrere Zustände annehmen bzw. eine Variable kann in einem Bereich jeden Wert annehmen. Je nach Wahl und Einstellung der Variablen zeigt das System ein unterschiedliches Verhalten. Der Nutzer oder Betreiber des Systems möchte, daß das System ein bestimmtes Verhalten zeigt. Dazu muß er diejenige Einstellung der Variablen suchen, die dieses oder ein naheliegendes Verhalten hervorruft. Eine weitere Möglichkeit ist, daß nach dem besten Verhalten des Systems gesucht werden soll, wobei die inhaltliche Fragestellung - was ist das beste Verhalten dieses Systems - sehr unterschiedlich aussehen kann. Das System soll besonders gut an eine bestimmte Aufgabenstellung angepaßt sein. Stets muß nach einer Einstellung bzw. Kombination der Variablen gesucht werden, die das gewünschte Verhalten erbringen. Dieser Prozeß der Suche nach der gewünschten Einstellung der Variablen wird als Optimierung bezeichnet.
Das Verhalten eines Systems wird durch die Zielfunktion beschrieben. Für jede Einstellung der Variablen läßt sich durch die Zielfunktion ein Zielfunktionswert, oft auch Gütewert genannt, berechnen. Ist die Zielfunktion so definiert, daß ein kleinerer Zielfunktionswert besser ist, dann wird von einer Minimierung gesprochen. Das bedeutet, daß die Variablen gesucht werden, die den minimalen Zielfunktionswert ergeben. Die umgekehrte Suche entspricht einer Maximierung. Jede zu maximierende Zielfunktion läßt sich durch Multiplikation mit -1 in eine zu minimierende Zielfunktion umwandeln. Deshalb wird ohne Verlust an Allgemeingültigkeit im folgenden immer von einer Minimierung ausgegangen.
Von den Variablen wird durch den für jede Variable vorgegebenen Definitionsbereich ein Suchraum aufgespannt, der von den Optimierungsverfahren auf die unterschiedlichste Art und Weise durchmustert wird. An einem Ende der Skala steht die zufällige Suche, bei der zufällige Kombinationen von Variablenwerten probiert werden und die für jedes Problem anwendbar ist. Auf der anderen Seite stehen mathematische Verfahren, die über die Auswertung mathematischer Eigenschaften (Ableitungen usw.) günstige Variablenwerte ergeben, dafür aber spezielle Eigenschaften der Zielfunktion erfordern und dadurch in ihrer Anwendbarkeit eingeschränkt sind. Für alle Verfahren stellen sich die Fragen:
Je nachdem, wie jede dieser Fragen beantwortet wird, können die verschiedensten Verfahren unterschieden werden. Über viele Jahre hinweg wurde eine riesige Anzahl von Verfahren zur Optimierung entwickelt.
Bis hierher wurde die Optimierung als ein technisches Verfahren betrachtet. Bei einem Blick in unsere Umgebung ist sehr schnell festzustellen, daß wir von einer Vielzahl lebender Systeme umgeben sind. Eine genauere Betrachtung zeigt, wie gut die vielen unterschiedlichen Lebewesen an ihren jeweiligen Lebensraum angepaßt sind. Jedes Individuum stellt eine Einstellung von Variablen dar, die Zielfunktion ist der Lebensraum eines Individuums und der Zielfunktionswert die Überlebenschance eines Individuums. Je besser ein Individuum an seine Umgebung angepaßt ist, um so bessere Überlebens- und Fortpflanzungschancen hat es. Dabei sind der Lebensraum und die Überlebenschance bei natürlichen Individuen sehr komplexe Größen. Diese Anpassung ist ein Optimierungsprozeß, der seit der Entstehung des Lebens abläuft und immer weiter geht - die Evolution.
Von Charles Darwin wurde 1848 die Bedeutung der Evolution in seinem Buch ,,On the origin of species by natural selection" [Dar1859] zum ersten Mal dargestellt. Von Darwin wurde auch gezeigt, welche Mechanismen hinter der Evolution stecken. Dies sind zum ersten die Selektion und zum zweiten die Variation. Die Prozesse der Selektion (Auswahl) entscheiden unter anderem, welche Individuen Nachkommen erzeugen oder welche Individuen überleben. Durch die Variation wird bestimmt, wie die Eltern Nachkommen produzieren.
Ist das alles? Im Prinzip ja! Die Evolution ist ein Prozeß, der auf sehr einfachen Prinzipien basiert. Trotzdem (oder vielleicht gerade deshalb) ist die Evolution ein sehr leistungsfähiges Verfahren, wie ein genauerer Blick in unsere Umgebung deutlich zeigt.
Es stellt sich die Frage, inwieweit es möglich ist, die in der Natur vorhandenen Prinzipien und Mechanismen auf technische Systeme zu übertragen. Können die Vorgänge der natürlichen Evolution zur Adaption bzw. Optimierung technischer Systeme verwendet werden? Die Erkenntnisse aus dem Gebiet der biologischen Evolution, der wissenschaftlichen Genetik und der Populationsgenetik bieten dazu eine große Fülle an Informationen. Die Zielsetzung liegt darin, aus dieser Menge an komplexen Erkenntnissen die Prinzipien und Methoden zu extrahieren, welche die grundlegende Struktur des Evolutionsprozesses charakterisieren. Darauf aufbauend können nachfolgend weitere Teilbereiche betrachtet werden. Ziel kann dabei aber nicht ein reines Kopieren der natürlichen Prozesse und Vorgänge sein. Vielmehr sollen die erkannten Prinzipien auf technische Systeme übertragen werden. Dies kann zu einer starken Analogie zu natürlichen Prozessen führen, aber auch zu einer hohen Abstraktion von diesen. Mit dieser Übertragung von Prinzipien der natürlichen Evolution auf technische Systeme in den verschiedensten Abstufungen beschäftigt sich das Gebiet der Evolutionären Algorithmen.
Erste Ansätze zur Entwicklung und Verwendung Evolutionärer Algorithmen wurden in den 50er Jahren unternommen. In den 80er Jahren wurden die Evolutionären Algorithmen populärer. Aber erst in den letzten Jahren verzeichnete dieses Gebiet eine rasante Entwicklung. Kapitel 2, ab S., geht ausführlich auf die historische Entwicklung der Evolutionären Algorithmen ein, stellt frühe Arbeiten vor und gibt einen kurzen Überblick über die aktuellen Entwicklungen.
Im Kapitel 3, ab S., werden die Struktur, der Aufbau und ausgewählte Operatoren Evolutionärer Algorithmen erläutert. Die Beschreibung der Evolutionären Algorithmen folgt dabei dem Prinzip, daß von einer vereinfachenden Variante ausgegangen wird. Aufbauend auf dieser werden Erweiterungen des Aufbau, der Struktur und einzelner Algorithmen vorgestellt. Dieses Prinzip zieht sich durch alle Ebenen bis zur Erläuterung verschiedener Operatoren. Es wird immer versucht, die Gemeinsamkeiten aufzuzeigen. Dadurch wird es einfacher, die Auswirkungen der vorhandenen Unterschiede zu erkennen und besser abzuschätzen. Scheinbar unterschiedliche Algorithmen werden dadurch oftmals als Spezialfälle anderer Algorithmen erkannt.
In Kapitel 4, ab S., werden verschiedene Populationsmodelle vorgestellt. Jedes der Modelle, globales, regionales und lokales Modell, setzt auf einer unterschiedlichen Abstraktionsebene an. Durch die Anwendung der Modelle wird eine verbesserte und differenzierte Modellierung der Wechselwirkungen zwischen Individuen in einer Population erreicht. Eine gleichzeitige Anwendung der Modelle in einer hierarchischen Struktur ist direkt möglich. Dies führt zu einer weiter verbesserten und robusteren Suche bei großen und komplexen Problemen.
Auf der Grundlage des regionalen Modells werden zwei Erweiterungen dieses Modells vorgestellt und ausführlich erläutert:
Beide Erweiterungen führen zu einer verbesserten Modellierung der Prozesse in einer Population. Außerdem orientieren sich die Erweiterungen an Prozessen, die ähnlich in der Natur zu beobachten sind. Diese Erweiterungen führen zu einer Leistungssteigerung des Evolutionären Algorithmus und zu einer weiter verbesserten robusten Suche.
Speziell in der praktischen Anwendung können damit neue Prinzipien genutzt werden:
Diese Prinzipien konnten bisher nur durch äußere Mechanismen zur Anwendung gebracht werden und waren damit nicht integraler Bestandteil Evolutionärer Algorithmen.
Bei der Arbeit mit Evolutionären Algorithmen werden große Mengen von Daten und Zwischenergebnissen produziert. Diese Daten sind relativ einfach strukturiert. Durch die auftretende Größe der Datenmenge ist es aber unmöglich, diese Zahlen direkt auszuwerten. In Kapitel 5, ab S., werden Methoden und Verfahren der Visualisierung vorgestellt, die für eine Auswertung dieser Datenmengen gut geeignet sind. Durch eine Zusammenfassung der Daten und eine Abstraktion der vielen Einzelschritte innerhalb eines Evolutionären Algorithmus konnten visuelle Verfahren entwickelt werden, die ein Verständnis des Verhaltens und der Arbeitsweise Evolutionärer Algorithmen ermöglichen. Weiterhin können dadurch der Vergleich verschiedener Evolutionärer Algorithmen und die komfortable Interpretation der Ergebnisse durchgeführt werden.
Die dargestellten Visualisierungsverfahren ermöglichen eine Bewertung des Verlaufs eines Evolutionären Algorithmus unter verschiedenen Aspekten:
Außerdem werden Verfahren zur Visualisierung von Eigenschaften der Zielfunktion vorgestellt. Insgesamt betrachtet stehen mit diesen Visualisierungsmethoden fortgeschrittene Verfahren zur Untersuchung Evolutionärer Algorithmen zur Verfügung, die besonders bei der Lösung praktischer Probleme von hohem Nutzen sind.
In Kapitel 6, ab S., wird eine Implementierung der in den Kapiteln 3-5 dargestellten Verfahren und Methoden vorgestellt, die Genetic and Evolutionary Algorithm Toolbox for use with Matlab (GEATbx). In diesem Programmpaket sind alle besprochenen (und weitere) Verfahren, Populationsmodelle und Visualisierungsmethoden enthalten. Sie stehen damit unter Matlab [MW94] direkt zur Verfügung und können für die Lösung verschiedenster Probleme eingesetzt werden. Durch die Implementierung für Matlab und die Erstellung der Dokumentation in HTML wurde eine vollständige Plattformunabhängigkeit der GEATbx erreicht.
Nach den theoretischen Darstellungen und der programmtechnischen Umsetzung in den bisherigen Kapiteln werden in Kapitel 7, ab S., zwei Anwendungen ausführlich vorgestellt, die mit Hilfe der behandelten Evolutionären Algorithmen gelöst wurden:
Die Darstellung der Lösung erfolgt in zwei Richtungen. Erstens wird gezeigt, wie durch Einbeziehung von problemspezifischem Wissen die Problemgröße verringert werden konnte bzw. die Lösung des Problems vereinfacht werden konnte. Zweitens werden die Evolutionären Algorithmen gezeigt, die zur Lösung der Probleme genutzt wurden. Dabei kommen die in Kapitel 3 vorgestellten Operatoren, die in Kapitel 4 erläuterten Populationsmodelle und Erweiterungen sowie die in Kapitel 5 erarbeiteten Visualisierungsmethoden zum Einsatz. Für die Lösung wurde die in Kapitel 6 beschriebene GEATbx verwendet.
Beide vorgestellten Anwendungen stellen komplexe Probleme dar, die mit anderen Optimierungsverfahren nicht oder nur schwer zu lösen gewesen wären. Insbesondere die einfache Art und Weise, mit der bei Evolutionären Algorithmen problemspezifisches Wissen in den Optimierungsprozeß eingebunden werden kann, stellte einen Vorteil für die Lösung dieser Probleme dar. Für beide Anwendungen konnten neue Ergebnisse gefunden werden bzw. Aufgaben in einer Größenordnung gelöst werden, die bisher nicht bearbeitbar waren.
Nach der Zusammenfassung und dem Ausblick in Kapitel 8, ab S. enthält Kapitel 9, ab S., eine Zusammenstellung der in dieser Arbeit verwendeten Literatur. Die einzelnen Einträge wurden dabei nach thematischen Gebieten eingeordnet, die sich weitgehend an der Gliederung dieser Arbeit orientieren. Dadurch wird neben der einfachen Aufführung der Arbeiten gleichzeitig ein besserer Überblick über die Arbeiten eines thematischen Bereiches gegeben. Der Anhang beginnt mit einem Verzeichnis der verwendeten Abkürzungen. Im folgenden Glossar werden in einer kompakten Form viele Begriffe aus dem Gebiet der Evolutionären Algorithmen sowie aus angrenzenden Bereichen erläutert. Der Rest des Anhangs enthält erweiterte Informationen zu den Anwendungen aus Kapitel 7, die für ein tieferes Verständnis der verwendeten Modelle oder Simulationen notwendig sind, bei der Erläuterung der Lösung der Probleme aber unverhältnismäßig viel Platz eingenommen hätten.
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).