Grundbegriffe
Um die Funktionsweise der evolutionären Algorithmen eindeutig zu beschreiben muss eine eindeutige Begrifflichkeit verwendet werden. In der Literatur werden oftmals verschiedene Begriffe für einen gemeinsamen Vorgang verwendet.
Crossover
Crossover ist eine Art der Rekombination, die oft beispielhaft für alle Arten der Rekombination genannt wird. Es werden Teile der beiden Eltern über Kreuz getauscht und daraus die Kinder erzeugt.
Im Kapitel Rekombination werden diese Vorgänge ausführlich erklärt.
Fitness
Als Fitness wird relativer Wert bezeichnet, wobei die besten Individuen einer Generation eine bessere Fitness besitzen als die schlechteren. Abhängig von diesem Wert findet eine Selektion für die nachfolgende Generation statt. Anschließend wird, basierend auf der Fitness, die Anzahl der jeweiligen Nachkommen fest gelegt.
Berechnet wird die Fitness für die Individuen durch eine Bewertungs- oder auch Objektfunktion. Die Rechenzeit für diese Objektfunktion ist ausschlaggebend für die Laufzeit des gesamten Programmes, da sie für jedes einzelne Individuum der gesamten Population aller Generationen berechnet werden muss.
Mutation
Die Mutation ist die zufällige Veränderung der Erbmasse. Im Computer findet diese zufällige Veränderung nicht wie in der Natur z.B. durch die natürliche Strahlung statt. Vergleichbar mit der Natur ändern sich zwar auch zufällig die Zustände in Speicherzellen oder bei der Datenübertragung, diese werden jedoch durch technische Vorkehrungen wie Prüfsummen erkannt und korrigiert.
Die Mutationsrate gibt die Geschwindigkeit in der Veränderung der Individuen an. Eine hohe Mutationsrate hat den Vorteil, dass sich die Population schnell einem Optimum annähert. Durch die ständig weitergehende Mutation bleibt jedoch ein größerer Abstand vom Optimum als bei einer kleineren Mutationsrate.
Auch die Natur hat Möglichkeiten, die Mutation sehr gering zu halten. Am Anfang der Evolution lag die Mutationsrate bei 10-2, im Laufe der Jahrtausende entwickelten sich jedoch andere Mechanismen bei der Vervielfältigung des Erbgutes. Hier liegen die Mutationsraten bei 10-6 und mit den Verbesserungen bei der Fehlerkorrektur sogar bei 10-8
Rekombination
Kombination von zwei Individuen. Dabei werden Teile der Elternindividuen zu einem neuen Kind zusammengesetzt. Der Unterschied zur Mutation besteht darin, dass sich die einzelnen Teile nicht ändern, sondern nur neu kombiniert werden. Eine Rekombination ist daher kein Evolutionsfaktor. Die neu entstandenen Individuen haben nur unterschiedliche Eigenschaften der Eltern geerbt.
Bei der Rekombination gibt es mehrere Methoden, die einzeln oder auch in Kombination angewendet werden.
Selektion
Auswahl der besten Individuen einer Generation, als Eltern für die nachfolgende Generation. Ein bedeutender Faktor für die Selektion der neuen Eltern ist die Fitness der einzelnen Individuen.
Individuum
Ein Individuum ist eine einzelne Lösung aus einer Gruppe von Lösungen.
Population
Die Population bezeichnet die Summe aller Lösungen (Individuen). Neben der Anzahl der Generationen bestimmt die Größe (Anzahl der Individuen) der Population die Rechenzeit maßgeblich mit.
Generation
Als Generation wird jeweils die gesamte Population eines Entwicklungsschrittes bezeichnet. Ausgehend von einer Startpopulation, der ersten Generation, werden neue Generationen berechnet und ersetzen die vorhergehende. Bei einigen Methoden bleiben dabei die besten Individuen erhalten, andere ersetzen die Elterngeneration vollständig durch neue Individuen, der Kindgeneration.
Um aus der Elterngeneration die Kindgeneration zu berechnen, wird zunächst die Fitness der einzelnen Individuen berechnet. Eine anschließende Selektion wählt die verbleibenden Eltern aus und deren Fitness bestimmt wiederum die Anzahl der Nachkommen mit.
Die Anzahl der Generationen ist oft eine Abbruchbedingung, um die Rechenzeit zu begrenzen.