Information Technology Reference
In-Depth Information
als schlechtere Individuen. Dieses Prinzip entspricht der differentiellen Reproduk-
tion der Evolutionstheorie (siehe Abschnitt 10.1). Die Stärke der Bevorzugung gu-
ter Individuen nennt man
Selektionsdruck
.BeiderWahldesSelektionsdrucksgibtes
einen Gegensatz von
Erforschung des Suchraums
(engl.
exploration
)und
Ausbeutung
guter Individuen
(engl.
exploitation
). Soll der Suchraum erforscht werden, so sollten
die Individuen möglichst breit über den Suchraum gestreut sein, damit die Chancen,
dass das globale Optimum gefunden wird, möglichst groß sind. Demnach ist hier
ein geringer Selektionsdruck wünschenswert. Bei der Ausbeutung guter Individuen
sollte das (u. U. lokale) Optimum in der Nähe guter Individuen angestrebt werden.
Sie sollen zum Optimum hin konvergiert werden. Also wünscht man sich in solch
einer Situation einen hohen Selektionsdruck.
Demzufolge muss während der Evolution stets eine Wahl des Selektionsdrucks
getroffen werden. Die beste Strategie ist ein zeitabhängiger Selektionsdruck, wobei
man einen geringen Selektionsdruck in früheren Generationen bzw. einen höheren
Selektionsdruck in späteren Generationen benutzen sollte. Dies hat zur Folge, dass
der Suchraum zuerst gut erforscht wird und dann eine Ausbeutung der erfolgver-
sprechendsten Region erfolgt. Der Selektionsdruck wird über eine Skalierung der
Fitnessfunktion oder über Parameter des Selektionsverfahrens gesteuert. Im Folgen-
den behandeln wir deswegen einige wichtige Selektionsverfahren und Skalierungs-
methoden.
11.2.1 Fitnessproportionale Selektion
Die
Glücksradauswahl
(engl.
roulette wheel selection
)istdaswohlbekanntesteVerfah-
ren. Sie berechnet die relative Fitness der Individuen
f
abs
(
s
)
s
pop(
t
)
f
rel
(
s
)=
f
abs
(
s
)
und interpretiert sie als Auswahlwahrscheinlichkeit eines Individuums. Deswegen
heißt dieses Verfahren auch
fitnessproportionale Selektion
.WirerwähnenandieserStel-
le, dass die absolute Fitness
f
abs
(
s
) in diesem Fall nicht negativ sein darf. Gegebe-
nenfalls ist ein positiver Wert zu addieren oder negative Werte sind Null zu setzen.
Desweiteren muss die Fitness zumaximieren sein. Ansonsten würden schlechte Indi-
viduen mit hoher Wahrscheinlichkeit gewählt werden. Zur Veranschaulichung des
Verfahrens dient ein Glücksrad mit einem Sektor je Individuum
s
(siehe Abbildung
11.4a). Die Sektorgrößen entsprechen den relativen Fitnesswerten
f
rel
(
s
).
Hat ein Individuum eine sehr hohe Fitness, kann es die Auswahl
dominieren
.Dies
ist in Abbildung 11.4b verdeutlicht. In den Folgegenerationen wird diese Dominanz
noch verstärkt, da dann Kopien und sehr ähnliche Individuen vorliegen. Als Ergeb-
nis kommt es zum
Crowding
:DiePopulationbestehtausgleichenundsehrähnlichen
Individuen. Ein Crowding führt dazu, dass das (lokale) Optimum sehr schnell gefun-
den wird. Als größter Nachteil dieses Effekts ist die wohl schwindende Diversität der
Population zu sehen. Lediglich ein oder weniger gute Individuen können dann über-
haupt ausgebeutet werden. Somit findet keine Erforschung des Suchraums mehr
statt. Vielmehr handelt es sich beim Crowding um eine lokale Optimierung. Wie
bereits erwähnt ist dies in späten Generationen erwünscht. Am Anfang schadet es
der Evolution allerdings sehr.
