Die Arbeit stellt Evolutionäre Algorithmen als stochastische Verfahren zur Optimierung von Systemen vor.
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.
Es 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. Statt auf die Unterschiede zu verweisen, werden die Gemeinsamkeiten sowie die Anwendbarkeit der Verfahren und Operatoren auf verschiedene Klassen von Problemen in den Vordergrund gestellt. Dieser Gedanke ist eine der Grundlagen der vorliegenden Arbeit.
Ausgehend von einer einfachen Struktur Evolutionärer Algorithmen werden Verfahren und Operatoren vorgestellt und erläutert, aus denen sich ein Evolutionärer Algorithmus zusammensetzt. In dieser Darstellung werden nicht einzelne Algorithmen oder Operatoren hervorgehoben, sondern es werden die Zusammenhänge bzw. Abhängigkeiten untereinander 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.
Die Unterteilung der Population bei Evolutionären Algorithmen, die für die gleichzeitige Berechnung von Varianten benötigt wird, führt zur Beschreibung von Populationsmodellen. In der Arbeit wird ein Überblick über bisherige Klassifikationen von Populationsmodellen gegeben und die Unterteilung nach der Reichweite der Selektion in globales, regionalen und lokales Modell als am besten geeignet verwendet. Eine Beschreibung der einzelnen Populationsmodelle wird vorgenommen.
Eine allgemeine Beschreibung von Nachbarschaftstopologien, die für das regionale und das lokale Modell angewendet werden kann, wird erstmals 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 insbesondere beim Vergleich verschiedener Topologien.
Neue Erweiterungen des regionalen Modells werden vorgestellt: die Anwendung verschiedener Strategien und der Einsatz 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. 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. Neben der Berechnung des Erfolgs der einzelnen Strategien durch die Ordnung der Unterpopulationen werden insbesondere Methoden zum visuellen Vergleich der Strategien und zur Auswertung des Erfolgs der einzelnen Strategien vorgestellt und in der Anwendung gezeigt.
Beim Einsatz konkurrierender Unterpopulationen 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.
Erstmals werden umfassend 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, für unterschiedliche Mengen an Daten, 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. 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 der Arbeit 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, Grafiken und Anwendungen wurden mit dieser Toolbox berechnet und erzeugt. Die plattformunabhängige Programmierung und Dokumentation erlaubt einen direkten Einsatz auf allen Rechnersystemen, auf denen MATLAB verfügbar ist.
Zwei Anwendungen werden beschrieben, die im Rahmen dieser Arbeit gelöst 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.
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.
Im Ausblick wird auf die weitere Entwicklung Evolutionärer Algorithmen eingegangen. Zwei Aspekte werden dabei vertiefend betrachtet: Kodierung der genetischen Information sowie Diploidie und Polyploidie.
Die Art der Kodierung der genetischen Information ist eine problemspezifische Frage. Durch Verwendung einer an das Problem angepaßten Kodierung wird zusätzliches Wissen in den Suchprozeß eingebracht. Dies führt meist zu einer Fokussierung und Beschleunigung der Suche. Eine einfache Kodierung, die mit einfachen und universellen Operatoren arbeitet, kann dagegen eine höhere Variabilität und Vielfalt erzeugen. Dadurch wird die Suche aber im Allgemeinen verlangsamt.
In der Natur liegt bei den meisten niederen Lebewesen die genetische Information in einfacher Ausführung vor (haploid). Aber so gut wie alle höheren Lebewesen haben einen diploiden oder polyploiden Chromosomensatz. Je komplexer die Organismen sind, um so komplexer ist die zugrundeliegende Struktur. Es wird eine Übersicht zu bisherigen Arbeiten der Verwendung diploider Informationen in Evolutionären Algorithmen gegeben. Die Anwendung der Diploidie kann die folgenden Vorteile für Evolutionäre Algorithmen bringen: Erhaltung der Verschiedenartigkeit der Population und schnelle Adaption an Veränderungen der Zielfunktion.
In den künstlichen Welten heutiger Evolutionärer Algorithmen, die beschränkte Populationen, stationäre Zielfunktionen und eine geringe Anzahl von Generationen benutzen, ist allerdings kein Bereich erkennbar, in dem ein diploides oder polyploides System einen Vorteil gegenüber einem vernünftig entworfenen haploiden System bringt. Mit der weiteren Entwicklung Evolutionärer Algorithmen werden aber schrittweise immer größere Probleme bearbeitet. Bei diesen können mehrere Zielfunktionen gleichzeitig zum Einsatz kommen; die Entwicklung des Systems verläuft über eine wesentlich längere Zeit und die Populationen sind deutlich größer. In diesen neuen Umgebungen sollte der Einsatz diploider Systeme in Betracht gezogen werden, da dann die Vorteile dieser Systeme gegenüber haploiden Systemen besser zur Wirkung kommen können.
Die Arbeit enthält ein umfangreiches Literaturverzeichnis zu den Aspekten, die in der Arbeit vertiefend behandelt werden. Außerdem werden in einem Glossar wichtige Begriffe aus den Bereichen Biologie, Genetik und Evolutionäre Algorithmen in ihrem jeweiligen Kontext erläutert.