8.1 Zusammenfassung

In dieser Arbeit werden Evolutionäre Algorithmen als Verfahren zur Optimierung von Systemen vorgestellt. In Kapitel 1 wird ein Bogen von den Vorgängen in der Natur, speziell der natürlichen Evolution, zu deren Anwendung bei der Lösung von Problemen durch Adaption an eine vorgegebene Aufgabenstellung gespannt. Durch eine Übertragung der in der Natur zu beobachtenden Vorgänge sowie durch die Abstraktion dieser Vorgänge können Evolutionäre Algorithmen entwickelt werden. Diese Algorithmen erlauben die Lösung technischer Probleme in einer Weise, die ähnlich einfach und gleichzeitig leistungsfähig wie die natürliche Evolution ist.

In Kapitel 2 wird eine Übersicht über die historische Entwicklung Evolutionärer Algorithmen sowie die frühen Arbeiten auf diesem Gebiet gegeben. Dabei wird kurz auf die drei Schulen Evolutionärer Algorithmen eingegangen: Evolutionäre Programmierung, Evolutionsstrategien und Genetische Algorithmen. Aus heutiger Sicht sind die früheren Unterschiede zwischen diesen Richtungen kaum noch vorhanden. Statt auf diese Unterschiede zu verweisen, sollten die Gemeinsamkeiten sowie die Anwendbarkeit der Verfahren und Operatoren auf verschiedene Klassen von Problemen in den Vordergrund gestellt werden. Dieser Gedanke war eine der Grundlagen bei der Anfertigung der vorliegenden Arbeit.

Die Darstellung der Evolutionären Algorithmen beginnt mit einer Übersicht über die grundlegende Struktur Evolutionärer Algorithmen zu Beginn von Kapitel 3. Ausgehend von dieser einfachen Struktur werden die Verfahren und Operatoren vorgestellt, aus denen sich ein Evolutionärer Algorithmus zusammensetzt. Im weiteren Verlauf des Kapitels werden die Verfahren und Operatoren beschrieben und ihre Wirkungsweise erläutert. Anders als in vielen Arbeiten zu Evolutionären Algorithmen werden bei dieser Darstellung nicht einzelne Algorithmen oder Operatoren hervorgehoben oder erläutert. Statt dessen werden ausgehend von einer einfachen Struktur diese durch weitere Verfahren erweitert; nachfolgend werden die einzelnen Teilbereiche anhand ausgewählter Operatoren und Methoden beschrieben. Durch diese hierarchische Darstellung erfolgt eine einheitliche Beschreibung, die vom allgemeinen Fall ausgeht und diesen mit speziellen Varianten untersetzt. Dies ermöglicht nicht nur eine sinnvollere Beschreibung, sondern erleichtert das Erfassen und Verstehen der einzelnen Komponenten als Teil eines Ganzen und in ihrer Wechselwirkung untereinander.

In Evolutionären Algorithmen müssen an mehreren Stellen gleichartige Berechnungen für eine größere Anzahl von Varianten durchgeführt werden. Diese Berechnungen können parallel ausgeführt werden. Dazu wird eine Unterteilung der Population vorgenommen, die zur Beschreibung von Populationsmodellen führt. Zu Beginn von Kapitel 4 wird ein Überblick über bisherige Unterteilungen von Populationsmodellen gegeben. Für die weitere Arbeit wird die Unterteilung nach der Reichweite der Selektion als am besten geeignet ausgewählt. Diese unterteilt die Populationsmodelle in globales, regionales und lokales Modell. Diese Modelle werden in den nachfolgenden Abschnitten vorgestellt. Insbesondere werden Hinweise für die Wahl und Einstellung der verschiedenen Parameter und ihre Abhängigkeiten untereinander gegeben. Eine allgemeine Beschreibung von Nachbarschaftstopologien, die für das regionale und das lokale Modell angewendet werden kann, wird in Unterabschnitt 4.4.2 vorgenommen. Diese Beschreibung ermöglicht eine Ausdehnung der Nachbarschaftsstrukturen auf beliebige Dimensionen und enthält alle vorher behandelten Topologien als Spezialfälle. Die Vorteile dieser einheitlichen Betrachtung zeigen sich beim Vergleich verschiedener Topologien.

In den Abschnitten 4.5 und 4.6 werden neue Erweiterungen des regionalen Modells vorgestellt: die Anwendung verschiedener Strategien und konkurrierender Unterpopulationen. Die Anwendung verschiedener Strategien ermöglicht die gleichzeitige Verwendung verschiedener Parametereinstellungen für jede der Unterpopulationen. Dadurch ergeben sich mehrere Verbesserungen. Einerseits ist die Anwendung verschiedener Strategien in der Durchführung schneller und einfacher als mehrere unabhängige Experimente mit unterschiedlichen Parametersätzen. Die Ergebnisse können in einer kompakten und überschaubaren Weise dargeboten werden, wodurch die Bewertung des Erfolgs der Strategien direkt und einfach möglich ist. Erfolglose und erfolgreiche Strategien können voneinander getrennt werden. Der während eines Laufs unterschiedliche Erfolg der Strategien kann direkt und in Wechselwirkung mit anderen Strategien bewertet werden. Andererseits können sich die Strategien innerhalb eines Laufs untereinander ergänzen, wodurch es zu besseren Ergebnissen kommt, als bei getrennt voneinander verwendeten Strategien. In Abschnitt 4.5 werden neben der Berechnung des Erfolgs der einzelnen Strategien durch die Ordnung der Unterpopulationen insbesondere Methoden zum visuellen Vergleich der Strategien und zur Auswertung des Erfolgs der einzelnen Strategien vorgestellt und in der Anwendung gezeigt.

Noch einen Schritt weiter geht der Einsatz konkurrierender Unterpopulationen. Dabei werden nicht nur verschiedene Strategien gleichzeitig angewendet, sondern es findet ebenfalls eine Verteilung der zur Verfügung stehenden Ressourcen entsprechend des Erfolgs der einzelnen Strategien statt. Erfolgreiche Strategien erhalten mehr Ressourcen zur Verfügung gestellt als erfolglose Strategien. Dadurch kommt es zu einer dynamischen Verteilung der Ressourcen mit einer Bevorzugung der erfolgreichen Strategien. Für die Verteilung der Ressourcen werden Analogien zur Fitneßzuweisung gezogen und diese Verfahren entsprechend für die Aufteilung der Ressourcen angewendet. Durch die Verteilung der Ressourcen kommt es zu einer Anpassung der Strategieparameter während eines Laufs. Diese Anpassung muß nicht von außen oder vom Benutzer vorgegeben werden, sondern erfolgt in Abhängigkeit des Verlaufs der Optimierung. Es können damit nicht nur verschiedene Strategien gleichzeitig angewendet werden, sondern die erfolgreichen Strategien erhalten einen großen Teil der Ressourcen zur Verfügung gestellt, und die erfolglosen Strategien verbrauchen nur einen kleinen Teil der Ressourcen. Ein ,,Aussterben" der zu einer Zeit erfolglosen Strategien wird verhindert. Damit wird eine Ergänzung mehrerer Strategien untereinander bei effektiver Verteilung der Ressourcen ermöglicht.

Die Anwendung verschiedener Strategien und der Einsatz konkurrierender Unterpopulationen sind ein weiterer Schritt zur Entwicklung leistungsfähiger Evolutionärer Algorithmen für die Lösung großer und schwieriger Probleme. Die Vorteile dieser Erweiterungen des regionalen Populationsmodells zeigen sich besonders bei der Bearbeitung praktischer Probleme, bei denen es auf den schnellen Test verschiedener Strategien und die Auswertung dieser Läufe bei einer gleichzeitig effektiven Verteilung der zur Verfügung stehenden Ressourcen ankommt.

Nach der Beschreibung Evolutionärer Algorithmen werden in Kapitel 5 Methoden zur visuellen Auswertung Evolutionärer Algorithmen vorgestellt. Die bei der Arbeit Evolutionärer Algorithmen anfallenden Daten sind relativ einfach strukturiert. Durch die große Menge an Daten müssen diese aber einer Bearbeitung unterzogen werden, um sie für den Anwender verständlich und benutzbar zu machen. Die dargestellten Methoden und Verfahren ermöglichen eine Visualisierung des Verlaufs und der Ergebnisse der Arbeit Evolutionärer Algorithmen. Die Visualisierung kann für unterschiedliche zeitliche Bereiche (eine, mehrere, alle Generationen eines Laufs), für unterschiedliche Mengen an Daten (einzelne, mehrere, alle Individuen einer Population), für direkt zur Verfügung stehende Werte oder für abgeleitete Werte erfolgen. Zusätzlich werden Methoden zur Visualisierung von Eigenschaften der Zielfunktion vorgestellt, die bei der Analyse eines Problems hilfreich sind.

Mit den vorgestellten Verfahren zur Visualisierung stehen leistungsfähige Methoden zur Verfügung, die einen schnellen und effektiven Überblick über die verschiedensten Aspekte des Verlaufs und der Ergebnisse Evolutionärer Algorithmen ermöglichen. Durch den Einsatz der Visualisierungsverfahren können Einsichten in die Arbeit Evolutionärer Algorithmen gewonnen werden, die auf anderem Wege nicht möglich sind bzw. in den anfallenden Datenmengen verborgen bleiben würden. Die präsentierten umfangreichen Beispiele zeigen den Einsatz der Verfahren an realen und Testproblemen und machen auf die aus den jeweiligen Darstellungen ablesbaren Informationen aufmerksam.

Alle in den Kapiteln 3, 4 und 5 vorgestellten und beschriebenen Verfahren, Operatoren und Methoden sind in der Genetic and Evolutionary Algorithm Toolbox for use with Matlab implementiert. Diese Toolbox stellt die umfassendste Implementierung Evolutionärer Algorithmen unter dem Programmiersystem Matlab dar, die zur Zeit verfügbar ist. Alle in dieser Arbeit vorgestellten Beispiele und Grafiken wurden mit dieser Toolbox berechnet und erzeugt. Die in Kapitel 7 besprochenen Anwendungen wurden mit dieser Toolbox gelöst. Weiterhin ist die Toolbox bei mehreren internationalen Forschergruppen und industriellen Anwendern im Einsatz und hat sich dort in den verschiedensten Anwendungsbereichen bewährt. Die plattformunabhängige Programmierung und Dokumentation erlaubt einen direkten Einsatz auf allen Rechnersystemen, auf denen Matlab verfügbar ist.

Den Abschluß dieser Arbeit bildet die Beschreibung zweier Anwendungen in Kapitel 7, die als Beispiele von in den letzten Jahren gelösten Problemen exemplarisch ausgewählt wurden: die Optimierung des Klimas in einem Gewächshaus und die Optimierung eines Gleichstrom-Stellers. Beide Anwendungen stellen komplexe Probleme dar. Besonderes Augenmerk wurde auf die Einbringung von problemspezifischem Wissen in den Optimierungsprozeß gelegt. Dies ist bei Evolutionären Algorithmen an verschiedenen Punkten und relativ einfach möglich. Durch dieses problemspezifische Wissen kann die Suche nach Lösungen deutlich beschleunigt bzw. die Qualität der erreichten Lösungen verbessert werden. Die hier dargestellten Anwendungen geben einen kleinen Einblick in das breite Spektrum praktischer Probleme, die durch die systemtechnische Anwendung Evolutionärer Algorithmen bearbeitet und gelöst werden können. Unter Verwendung entsprechend zugeschnittener Werkzeuge stellen Evolutionäre Algorithmen leistungsfähige Optimierungsverfahren mit unterschiedlichsten Eigenschaften für die praktische Anwendung dar. Sie können direkt und einfach eingesetzt werden und bei der Lösung einer großen Klasse von Problemen helfen. Mit Evolutionären Algorithmen konnten in vielen Anwendungen bessere Lösungen gefunden werden, als dies mit klassischen Optimierungsverfahren möglich war.

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