Evolutionsstrategie
aus Wikipedia, der freien Enzyklopädie
Evolutionsstategien (ES) sind heuristische Optimierungsverfahren und gehören zu den Evolutionären Algorithmen. Sie werden vor allem für Probleme eingesetzt, für die keine geschlossene Lösung vorliegt und stehen in Konkurrenz zu klassischen Suchstrategien.
Viele biologische, technische und menschliche Prozesse laufen nach einem der biologischen Evolution ähnlichen Prinzip ab.
Dieses Prinzip der Evolution besteht aus den Prozessen
- Generierung neuer Elemente durch Rekombination und durch Variation vorhandener Elemente oder durch Neuentnahme aus einer Art Bibliothek bzw. Gedächtnis
- Zusammenbringen dieser Elemente mit einem weiteren Prozess, der letztlich zu einer Auswahl von Elementen führt, indem einzelne relativ gefördert und andere relativ geschwächt werden. Es wird also innerhalb der Menge der Elemente als Ganzes eine Differenz, ein Kontrast, eine Auswahl, eine Form erzeugt.
- (In einem fortlaufenden evolutionären Kreislauf werden die in der Auswahlphase verstärkten Elemente auch verstärkt zu denen, die als Grundlage für die Generierung neuer Elemente in A genommen werden. Es entsteht eine sich selbstverstärkende bzw. sich stabilisierende Form)
Je nachdem wieweit man diese Definition versteht, umfasst sie die biologische Evolution, die technische Evolution, Kreative Meinungsbildungsprozesse, soziales Lernen, Gedankensysteme, Rückkopplungs- und zirkuläre Editiersysteme, genetische Algorithmen.
Inhaltsverzeichnis |
[Bearbeiten] Definition
Die Evolutionsstrategien umfassen eine Rubrik der Optimierungsalgorithmen, in denen die biologische Evolution, soweit für die Lösung des Problems vorteilhaft, nachgebildet wird. Das Ziel ist nicht eine möglichst genaue, sondern eine dem Problem angemessene Nachbildung.
Eine typische Evolutionsstrategie umfasst folgende Schritte
- Initialisierung: Nach einem zufälligen Verfahren wird eine bestimmte Anzahl von Individuen generiert.
- Selektion : Die Selektion bezeichnet die Methode, nach der ein Elter ausgewählt wird. Bei den Evolutionsstrategien werden die Eltern nach dem Zufallsprinzip ausgewählt.
- Rekombination: Die Rekombination ist die Art, nach der aus einem oder mehreren Eltern ein oder mehrere Nachkommen generiert werden. Es gibt verschiedene Arten der Rekombination. Bei der einfachsten Methode wird ein selektierter Elter ohne Rekombination übernommen.
- Mutation: Die Mutation bezeichnet eine meist geringfügige Veränderung des Nachkommens. Bei den Evolutionsstrategien wird meist eine kleine Zahl auf den ausgewählten Teil addiert oder subtrahiert. Wie stark der mutierte Wert von dem Ursprungswert abweichen kann, wird durch die Streuung bestimmt. Auf dem alten Wert wird eine normalverteilte Zahl mit dem Mittelwert 0 und einer Standardabweichung σ addiert:
- Bewertung: Mit Hilfe einer Fitnessfunktion wird die Fitness der Individuuen bewertet. Nach der Fitness der Individuen wird entschieden, welche Individuen die nächste Generation bilden.
- Generieren: Eine bestimmte Anzahl der fittesten Individuen bilden die neue Generation von Individuen. Der nächste Durchlauf wird mit der Selektion begonnen.
[Bearbeiten] Arten
Im folgenden werden die Grundarten der Evolutionsstrategie näher erläutert. Diese Arten können beliebig verschachtelt werden um auf ein Problem zugeschnitten zu werden. Die jeweiligen Algorithmen laufen unendlich bis ein Abbruchkriterium erfüllt ist. Dieses Abbruchkriterium ist meist entweder eine bestimmte Anzahl von maximalen Generationen, das Erreichen des Ergebnisses oder eine Kombination von beidem.
[Bearbeiten] (1 + 1) − ES
Hier umfasst jede Population nur ein Individuum. Aus dem Elter wird ein neues Individuum generiert. Die Selektion entfällt bei dieser Methode. Der Nachkomme wird durch Mutation verändert. Mit Hilfe der Fitnessfunktion wird die Fitness berechnet. Dann wird der fittere der beiden Individuen in die nächste Generation übernommen.
[Bearbeiten] (μ + 1) − ES
Hier umfasst jede Generation μ Individuen. Per Zufall wird ein Elter ausgewählt und mit ihm ein Kind-Individuum generiert. Die Fitness wird berechnet. Dann wird das am wenigsten fitte Individuum entfernt. Die verbliebenen bilden die neue Generation.
[Bearbeiten] (μ + λ) − ES
Hier umfasst jede Generation μ Individuen. Aus den μ Eltern werden λ Kinder generiert, mit λ
μ. Die Fitness von allen Kindern und Eltern wird berechnet und die μ fittesten (aus Eltern und Kindern) bilden die nächste Generation. Der Quotient λ / μ wird als Selektionsdruck bezeichnet.
[Bearbeiten] (μ, λ) − ES
Hier umfasst jede Generation μ Individuen. Aus den μ Eltern werden λ Kinder generiert, mit λ μ. Die Eltern werden gelöscht und spielen für die Bildung der nächsten Generation keine Rolle mehr. Die Fitness von allen λ Kindern wird berechnet und die μ fittesten der λ Individuen bilden die nächste Generation. Bei dieser Methode kann kein Individuum länger als eine Generation überleben, und die Fitnesskurve ist im Gegensatz zur (μ+ λ) − ES nicht monoton steigend.
[Bearbeiten] (μ', λ'(μ, λ)γ) − ES
Die μ' Elter erzeugen λ' Kinder und die Kinder werden für γ Generationen isoliert. In jeder der γ Generationen generiert jede isolierte Population λ Nachkommen. Die Fitness wird berechnet und die μ fittesten der Nachkommen werden in die nächste Generation übernommen. Nach den γ isolierten Generationen wird die beste der λ' Populationen aufgewählt und erzeugt als nächste Elterpopulation wieder λ' Kinder. Wie auch durch (μ+ λ) − ES bzw. (μ, λ) − ES lassen sich auch mit verschachtelten Evolutionsstrategien multimodale Optimierungsprobleme lösen. Die Anwendung verschachtelter ES kann in sehr komplexen multimodalen Optimierungsproblemen (z.B. nicht-linearen Regressionen) erfolgreicher sein als die Anwendung gewöhnlicher Evolutionsstrategien.
Das Verhalten kann mit Gipfelspringen und Gipfelklettern erläutert werden: http://www.bionik.tu-berlin.de/institut/s2mulmo.html Im Gütegebirge erzeugt ein Start-Punkt z.B. drei Nachkommen die zufällig verteilt werden. Diese erklimmen dann in der Isolationsphase den jeweils nächsten Gipfel. Nach der Isolationphase werden dann die besten als neue Startpunkte neue Nachkommen erzeugen.
[Bearbeiten] Besonderheiten
Das besondere an den Evolutionsstrategien im Gegensatz zu anderen Evolutionären Algorithmen ist, das sich der Algorithmus dynamisch anpassen kann. Die Schrittweite, also die Stärke, wie eine Mutation einen Wert verändert, kann dynamisch angepasst werden. Dies nennt sich Schrittweitenregelung.
[Bearbeiten] 1/5-Erfolgsregel
Die von I. Rechenberg theoretisch abgeleitete 1/5-Erfolgsregel besagt, dass der Quotient aus den erfolgreichen Mutationen (also Mutationen, die eine Verbesserung der Fitness bewirken) zu allen Mutationen etwa ein Fünftel betragen sollte. Ist der Quotient größer, so sollte die Streuung der Mutationen erhöht werden; ist der Quotient kleiner, so sollte die Streuung verringert werden.
[Bearbeiten] Probleme
Der Hauptoperator der Evolutionsstrategie ist die Mutation. Hat man eine gute Mutationsstrategie und eine gute Schrittweitenanpassung, so ist der Erfolg am wahrscheinlichsten. Das Problem ist, diese guten Werte zu finden. Rechenberg hat diese zentrale Schwierigkeit mit dem Begriff Evolutionsfenster benannt. Das Evolutionsfenster bezeichnet den schmalen Grat der für die Evolution sinnvollen Schrittweiten zwischen den zu großen Schritten (große Änderungen mit der Möglichkeit von Rückschritten) und zu kleinen Schritten (kleine Änderungen mit der Möglichkeit des Stillstandes) der Mutation. Es existiert noch kein Rezept, wie man garantiert das Evolutionsfenster treffen kann.
[Bearbeiten] Beispiel
[Bearbeiten] Varianten
- CMA-ORTHO
- CMA-MULTI
- CMA-ES
[Bearbeiten] Historie
Das Verfahren der Evolutionsstrategie wurde 1964 von Ingo Rechenberg entwickelt und 1965 publiziert (Royal Aicraft Establishment, Library Translation 1122, Farnborough). Später wurde es von vielen Anderen, in besonderem Maße von Hans-Paul Schwefel, weiterentwickelt.
[Bearbeiten] Literatur
- Ingo Rechenberg, Cybernetic Solution Path of an Experimental Problem (1965), In: Evolutionary Computation - The Fossil Record, Edited by D. B. Fogel, 1998, IEEE Press, ISBN 0-7803-3481-7
- Ingo Rechenberg, Evolutionsstrategie. Optimierung technischer Systeme nach Prinzipien der biologischen Evolution , Frommann Holzboog, 1973, ISBN 3-7728-0373-3 (Diss. von 1970)
- Ingo Rechenberg, Evolutionsstrategie '94, Frommann Holzboog, 1994, ISBN 3-7728-1642-8
- Hans-Paul Schwefel: Evolution and Optimum Seeking: New York: Wiley & Sons 1995, ISBN 0471571482
- Hans-Georg Beyer: The Theory of Evolution Strategies: Berlin Heidelberg New York: Springer 1998, ISBN 3-540-67297-4
