Evolutions Strategien (ES)


(Contents)(Previous)(Next)

Evolutions Strategien basieren zunächst hauptsächlich auf der Beobachtung, dass die Kinder den Eltern ähnlich sind und dass eine Art "Evolutionsfenster" existiert. Ist nämlich die Variation der Kinder zu gering, so ergibt sich nahezu keine Evolution, ist sie hingegen zu gross, so sind die Nachkommen mehrheitlich viel schlechter als die Eltern. Diese Beobachtung wird durch die Angabe einer Wahrscheinlichkeitsverteilung präzisiert und entsprechend implementiert. Dies erinnert stark an die Wahrscheinlichkeitsverteilung bei Simulated Annealing. Tatsächlich wurde bei ES zuerst mit einer Population von zwei Individuen (1 Elter, 1 Kind) und einem einfachen Mutation-Selektions Mechanismus (ohne geschlechtliche Fortpflanzung) gearbeitet. Dabei wurde bei der Selektion im Prinzip entschieden, ob Elter oder Kind überleben soll. Diese einfache ES Version unterscheidet sich kaum von SA.

In den heute üblichen Verallgemeinerungen wird mit einer Population von n Eltern gestartet. Anders als bei SA werden die Individuen nicht nur durch ihren Ort (Ortsvektor r) im Suchraum, sondern zusätzlich durch eine Störungsvektor s charakterisiert. Der Störungsvektor s definiert die Streuung (Variation) bei der Erzeugung von Nachfahren. Für diese gilt zunächst

width="136".

Dabei bezeichnet h einen Vektor, dessen Komponenten h standard Gauss'sche Zufallszahlen (in den Intervallen 0…salt) sind. Nun muss natürlich auch sneu definiert werden:

width="292".

Dabei bezeichnet h wieder standard Gauss'sche Zufallszahlen (im Intervall 0…1). Wichtig ist zu beachten, dass der Exponent eine Linearkombination von einem "globalen", richtungsunabhängigen Teil mit einem "individuellen", vektoriellen Teil ist. Die entsprechenden Gewichtsfaktoren tglobal und tind werden üblicherweise vom Benutzer definiert und haben einen beachtlichen Einfluss auf den Suchvorgang.

Offenbar ist (rneu,sneu) ein Kind von einem einzigen Elter (ralt,salt). Pro Elter lassen sich wegen der Zufallszahlen beliebig viele Kinder erzeugen. Es stellt sich nun natürlich die Frage, welche Eltern zur Fortpflanzung ausgewählt werden sollen (Selektion) und wie viele Kinder gezeugt werden sollen. Diese Frage kann sehr unterschiedlich beantwortet werden. Im wesentlichen ist jedoch klar, dass Eltern mit höherer Fitness mehr oder weniger strikt bevorzugt werden sollen.

Übungsaufgabe: Schlage unterschiedliche Selektionsalgorithmen vor und vergleiche diese.

Werden m Kinder gezeugt, so hat man zunächst eine Population von n+m Individuen. Will man die Populationsgrösse nicht wachsen lassen, so müssen nun m Individuen eliminiert werden. Ist m=n, so kann man einfach die n Eltern streichen und die Kinder zu Eltern der neuen Population machen. Für m>n muss man auch m-n Kinder streichen und für m<n muss man n-m Eltern überleben lassen. Da es passieren kann, dass alle Kinder weniger fit als die fittesten Eltern sind, ist es problematisch, Eltern zu streichen ohne deren Fitness zu berücksichtigen. Es macht daher Sinn, Eltern und Kinder nicht prinzipiell zu unterscheiden und von den n+m Individuen die m schlechtesten zu löschen. Eine derartige ES wird üblicherweise (n+m) ES genannt, die zuerst erwähnte Variante hingegen (n,m) ES. Die einfachste Variante ist ein (1+1) ES, welcher im wesentlichen einfachem SA entspricht.

Übungsaufgabe: Konkretisiere eine (1,1) ES und überlege die zu erwartenden Probleme.

Übungsaufgabe: Natürlich kann man auch bei der Selektion der zu löschenden Individuen mehr oder weniger strickt vorgehen und z.B. die schlechtesten Individuen nur mit höherer Wahrscheinlichkeit sterben lassen. Überlege die zu erwartenden Vor- und Nachteile.

Die bisher skizzierten ES basierten auf Kinder mit einem Elter, also im wesentlichen auf einer Evolution bei der nur Mutationen die Eigenschaften der Individuen verändern. Will man Kinder mit zwei oder mehreren Eltern zeugen, so müssen entsprechende Operatoren definiert werden.

Übungsaufgabe: Schlage verschiedene Varianten von Reproduktionsoperatoren mit zwei Eltern vor. Hinweis: man erinnere sich an die deterministischen Algorithmen, insbesondere jene mit Intervallunterteilung. Dabei ist sowohl rneu als auch sneu anzugeben. Überlege für einen einfachen, zweidimensionalen Suchraum, wo die Kinder je nach Operator zu liegen kommen. Welche Operatoren scheinen vielversprechend?


(Contents)(Previous)(Next)