Evolutionäre Algorithmen

Dieses Zitat von John Holland zielt weniger auf die biologische Evolution selbst, sondern viel mehr auf die Idee, Prinzipien der Evolution zu nutzen, um Probleme mit dem Computer zu lösen. Die klassische Strategie zur Lösung von Problemen mit dem Computer besteht darin, auf der Grundlage möglichst detaillierten Wissens über die Struktur und die Eigenschaften des Problems ein effizientes Verfahren zu entwickeln, das die gewünschte Lösung konstruiert. Voraussetzung für diese Vorgehensweise ist zum einen, dass die benötigten strukturellen Informationen über das Problem genau bekannt sind, und zum anderen, dass Experten und Programmierer die Zeit und den Aufwand investieren, an einem entsprechenden Modell und seiner Implementierung zu arbeiten. Die erste Voraussetzung ist nicht immer gegeben, die zweite bedeutet meist erhebliche Kosten. Experten müssen zunächst ein Modell erstellen, auf der Basis dieses Modells geeignete Problemlösungsstrategien entwickeln und diese Verfahren schließlich implementieren.

Das Ziel dieses Kapitels besteht in einer Definition und Klassifikation von Optimierungsproblemen. Zunächst sollen aber einige Beispiele für Optimierungsprobleme erläutert werden, die zur Einführung der notwendigen Begriffe geeignet sind und die Optimierungsproblemen zugrunde liegenden Strukturen veranschaulichen.

Bevor wir uns dem eigentlichen Thema dieses Buches — den evolutionären Algorithmen — widmen, soll in diesem Kapitel eine Auswahl bekannter, sowohl klassischer als auch moderner Optimierungsverfahren kurz besprochen werden. Eine detaillierte Diskussion der Verfahren würde den Rahmen dieses Buches bei weitem sprengen, so dass wir auf die entsprechende Literatur verweisen. Ein guten Überblick über klassische Optimierungsverfahren findet sich in [Pap96].

In diesem Kapitel sollen die grundlegende Terminologie evolutionärer Algorithmen eingeführt und deren Gebrauch am Beispiel kanonischer genetischer Algorithmen veranschaulicht werden.

Da der theoretische Untersuchungen über genetische Algorithmen hauptsächlich bei einer Restriktion auf das binäre Alphabet (Allele nur 0,1) und für die Verwendung des einfachen, in Abschnitt 4.2 vorgestellten Algorithmus durchgeführt wurden, werden wiruns in diesem Kapitel auf diesen Bereich einschränken.

Angesichts der Vielzahl der Optimierungsalgorithmen stellt sich die Frage nach ihrer Anwendbarkeit bei konkreten, praktischen Problemen. Wann macht es Sinn, welchen Algorithmus zu nutzen. Eine eindeutige Antwort lässt sich auf diese Frage nur selten geben. Einige der in Kapitel 3 genannten Verfahren sind von vornherein auf stetige und/oder differenzierbare Zielfunktionen beschränkt, andere nur bei unimodalen Fitnesslandschaften mit Erfolg einzusetzen (z.B. Hillclimbing). Bezüglich der von evolutionären Algorithmen gut bearbeitbaren Probleme lassen sich einige allgemeine Aussagen machen (siehe [Mit96, Nis97]). Sie lassen sich gegenüber anderen Modellen erfolgreich einsetzen, wenn

Wir haben bereits den kanonischen genetischen Algorithmus kennen gelernt sowie zahlreiche Varianten von genetischen Operatoren und Verfahren wie Selektion, Mutation und Crossover diskutiert. In diesem Kapitel wird eine Klassifizierung evolutionärer Algorithmen beschrieben, die zum Teil auf historischen Entwicklungen beruht. Man sollte die einzelnen Modelle evolutionärer Algorithmen allerdings nicht als konkurriende, sich gegenseitig ausschließende Verfahren betrachten, sondern bei einem realen Optimierungsproblem die geeigneten Komponenten und Techniken der einzelnen Verfahren sinnvoll miteinander kombinieren. Wo eine binäre Kodierung angebracht ist, sollte man sie verwenden. Bei reellen Parametern ist meistens auch eine Fließkommakodierug einer binären Kodierung vorzuziehen. Und wenn sowohl diskrete als auch kontinuierliche Parameter zu optimieren sind, dürfen in einem Chromosom Gene beiden Typs auftreten.

Will man die Leistungsfähigkeit eines evolutionären Algorithmus für ein spezielles Problem oder eine Problemklasse beurteilen, sollten geeignete Tests durchgeführt. In diesem Kapitel sollen die Vorgehensweise bei derartigen Tests sowie einige Testfunktionen vorgestellt werden.

Dieses Kapitel beinhaltet eine kurze Einführung in die Thematik der Fuzzy-Systeme. Wir beschränken uns auf die wesentlichen Definitionen und Konzepte, die für das Verständnis des Kapitels 10 über Kombinationen von evolutionären Algorithmen mit Fuzzy-Systemen erforderlich sind. [KGK94] gibt eine ausführliche Einführung in die Grundlagen der Fuzzy- Systeme, [MKKN02] behandelt vor allem die regelungstechnischen Aspekte der Fuzzy- Systeme, deren Konzepte auch häufig im Zusammenhang mit evolutionären Algorithmen verwendet werden.

In diesem abschließenden Kapitel sollen die wichtigsten Kombinationen von evolutionären Algorithmen mit Fuzzy-Systemen aufgezeigt werden. Es gibt zu diesem Thema inzwischen so umfangreiche Literatur, dass nur ein Teil der Beiträge in das Literaturverzeichnis aufgenommen werden konnte. Allein das bereits 1997 erschienene Buch [Ped97] über „ Fuzzy Evolutionary Computing” enthält 299 Literaturverweise.