mini|200px|Die Antenne der Space-Technology-5-Satelliten wurde mit einem EA entwickelt.

Evolutionäre Algorithmen (EA) sind eine Klasse von stochastischen, metaheuristischen Optimierungsverfahren, deren Funktionsweise von der Evolution natürlicher Lebewesen inspiriert ist. Sie bilden zusammen mit den künstlichen neuronalen Netzen und der Fuzzylogik die Grundlage der Computational Intelligence.

In Anlehnung an die Natur werden Lösungskandidaten für ein bestimmtes Problem künstlich evolviert, EAs sind also naturanaloge Optimierungsverfahren. Die Zuordnung zu den stochastischen und metaheuristischen Algorithmen bedeutet vor allem, dass EAs meist nicht die beste Lösung für ein Problem finden, aber bei Erfolg eine hinreichend gute, was in der Praxis vor allem bei NP-vollständigen Problemen bereits wünschenswert ist. Die Verfahren verschiedener EAs unterscheiden sich untereinander in erster Linie durch die genutzten Selektions-, Rekombinations- und Mutationsoperatoren, das Genotyp-Phänotyp-Mapping sowie die Problemrepräsentation.

Die ersten praktischen Implementierungen evolutionärer Algorithmen wurden Ende der 1950er Jahre veröffentlicht,Peter Bentley, David Corne: Creative Evolutionary Systems. Morgan Kaufmann, San Francisco, CA, 2001, S. 10. ISBN 978-1-55860-673-9 allerdings äußerten sich bereits in den vorhergehenden Jahrzehnten Wissenschaftler zum Potenzial der Evolution für maschinelles Lernen.David B. Fogel: Evolutionary Computation: Toward a New Philosophy of Machine Intelligence. Wiley, New York, S. 59, 2005. ISBN 978-0-471-66951-7

Es gibt vier Hauptströmungen, deren Konzepte zumindest historisch voneinander zu unterscheiden sind: genetische Algorithmen Evolutionsstrategien genetische Programmierung und evolutionäre Programmierung

Heute verschwimmen diese Abgrenzungen zunehmend. Für eine bestimmte Anwendung wird ein EA geeignet entworfen, wobei in den letzten Jahrzehnten viele verschiedene Algorithmen und einzelne Operatoren entwickelt wurden, die heute benutzt werden können.

Die Anwendungen von EAs gehen über Optimierung und Suche hinaus und finden sich auch in Kunst, Modellierung und Simulation, insbesondere auch bei der Untersuchung evolutionsbiologischer Fragestellungen.

Einführung Evolutionäre Algorithmen werden vorrangig zur Optimierung oder Suche eingesetzt. Konkrete Probleme, die mit EAs gelöst werden, sind äußerst divers, z. B.: die Entwicklung von Sensornetzen, Aktienmarktanalyse, RNA-Strukturvorhersage, Schedulingprobleme, Designoptimierung (siehe auch obiges Bild der Satellitenantenne) oder Roboterbahnplanung. Auch bei Problemen, über deren Beschaffenheit nur wenig Wissen vorliegt, können sie zufriedenstellende Lösungen finden. Dies ist auf die Eigenschaften ihres natürlichen Vorbildes zurückzuführen.

Natürliches Vorbild Evolutionärer Algorithmus Beispiel Organismus Lösungskandidat Autotür Fortpflanzungserfolg Wert der Fitnessfunktion Strömungswiderstand Natürliche Mutation Mutation Änderung der Form

In der biologischen Evolution sind die Gene von Organismen natürlich vorkommenden Mutationen ausgesetzt, wodurch genetische Variabilität entsteht. Mutationen können sich positiv, negativ oder gar nicht auf die Erben auswirken. Da es zwischen erfolgreichen Individuen zur Fortpflanzung (Rekombination) kommt, können sich Arten über mehrere Generationen an einen vorliegenden Selektionsdruck anpassen (z. B. Klimaveränderungen oder die Erschließung einer ökologischen Nische). Diese vereinfachte Vorstellung wird in der Informatik idealisiert und künstlich im Computer nachgebildet. Dabei wird die Güte eines Lösungskandidaten explizit mit einer Fitnessfunktion berechnet, sodass verschiedene Kandidaten vergleichbar sind.

Entsprechend dem natürlichen Vorbild gibt es bei den EAs Individuen, die aus einem Genom bestehen, welches die zu bestimmenden Eigenschaften der gesuchten Lösung in geeigneter Weise enthält. Ein Individuum entspricht einem Lösungskandidaten. Die durch die genetischen Operatoren erzeugten Individuen werden Nachkommen oder Kinder genannt. Eine Iteration des Verfahrens heißt entsprechend dem biologischen Vorbild Generation. Weitere Begriffsdefinitionen können in der VDI-Richtlinie VDI/VDE 3550 gefunden werden.

In der Praxis könnte z. B. die Form einer Autotür so optimiert werden, dass der aerodynamische Widerstand minimal wird. Die Eigenschaften einer potenziellen Lösung werden dabei im Rechner als Genom gespeichert. Häufige Problemrepräsentationen sind Genome aus binären oder reellen Zahlen oder eine Reihenfolge bekannter Elemente (bei kombinatorischen Problemen, z. B. Travelling Salesman).

Die starken Vereinfachungen, die im Vergleich zur Evolution getroffen werden, stellen ein Problem in Bezug auf die Erforschung evolutionsbiologischer Fragestellungen mit EAs dar. Ergebnisse können nicht einfach auf die komplexere Natur übertragen werden.

Pseudocode Das grobe Verfahren evolutionärer Algorithmen besteht meist aus einer Initialisierung und einer Generationsschleife, die solange durchlaufen wird, bis ein Abbruchkriterium erfüllt ist. Dazu nachfolgend ein Pseudocode, dessen Notation an die von Krasnogor angelehnt ist:

Pseudocode eines elitären EAs mit sexueller Reproduktion:

Initialisierung: ; // Initialisierung des Generationszählers Erzeuge eine zufällige Startpopulation ; Berechne die Fitness ; // initiale Bewertung while Abbruchkriterien sind nicht erfüllt do

Nachfolgegeneration: ; // erhöhe Generationszähler end while Ergebnis: Liefere bestes Individuum als Ergebnis ab; Bei der Initialisierung der Startpopulation werden die Individuen zufällig erzeugt, um eine möglichst breite Abdeckung des Suchraums und eine hohe genotypische Diversität zu erhalten. In Abweichung davon kann es aber auch zielführend sein, einen kleinen Teil (maximal 20 %) der initialen Individuen durch geeignete (Meta-)Heuristiken, eventuell basierend auf Lösungen ähnlicher Aufgaben, zu generieren.

Die Bestimmung von , Partnerwahl oder Elternselektion genannt, erfolgt bei den meisten EAs fitnessbasiert und gehört zusammen mit der Auswahl der Individuen zur Bildung der nächsten Generation zu den Selektionsmechanismen des Verfahrens, welche der evolutionären Suche die Richtung geben. Es gibt eine Vielzahl von Methoden zur Partnerwahl, darunter die einfache fitnessproportionale Selektion, die Turnierselektion und die häufiger verwendete rangbasierte Selektion.

Meist werden die Nachkommen durch Rekombination zweier Eltern aus mit anschließender Mutation erzeugt, was der geschlechtlichen Reproduktion im biologischen Vorbild entspricht. Die asexuelle Reproduktion würde einer Mutation von Elter-Klonen entsprechen. Durch mehrfache Ausführung dieser Operatoren können je nach Ausgestaltung des EAs auch mehr als nur zwei Nachkommen pro Paarung erzeugt werden.

Bei der Bewertung wird jedem Nachkommen entsprechend seiner Güte ein Wert der Fitnessfunktion zugewiesen. Die Fitness steuert die Reproduktionswahrscheinlichkeit der Individuen und kann zusammen mit der nachfolgend beschriebenen Selektion als die Umsetzung von Darwins „natürliche Auslese“ angesehen werden.

Die Nachfolgegeneration, also die Menge mit Individuen, wird fitnessbasiert entweder aus der Menge der Eltern in und der Nachkommen in (sogenannte Plus-Strategie) oder nur aus der Menge (Komma-Strategie) ausgewählt. Da bei der Plus-Strategie das beste Elternindividuum im Gegensatz zum biologischen Vorbild überleben kann, wird ein EA mit dieser Selektionsform auch als elitär bezeichnet. Auf die damit verbundene Problematik wird im Abschnitt Konvergenz eingegangen.

Als Abbruchkriterien werden häufig die Anzahl durchlaufener Generationen, die vergangene Zeit oder die erreichte Lösungsqualität herangezogen. Außerdem kann die Stagnation erfasst werden, z. B. in dem man die Generationen ohne Verbesserung des besten Nachkommen oder ohne Übernahme eines Nachkommen in die Nachfolgegeneration zählt.

Bestandteile Evolutionäre Algorithmen unterscheiden sich untereinander vor allem in der jeweiligen genetischen Repräsentation, der Fitnessfunktion und den genutzten genetischen Operatoren: Mutation, Rekombination und Selektion.

250px|mini|Die Rastrigin-Funktion ist eine multimodale Funktion, da sie viele lokale Extrema aufweist. Dies stellt einen Nachteil für den Rekombinationsoperator dar. Mutation und Rekombination sind die Suchoperatoren evolutionärer Algorithmen, mit denen der Suchraum erkundet wird. Ihre Anwendung auf Lösungskandidaten kann keine Verbesserung garantieren,Mitsuo Gen, Runwei Cheng: Genetic Algorithms and Engineering Optimization. Wiley, New York, 2000, S. 8. ISBN 978-0-471-31531-5. doi:10.1002/9780470172261 allerdings erhält der Suchprozess durch die Selektion eine Richtung, die bei erfolgreicher Konzeption zum globalen Optimum oder zumindest in dessen Nähe führt. Während mit dem Mutationsoperator völlig neue Bereiche des Suchraums erschlossen werden können, ermöglicht die Rekombination vor allem die Zusammenführung erfolgreicher Teillösungen oder Schemata bei den klassischen genetischen Algorithmen (Building-Block-Hypothese). Eine erfolgreiche Suche basiert also auf der Kombination beider Suchoperatoren. Der Erfolg eines Rekombinationsoperators hängt von der Beschaffenheit der Fitnesslandschaft ab. Je mehr lokale Optima die Fitnesslandschaft aufweist, desto wahrscheinlicher erzeugt die Rekombination aus zwei Individuen, die sich auf benachbarten lokalen Optima befinden, einen Nachfahren im Tal dazwischen. Mutationen sind von dieser Eigenschaft der Fitnesslandschaft nahezu unabhängig.William M. Spears: The Role of Mutation and Recombination in Evolutionary Algorithms. Springer, Berlin, Heidelberg, 2000, S. 225f. doi:10.1007/978-3-662-04199-4

Der Entwurf der verschiedenen Komponenten bestimmt, wie sich der evolutionäre Algorithmus bei der Optimierung des gegebenen Problems in Bezug auf Konvergenzverhalten, benötigte Rechenzeit und die Erschließung des ProblemraumsBill Worzel, Terence Soule, Rick Riolo: Genetic Programming Theory and Practice VI. Springer, Berlin, Heidelberg, 2009, S. 62. doi:10.1007/978-0-387-87623-8 verhält. Insbesondere müssen die genetischen Operatoren sorgfältig auf die zugrunde liegende Repräsentation abgestimmt sein, sodass sowohl die bekannten, guten Regionen des Problemraums genutzt, als auch die unbekannten Regionen erkundet werden können.Oscar Cordón, Francisco Herrera, Frank Hoffmann, Luis Magdalena: Genetic Fuzzy Systems: Evolutionary Tuning and Learning of Fuzzy Knowledge Bases. World Scientific Publishing, Singapore, 2002, S. 95. doi:10.1142/4177 Dabei spielen die Beziehungen zwischen Such- und Problemraum eine Rolle. Im einfachsten Fall entspricht der Suchraum dem Problemraum (direkte Problemrepräsentation).

Theoretische Grundlagen No-free-Lunch-Theorem

Das No-free-Lunch-Theorem der Optimierung besagt, dass alle Optimierungsstrategien gleich effektiv sind, wenn die Menge aller Optimierungsprobleme betrachtet wird. Unter der gleichen Voraussetzung ist auch kein evolutionärer Algorithmus grundsätzlich besser als ein anderer. Dies kann nur dann der Fall sein, wenn die Menge aller Probleme eingeschränkt wird. Genau das wird in der Praxis auch zwangsläufig getan. Ein EA muss also Problemwissen ausnutzen (z. B. durch die Wahl einer bestimmten Mutationsstärke). Werden also zwei EAs verglichen, dann wird diese Einschränkung impliziert. Darüber hinaus kann ein EA Problemwissen nutzen, indem z. B. ein Teil der Startpopulation nicht zufällig generiert wird, sondern einige Individuen durch Heuristiken oder andere Verfahren erzeugt werden. Eine weitere Möglichkeit besteht darin, geeignete Heuristiken, lokale Suchverfahren oder andere problembezogene Verfahren bei der Erzeugung der Nachkommen zu beteiligen. Diese Form der Erweiterung eines EAs ist auch als Memetischer Algorithmus bekannt. Beide Erweiterungen spielen bei praktischen Anwendungen eine große Rolle, da sie den Suchprozess beschleunigen und robuster machen können.

Konvergenz