Information Technology Reference
In-Depth Information
Markierung
s
4
s
3
s
5
s
2
s
6
s
1
Abbildung 11.8: Stochastic Universal Sampling
parameter, wodurch die Fitnessunterschiede größer werden. Die Folge ist, dass im
Laufe der Generationen der Selektionsdruck steigt.
11.2.3 Erwartungswertmodell
Bei der Glücksradauswahl ist die Auswahl der Individuen zwar fitnessproportio-
nal, aber dennoch zufällig. Es gibt also keine Garantie, dass gute Individuen in die
nächste Generation kommen, nicht einmal für das beste Individuum. Allgemein gilt,
dass die Zahl der Nachkommen eines Individuums stark vom Erwartungswert ab-
weichen kann. D. h., dass es eine hohe Varianz der Nachkommenzahl gibt. Deshalb
bezeichnen wir dieses Phänomen auch als
Varianzprobl em
der Glücksradauswahl be-
zeichnet.
Eine sehr einfache, aber nicht unbedingt empfehlenswerte Lösung liegt in der
Diskretisierung des Fitnesswertebereichs: Zuerst werden der Mittelwert
µ
f
(
t
) und
die Standardabweichung
f
(
t
) der Population berechnet. Falls
µ
f
(
t
)
f
(
t
)
>
f
(
s
)
gibt es keinen Nachkommen von
s
in der Zwischenpopulation. Sollte
µ
f
(
t
)
f
(
t
)
f
(
s
)
µ
f
(
t
)+
f
(
t
)
, so kommt genau ein Nachkomme von
s
weiter. Wenn
f
(
s
)
>
µ
f
(
t
)+
f
(
t
)
, dann kommen zwei Nachkommen von
s
in die Zwischenpopulation.
Eine Lösungsmöglichkeit für das Varianzproblem ist das
Erwartungswertmodell
.
Hierbei erzeugt man für jeden Lösungskandidaten
f
rel
(
s
) ·|pop| Individuen. Ab-
schließend füllt man die freien Plätze in der Zwischenpopulation durch eine Glücks-
radauswahl auf.
Eine Alternative zum Erwartungswertmodell bietet das sogenannte
Stochastic
Universal Sampling
(siehe Abbildung 11.8). Hierbei läuft die Auswahl der Zwischen-
population wie folgt ab. Das Glücksrad wird einmal gedreht. Je Markierung wird
ein Chromosom gewählt. In Abbildung 11.8 wären dies 1
s
1
,1
s
2
,2
s
3
,2
s
5
.
Überdurchschnittlich gute Individuen kommen durch diese Methode sicher in die
Zwischenpopulation.
Es gibt viele Varianten des Erwartungswertmodells. Die Frage ist, wie man die
restlichen Individuen der (Zwischen-)Population erzeugt. Einige Verfahren, die un-
terschiedliche Antworten auf diese Frage geben, erwähnen wir hier kurz. Einerseits
können Verfahren, die aus der Wahlauswertung zur Verteilung der Mandate bzw.
