"Evolutionäre Algorithmen - Verfahren, Operatoren, Hinweise aus der Praxis"

Hartmut Pohlheim
Berlin, Heidelberg, New York: Springer-Verlag
322 Seiten, 105 Abbildungen und Tabellen
mit Matlab-Toolbox auf CD-ROM (GEATbx 1.95, Vollversion)

ISBN 3-540-66413-0 (erschienen: Oktober 1999)
Preis: DM 98,- DM
www.pohlheim.com/eavoh/

Einleitung

Überall in unserer Umgebung und bei der Arbeit begegnen wir 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 (globale 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 (lokale Suche). 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.

Bisher 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. Darwin zeigte auch, 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.

In Kap. 2 werden die Struktur und der Aufbau Evolutionärer Algorithmen übersichtsartig vorgestellt. Die Grundprinzipien ihrer Funktionsweise werden vorgestellt und die Operatoren und Methoden in ihrem Ablauf umrissen. Die Eigenschaften Evolutionärer Algorithmen werden genannt und auf deren Auswirkungen für den Einsatz bzw. Nichteinsatz Evolutionärer Algorithmen hingewiesen. Damit soll dem Leser ein schneller Einstieg in das Gebiet der Evolutionären Algorithmen ermöglicht und ein Überblick gegeben werden, ob die Anwendung Evolutionärer Algorithmen bei seinen zu lösenden Optimierungsproblemen sinnvoll ist. Für weitergehende Fragen wird gezielt auf die entsprechenden Kapitel und Abschnitte im folgenden Text verwiesen.

Auf diesen einführenden Erläuterungen aufbauend werden in Kap 3 die grundlegenden Operatoren Evolutionärer Algorithmen ausführlich vorgestellt und erläutert. Die Beschreibung der Bestandteile Evolutionärer Algorithmen geht von einer vereinfachenden Variante aus. Darauf fußend werden Erweiterungen des Aufbau, der Struktur und der einzelnen Operatoren und Algorithmen vorgestellt. Dieses Prinzip zieht sich durch alle Ebenen bis zur Erläuterung verschiedener Varianten von Operatoren und Methoden. Es wird immer versucht, die Gemeinsamkeiten aufzuzeigen. Dies erleichtert es dem Leser deutlich, die Auswirkungen der vorhandenen Unterschiede zu erkennen und besser abzuschätzen. Scheinbar unterschiedliche Algorithmen lassen sich dadurch oftmals als Spezialfälle anderer Algorithmen erkennen.

In Kap. 4 werden Populationsmodelle vorgestellt, die bei Evolutionären Algorithmen zum Einsatz kommen. 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 Evolutionärer Algorithmen 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 Kap. 5 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 werden visuelle Verfahren entwickelt, 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 und zur hochdimensionalen Visualisierung 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 Kap. 6 wird eine Implementierung der in den Kapiteln 2-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. Die dem Buch beiliegende CD enthält Version 1.95 der GEATbx. Der Leser kann damit die besprochenen Verfahren und Methoden direkt auf eigene Probleme anwenden.

Nach den theoretischen Darstellungen und der programmtechnischen Umsetzung in den bisherigen Kapiteln wird in Kap. 7 gezeigt, wie sich aus den Evolutionären Operatoren und Methoden leistungsfähige Evolutionäre Algorithmen zusammenstellen lassen. Für einige in der Praxis häufig vorliegende Problemklassen (Parameteroptimierung, kombinatorische Optimierung) werden angepaßte Evolutionäre Algorithmen zusammengestellt und in ihrer Parametrisierung begründet. Mit diesen fertigen Evolutionären Algorithmen lassen sich viele Fragen zur Parametrisierung Evolutionärer Algorithmen beantworten. Die Kombination der einzelnen Operatoren und deren Parameter wird verständlich. Der Anwender kann diese angepaßten Algorithmen direkt auf seine eigenen Anwendungen und Problemstellungen übertragen bzw. anpassen.

In Kap. 8 wird die Optimierung ausgewählter Anwendungen detailliert vorgestellt. Den Anfang bildet eine allgemeine Darstellung des prinzipiellen Vorgehens bei der Bearbeitung eines neuen Optimierungsproblems, Abschn. 8.1. Dieser Abschnitt stellt eine einführende Anleitung dar. Es werden die Schritte erläutert, die bei der ingenieurtechnischen Lösung von Optimierungsproblemen zu beachten sind bzw. bei der Problemlösung helfen. Außerdem werden verschiedene Varianten zur Voruntersuchung der zu lösenden Optimierungsprobleme gezeigt, die auch bei der Verwendung anderer Optimierungsverfahren angewendet werden können bzw. sollten.

Die Anwendungsbeispiele in den folgenden Abschnitten von Kap. 8 wurden aus mehreren Problemklassen als jeweils repräsentative Beispiele ausgewählt. Die Probleme werden vorgestellt und die vorgenommenen Schritte zur Lösung der bestehenden Optimierungsaufgabe ausführlich gezeigt sowie die verwendeten Evolutionären Algorithmen beschrieben. Dadurch werden dem Leser Beispiele gegeben, die direkt auf die eigenen zu lösenden Aufgaben übertragen werden können.

Die Darstellung des Lösungsweges erfolgt je nach der Komplexität der behandelten Aufgabe in verschiedenen Richtungen. Einfache Probleme dienen der Demonstration des prinzipiellen Herangehens an die Problemlösung. Bei den komplexeren Problemen wird u.a. gezeigt, wie durch Voruntersuchungen des Systemverhaltens und die Einbeziehung von problemspezifischem Wissen die Problemgröße verringert bzw. die Lösung des Problems vereinfacht werden kann. Außerdem wird die Anwendung der Visualisierungsmethoden gezeigt.

Einige der 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, stellt einen Vorteil für die Lösung dieser Probleme dar. So konnten für einige der Anwendungen neue Ergebnisse gefunden bzw. Aufgaben in einer Größenordnung gelöst werden, die bisher nicht bearbeitbar waren.

In Kap. 9 wird eine Zusammenfassung des Buches gegeben. Der folgende Ausblick beleuchtet einige Aspekte Evolutionärer Algorithmen, die in den kommenden Jahren größere Bedeutung erlangen könnten, wenn sehr große und komplexe Systeme gelöst werden müssen.

Im Anhang wird ausführlich auf die historische Entwicklung Evolutionärer Algorithmen eingegangen. 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är. Aber erst in den 90er Jahren verzeichnete dieses Gebiet eine rasante Entwicklung. Abschnitt A.1 stellt frühe Arbeiten Evolutionärer Algorithmen vor und gibt einen kurzen Überblick über die aktuellen Entwicklungen. Der Rest des Anhangs enthält erweiterte Informationen zu den Anwendungen aus Kap. 8, 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.

Das Literaturverzeichnis ab S.281 stellt die in dieser Arbeit verwendete Literatur zusammen. Die einzelnen Einträge wurden dabei thematischen Gebieten zugeordnet, 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. Im folgenden Glossar werden in einer kompakten Form viele Begriffe aus dem Gebiet der Evolutionären Algorithmen sowie aus angrenzenden Bereichen erläutert. Das ausführliche Sachverzeichnis bietet einen schnellen Zugang zu allen Bereichen des Buches über die entsprechenden Stichworte.