Evolutionsstrategie

Evolutionsstrategien (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, wie weit man diese Definition fasst, umschließt sie die biologische Evolution, die technische Evolution, Kreative Meinungsbildungsprozesse, soziales Lernen, Gedankensysteme, Rückkopplungs- und zirkuläre Editiersysteme, genetische Algorithmen.

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

1. Initialisierung: Nach einem zufälligen Verfahren wird eine bestimmte Anzahl von Individuen generiert.
2. Selektion : Die Selektion bezeichnet die Methode, nach der ein Elter ausgewählt wird. Bei den Evolutionsstrategien werden die Eltern nach dem Zufallsprinzip ausgewählt - unter denen, die nach der Bewertung (s.u.) die aktuelle Generation bilden.
3. Rekombination (Vererbung): 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.
4. 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 (eine Eigenschaft des Individuums) addiert oder subtrahiert. Wie stark der mutierte Wert von dem Ursprungswert abweichen kann, wird durch die Streuung bestimmt (auf den alten Wert wird eine normalverteilte Zahl mit dem Mittelwert 0 und einer Standardabweichung σ addiert: $x_{neu} = x_{alt} + N(0,\, \sigma )$ ).
5. Bewertung: Mit Hilfe einer Bewertungsfunktion wird die Qualität der Individuen bewertet. Auf dieser Grundlage wird entschieden, welche Individuen die nächste Generation bilden.
6. Generieren: Eine bestimmte Anzahl der besten Individuen bilden die neue Generation von Individuen. Der nächste Durchlauf wird mit der Selektion begonnen.

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 so lange, 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.

(1 + 1) − ES

Hier umfasst jede Population nur ein Individuum. Aus dem Elter wird ein neues Individuum generiert. Die Rekombination entfällt bei dieser Methode. Der Nachkomme wird durch Mutation verändert. Mit Hilfe der Bewertungsfunktion wird die Anpassung berechnet. Dann wird der passendere der beiden Individuen in die nächste Generation übernommen.

(μ + 1) − ES

Hier umfasst jede Generation μ Individuen. Per Zufall wird ein Elternteil ausgewählt und mit ihm ein Nachkomme gebildet. Nach Bewertung werden die µ besten Individuen in die folgende Generation übernommen.

(μ + λ) − ES

Hier umfasst jede Generation μ Individuen. Aus den μ Eltern werden λ Kinder generiert. Die Anpassung von allen Kindern und Eltern wird berechnet und die μ passendsten (aus Eltern und Kindern) bilden die nächste Generation. Der Quotient λ / μ wird als Selektionsdruck bezeichnet.

(μ, λ) − ES

Hier umfasst jede Generation μ Individuen. Aus den μ Eltern werden λ Kinder generiert, mit λ$\ge$ μ. Die Eltern werden gelöscht und spielen für die Bildung der nächsten Generation keine Rolle mehr. Die Anpassung von allen λ Kindern wird berechnet und die μ passendsten der λ Individuen bilden die nächste Generation. Bei dieser Methode kann kein Individuum länger als eine Generation überleben, und die Anpassungskurve ist im Gegensatz zur (μ+ λ) − ES nicht monoton steigend.

(μ', λ'(μ, λ)^γ) − ES,    (μ'+ λ'(μ+ λ)^γ) − ES,    (μ'+ λ'(μ, λ)^γ) − ES,    (μ', λ'(μ+ λ)^γ) − ES

Hier gibt es μ' Populationen mit je μ Individuen. Die μ' Elternpopulationen erzeugen λ' Kinderpopulationen mit je μ Individuen und die Kinderpopulationen werden für γ Generationen isoliert. In jeder der γ Generationen generiert jede isolierte Population λ Nachkommen. Die Anpassung wird berechnet, und die μ angepasstesten der Nachkommen werden in die nächste Generation übernommen. Nach den γ isolierten Generationen werden μ' der besten λ' Populationen ausgewählt und erzeugen als nächste Elternpopulationen wieder λ' Kinderpopulationen. Wie 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. nichtlinearen 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.

Besonderheiten

Das besondere an den Evolutionsstrategien im Gegensatz zu anderen Evolutionären Algorithmen ist, dass sich der Algorithmus dynamisch anpassen kann. Die Schrittweite, also die Stärke, wie eine Mutation einen Wert verändert, kann dynamisch angepasst werden. Dies wird als Schrittweitenregelung bezeichnet.

1/5-Erfolgsregel

Die von I. Rechenberg ^[1] theoretisch abgeleitete 1/5-Erfolgsregel besagt, dass der Quotient aus den erfolgreichen Mutationen (also Mutationen, die eine Verbesserung der Anpassung 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.

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.

Varianten

• CMA-ES

Geschichte

Das Verfahren der Evolutionsstrategie wurde 1964 von Ingo Rechenberg entwickelt und 1965 publiziert (Royal Aircraft Establishment, Library Translation 1122, Farnborough). Später wurde es von vielen anderen, in besonderem Maße von Hans-Paul Schwefel, weiterentwickelt.

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 0-471-57148-2
• Hans-Georg Beyer: The Theory of Evolution Strategies: Berlin Heidelberg New York: Springer 1998, ISBN 3-540-67297-4
• Hannes Geyer et al., Vergleich zwischen klassischen und verschachtelten Evolutionsstrategien am Beispiel einer nichtlinearen Regression an Oberflächenspannungen in R², Interner Bericht CI-66/99 des Sonderforschungsbereichs 531: 'Design und Management komplexer technischer Prozesse und Systeme mit Methoden der Computational Intelligence', Dortmund 1999, https://eldorado.tu-dortmund.de/bitstream/2003/5371/1/ci66.pdf Download PDF]

Weblinks

• I. Rechenberg (TU Berlin): Evolutionsstrategie
• Evolutionsstrategie im Detail
• Informationen über Evolutionsstrategien

Fußnoten

1. ↑ Ingo Rechenberg, Evolutionsstrategie. Optimierung technischer Systeme nach Prinzipien der biologischen Evolution , Frommann Holzboog, 1973, ISBN 3-7728-0373-3 (Diss. von 1970), Kapitel 15