Information Technology Reference
In-Depth Information
f
f
f
v
0.2
v
0.1
v
0.05
Abbildung 11.7: Illustration des Variationskoeffizienten. Bei zu hohem Variationsko-
effizienten kommt es zu vorzeitiger Konvergenz, bei zu niedrigem zu verschwinden-
dem Selektionsdruck.
v
0.1 ist erfahrungsgemäß ein guter Wert.
Empirisch wurde festgestellt, dass ein Variationskoeffizient
v
0.1 ein gutes Ver-
hältnis von Erforschung und Ausbeutung liefert. Weicht
v
von diesem Wert ab, so
sollte man versuchen, diesen Wert durch Anpassung der Fitnessfunktion
f
zu errei-
chen (z. B. durch Skalierung oder Exponentiation). Für die praktische Berechnung
von
v
ersetzen wir den Lösungsraum durch die aktuelle Population pop
(
t
)
,da
v
nicht berechen-, sondern nur schätzbar ist. Wir berechnen und adaptieren dann in
jeder Generation sowohl den Wert von
v
(
t
)
als auch die Fitnesswerte entsprechend.
Für die
-Skalierung gilt
=
1
/
v
wobei
v
=
0.1. Unterschiedliche Anpassungen
der Fitnessfunktion anhand von
v
sind in Abbildung 11.7 dargestellt.
Eine weitere Möglichkeit, die Fitnessfunktion anzupassen, besteht in der Einfüh-
rung einer
Zeitabhängigkeit
.DafürbestimmenwirdierelativeFitnessnichtdirektaus
der zu optimierenden Funktion
f
(
s
),sondernaus
g
(
s
) (
f
(
s
))
k
(
t
)
.Derzeitabhän-
gige Exponent
k
(
t
)
steuert den Selektionsdruck. Laut Michalewicz [1996] kann man
k
(
t
)
durch ein Verfahren bestimmen, das berücksichtigt, dass sich der Variationsko-
effizient
v
in der Nähe von
v
0.1 halten soll:
2
(
v
)
1
v
v
t
T
+
1
·
2
k
(
t
)=
tan
wobei
v
,
1
,
2
,
Parameter des Verfahrens sind,
v
der Variationskoeffizient (z. B.
aus der Anfangspopulation geschätzt),
T
die maximale Anzahl zu berechnender
Generationen,
t
der aktuelle Zeitschritt (laufende Nummer der Generation) sind.
Wir empfehlen für dieses Verfahren folgende Belegung der Parameter:
v
=
0.1,
1
=
0.05,
2
=
0.1,
=
0.1.
Die
Boltzmann-Selektion
stellt eine andere zeitabhängige Fitnessfunktion dar. Sie
bestimmt die relative Fitness nicht direkt aus der zu optimierenden Funktion
f
(
s
)
,
sondern aus
g
(
s
) exp
f
(
s
)
kT
.DerzeitabhängigeTemperaturparameter
T
steu-
ert den Selektionsdruck.
k
ist eine Normierungskonstante, die an die Boltzmann-
Konstante erinnert. Die Temperatur kann z. B. linear bis zu einer vorher festgeleg-
ten Maximalzahl an Generationen abnehmen. Die Idee dieses Auswahlverfahrens
ähnelt der des simulierten Ausglühens (siehe Abschnitt 12.2.2): In frühen Genera-
tionen ist der Temperaturparameter hoch, die relativen Unterschiede zwischen den
Fitnesswerten daher gering. In späteren Generationen senkt man den Temperatur-