Information Technology Reference
In-Depth Information
genügend breit zu durchsuchen. Um die Dominanz einer solchen Super-Verarbeitungs-
einheit zu verhindern, kann das
Ranking
zur Auswahl benutzt werden. Dabei werden die
Individuen nach ihrer Fitness sortiert. Die Auswahl erfolgt dann gemäß der Position in-
nerhalb dieser Liste, d. h. die Selektions-Wahrscheinlichkeit ist im einfachsten Fall eine
lineare Funktion der Rangfolge.
Eine wichtige Unterscheidung für die Reproduktion besteht darin, ob aus der ganzen
Population ausgewählt wird, oder nur aus der lokalen Umgebung einer Verarbeitungs-
einheit. Die Umgebung kann dabei zuerst einmal als räumliche Nähe gedacht werden,
d. h. jede Verarbeitungseinheit besitzt eine Position und sucht sich seinen Partner in der
Nähe aus. Durch diesen Mechanismus können sich lokal Subpopulationen mit besonderen
Eigenschaften ausprägen, was eine vorzeitige Konvergenz verhindern kann. Eine andere
Nachbarschaftsbeziehung kann darin bestehen, dass zwei Verarbeitungseinheiten zueinan-
der ähnlich sein müssen, damit sie miteinander gekreuzt werden können. Auch hierdurch
wird Diversivität länger aufrechterhalten. Diese Unterscheidung in lokale und globale Se-
lektion ist auch aus der Sicht der Implementierung von Bedeutung.
Auch bei den
Ersetzungsstrategien
gibt es vielfältige Variationen, die teilweise mit-
einander kombiniert werden können. Die klassische Methode für genetische Algorithmen
ist der
Generationenwechsel
: die alten Verarbeitungseinheiten in der Population werden
immer komplett durch die neuen Verarbeitungseinheiten ersetzt. Dabei können natürlich
neu erzeugte Verarbeitungseinheiten identisch zu alten sein. Es ist aber nicht garantiert,
dass die besten Verarbeitungseinheiten der Population beim Generationenwechsel er-
halten bleiben. Somit kann der Fitnesswert der jeweils besten Verarbeitungseinheit auch
wieder absinken. Um den Verlust der besten Verarbeitungseinheiten beim Generationen-
wechsel zu verhindern, kann mit einer sogenannten
Elite
gearbeitet werden. Die besten n
Verarbeitungseinheiten, wobei n ein einstellbarer Parameter ist, werden automatisch in die
nächste Generation übernommen. Somit wird garantiert, dass der Fitnesswert der jeweils
besten Verarbeitungseinheiten eine monoton steigende Funktion ist.
Eine Alternative zum Generationenwechsel bietet der
kontinuierliche genetische Algo-
rithmus
. Dieser besteht darin, für jede neu erzeugte Verarbeitungseinheit sofort zu über-
prüfen, ob sie in die Population aufzunehmen ist. Dies kann an Bedingungen geknüpft
sein, wie beispielsweise, wenn die neue Verarbeitungseinheit besser ist als mindestens
eine Verarbeitungseinheit in der Population oder wenn es nicht schon eine gleiche Ver-
arbeitungseinheit gibt. Freiheit besteht auch in der Auswahl der zu entfernenden Verarbei-
tungseinheit. So kann beispielsweise die Verarbeitungseinheit mit der geringsten Fitness
oder eine eher zufällige Verarbeitungseinheit gelöscht werden.
Die
Mutation
führt eine Änderung auf einem einzelnen Chromosom durch. Dabei wird
für jedes Gen ermittelt, ob gemäß der Mutationswahrscheinlichkeit eine Veränderung
durchgeführt werden soll. Wenn ja, dann erfolgt die Änderung gemäß der Mutationsvor-
schrift. Bei der traditionellen Bitstring-Kodierung ist die Mutation einfach ein Bitflip. Bei
vielen Anwendungen werden jedoch spezielle Mutationsoperatoren definiert, bei denen
Änderungen nicht an allen Positionen mit der gleichen Wahrscheinlichkeit durchgeführt
werden. Damit kann dem Wissen, das man über den Anwendungsbereich hat, Rechnung
