Evolutionärer Algorithmus
Ein Evolutionärer Algorithmus (EA) ist ein Optimierungsverfahren, das als Vorbild die biologische Evolution hat.Die Evolution ist ein sehr effizientes Optimierungsverfahren. Sie ist in der Lage, durch Manipulation des Erbgutes innerhalb kürzester Zeiträume selbst komplexe Lebensformen und Organismen an ihre Umwelt- und Lebensbedingungen anzupassen. Die erstaunlichste Eigenschaft der Evolution ist die relative Einfachheit ihrer Vorgehensweise und das Zusammenwirken der verschiedenen Steuerungsmechanismen. In einem einfachen Modell lässt sich der durchgeführte Suchprozess auf drei einfache Prinzipien zurückführen: Mutation, Selektion und Rekombination.
- Die Mutation des Erbgutes ist ein ungerichteter Prozess, dessen Sinn einzig in der Erzeugung von Alternativen und Varianten liegt. Aus Sicht der Optimierungstheorie kommt der Mutation die Aufgabe zu, lokale Optima zu überwinden. Sie sorgt dafür, dass die Population nicht frühzeitig in ein lokales Optimum konvergiert. Die Mutationswahrscheinlichkeiten pro Gen liegen im allgemeinen zwischen und .
- Die Rekombination (Crossover) der Erbinformation liegt hinsichtlich ihres Beitrages zur Zielfindung im Rahmen der Evolution zwischen Mutation und Selektion. Die Stellen, an denen ein Crossover zwischen homologen Chromosomen stattfindet, werden zufällig bestimmt. Die eigentliche Rekombination erfolgt aber nicht mehr zufällig. Nahe beieinanderliegende und funktional verbundene Gene werden seltener getrennt als weiter auseinanderliegende Gengruppen.
- Die Selektion ist für die eigentliche Steuerung der Suchrichtung der Evolution zuständig. Sie bestimmt die Richtung, in der sich das Erbgut verändert, indem sie festlegt, welche Phänotypen sich stärker vermehren. Die Selektion wäre demnach, wenn es keine Störungen gäbe, eine deterministische Komponente innerhalb der Evolution. In der Natur wird die Selektion jedoch immer wieder durch meist zufällige Ereignisse gestört. Auch die am besten an ihre Umgebung angepassten Individuen können durch ein Unglück sterben, bevor sie Nachkommen zeugen. Damit würde die genetische Information, die ein Optimum darstellt, verloren gehen. Zwei weitere Einflüsse machen die Selektion zu einem indeterministischen Faktor. Zum einen ist sie keine konstante Größe, da sich die Umwelt und die Lebensbedingungen der Individuen ändern können, zum anderen gibt es eine Rückkopplung zwischen den einzelnen Individuen und ihrer Umgebung. Diese können durch Eingriffe in die Umwelt ihre eigene Selektion beeinflussen.
- Sie bieten eine parallele Suche in einer Population von möglichen Lösungen, so daß immer mehrere potentielle Lösungen gefunden werden.
- Sie benötigen keine Gradienteninformation, können also auch bei nichtlinearen oder diskontinuierlichen Problemen angewendet werden.
- Sie gehören zur Klasse der stochastischen Suchverfahren, ermöglichen also auch die Behandlung komplizierter Probleme, die aufgrund eines zu hohen Rechenaufwandes mit traditionellen Optimierungsmethoden nicht mehr handhabbar sind.
- Evolutionäre Algorithmen bieten keine Garantie das globale Optimum zu finden.
- Evolutionäre Algorithmen sollten nicht zur Lösung von Problemen benutzt werde, für die es bereits traditionelle Optimierungsverfahren gibt, da diese in der Regel effizienter sind. So sind z.B. Newton-Raphson-Methoden, die Gradienten bei der Optimierung verwenden, bei der Suche lokaler Minima um ein vielfaches schneller und genauer als Evolutionäre Algorithmen.
- Genetische Programmierung
- Genetische Algorithmen
- Evolutionsstrategien
- Evolutionäre Programmierung
- Klassifizierungs-Systeme