Evolutionsalgorithmen (Evolutionäre Algorithmen)

Unter Evolutionsalgorithmen versteht man mathematische und algorithmische Modelle der Evolution. Es handelt sich dabei um Verfahren, mit deren Hilfe Such- und Optimierungsprobleme nach dem Vorbild der biologischen Evolution angegangen werden können. Sie beschreiben besonders für die Computersimulation und Anwendungen der Informatik geeignete Modelle der Evolution.

Evolutionsalgorithmen zählen zu den Meta-Heueristiken, einer Gruppe von Optimierungsverfahren, die nicht zwingend das globale Optimum einer Optimierungsaufgabe finden. Der Einsatz dieser Meta-Heueristiken ist allerdings erst bei „schwereren” Problemstellungen wie kombinatorischen Optimierungsproblemen sinnvoll. Sind beispielsweise bei kombinatorischen Optimierungsproblemen, wie dem Problem der Traveling Sales Person (TSP) nur einige wenige Städte ohne weitere Nebenbedingungen anzufahren, so lässt sich das Problem wunderbar und vor allem exakt mit dem Branch & Bound-Verfahren lösen. Anders sieht es aus, wenn sehr viele Städte bereist werden müssen. Exakte Verfahren, wie Branch & Bound müssen hier passen, da sie ein exponentielles Zeitverhalten haben. Eine Erhöhung der zu bereisenden Städte führt also zu einer exponentiellen Erhöhung des für die Lösung des Problems benötigten Zeitbedarfs.

Im Gegensatz dazu arbeiten Evolutionsalgorithmen mit einer Abbruchbedingung die besagt, dass eine bestimmte Anzahl von Verarbeitungsschritten berechnet werden sollen, nach denen die beste gefundene Lösung als Lösung fest steht oder aber mit einem zu erreichenden Zielwert für die Güte. Letzteres führt dazu, dass das Verfahren solange durchgeführt wird, bis eine Lösung gefunden wurde, die der Güteanforderung genügt. Auch Vorgaben, wie eine bestimmte maximale Laufzeit oder Kombinationen aus diesen Bedingungen, können genutzt werden.

Verarbeitungsschritte

allgemeiner Ablauf der Verarbeitung eines Evolutionsalgorithmus

Abbildung 1:

Allgemeiner Ablauf der Verarbeitung
eines Evolutionsalgorithmus

Die einzelnen Verarbeitungsschritte, die in Abbildung 1 dargestellt sind, laufen bei allen Evolutionsalgorithmen gleich oder zumindest sehr ähnlich ab. Eine Population stellt hier eine gewisse Anzahl von Individuen zusammen, die wiederum je eine mögliche Lösung des Optimierungsproblems darstellen. Dabei ist die Lösung in Form eines Variablensatzes im Individuum gespeichert.

Bei der Initialisierung der Population wird jedes Individuum zunächst initialisiert und dann anhand einer Bewertungsfunktion bewertet. Die Initialisierung kann hier mit zufällig erzeugten Werten, wie durch Starteinstellungen erfolgen, die durch ein anderes – beispielsweise Heueristisches – Optimierungsverfahren erzeugt wurden. Nachdem diese Schritte durchgeführt wurden, steht die Startpopulation fest, mit der nun der Optimierungsprozess beginnen kann.

Es folgt der so genannte Generationsschritt, in dem aus der aktuellen Generation n – nach Erzeugung der Startpopulation der Generation 0 – die Folgegeneration n+1 errechnet wird. Aus den Individuen der Population, die sich in der n-ten Generation befinden, werden nun nach einem bestimmten Eltern-Selektionsschema Individuen ausgewählt, die in diesem Generationsschritt als Elter-Individuen herangezogen werden und später Nachkommen erzeugen sollen. Als nächstes werden durch Rekombination oder Klonen Nachkommen – auch Kinder genannt – erzeugt, die mit einer gewissen Wahrscheinlichkeit mutiert werden. Bei einer Mutation werden Teile des Variablensatzes eines Individuums (meist geringfügig) verändert. Da die Variablensätze von Individuen, die durch Rekombination neu erzeugt oder durch Mutation modifiziert wurden, sich verändert haben müssen diese Individuen nun wiederum neu bewertet werden. Zum Schluss landen die Nachkommen und – je nach Selektionsverfahren – auch die Individuen der Ausgangspopulation des Generationsschritts in der Selektionsurne. Bei der Selektion werden dann aus den Individuen, die sich in der Selektionsurne befinden, jene Individuen gelöscht, die nicht in die Folgegeneration übernommen werden sollen. Welche Individuen dies sind, wird durch das Selektionsverfahren entschieden. Die Individuen, die sich nach der Selektion noch in der Selektionsurne befinden, werden in die Folgegeneration übernommen und bilden die Ausgangspopulation für den nächsten Generationsschritt.

Lernen von der Natur

In der Natur dienen die Mechanismen der Evolution der Anpassung von Individuen an ihre Umgebung. Je besser sich ein Individuum an seine Umgebung anpasst, desto größer ist die Wahrscheinlichkeit, dass es sich – sei es durch Flucht oder durch entsprechende Abwehrmaßnahmen – gegen Fressfeinde durchsetzt, dass es sich auch in schlechten Zeiten ausreichend mit Nahrungsmitteln versorgt oder dass es dafür sorgt, dass seine Erbinformationen weiter gegeben werden, etwa durch Vorteile bei der Brautwerbung.

Man könnte also sagen, dass die Evolution ein natürlicher Optimierungsprozess ist, der über Jahrmillionen seine Effizienz unter Beweis gestellt hat. Warum also sollte man nicht versuchen, aus diesen Mechanismen zu lernen und sie – natürlich auf die jeweilige Problemstellung und die anzuwendenden technischen Gegebenheiten angepasst – auf die uns beschäftigenden Optimierungsprobleme anzuwenden.

Geteiltes Leid ...

Evolutionsalgorithmen eignen sich besonders für die parallele Simulation auf massiv-parallelen Rechnern oder Clustersystemen. Durch das Aufteilen in einzelne Populationen kann die Verarbeitung auf mehrere Prozesse, die auf unterschiedlichen Prozessoren oder gar Rechnern laufen, verteilt und somit eine Beschleunigung des Verfahrens erreicht werden. Zudem bildet eine parallele Verarbeitung dieser Verfahren die tatsächliche biologische Evolution realistischer nach. In der Natur entwickelt sich jedes Individuum parallel zu seinen Artgenossen, wobei sich diese Individuen darüber hinaus auch gegenseitig beeinflussen.

Daneben können sich in der Natur auch Teil-Populationen einer Art, die keine direkten Berührungspunkte – beispielsweise angrenzende Reviere – besitzen, teilweise unterschiedlich entwickeln und ihre Erbinformationen dennoch durch Emigration langsam vermischen. Diese Emigrationsmechanismen erweitern den Gen-Pool der Teil-Populationen und führen zur Verbreitung neuer „Ideen”. Eine gewisse Varianz der Individuen ist auch wichtig für das Überleben einer Art. Die Vorteile von Individuen, die sich allzu sehr spezialisiert haben, können sich – durch rasche Änderung der Lebensbedingungen – sehr schnell relativieren oder sich gar negativ auswirken. Emigrationsprozesse dieser Art lassen sich auf verteilten Systemen mit Hilfe von Message-Passing-Systemen ebenfalls realisieren.

Bei den Verfahren der Evolutionsalgorithmen unterscheidet man im Wesentlichen zwischen zwei Modellen. Dies sind zum einen das Modell der Evolutionsstrategien und zum anderen das Modell der Genetischen Algorithmen.