Information Technology Reference
In-Depth Information
sind dagegen für eine Parallelisierung weniger geeignet, da sie eine globale Betrach-
tung der Population erfordern.
13.3.1
Inselmodell und Migration
Auch wenn wir z. B. ein sehr schwer zu parallelisierendes Selektionsverfahren ver-
wenden wollen, kann eine Parallelisierung erreicht werden, indem man mehrere
unabhängige Populationen parallel berechnet. Jede Population wird als eine Insel
bewohnend angesehen, daher der Name
Inselmodell
. Das reine Inselmodell ist äqui-
valent zu einer mehrfachen seriellen Ausführung des gleichen EA. Es liefert meist
etwas schlechtere Ergebnisse als ein einzelner Lauf mit entsprechend größerer Popu-
lation. Zwischen den Inselpopulationen können zu festgelegten Zeitpunkten (nicht
in jeder Generation) Individuen ausgetauscht werden. Man spricht in diesem Fall
von Migration (Wanderung). Es findet normalerweise keine direkte Rekombination
von Chromosomen statt, die von verschiedenen Inseln stammen. Erst nach einer Mi-
gration wird genetische Information von einer Insel mit der einer anderen Insel kom-
biniert.
Zur
Steuerung der Migration zwischen Inseln
existierten ganz verschiedene Model-
le. Beim
Zufallsmodell
werden die beiden Inseln, zwischen denen Individuen ausge-
tauscht werden sollen, zufällig bestimmt. Beliebige Inseln können Individuen aus-
tauschen. Bei
Netzwerkmodell
werden die Inseln in einem Graphen angeordnet. In-
dividuen können zwischen den Inseln nur entlang der Kanten des Graphen wan-
dern. Die Kanten, über die Individuen ausgetauscht werden sollen, werden zufäl-
lig bestimmt. Existiert ein
Wettbewerb zwischen den Inseln
,dannunterscheidensich
die evolutionären Algorithmen, die auf den Inseln angewandt werden, in Verfah-
ren und/oder Parametern. Die Populationsgröße einer Insel wird entsprechend ih-
rer durchschnittlichen Fitness der Individuen erhöht oder erniedrigt. Es gibt jedoch
eine Mindestpopulationsgröße, die nicht unterschritten werden darf.
13.3.2 Zellulare evolutionäre Algorithmen
Diese Art der Parallelisierung nennt man auch
“isolation by distance”
.DieProzessoren
werden in einem (rechtwinkligen) Gitter angeordnet. Das Gitter bedeckt gewöhnlich
die Oberfläche eines Torus. Selektion und Crossover werden auf im Gitter benach-
barte (durch Kanten verbundene), Mutation auf einzelne Prozessoren beschränkt.
Z. B. verwaltet jeder Prozessor ein Chromosom. Bei der
Selektion
wählt ein Prozessor
das beste Chromosom seiner (vier) Nachbarprozessoren oder eines dieser Chromo-
somen zufällig nach ihrer Fitness. Der Prozessor führt
Crossover
mit dem gewählten
und dem eigenen Chromosom durch oder mutiert sein Chromosom. Er behält den
besseren der beiden Nachkommen bzw. von Elter und Kind. Es bilden sich Gruppen
benachbarter Prozessoren, die ähnliche Chromosomen verwalten. Dies mildert die
oft zerstörende Wirkung des Crossover.
13.3.3 Mühlenbeins Ansatz
Mühlenbeins Ansatz [Mühlenbein 1989] ist eine Kombination von EA mit Zufall-
saufstieg. Jedes Individuum führt hierbei einen lokalen Zufallsaufstieg durch, d. h.
