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 Prozesses, 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.
Definition
Die Evolutionsstrategien umfassen einen Rubrik der Optimierungsalgorithmen in denen die biologischen 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 Elter nach dem Zufallsprinzip ausgewählt.
- Rekombination: Die Rekombination ist die Art nach der aus einem oder mehreren Elter 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 meisst geringfügige Veränderung des Nachkommens. Bei den Evolutionsstrategien wird meisst eine kleine Zahl auf den ausgewählten Teil addiert oder subtrahiert. Wie stark der mutierte Wert von dem Ursprungswert abweichen kann, wird duch 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.
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.
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.
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 wenigste fitte Individuum entfernt. Die verbliebenen bilden die neue Generation.
Hier umfasst jede Generation μ Individuen. Aus den μ Eltern werde λ Kinder generiert, mit λ μ. Die Fittnes von allen Kindern wird berechnet und die μ fittesten bilden die nächste Generation.
,
Hier umfasst jede Generation μ Individuen. Aus den μ Eltern werde λ Kinder generiert, mit λ μ. Die Eltern werden gelöscht. Die Fittnes von allen Kindern wird berechnet und die μ fittesten Individuen bilden die nächste Generation. Bei dieser Methode kann kein Individuum länger als eine Generation überleben.
, ,
Die μ' Elter werden λ' mal kopiert und die einzelnen Kopien werden fuer γ Generationen isoliert. In jeder der γ Generationen generiert jede isolierte Population λ Nachkommen. Die Fittness 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 als nächste Elterpopulation wieder λ' mal kopiert.
Besonderheiten
Das besondere an den Evolutionsstrategien im Gegensatz zu anderen Evolutionären Algorithemen 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. Nach Rechenberg sollte dies nach der ¹/₅ Erfolgsregel geschehen.
¹/₅ Erfolgsregel
Die ¹/₅ Erfolgsregel besagt, das der Quotient aus den erfolgreichen Mutationen (also Mutationen, die eine Verbesserung der Fittness bewirken) zu allen Mutationen sollte mindestens ¹/₅ betragen. 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 garantiert. Das Problem ist diese guten Werte zu finden. Rechenberg hat diese zentrale Schwierigkeit und mit dem Begriff Evolutionsfenster benannt. Das Evolutionsfenster bezeichnet den schmalen Grad 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 Evolutionsfensten treffen kann.
Beispiel
Beispiele für technische Verfahren, die Evolutionsstrategien enthalten sind genetische Algorithmen, allgemeine Problemlösungsstrategie.
Historie
Das Verfahren der Evolutionsstrategie wurde in der 60er Jahren von I. Rechenberg entwickelt und um 1973 publiziert. Später wurde es von vielen Anderen, besonders durch H.P. Schwefel in den 70er und 80er Jahren, weiterentwickelt. Es wurde eine Art Wettstreit mit den Entwicklern der Genetischen Algorithmen ausgetragen. Keiner wollte die andere Partei ernstnehmen. Erst langsam entwickeln sich kooperative Arbeiten.
Literatur
- Ingo Rechenberg, Evolutionsstrategie '94, Frommann Holzboog, 1994, ISBN 3772816428
- Hans-Paul Schwefel: "Evolution and Optimum Seeking": New York: Wiley & Sons 1995, ISBN 0471571482