Information Technology Reference
In-Depth Information
gelangt. Auch wenn das beste Individuum in die Zwischenpopulation gewählt wur-
de, ist es nicht vor Veränderungen durch genetische Operatoren geschützt. Dies gilt
natürlich auch für das Erwartungswertmodell. Folglich kann die Fitness des besten
Individuums von einer Generation zur nächsten auch wieder abnehmen, was ge-
nerell unerwünscht ist. Eine Lösung dieses Problems stellt der Elitismus dar. Wir
übernehmen dafür einfach das beste Individuum (oder die
k
,1
k
<
|pop|,besten
Individuen) unverändert in die nächste Generation. Somit bleibt die Elite einer Po-
pulation erhalten, was dem Verfahren auch seinen Namen gibt. Man muss beachten,
dass die Elite nicht von der normalen Auswahl ausgenommen wird, da sie ja auch
noch durch genetische Operatoren verbessert werden kann.
Beim Elitismus ersetzen Nachkommen (lies Produkte aus Mutation bzw. Crosso-
ver) meistens ihre Eltern. Eine abgewandelte Form ist der
lokale Elitismus
,beidem
es einen Elitismus zwischen Eltern und ihren Nachkommen gibt. Das bedeutet bei
der Mutation, dass ein mutiertes Individuum seinen Elter nur dann ersetzt, wenn es
eine mindestens ebenso gute Fitness besitzt. Beim Crossover hingegen werden die
vier am Crossover beteiligten Individuen (zwei Eltern und zwei Nachkommen) ab-
steigend nach ihren Fitnesswerten sortiert. Die beiden besten Individuen werden in
die nächste Generation übernommen. Der Elitismus bietet den großen Vorteil, bes-
sere Konvergenzeigenschaften zu besitzen, da das lokale Optimum konsequenter
angestrebt wird. Ein Nachteil bildet die relativ große Gefahr des Hängenbleibens in
lokalen Optima, da keine (lokalen) Verschlechterungen möglich sind.
11.2.7 Nischentechniken
Das Ziel von Nischentechniken ist ein explizites Vermeiden des Crowding, das wir
im Abschnitt 11.2.1 besprochen haben. Das
deterministische Crowding
ist eine solche
Nischentechnik. Hierbei ist die Idee, dass erzeugte Nachkommen stets die ihnen ähn-
lichsten Individuen der Population ersetzen. Dies hat zur Folge, dass der Suchraum
lokal weniger dicht besetzt wird. Allerdings benötigen wir somit ein Ähnlichkeits-
oder Abstandsmaß für die Individuen, was für bestimmte nicht trivial zu sein
scheint. Bei binärkodierten Chromosomen kann man z. B. den Hamming-Abstand
verwenden. Eine Variante dieser Nischentechnik ist folgender Ansatz: Beim Crosso-
ver werden zwei Paare von Individuen aus je einem Elter und einem Nachkommen
gebildet, wobei ein Nachkomme dem ihm ähnlichsten Elter zugeordnet wird. Aus
jedem Paar wird das bessere Individuum übernommen. Diese Variante bietet den
Vorteil, dass deutlich weniger Vergleiche zwischen Individuen nötig sind, da nicht
die ganze Population betrachtet wird.
Eine weitere Nischentechnik ist das sogenannte
Sharing
.DieGrundideedesSha-
ring ist, die Fitness eines Individuums dann zu reduzieren, wenn sich in seiner Nach-
barschaft noch weitere Individuen befinden. Anschaulich teilen sich die Individuen
die Ressourcen (hier in Form der Fitness) einer Nische. Auch hier benötigt man ein
Ähnlichkeits- oder Abstandsmaß für die Individuen. Eine Beispielfunktion für das
Sharing ist
f
(
s
)
s
pop(
t
)
g
(
d
(
s
,
s
))
f
share
(
s
)=
