Evolutionsstrategien – oder kurz ES – stellen eine Variante der Evolutionsalgorithmen (Evolutionären Algorithmen) dar. Sie wurden in den sechziger Jahren von Ingo Rechenberg an der Technischen Universität Berlin begründet und später von ihm selbst und insbesondere von Hans-Paul Schwefel und anderen weiterentwickelt. Diese Weiterentwicklungen und Erweiterungen haben dazu geführt, dass es heute eine ganze Reihe unterschiedlicher Evolutionsstrategien gibt, die in sich geschlossen sind und teilweise aufeinander aufbauen.
Die verschiedenen Varianten bilden die tatsächlichen biologischen Gegebenheiten in unterschiedlichen Komplexitätsstufen der Imitation ab. Sie unterscheiden sich im Wesentlichen in der Art und Weise, wie Populationen und Individuen mutiert, rekombiniert, zusammengefasst und selektiert werden.
Dennoch wird der „Idealfall” einer naturgetreuen Abbildung der biologischen Evolution nicht erreicht, was auch von Rechenberg nicht beabsichtigt ist. Vielmehr verwendet er das natürliche Vorbild als Ansatz für ein idealisiertes Schema, welches zu denselben Ergebnissen führen soll. Rechenberg sieht die biologische Evolution eher als Richtlinie zur Entwicklung seiner Evolutionsstrategien. Die verschiedenen Varianten der Evolutionsstrategien werfen die Frage auf, inwieweit die Evolution im Modell simuliert werden soll und muss. Auf diese Frage gibt es allerdings keine allgemein gültige Antwort, da der Grad der Imitation stark vom jeweils vorliegenden Problem abhängt.
Aufgrund der Tatsache, dass Rechenberg als Ingenieur an der Lösung von Problemen der reellen Parameter-Optimierung interessiert war, wählte er eine in reellen Zahlen codierte Darstellung der Erbinformationen. Das bedeutet, dass die Chromosomen in Form von Vektoren von reellen Zahlen vorliegen und eine Population eine Menge dieser Vektoren darstellt. Evolutionsstrategen gehen, im Gegensatz zu den Verfechtern der Genetischen Algorithmen, demnach nicht auf die Genstruktur von natürlichen Individuen ein. Diese gleichzeitig kompakteste Form der Modellierung eines Individuums ist allerdings nicht immer die zweckmäßigste, denn auch die Codierung der Aufgabenstellung hängt von der jeweiligen Aufgabe ab, die durch eine Evolutionsstrategie gelöst werden soll. Das bedeutet, dass es keine Problemunabhängige und allgemeingültige Codierung gibt, die sich gleichermaßen für jede Problemstellung eignet.
Für die verschiedenen Varianten der Evolutionsstrategien entwickelte Rechenberg eine eigene Notation. Aus dieser Notation ist ersichtlich, auf welche Art und Weise der Evolutionsprozess vonstatten geht. Darüber hinaus schuf er einen Spielkartensatz der Evolutionsstrategien, mit dem sich Evolutionsstrategien visualisieren lassen. Es existieren dabei Symbole für Individuen, Populationen und solche für Evolutionsmechanismen wie Manipulation, Auswahl und Bewertung.
Die einzelnen Varianten der Evolutionsstrategien werden in den folgenden Abschnitten kurz beschrieben.
Die einfachste Variante der Evolutionsstrategien ist die (1 + 1) – Evolutionsstrategie. Durch die Selbstreproduktion eines einzelnen Individuums (einem Vektor von Parametern in Form von reellen Zahlen) wird zunächst ein identischer Nachkomme erzeugt. Als nächstes werden, durch Addition zufälliger positiver oder negativer Werte, die einzelnen Komponenten des Nachkommens verändert (mutiert). Jetzt kann der mutierte Nachkomme und das Ausgangsindividuum mit Hilfe der Qualitätsfunktion bewertet werden. Zum Schluss wird nach dem Prinzip „survival of the fittest” entschieden, welches der beiden Individuen zur Erzeugung weiterer Nachkommen verwendet wird. Das jeweils schlechtere Individuum wird gelöscht (selektiert). In dem Fall, dass beide Individuen den gleichen Qualitätswert haben, wird eines der beiden Individuen zufällig ausgewählt.
Diese einzelnen Schritte werden nun so lange wiederholt, bis eine ausreichend gute Lösung gefunden wurde. Ausreichend gute Lösung heißt hier, dass man für die Qualität einen Grenzwert festlegt, bei dessen Erreichen der Algorithmus stoppt. Dies wird vor allem bei Problemstellungen benötigt, bei denen man nicht weiß, ob es sich bei der jeweils gefundenen Lösung um das globale Optimum oder ein lokales Optimum handelt und es genügt, eine annähernd optimale Lösung zu finden.
Zudem können andere Abbruchkriterien eingeführt werden. So ist es beispielsweise denkbar, eine maximale Rechenzeit für die Simulation fest zu legen oder eine maximale Anzahl an Generationsschritten durchzuführen. Bei der Festlegung eines anderen Abbruchkriteriums, als eines zu erreichenden Qualitätswertes, besteht allerdings die Gefahr, dass das Finden einer optimalen Lösung durch frühzeitigen Abbruch verhindert wird.
Die hier beschriebene Evolutionsstrategie bearbeitet lediglich ein einziges Individuum (nur bis zur Selektion existieren kurzzeitig zwei Individuen) - es gibt keine Population - und verbessert dieses ausschließlich durch Mutationen.
Bei der (μ + λ) – Evolutionsstrategie handelt es sich um eine Verallgemeinerung der (1 + 1) – Evolutionsstrategie, die den seriellen Charakter der (1 + 1) – Evolutionsstrategie überwindet, indem nicht nur ein Individuum, sondern eine Population bearbeitet wird. Dabei ist μ die Anzahl der Elter-Individuen und λ die Anzahl der von diesen zu erzeugenden Nachkommen, wobei μ und λ ganze Zahlen und λ ≥ μ ≥ 1 sind.
Die Evolutionsschritte laufen prinzipiell genau so ab, wie bei der (1 + 1) – Evolutionsstrategie. Von den μ Eltern werden mit gleicher Wahrscheinlichkeit zufällig λ Eltern zur Erzeugung von λ Nachkommen ausgewählt. Dabei ist eine Mehrfachauswahl nicht nur möglich, sondern, für den Fall, dass μ < λ ist, auch nötig. Wie auch bei der (1 + 1) – Evolutionsstrategie werden die λ Nachkommen mutiert und gemeinsam mit den Eltern bewertet. Aus der Selektionsurne, in der gleichermaßen die Eltern wie auch die mutierten Nachkommen landen, werden die μ besten Individuen als Eltern der nächsten Generation ausgewählt.
Aus dieser Strategie resultiert – aufgrund der Tatsache, dass grundsätzlich die Eltern und Nachkommen zur Selektion herangezogen werden – dass die Qualität der Individuen einer Population von Generation zu Generation nie schlechter werden kann, wobei die Größe der Elternpopulation stets gleich bleibt.
Aufgrund der Tendenz von (μ + λ) – Evolutionsstrategien zu lokalen Optima, führte Hans-Paul Schwefel die Komma-Notation ein. Bei diesem Verfahren werden nur noch die λ Nachkommen zur Auswahl der μ Eltern der Folgegeneration herangezogen. Die Eltern der Vorgängergeneration werden grundsätzlich „vergessen”, wodurch die Evolution zumindest naturgetreuer nachgeahmt wird, da es im Gegensatz zur (μ + λ) – Evolutionsstrategie keine potenziell unsterblichen Individuen mehr gibt. Individuen leben somit nur noch genau eine Generation.
Die Gefahr der vorzeitigen Konvergenz zu einem lokalen Optimum führt oft dazu, dass das globale Optimum nicht gefunden wird, da durch Mutation keine weitere Verbesserung erreicht werden kann. Zudem ändert sich der Verlauf der Qualitätsfunktion. Mit der Qualitätsfunktion wird das Verhalten der Individuen einer Population über die Generationsschritte hinweg beschrieben. So kann man die Güte des besten Individuums über die Generationsschritte hinweg beobachten und als Qualitätsmaß auffassen. Während sich der Verlauf der Qualitätsfunktion bei der (μ + λ) – Evolutionsstrategie monoton (steigend oder fallend, je nach Optimierungsziel) verhält, verhält sich die Qualitätsfunktion der (μ , λ) – Evolutionsstrategie unter Umständen stark nach oben und nach unten schwankend. Dies liegt daran, dass die Individuen der Eltergeneration durchweg eine bessere Qualität haben können, als die der Nachkommen. Da die Eltern stets „vergessen” werden kann es so vorkommen, dass die Individuen der Folgegeneration durchweg schlechter sein können, als die der Vorgängergeneration, was zu Rückschritten im Optimierungsprozess führen kann.
Wie stark diese Schwankungen der Qualitätsfunktion ausfallen, hängt in der Regel von der Stärke der Mutation ab. Bei einer geringfügigen Mutation treten im Allgemeinen auch geringfügige Änderungen der Qualitätsfunktion auf. Geringfügige Mutationen führen deshalb auch bei Evolutionsstrategien zu besseren Ergebnissen.
Die (μ + λ) – und die (μ , λ) – Evolutionsstrategien werden, für den Fall, dass die Selektionsstrategie keine Rolle spielt, zur (μ # λ) – Evolutionsstrategie zusammengefasst, wobei '#' für '+' oder ',' steht.
Im Gegensatz zu den bisher beschriebenen Varianten nutzt diese Evolutionsstrategie die sexuelle Rekombination. Sie läuft im Prinzip genau so ab, wie die (μ # λ) – Evolutionsstrategien, mit der Ausnahme, dass anstelle des Clonens zur Erzeugung der Nachkommen eine Rekombination durchgeführt wird.
Zur Erzeugung eines Nachkommen werden jetzt nicht mehr ein Elter, sondern eine Gruppe, nämlich ρ Elter-Individuen, herangezogen, was bedeutet, dass für die zu erzeugenden λ Nachkommen λ mal ρ Elter rekombiniert werden. Die Elter-Individuen werden auch hier zufällig mit gleicher Wahrscheinlichkeit ausgewählt und dupliziert.
Um aus den Duplikaten der je ρ Elter-Individuen einen Nachkommen zu erzeugen macht man sich die Tatsache zu nutze, dass die Individuen in Form von Vektoren reeller Zahlen codiert sind. Die Evolutionsstrategen nutzen meist eine von zwei unterschiedlichen Rekombinationsstrategien, mit deren Hilfe aus den ρ Elter-Individuen ein Nachkomme erzeugt wird.
Die Erste rekombiniert die Duplikate der Elter-Individuen dadurch, dass der Nachkomme für die jeweiligen Vektorpositionen den Durchschnittswert der selben Vektorpositionen der Elter-Individuen verwendet.
Beispiel für ρ = 2 (zwei Eltervektoren):
Aus den Vektoren a = <7, 5, 2>
und b = <5, 9, 4> wird somit
c = <(7+5)/2, (5+9)/2, (2+4)/2> und somit c = <6, 7, 3>
Bei der zweiten Strategie werden die einzelnen reellen Zahlen der Duplikate der Elter-Vektoren gleicher Position zufällig untereinander vertauscht. Zum Schluss wird per Zufall einer der so entstandenen Nachkommen ausgewählt.
Beispiel für ρ = 2:
Die Vektoren a = <7, 5, 2> und b = <5, 9, 4> werden durch eine Vertauschungsmaske m = <1, 1, 0>, die in diesem Spezialfall mit ρ = 2 festlegt, ob eine Vertauschung der jeweiligen Position stattfindet (dabei bedeutet 0 es wird nicht vertauscht und 1 es wird vertauscht), zu c1 = <5, 9, 2> und c2 = <7, 5, 4> aus denen einer der Vektoren zufällig ausgewählt wird.
Nachdem ein Nachkomme durch die Rekombination erzeugt wurde, kann mit der Mutation und den weiteren Schritten der verwendeten (μ # λ) – Evolutionsstrategie fortgefahren werden.
Zwei wichtige Faktoren der Evolutionsstrategien sind der Selektionsdruck und Populationswellen. Mit Hilfe der (μ # λ) – Evolutionsstrategien lassen sich die Auswirkungen dieser Faktoren auf die Simulation auf einfache Weise untersuchen.
Unter dem Selektionsdruck versteht man den Quotienten s = (μ / λ). Damit kann der Selektionsdruck durch Variation der Werte von μ und λ beliebig zwischen den Extremwerten 0 (starker Selektionsdruck) und 1 (schwacher Selektionsdruck) eingestellt werden. Ist λ im Verhältnis zu μ groß, was bedeutet, dass wesentlich mehr Nachkommen erzeugt werden, als in die nächste Generation übernommen werden, so findet eine stärkere Auslese statt, der Selektionsdruck ist also groß.
Ähnlich wie der Selektionsdruck lassen sich auch Populationswellen simulieren. Unter Populationswellen versteht man die Veränderung der Individuenanzahl einer Population. Simulieren lassen sich diese mit (μ # λ) – Evolutionsstrategien, indem der Wert von μ systematisch oder zufällig geändert wird. Wenn bei dieser Simulation der Selektionsdruck konstant bleiben soll, so muss λ im gleichen Verhältnis geändert werden wie μ.
Nach den zuvor beschriebenen Varianten hat Rechenberg ein Modell entwickelt, welches besonders für die parallele Verarbeitung interessant ist. Er erweiterte seine Notation um die Evolution von Populationen durch das Einführen einer weiteren Klammerebene. Die Werte innerhalb der runden Klammern bezeichnen dabei weiterhin Individuen und die Werte außerhalb bezeichnen Populationen.
Eine [4,8(12,16)]-Evolutionsstrategie beispielsweise bezeichnet vier unabhängige Populationen, die „nach dem selben Schema wie zuvor auf Individuenebene” acht neue Populationen erzeugen. Diese Populationen mit je zwölf Individuen erzeugen wie bisher sechzehn Nachfolger, die nach der Komma-Variante behandelt werden. Jetzt werden diese acht Populationen in eine Urne geworfen und die besten vier Populationen überleben nach der Komma-Variante.
Es gibt nun mehrere Gesichtspunkte nach denen diese Populationsauswahl statt finden kann. Das Qualitätsmaß für Populationen könnte beispielsweise die durchschnittliche Qualität der in der Population enthaltenen Individuen sein. Man könnte aber auch die Qualität des besten Individuums der Population mit der Qualität der Population gleich setzen. Denkbar wäre auch, daß man die Varianz der Individuenqualitäten in die Bewertung einfließen lässt.
Das vorherige Beispiel lässt sich auch auf alle möglichen Kombinationen von ',' und '+'-Evolutionsstrategien anwenden. Gleiches gilt auch für die Varianten der sexuellen Rekombination, wobei das Mischungssymbol sowohl auf Individuen- als auch auf Populationsebene angewandt werden kann. Auf Individuenebene werden dann einzelne Variablen (Gene) rekombiniert, wohingegen auf Populationsebene ganze Individuen zwischen den Populationen ausgetauscht werden.
Durch eine solche Evolutionsstrategie ist somit eine Simulation des Genflusses zwischen unterschiedlichen Populationen möglich. Die Populationen entwickeln sich parallel und unabhängig voneinander und tauschen Individuen untereinander aus. Ob die Individuen dabei zufällig oder nach einem bestimmten Schema ausgetauscht werden, ist dabei eine Frage der Implementierung.
Die Evolutionsstrategie mit Populationen wurde zur Simulation isolierter Populationen zusätzlich erweitert. In der Notation macht sich dies durch eine hochgestellte Isolationszahl bemerkbar die besagt, wie lange (bei angenommenem Zeitmaß) oder wie viele Generationen sich die Populationen isoliert entwickeln sollen, bevor sie in die Auswahlurne müssen. Durch diese Vorgehensweise können die Populationen den Suchraum simultan in verschiedenen Regionen abklopfen.
Obgleich sich die Verschachtelung der beschriebenen Strategien beliebig weit fortsetzen kann, macht dies für die praktische Anwendung der Evolutionsstrategien wenig Sinn. Da eine weitere Verschachtelung bisher keine erkennbaren Vorteile gebracht haben, endet die Standard-Evolutionsstrategie bei der zweiten Stufe und lautet deshalb
[u/v # w (μ/ρ # λ)/n] – Evolutionsstrategie.
Zwar werden von Rechenberg Richtwerte für die einzelnen Parameter der Evolutionsstrategie vorgeschlagen, diese sind aber aufgrund der starken Problemabhängigkeit bei vielen Qualitätsfunktionen eher von Nachteil. Bei „gutartigen” Problemen wird für einfache, glatte Qualitätsfunktionen die (1#5) – Evolutionsstrategie vorgeschlagen. Eine gleichmäßige Konvergenz erreicht man zusammen mit der weiter unten beschriebenen mutativen Schrittweitenregelung, mit der (1#10) – Evolutionsstrategie. Eine hohe Zuverlässigkeit wird durch Einstellung des Selektionsdrucks im Bereich von 1/5 und 1/3 erreicht. Das optimale Mischungsverhältnis gibt Rechenberg mit ρ = μ an.
Die Mutation spielt bei den Evolutionsstrategien eine wichtige Rolle, da die Evolutionsstrategien auf der Verdoppelung der Individuen basiert. Durch die Mutation der Kopien entsteht ein neues Individuum mit einem modifizierten Variablensatz (Genen). Die Mutation erfolgt nach dem Prinzip der statistischen Normalverteilung, während die Selektion von sich fortpflanzenden Individuen und Populationen sowie deren Mischung und Rekombination nach der statistischen Gleichverteilung erfolgt. Dies bedeutet, dass die Elter-Selektion der Individuen unabhängig von der Fitness (Qualität) des jeweiligen Individuums ist.
In der Natur treten geringfügige Änderungen des Erbguts mit größerer Wahrscheinlichkeit auf als große. Wie schon erwähnt, werden mutierte Nachkommen durch das duplizieren von Ausgangsvektoren mit anschließender Addition eines Zufallsvektors erzeugt. Die Erzeugung von Nachkommen kann also wie folgt beschrieben werden:
xneu := xalt + N(0,σ)
N(0,σ) ist ein Vektor von unabhängigen Gauß-verteilten Zufallszahlen mit dem Mittelwert 0 und der Standardabweichung σ, wobei bei der Gauß`schen Glockenkurve Werte, die nahe am Mittelwert liegen, häufiger auftreten als Werte, die bei der positiven oder negativen Standardabweichung liegen. Dabei können für die einzelnen Vektorpositionen unterschiedliche Standardabweichungen vorliegen. Da die Zufallswerte von der negativen bis zur positiven Standardabweichung reichen, werden somit positive oder negative Zufallswerte addiert.
Diese Variante hat den Nachteil, dass die Standardabweichungen über alle Generationen konstant bleiben. Um nun möglichst schnell das Optimum zu erreichen ist es wünschenswert, dass die Schrittweite in Abhängigkeit von Erfolg oder Misserfolg der Mutationen angepasst werden kann. Während eine kleine Schrittweite meist zu einem langsamen Fortschreiten führt, führt eine große Schrittweite oft zu unkoordinierten und unnötigen Sprüngen im Suchraum.
Auf der Suche nach der optimalen Streuung der Zufallszahlen untersuchte Rechenberg zwei einfache Qualitätsfunktionen. Dies waren zum einen eine lineare (Korridor-Modell) und zum anderen eine quadratische (Sphären-Modell) Qualitätsfunktion. Diese Untersuchungen führten zur 1/5-Erfolgsregel.
Die 1/5-Erfolgsregel besagt, dass der Vektor der Standardabweichungen verändert werden muss, wenn der Quotient aus erfolgreichen zu allen Mutationen nicht 1/5 beträgt. Daraus ergibt sich folgender Ansatz:
σ(t+n) := c ⋅ σ(t) wenn p > 1/5, (die Streuung wird erhöht)
σ(t+n) := d ⋅ σ(t) wenn p < 1/5 (die Streuung wird verringert, da Mutationen seltener erfolgreich sind) und
σ(t+n) := σ(t) wenn p = 1/5 (Streuung wird beibehalten)
Es wird also nach n Generationen der Erfolg der eingestellten Standardabweichungen geprüft, wobei p die über n Generationen durchschnittliche Erfolgsquote der Mutationen ist. Die Konstanten wurden von Schwefel mit c = 1,22 und d = 0,82 angegeben.
Nachteilig an der 1/5-Erfolgsregel ist neben der Tatsache, dass sie nur als grobe Richtlinie anzusehen ist, ihr statischer Charakter. Sie ist nicht problemabhängig und kann zu einer frühzeitigen Konvergenz zu einem lokalen Optimum führen.
Aufgrund der Problemabhängigkeit der mutativen Schrittweitensteuerung, die im Prinzip für jedes Problem angepasst werden müsste, erweiterte Schwefel das von Rechenberg vorgegebene Modell dahin gehend, dass er die komponentenbezogenen Standardabweichungen selbst am Evolutionsprozess teilnehmen ließ. Er erweiterte damit den eigentlichen Problemvektor des Individuums um den Vektor der Standardabweichungen, der nun ebenfalls am Mutations- und Selektionsprozess teilnehmen sollte. Dadurch können sich die Standardabweichungen automatisch auf die Problemstellung einstellen.
Mit dieser Codierung sind nun die selben Rekombinationsverfahren, wie bei der (μ/ρ # λ) – Evolutionsstrategie auch unter Einbeziehung der Standardabweichungen, möglich.
Ein Individuum, beschrieben durch den Vektor <xalt, σalt> (Problem und Abweichungskomponente), kann nun nach dem folgenden Schema durchgeführt werden:
σneu := σalt ⋅ eN(0,Δ)
xneu := xalt + N(0,σneu)
Dabei bestimmt der frei wählbare Parameter Δ die Größe der Anpassung der Schrittweite, während die Verwendung der Exponentialfunktion negative Streuungen vermeidet und kleine Änderungen bevorzugt. Negative Zufallswerte sorgen dabei für eine Verkleinerung der Schrittweite, während positive für eine Vergrößerung sorgen.
Rechenberg hat einen ähnlichen Ansatz für die Mutation des Problemvektors x. Die Mutation soll demnach wie folgt ablaufen:
xneu := xalt + a ⋅ b ⋅ N(0,1/√n)
Der Faktor a ist konstant und stellt die eigentliche Schrittweite dar, wohingegen der Faktor b deterministisch oder zufällig gewählt wird. Bei jedem Individuum muss nun entschieden werden, ob b größer oder kleiner wird. Zur Justierung von b schlug Rechenberg einen Faktor von 1,5 vor, was für die Bestimmung von b für jedes Individuum zu folgenden Fällen führt:
bneu := balt ⋅ 1,5 oder
bneu := balt ⋅ 1 / 1,5
Neben der zufälligen Bestimmung besteht die Möglichkeit, dass eine Hälfte der Population eine größere, die andere Hälfte hingegen eine kleinere Schrittweite erhält.
Die Mutation in Verbindung mit der automatischen Schrittweitenanpassung sind zugleich der Fortschrittsmotor, wie auch der Hemmschuh der Evolutionsstrategien. Setzt man die falsche Mutationsstrategie, sowie eine unpassende Schrittweitenanpassung ein, so sind die Bemühungen zum Scheitern verurteilt, da es keine Richtlinie für das weitere Vorgehen gibt und die Optimierung damit nicht zielgerichtet ist.
¬ News
15.08.2008Schleifen in PHP: Die While-Schleife » mehr 13.08.2008Nutzung von Variablen unter PHP: Definition, Sichtbarkeit und vordefinierte Variablen » mehr 11.08.2008Ausgabe von Datum und Zeit mit PHP nach Konvertierung in ein String » mehr Eine vollständige News-Liste ist auf der News-Seite zugänglich.
Internetseite erstellen •
Homepage-Marketing •
Homepage Service