Information Technology Reference
In-Depth Information
Eine Funktion f auf einem metrischen Raum heißt nun „kontraktiv“, wenn für jeweils zwei
Elemente x und y gilt:
d(f(x), f(y)) < d(x,y) und d(f
n
(x), f
n
(y)) < d(f
n-1
(x), f
n-1
(y)) (3.3)
für n-fach iterierte Anwendungen von f auf x und y. Eine kontraktive Funktion zieht also die
Elemente des metrischen Raumes gewissermaßen zusammen.
Das von dem polnischen Mathematiker Banach formulierte
Fixpunkttheorem
besagt, dass eine
kontraktive Funktion immer einen Konvergenzpunkt hat. Man kann jetzt zeigen, dass der Algo-
rithmus bestimmter GA sich unter speziellen Bedingungen als eine kontraktive Funktion dar-
stellen lässt, wenn man als Distanz d zwischen den Elementen die Differenz zwischen deren
Bewertungen durch die Bewertungsfunktion nimmt. Dann folgt die Existenz eines Konver-
genzpunktes, d. h. eines (Sub)Optimums, direkt aus dem Satz von Banach. Der Beweis gilt so
allerdings nur für bestimmte GA, für die eine spezielle Metrik definiert wurde. Diese hat fol-
gende Form:
Sei P = (x
1
,...,x
n
) die zu optimierende Population und Eval(P) die Bewertungsfunktion für den
GA, die definiert wird als
Eval(P) =
1
/
n
¦eval(x
i
),
(3.4)
d. h. als der arithmetische Durchschnitt der Bewertungen der „Individuen“. Dann lässt sich die
Distanz d zwischen zwei Populationen P
1
und P
2
definieren als
-
0 falls P
1
P
2
und
1 M Eval P
1
1 M Eval P
2
sonst
°
°
dP
1
,P
2
(3.5)
.
Hierbei ist M die obere Grenze der eval(x)-Funktion für den jeweiligen Wertebereich, also
eval(x) d M für alle x P
(3.6)
und demnach
Eval(P) d M
(3.7)
für alle Populationen P.
Man kann jetzt ohne Schwierigkeiten zeigen, dass d in der Tat eine Metrik definiert, also die
obigen drei Axiome erfüllt. Als kontraktive Funktion werden die Durchläufe des GA definiert,
allerdings mit der Maßgabe, dass nur die Durchläufe berücksichtigt werden, die eine Verbesse-
rung gegenüber den bisherigen Durchläufen erbringen. Durchläufe, die keine Verbesserung
ergeben, werden sozusagen aus der Betrachtung herausgenommen.
Da der oben definierte metrische Raum vollständig ist (was das genau ist, ist hier nicht wesent-
lich), sind die Bedingungen des Banachschen Fixpunktsatzes erfüllt und es folgt für diese Mo-
difikation des Standard-GA dessen Konvergenz. Allerdings gilt dieser Beweis offensichtlich
nur für die Fälle, bei denen tatsächlich eine schrittweise Verbesserung der Populationen erfolgt.
Da dies durchaus nicht immer gesichert ist, bringt der Beweis zwar grundsätzliche Einsichten
in Konvergenzeigenschaften von GA, hat jedoch nur bedingten praktischen Wert. Außerdem
ist die Definition von Eval(P) als Durchschnitt der individuellen Bewertungen auch längst nicht
in allen Fällen sinnvoll; beim ersten Beispiel oben ging es ja um die Addition der 1-Kompo-
nenten.
Insbesondere wird bei diesem speziellen Beweis offensichtlich vorausgesetzt, dass neben der
Bewertung der Populationen, also normalerweise der jeweiligen Vektoren, auch die einzelnen
Search WWH ::
Custom Search