Evolutionsstrategien

Die Entwicklung der Evolution resultiert aus den Überlegungen die biologischen Evolution auf nichtbiologische Probleme zu übertragen. Dabei haben sich zwei Modelle herausentwickelt, die sich für Computersimulationen und Anwendungen in der Informatik eignen. Die Evolutionsstrategien und die genetischen Algorithmen. Die Evolutionsstrategie, die im folgenden beschrieben werden soll, wurde in den sechziger Jahren von Ingo Rechenber an der TU Berlin entwickelt. Sie wurden später von ihm, sowie auch von anderen Forschern, insbesonders von Hans-Paul Schwefel, verbessert und erweitert. Am Anfang waren die Modelle noch sehr abstrakt und vernachlässigten viele Details der biologischen Evolution. Dies wurde später behoben, doch Rechenberg hielt eine naturgetreue Nachbildung der Evolution nicht für sinnvoll. Genauer schrieb er in seinem Buch: "Nun ist es falsch zu glauben, ein natürliches Vorbild müsse möglichst genau kopiert werden, um höchste Vollkommenheit in der technischen Ebene zu erreichen. (...) Das Verstehen des jeweiligen biologischen Vorganges kann ebenso wertvoll sein, wenn es darauf gelingt, ein idealisiertes Schema zu entwerfen, das die gleiche Wirkung hervorbringt." Es gibt demnach verschiedene Varianten der ES, die jeweils unterschiedliche Details der biologischen Evolution stärker berücksichtigen. Daraus resultiert jedoch auch ein Dilemma: Wie exakt muß oder sollte man die Evolution nachahmen; oder kann es sogar passieren, daß man sie überrepräsentiert. Diese Frage spaltete die Forscher dann auch in zwei Lager, auf der einen Seite die deutsche Schule um Rechenberg, die die biologische Evolution nur als Richtschnur zur Entwicklung von Optimierungsverfahren benutzt und auf der anderen Seite die amerikanische Schule der Verfechter der genetischen Algorithmen um Holland und Goldberg, die sich eher dafür interessieren, wie es der Evolution gelingt, Informationen zu codieren und zu verarbeiten und diese über die Generationen hinweg weiterzureichen. Leider arbeiten die beiden Schulen nicht zusammen, sondern gehen völlig getrennte Wege.

Rechenberg gelingt es mit nur 10 Symbolen auszukommen, um alle Vorgänge des Evolutionsmodells darzustellen. Um Individuen darzustellen, verwendet er Karten mit Punkten darauf, die die Gene darstellen. Mehrere Karten hintereinander stellen eine Population dar. Ein Kreis um die Karten herum stellt eine Urne für eine Auswahl dar. Ein Pfeil, der mit "w" markiert auf eine Urne zeigt, bedeutet eine zufällige Auswahl. Führt ein mit "Q" markierter Pfeil von der Urne weg, findet die Auswahl mit Hilfe einer Qualitätsfunktion statt. Zeigt ein mit "Q" markierter Pfeil auf eine Karte, so bedeutet dies eine Bewertung des Individuums. Die Umwandlung abstrakter Erbinformationen in ein Individuum ist durch eine Zickzacklinie angedeutet. Auf den nachfolgenden Phänotypen zeigt dann vielfach ein mit "Q" beschrifteter Pfeil, der andeutet, daß er nun bewertet werden kann. Symbol IV stellt eine einfache Duplikation eines Individuums dar. Einblitzartiger Pfeil, der auf ein Individuum zeigt stellt eine Mutation dar, Symbol VII schließlich eine Rekombination. Ist die Urne gekreuzt (Symbol X), so handelt es sich um eine isolierte Population.

Bei der Anwendung von Evolutionsstrategien geht es vielfach um eine Optimierung von Parametern. Die Erbinformation, die ein Individuum besitzt, wird deshalb als Vektor von reellen Zahlen dargestellt. Die komplizierte Genstruktur und Codierung der Chromosomen wurde also sehr vereinfacht. Für die frühen Evolutionsstrategen gab es daher nur zwei wesentliche Informationen: die Werte der zu optimierenden Parameter und die Werte der zu optimierenden Qualitätsfunktion.

(1+1)-Evolutionsstrategie

Das Modell (1+1) ist die einfachste Form der Evolutionsstrategie. Hier wird ein "UR-Individuum", ein Elter, dupliziert; dieser Nachkomme wird dann mutiert. Bei der darstellung als Vektor bedeutet dies, daß zu jeder Komponente des Vektors ein zufälliger kleiner positiver oder negativer Wert addiert wird. Elter und Kind kommen zusammen in eine Urne. Das Individuum, das den besseren Wert für die Qualitätsfunktion liefert, wird als neuer Elter ausgewählt. (Survival of the fittest) Dies wiederholt sich immerfort bis ein definiertes Abbruchkriterium erreicht ist. Darauf wird später noch genauer eingegangen. Dieses Modell läßt die sexuelle Rekombination außer acht. Trotz der Einfachheit findet man sinnvolle Anwendungen, Dank der Möglichkeiten der Schrittweitenregelung der Mutation.

Dieses Modell ist die Verallgemeinerung der (1+1)-Evolutionsstrategie. Man verwendet m Eltern, die l Kinder erzeugen. Dabei muß gelten: l ³ m ³ 1. Die Eltern, die die Kinder Erzeugen, werden zufällig mit gleicher Wahrscheinlichkeit ausgewählt. Von den m Eltern und l Kindern, die zusammen in die Urne geworfen werden, werden die m besten Individuen als neue Eltern herausgenommen. Die Qualität der besten Individuen wird so von Generation zu Generation nie schlechter.

Bei der (m+l)-Evolutionsstrategie überleben die m besten aus den Eltern und Kindern. Das hat zur Folge, daß Individuen mehrere Generationen hindurch überleben können, wenn ihre Qualitätsfunktion besser ist als die aller anderen. In gewissem maße ist das gewollt und es kommt in der Natur auch durchaus vor. Dies kann jedoch von Nachteil sein, z.B., wenn man sich mit einem solchen Individuum in einem lokalen Optimum befindet. Die Komma-Notation, 1975 von Schwefel eingeführt, behebt dieses Manko. Die m besten, die überleben, werden nur noch aus den l Nachkommen ausgewählt. Man kommt damit der biologischen Evolution näher; es gibt keine unsterblichen Individuen mehr; jedes Individuum lebt nur noch für die Dauer einer Generation. Auch wenn in der Realität einige Lebewesen mehrere Generationen überleben, so ist dieser Ansatz trotzdem plausibler als Unsterblichkeit.

Bislang wurde die sexuelle Rekombination außer Acht gelassen. Es wurde deshalb die (m/r#l)-Evolutionsstrategie eingeführt. "#" steht dabei für "+" oder ",". Das Erzeugen der Duplikate geht anders als bei der (m#l)-Evolutionsstrategie vonstatten. Die sexuelle Rekombination wird in diesem Modell zusätzlich auch noch gegenüber dem biologischen Vorbild verallgemeinert. Die Nachkommen können nämlich nicht nur von 2 Eltern (Mutter und Vater) erzeugt werden, sondern von r Eltern.

Es werden also r Vektoren rekombiniert um einen Nachkommen zu erzeugen. Dazu gibt es zwei Möglichkeiten:

1. Entsprechende Werte (an gleicher Position) der r Vektoren werden gemittelt. Der Vektor der gemittelten Werte wird dem Kind zugeordnet. Die Erbinformation eines jeden Elter geht also mit 1/ r ein.
2. Der Wert eines Elters geht komplett in den Nachkommen ein. D.h., daß für jede Position des Nachkommen-Vektors zufällig ein Elter ausgesucht wird, dessen Wer der entsprechenden Position übernommen wird.

Bei einer (5/3,7)-Evolutionsstrategie werden aus 5 Eltern E₁-E₅ 7 Mal zufällig 3 ausgewählt, die jeweils ein Kind erzeugen. Aus diesen 7 werden wieder 5 Eltern ausgesucht. Ein solcher Schritt sei im folgenden beschrieben.

Beispiel: E₁=[a₁,b₁,c₁], E₂=[a₂,b₂,b₂], E₃=[a₃,b₃,c₃], AW=[2,3,1] Þ K₁=[a₂,b₃,c₁]

Aus den 5 Eltern seien zufällig E₁, E₂ und E₃ ausgewählt worden. Im Auswahl-Vektor AW sei zufällig festgelegt, welcher Elter eine bestimmte Position des Kind-Vektors bestimmt. E₂ gibt hier seinen ersten Wert, E₃ den zweiten und E₁ den dritten. Jede dieser Auswahlen erfolgt per Zufall mit Gleichverteilung.

Das Verhalten der Evolution kann variiert werden. Ein Parameter, dessen man sich dazu bedienen kann, ist der Selektionsdruck. Er ist definiert durch den Quotienten s=m/l. Aus den l Kindern gehen m neue Eltern hervor. S liegt zwischen 0 und 1 und gibt an wie stark die Auslese ist. Je kleiner der Wert, desto stärker ist die Auslese.

Es lassen sich auch Populationswellen simulieren, indem man m systematisch oder zufallsgesteuert verändert. Soll der Selektionsdruck gleich bleiben, muß man nur m und l im gleichen Maße verändern. In der Natur kann der Selektionsdruck zum Beispiel durch das Vorhandensein von natürlichen Feinden verändert werden. Bei gleichbleibendem l (Nachwuchs) variiert m durch das Verändern von s. Bleibt der Feind aus (s groß), so ändert sich in erster Näherung das Populationswachstum, die Individuen vermehren sich. Biologisch interessant sind periodische und zyklische Variationen von s.

Ein weiterer Parameter ist die Mutationsschrittweite. Sie ist die Größe des Zahlenwertes, der bei der Mutation zu den Komponenten des Vektors hinzugezählt wird. Kleine Werte verändern in der Regel die Qualitätsfunktion nur wenig, große hingegen verändern sie stark und können eine Lösungsfindung sogar verhindern. Hier muß man also einen angemessenen Wertebereich finden.

Schließlich muß noch festgelegt werden, wie lange die Evolution simuliert werden muß. Es müssen also Abbruchkriterien definiert werden. Im großen und ganzen gibt es drei verschiedene solcher Kriterien:

1. Am einfachsten ist es, abzubrechen, wenn die Qualitätsfunktion eines Nachkommen hinreichend gut ist. Voraussetzung ist natürlich, daß man ein Optimum definieren kann. Zudem muß sichergestellt sein, daß man sich nicht in einem lokalen Optimum wiederfindet, da dieses oft nutzlos ist.
2. Wenn die Optimale Lösung nicht bekannt ist, verwendet man oft das Überschreiten einer gewissen Zeit als Abbruchkriterium.
3. Ein anderes, doch ähnliches, Kriterium stellt der Abbruch nach einer gewissen Anzahl erzeugter Generationen dar. Man gibt also sozusagen die Anzahl der Iterationsschritte vor.

Bei den beiden zuletzt genannten Kriterien besteht jedoch die Gefahr, daß man das Fingen der optimalen Lösung durch zu frühzeitigen Abbruch verhindert.