Information Technology Reference
In-Depth Information
chend veränderte Funktion und überprüft, ob die Funktion dem Optimierungsziel näher
gekommen ist oder nicht. Ist sie dem Ziel näher gekommen, werden die neuen Parameter
übernommen, im anderen Fall werden sie verworfen. Dieser Kreislauf wiederholt sich so
lange, bis entweder das Optimierungsziel voll erreicht ist oder sich keine Verbesserungen
mehr ergeben. Für die Art und Weise, mit der man die Parameter variieren kann, gibt
es eine Reihe von verschiedenen, erprobten Verfahren, die im Rahmen des jeweiligen
Projektes evaluiert werden.
Evolutionäre Algorithmen
gehören zur Gruppe der rekursiven Algorithmen im All-
gemeinen und zu den stochastischen Such- bzw. Optimierungsmethoden im Speziellen.
Konzeptionell orientieren sie sich an den Mechanismen des natürlichen Evolutionsprozes-
ses. Sie zählen daher auch zu den naturanalogen Verfahren. Man unterscheidet darin vier
Hauptströmungen: Genetische Algorithmen, genetische Programmierung, Evolutionsstra-
tegien und evolutionäre Programmierung.
•
Genetische Algorithmen
verwenden häufig eine binäre Lösungspräsentation. Der we-
sentliche Selektionsschritt ist die Selektion zur Fortpflanzung. Diese erfolgt stochas-
tisch, so dass auch schlechten Individuen eine Chance zur Reproduktion gegeben wird.
Als Hauptsuchoperator dient das Crossover, während die Mutation nur mit geringer
Wahrscheinlichkeit aufritt.
•
Genetische Programmierung
, als ein weiterentwickelter Ansatz der genetischen Algo-
rithmen, greift die Problemstellung auf, inwieweit Computer lernen können, ein Prob-
lem zu lösen, ohne dafür explizit programmiert zu werden. Genetische Programmierung
erzeugt automatisch Problemlösungen, indem evolutionäre Operatoren auf passend re-
präsentierte Computerprogramme aus Klassen, Methoden, Variablen und Konstanten
angewendet werden. Dabei beginnt man mit stochastisch generierten Programmen.
• Bei der
Evolutionsstrategie
verwendet man im Allgemeinen einen Vektor reeller Zah-
len zur Lösungsrepräsentation. Der wesentliche Selektionsschritt ist die Selektion zum
Überleben. Sie erfolgt deterministisch, so dass nur die besten Individuen überleben.
Die Mutation auf Basis normalverteilter Zufallsgrößen ist als Suchoperator besonders
wichtig, doch spielt auch die Rekombination eine große Rolle.
•
Evolutionäre Programmierung
verwendet häufig einen Vektor reeller Zahlen zur Lö-
sungsdarstellung. Es wird jedoch mit einer stochastischen Form der Selektion gearbei-
tet und die Mutation bildet den einzigen Suchoperator.
Auf allgemeiner Ebene unterscheiden sich die evolutionären Algorithmen von konven-
tionellen Such- und Optimierungsverfahren zunächst durch die aus der Evolutionstheorie
entlehnte Terminologie (Tab.
2.2
):
Die Grundidee evolutionärer Algorithmen liegt nun in der Übersetzung der evolutio-
nären Variationsoperatoren Mutation und Rekombination sowie der Selektion in einen
Algorithmus. Den Rahmen des evolutionären Algorithmus bildet ein iterativer Prozess,
bei dem eine zufällige Variation der Lösungskandidaten eine entscheidende Rolle spielt.
Der erste Schritt ist die Erzeugung einer Reihe von verschiedenen potenziellen Lösun-
