Evolutionäre Algorithmen

Ü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, w o- bei 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.

Dieses Kapitel beschreibt Struktur und Aufbau Evolutionärer Algorithmen übersichtsartig. Ausgehend von der Definition Evolutionärer Algorithmen und einer kurzen Beschreibung der Arbeitsweise erfolgt die Entwicklung einer einfachen Struktur Evolutionärer Algorithmen. Diese wird nachfolgend durch spezielle Verfahren erweitert. Dabei bleibt die grundlegende Struktur aber weiterhin erhalten.

Dieses Kapitel beschreibt die Funktionsweise von grundlegenden Verfahren und Operatoren Evolutionärer Algorithmen. Die Erläuterungen bauen auf der einführenden Beschreibung in Kap. 2 auf.

Zu Beginn der Arbeit mit Evolutionären Algorithmen wurde ausschließlich eine gesamte Population verwendet. Mit der Verfügbarkeit von Parallelrechnern wurden Versuche zur Parallelisierung der Berechnungen durchgeführt. Die Motivation dafür kam aus verschiedenen Bereichen. Zunächst stand der Gedanke dahinter, daß auf diese Weise die Berechnungen auf mehrere Prozessoren verteilt werden können, wodurch sich die Rechenzeiten deutlich verringern lassen. Dadurch ergab sich gleichzeitig die Möglichkeit, Evolutionäre Algorithmen auf deutlich größere Probleme als bisher anzuwenden.

Evolutionäre Algorithmen erreichen ein komplexes Verhalten durch eine Anzahl von Verfahren, die in ihren algorithmischen Grundlagen einfach strukturiert sind. Dabei werden in einem sich immer wiederholenden Ablauf große Mengen an Daten produziert. Die in diesen Verfahren enthaltenen Operationen und die produzierten Daten geben dem Betrachter keine oder nur geringe Einsicht in das Verhalten, die Funktion bzw. die Auswirkungen des Evolutionären Algorithmus, sie tragen für sich genommen nur wenig zum Verständnis bei. Erst durch eine Auswahl und Zusammenfassung der Daten und eine Abstraktion der Einzelschritte ist es möglich, das Verhalten der Algorithmen zu verstehen bzw. zu vergleichen und die Ergebnisse ihrer Anwendung zu interpretieren. Die vielen kleinen Einzelteile, die jedes für sich wenig bis nichts bedeuten, müssen zu einem großen Ganzen zusammengefügt werden, um ein aussagefähiges und interpretierbares Gebilde zu entwickeln. Eines der leistungsfähigsten Werkzeuge dafür ist die Visualisierung dieser Daten.

Dieser Abschnitt beschreibt die Genetic and Evolutionary Algorithm Toolbox for use with Matlab [GEATbx]¹. Sie stellt eine Umgebung zum Arbeiten mit Evolutionären Algorithmen und eine Vielzahl von Funktionen und Routinen zur Implementierung spezieller Evolutionärer Algorithmen unter M(UPATLAB) [MW94] zur Verfügung.

In den bisherigen Kapiteln wurden einzelne Verfahren und Operatoren beschrieben. In diesem Kapitel wird erläutert, wie aus diesen Operatoren vollständige Optimierungsalgorithmen zusammengestellt werden können. Jeder dieser Optimierungsalgorithmen stellt einen Evolutionären Algorithmus dar¹.

In den folgenden Abschnitten werden ausgewählte Anwendungen vorgestellt, die einen Einblick in die Spannweite des Einsatzes Evolutionärer Algorithmen zur Lösung von Praxisproblemen geben. Alle Probleme wurden in den vergangenen Jahren mit Hilfe Evolutionärer Algorithmen aus der GEATbx, Kap. 6, bearbeitet und gelöst. Schwerpunkt der Darstellungen ist die Veranschaulichung des zu lösenden Problems, seine Zuordnung in eine der Problemklassen aus Kap. 7 und der beschrittene Lösungsweg bzw. der am Ende verwendete Lösungsansatz. Bei allen größeren Problemen wird Gebrauch von Methoden der problemspezifischen Visualisierung gemacht.

Das vorliegende Buch gibt eine umfassende Darstellung Evolutionärer Algorithmen. Am Beginn steht ein Überblick zu Aufbau und Struktur Evolutionärer Algorithmen. Auf diesem aufbauend werden die grundlegenden Bestandteile erläutert. Im Vordergrund steht dabei die Anwendbarkeit der vorgestellten Verfahren und Methoden zur Lösung praktischer Probleme. Dies zeigt sich auch bei den Erweiterungen Evolutionärer Algorithmen sowie der Visualisierung Evolutionärer Algorithmen. Beide Bereiche ermöglichen eine bessere Lösung großer und komplexer Probleme. Alle Darstellungen erfolgen unter dem Gesichtspunkt einer einheitlichen Betrachtung, wodurch der Überblick verbessert und das Verständnis erleichtert wird. Im folgenden Abschnitt werden die einzelnen Bereiche des Buches in ihren Grundaussagen kurz zusammengefaßt. Insbesondere werden die eigenständigen Beiträge dieser Buches hervorgehoben.