Evolutionärer Algorithmus
aus Wikipedia, der freien Enzyklopädie
Ein Evolutionärer Algorithmus (EA) ist ein Optimierungsverfahren, das als Vorbild die biologische Evolution hat.
Inhaltsverzeichnis |
[Bearbeiten] 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 biologische Prinzipien zurückführen: Mutation, Rekombination und Selektion.
- 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. Genetisch entspricht dies neuem Erbgut, das in die Population eingeführt wird und deren Diversität erhält.
- 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.
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 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 "Tournament"-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.
[Bearbeiten] Pseudocode
Auf einer Population P von möglichen Lösungen kann der EA-Pseudocode folgendermaßen aussehen:
initialisiere P(0) t = 0 Wiederhole bis Abbruchkriterien erfüllt sind: Bewerte P(t) Wähle P'(t) aus P(t) rekombiniere P'(t) mutiere P'(t) P(t+1) = P'(t) t = t+1 Fertig
[Bearbeiten] Geschichte
Bereits Anfang der sechziger Jahre begannen verschiedene Forschergruppen die Prinzipien der Evolution nachzuahmen, um effiziente Optimierungsalgorithmen zu entwickeln. So haben Holland und Goldberg die Genetischen Algorithmen (GA), Fogel das Evolutionäre Programmieren (EP), 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.
[Bearbeiten] 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.
[Bearbeiten] 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:
[Bearbeiten] 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
