Evolutionärer Algorithmus

Ein Evolutionärer Algorithmus (EA) ist ein Optimierungsverfahren, das als Vorbild die biologische Evolution hat.

Inhaltsverzeichnis

Verfahren

Die Evolution ist in der Lage, durch Manipulation des Erbgutes selbst komplexe Lebensformen und Organismen an ihre Umwelt- und Lebensbedingungen anzupassen. Sie löst damit ein sehr schwieriges Optimierungsproblem. Die erstaunlichste Eigenschaft der Evolution ist die relative Einfachheit ihrer Vorgehensweise und das Zusammenwirken der verschiedenen Steuerungsmechanismen. In einem einfachen Modell lässt sich der durchgeführte Suchprozess auf drei einfache Prinzipien zurückführen: Mutation, Selektion und Rekombination.

Die Mutation des Erbgutes ist ein ungerichteter Prozess, dessen Sinn einzig in der Erzeugung von Alternativen und Varianten liegt. Aus Sicht der Optimierungstheorie kommt der Mutation die Aufgabe zu, lokale Optima zu überwinden. Sie sorgt dafür, dass die Population nicht frühzeitig gegen ein lokales Optimum konvergiert. Die Mutationswahrscheinlichkeiten pro Gen liegen im allgemeinen zwischen $10 - 4$ und $10 - 7$ .
Die Rekombination (Crossover) der Erbinformation liegt hinsichtlich ihres Beitrages zur Zielfindung im Rahmen der Evolution zwischen Mutation und Selektion. Die Stellen, an denen ein Crossover zwischen homologen Chromosomen stattfindet, werden zufällig bestimmt. Die eigentliche Rekombination erfolgt aber nicht mehr zufällig. Nahe beieinanderliegende und funktional verbundene Gene werden seltener getrennt als weiter auseinanderliegende Gengruppen. Ein evolutionärer Algorithmus kann ohne Rekombination auskommen (d.h. es gibt eine asexuelle Fortpflanzung der einzelnen Individuen mit nur einem Elternteil pro Kind), in bestimmten Fällen ist die Anwendung von Rekombination jedoch effizienter.
Die Selektion ist für die eigentliche Steuerung der Suchrichtung der Evolution zuständig. Sie bestimmt die Richtung, in der sich das Erbgut verändert, indem sie festlegt, welche Phänotypen sich stärker vermehren. Die Selektion wäre demnach, wenn es keine Störungen gäbe, eine deterministische Komponente innerhalb der Evolution. In der Natur wird die Selektion jedoch immer wieder durch meist zufällige Ereignisse gestört. Auch die am besten an ihre Umgebung angepassten Individuen können durch ein Unglück sterben, bevor sie Nachkommen zeugen. Damit würde die genetische Information, die ein Optimum darstellt, verloren gehen. Zwei weitere Einflüsse machen die Selektion zu einem indeterministischen Faktor. Zum einen ist sie keine konstante Größe, da sich die Umwelt und die Lebensbedingungen der Individuen ändern können, zum anderen gibt es eine Rückkopplung zwischen den einzelnen Individuen und ihrer Umgebung. Diese können durch Eingriffe in die Umwelt ihre eigene Selektion beeinflussen.

Geschichte

Bereits Anfang der sechziger Jahre begannen verschiedene Forschergruppen die Prinzipien der Evolution nachzuahmen, um effiziente Optimierungsalgorithmen zu entwickeln. So haben Holland, Fogel und Goldberg die Genetischen Algorithmen (GA), Schwefel und Rechenberg die Evolutionsstrategischen Algorithmen (ES) entwickelt. Diese unabhängig voneinander entstandene Entwicklungen, die unter dem Sammelbegriff Evolutionäre Algorithmen (EA) zusammengefasst werden, haben die gemeinsame Eigenschaft, bewusst Prinzipien der Evolution nachzuahmen, um sie im Sinne von Optimierungsregeln einzusetzen.

Anwendungsgebiete

Die wichtigsten Anwendungsgebiete der Evolutionären Algorithmen sind Optimierungsprobleme, bei denen traditionelle Optimierungsverfahren aufgrund von Nichtlinearitäten, Diskontinuitäten und Multimodalität versagen. Die Eigenschaft ihrer Robustheit liegt darin begründet, dass zum einen keine Annahmen über das gestellte Problem getroffen werden, und zum anderen stets mit einer Menge von zulässigen Lösungen (Population von Lösungen) gearbeitet wird. Dadurch werden gleichzeitig mehrere Wege zum Optimum ausprobiert, wobei auch noch Informationen über die verschiedenen Wege (durch Vererbung bzw. Rekombination) ausgetauscht werden. Auf diese Weise wird das Wissen über das zugrundeliegende Problem in der gesamten Population verteilt, wodurch eine frühzeitige Konvergenz während der Optimierung verhindert werden kann.

Eigenschaften

Zusammenfassend kann man die Vor- und Nachteile der Evolutionären Algorithmen wie folgt beschreiben:

Sie bieten eine parallele Suche in einer Population von möglichen Lösungen, sodass immer mehrere potentielle Lösungen gefunden werden.
Sie benötigen keine Gradienteninformation, können also auch bei nichtlinearen oder diskontinuierlichen Problemen angewendet werden.
Sie gehören zur Klasse der stochastischen Suchverfahren, ermöglichen also auch die Behandlung komplizierter Probleme, die aufgrund eines zu hohen Rechenaufwandes mit traditionellen Optimierungsmethoden nicht mehr handhabbar sind.
Evolutionäre Algorithmen bieten im Allgemeinen keine Garantie, das globale Optimum zu finden. Jedoch gibt es für das Verfahren der simulierten Abkühlung (simulated annealing) unter weiteren Voraussetzungen einen Beweis, dass dieser das globale Optimum in endlicher Zeit findet.
Großer Nachteil der EAs ist der oft sehr große Rechenzeitbedarf: Evolutionäre Algorithmen sollten nicht zur Lösung von Problemen benutzt werde, für die es bereits traditionelle Optimierungsverfahren gibt, da diese in der Regel effizient sind. So sind z.B. Newton-Raphson-Methoden, die Gradienten bei der Optimierung verwenden, bei der Suche lokaler Minima um ein vielfaches schneller als Evolutionäre Algorithmen.

Zu den Evolutionären Algorithmen zählt man:

Weblinks

Karsten Weicker, Evolutionäre Algorithmen (pdf)

Evolutionäre Algorithmen - Begriffe und Definitionen. Online Version der VDI/VDE-Richtlinie-3550, Blatt C3