Information Technology Reference
In-Depth Information
In der Natur wird bei der
Rekombination
, die häufig auch Crossover genannt wird, das ge-
netische Material zweier Eltern kombiniert. Genauso liegt bei evolutionären Algorithmen
die Idee der Rekombination in der Kombination zweier Lösungen. Dabei lassen sich zwei
Hypothesen unterscheiden.
• Die
Building Block Hypothese
geht davon aus, dass sich gute Teil-Strings, die soge-
nannten Building Blocks, von verschiedenen Eltern durch Rekombination kombinieren
und im Laufe der Generationen vermehren. Diese guten Gene verteilen sich demnach
im Laufe der Generationen in der Population.
• Demgegenüber unterstellt der
Genetic Repair-Effekt
der Rekombination die Wirkung,
dass sich nicht die unterschiedlichen Merkmale an die Nachkommen vererben, sondern
die gemeinsamen. Die Nachkommen erhalten bei diesem Erklärungsmodell mit Sicher-
heit die Gene, die beide Eltern gemeinsam haben.
Der
Selektion
kommt als Gegenspieler der Variationsoperatoren Mutation und Rekom-
bination ein großer Stellenwert zu, da erst sie dem Optimierungsprozess eine Richtung
verleiht. Basierend auf ihrer Fitness wird ein Teil der Population ausgewählt, die übrigen
Lösungen werden verworfen. Die Selektion zur Paarung wählt die an der Rekombina-
tion beteiligten Lösungen aus. Währenddessen bestimmt die Überlebensselektion, welche
Lösungen überleben und in die nächste Generation übernommen werden. Diese durch
dieses Selektionsverfahren gewonnene, neue Generation von Lösungen wird dann wieder
selektiert usw. Dieser Kreislauf geht so lange weiter, bis eine der Stopp-Bedingungen er-
reicht ist. Dies ergibt folgendes Ablaufschema: Man beginnt mit einer häufig stochastisch
generierten Startmenge (Ausgangspopulation) von Lösungsalternativen (Individuen). Für
diese werden Fitnesswerte (Gütewerte) bestimmt. Es folgt ein iterativer Zyklus, indem
immer wieder aus den alten Lösungen neue, modifizierte Lösungsvorschläge erzeugt wer-
den. In diesem Generationszyklus werden Individuen aus der Population durch Selektion
zur Fortpflanzung bestimmt. Im Rahmen der Erzeugung von Nachkommen wird die in
den Eltern enthaltene Lösungsinformation kopiert (Replikation) und durch Anwendung
eines oder mehrerer Variationsoperatoren, wie z. B. Mutation oder Crossover, verändert.
Die sich ergebenden Nachkommen bewertet man und wählt dann aus, welche Individuen
in die neue Population übernommen werden (Selektion zum Überleben). Dabei können je
nach EA-Variante auch Eltern mit ihren Nachkommen ums Überleben konkurrieren. Das
Wechselspiel aus ungerichteter Veränderung von Lösungen durch die Variationsoperato-
ren und Bevorzugung der besten Lösungen im Selektionsprozess führt im Verlaufe vieler
Generationszyklen zu sukzessiv besseren Lösungsvorschlägen. Dieser Prozess wird so-
lange fortgesetzt, bis ein Abbruchkriterium greift.
Genetische Algorithmen
werden in Verbindung mit evolutionären Algorithmen ein-
gesetzt. Sie beschreiben eine sexuelle Fortpflanzung. Sexualität war in der biologischen
Evolution ein ganz entscheidender Schritt zur Beschleunigung der Entwicklung. Dieser
Algorithmus kombiniert statistisch die Eigenschaften verschiedener Wesen. Aus diesen
Ansätzen lassen sich die folgenden Merkmale ableiten:
