Evolutionärer Algorithmus

Ein Evolutionärer Algorithmus (EA) ist ein Optimierungsverfahren, das als Vorbild die biologische Evolution hat. Dabei werden Individuen durch ihre Eigenschaften (i.A. in Zahlenwerten) beschrieben; sie müssen sich bzgl. der Selektionsbedingungen als möglichst geeignet behaupten, und dürfen dementsprechend ihre Eigenschaften vererben - oder eben nicht. Im Laufe mehrerer Durchläufe entwickelt sich so die „Bevölkerung“ immer näher an das Optimum.

Verfahren

Während der Evolution wurden durch Veränderungen des Erbgutes hochkomplexe Lebensformen und Organismen an ihre Umwelt- und Lebensbedingungen angepasst. Es wird damit ein sehr schwieriges Optimierungsproblem gelöst. Das Erstaunliche daran ist die relative Einfachheit der Steuerungsmechanismen. In einem einfachen Modell lässt sich der Prozess auf lediglich drei biologische Prinzipien zurückführen, die iterativ immer wieder durchlaufen werden: Mutation, Rekombination und Selektion.

• Die Mutation des Erbgutes ist ein ungerichteter Zufallsprozess, der Alternativen und Varianten des Vorhandenen erzeugt. Aus Sicht der Optimierungstheorie kommt der Mutation die Aufgabe zu, lokale Optima zu überwinden. Genetisch entspricht dies neuem Erbgut, das in die Population eingeführt wird und deren Diversität steigert.
• Die Rekombination der Erbinformation erweitert die Vielfalt, da zuvor gekoppelte Eigenschaften zweier erfolgreicher Individuen nach dem Zufallsprinzip neu kombiniert werden. 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 bewertet die Ergebnisse des Zufallsexperimentes, und zwar ausschließlich anhand der aktuellen Umweltbedingungen. An dieser Stelle wird die Richtung der evolutiven Veränderungen gesteuert, indem optimierte Phänotypen sich stärker vermehren. Genetisch entspricht dies der Entfernung von weniger geeignetem Erbgut, das aus der Population entfernt wird und dessen Diversität vermindert.

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 zufällige Ereignisse gestört. Auch bestens an ihre Umgebung angepasste Individuen können durch ein Unglück sterben, bevor sie Nachkommen zeugen. Damit ginge die genetische Information, die ein Optimum darstellt, verloren. Zufallsstörungen dieser Art ließen sich allerdings über den Faktor Zeit noch beheben, da früher oder später das Optimum erneut entsteht, und sich dann per Selektion doch durchsetzt.

Eine weitere Eigenschaft macht die Selektion dagegen zu einem indeterministischen Faktor. Die Selektion ist keine konstante Größe, da sich die Umwelt- und Lebensbedingungen der Individuen während des Evolutionsprozesses ständig ändern. So zieht beispielsweise eine Optimierung der Tarnung einer Beuteart zwangsläufig eine Veränderung der Selektionsbedingungen bei der Räuberart nach sich; sind die Räuber an die verbesserte Beutetarnung angepasst, ist die zuvor optimale Tarnung nur noch suboptimal. Es gibt also eine Rückkopplung zwischen jedem einzelnen Individuum und seiner Umwelt, die vielfältigen Eigenschaften der Umweltfaktoren werden paradoxerweise auch durch die Eigenschaften der Individuen beeinflusst (die Umkehrung gilt trivialerweise sowieso). Diese hochkomplexen Veränderungen der biotischen Selektionsfaktoren wird nun durch globale Faktoren wie Klimaveränderungen, plattentektonische Prozesse etc. nochmals überformt. Beim Evolutionären Algorithmus werden diese variablen Selektionskriterien nun extrem vereinfacht, indem sie in der Regel als Invarianten definiert werden.

Algorithmisch kommt der Repräsentation der Individuen große Bedeutung zu. Wie wird eine potentielle Lösung genetisch kodiert? Was ist der Lösungsraum? Welche Variationsoperationen sind darin angebracht? Dies muss meist problemabhängig beantwortet werden, typische Repräsentationen sind Datenstrukturen wie Vektoren von Bits, reellen Parametern oder ganze Programme.

Daneben ist die Bewertungsmethode, auch Fitnessfunktion genannt, essentiell für die Leistung des EA. Sie muss in der Lage sein, die Qualität beliebiger Lösungen möglichst gut abzubilden, da sie das Selektionskriterium bildet und damit die Suchrichtung definiert. Grundregeln sind, dass die optimale Lösung maximal bewertet werden sollte, während ähnliche Lösungen ähnlich bewertet werden sollten. Außerdem helfen möglichst feine Abstufungen zwischen "schlechten" und "guten" Lösungen dem Suchvorgang. Typischerweise ist die Bewertung der rechenintensivste Teil eines EA. In der Regel werden einzelne Individuen unabhängig bewertet, indem sie auf einen reellen Wert abgebildet werden. Allerdings sind auch Turnier-Verfahren üblich, die jeweils eine Teilgruppe von Individuen betrachten und diese relativ vergleichen und Werte zuweisen. Je strenger das Bewertungsverfahren und die damit verbundene Selektion arbeiten, desto höher ist der Selektionsdruck. Je höher der Selektionsdruck, desto schneller konvergiert die Population gegen ein Optimum, desto höher ist jedoch auch die Gefahr, dass dies nur ein lokales Optimum ist.

Pseudocode

Auf einer Population P von möglichen Lösungen kann der EA-Pseudocode folgendermaßen aussehen:

t = 0
initialisiere P(0)
wiederhole bis Abbruchkriterien erfüllt sind:
 bewerte P(t)
 selektiere P'(t) aus P(t)
 rekombiniere P'(t)
 mutiere P'(t)
 P(t+1) = P'(t)
 t = t+1
fertig

Geschichte

Bereits Anfang der 1960er Jahre begannen verschiedene Forschergruppen die Prinzipien der Evolution nachzuahmen, um effiziente Optimierungsalgorithmen zu entwickeln. So haben John H. Holland und David E. Goldberg die Genetischen Algorithmen (GA), Lawrence J. Fogel das Evolutionäre Programmieren (EP), Hans-Paul Schwefel und Ingo Rechenberg die Evolutionsstrategischen Algorithmen (ES) entwickelt. Diese unabhängig voneinander entstandenen 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 (z.B. Nichtlineare Regression). 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 kaum Problemwissen, insbesondere keine Gradienteninformation, können also z.B. auch bei diskontinuierlichen Problemen angewendet werden.
• Sie gehören zur Klasse der stochastischen Suchverfahren und ermöglichen damit auch die Behandlung von Problemen, die mit traditionellen Optimierungsmethoden nicht mehr handhabbar sind.
• Evolutionäre Algorithmen bieten im Allgemeinen keine Garantie, das globale Optimum in vernünftiger Zeit zu finden.
• Großer Nachteil der EAs ist der oft sehr große Rechenzeitbedarf: Evolutionäre Algorithmen sind eher die schlechtere Wahl für Probleme, für die es spezielle Optimierungsverfahren gibt, da diese in der Regel effizienter arbeiten. 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:

• Genetische Programmierung
• Genetische Algorithmen
• Evolutionsstrategien
• Evolutionäre Programmierung

Literatur

• Ingrid Gerdes, Frank Klawonn, Rudolf Kruse, Evolutionäre Algorithmen: genetische Algorithmen - Strategien und Optimierungsverfahren - Beispielanwendungen Wiesbaden: Vieweg. 2004. ISBN 3528055707
• Volker Nissen, Einführung in evolutionäre Algorithmen: Optimierung nach dem Vorbild der Evolution Braunschweig: Vieweg. 1997. ISBN 3528054999
• Hartmut Pohlheim, Evolutionäre Algorithmen: Verfahren, Operatoren und Hinweise für die Praxis Berlin: Springer. 1999. ISBN 3540664130
• Karsten Weicker, Evolutionäre Algorithmen Stuttgart: Teubner. 2002. ISBN 3519003627
• Kenneth A. de Jong, Evolutionary Computation: A Unified Approach. A Unified Approach MIT Press. 2006. ISBN 0262041944
• Langdon, W. B., Poli, R., Foundations of Genetic Programming, Springer-Verlag, 2002. ISBN 3540424512
• Poli, R., Langdon, W. B., McPhee, N. F. (2008), A Field Guide to Genetic Programming, freely available via Lulu.com. ISBN 978-1-4092-0073-4

Weblinks

• Karsten Weicker, Evolutionäre Algorithmen (pdf) (218 kB)
• Evolutionäre Algorithmen - Begriffe und Definitionen. Online Version der VDI/VDE-Richtlinie-3550, Blatt C3
• Evolutionary Algorithms - Terms and Definitions. Online Version der VDI/VDE-Richtlinie-3550, Blatt C3
• Informationen zum Thema Evolutionsalgorithmen
• Global Optimization Algorithms - Theory and Application (PDF-Datei; 13,14 MB)

Implementierungen

• EvA2 (Java), umfassendes Framework für EA und heuristische Optimierung mit GUI.