Information Technology Reference
In-Depth Information
elitistischer Versionen bei GA und ES, auch wenn die Topologie natürlich nicht garantiert (und
auch nicht garantieren soll), dass die jeweils beste Lösung erhalten bleibt. Die Ähnlichkeit
jedoch, mit der sich diese beiden verschiedenen Verfahren auf das Verhalten der Optimie-
rungsalgorithmen auswirken, ist auffallend.
Ebenso wie die Einführung elitistischer Versionen garantiert die Topologie bei bestimmten
Problemklassen zusätzlich, dass relativ rasch günstige Werte erreicht und dann nicht mehr
verlassen werden. Dies kann man sich anhand des erwähnten biologischen Begriffs der Fitness-
Landschaft klar machen, bei der Berggipfel Optima darstellen und die Täler Minima. Wenn
diese Landschaft nicht zu sehr „zerklüftet“ ist, also die jeweiligen Optima nicht zu sehr ver-
schieden sind, dann besteht ein hinreichend gutes Konvergenzverhalten schon darin, eines der
lokalen Optima zu erreichen, da dies meistens den jeweiligen Problemanforderungen genügt.
Durch elitistische Versionen sowie eine entsprechende Topologie beim SA wird garantiert,
dass ein derartiges Optimum praktisch immer erreicht werden kann.
18
Die „topologielose“ Version des SA dagegen hatte in dem obigen Sinne keine Steuerung, son-
dern durch die reine Zufallsgenerierung der neuen Lösungen musste sie praktisch immer wie-
der von vorne anfangen. Dies erklärt sowohl die geringe Glätte der Optimierungskurve in den
längeren anfänglichen Phasen als auch das niedrige Optimierungsniveau: Da im Verlauf des
Abkühlungsprozesses die Wahrscheinlichkeit für die Selektion schlechterer Lösungen immer
geringer wurde, musste das SA sich auf den niedrigen Optimierungswerten stabilisieren, die es
bis dahin erreicht hatte. Es hatte gewissermaßen nicht genügend Zeit, bessere Werte zu errei-
chen, bevor nur noch die guten Lösungen selektiert wurden. Damit konnten jedoch ungünstige
lokale Optima nicht mehr verlassen werden. Wir hatten schon darauf verwiesen, dass ein
Grund für das schlechte Abschneiden der ersten SA-Version in einem zu schnellen Abküh-
lungsprozess liegen könnte. Bei den topologischen Versionen des SA dagegen konnte immer
auf dem schon Erreichten aufgebaut werden, so dass auch der Abkühlungsprozess sich nicht
mehr negativ auswirkte: Die günstigen Optima waren schon erreicht, als die Temperatur auf
ein Minimum gesenkt wurde.
Wir haben nun in 3.5 gezeigt, dass die Annahme einer stetigen Funktion z. B. bei biologischen
oder sozialen Problemen durchaus nicht erfüllt sein muss, sondern dass es „Lücken“ in der
Abbildung geben kann, also Fälle, bei denen räumliche Nähe im Lösungsraum keine Nähe im
Bewertungsraum bedeutet. Das ist auch sicher der Fall bei dem Problem, auf das die verschie-
denen Optimierungsalgorithmen angewandt wurden; wir haben es demnach hier mit nur „lokal
stetigen“ und nicht „global stetigen“ Abbildungen zu tun. Derartige „Lücken“ nennt man „Un-
stetigkeitsstellen“ oder auch „Singularitäten“. Dennoch wirkte sich die Topologie in der darge-
stellten Weise positiv aus. Dies ist nur dadurch zu erklären, dass die Anzahl der Singularitäten
in beiden Topologieversionen nicht sehr hoch sein kann.
M.a.W., die Wahrscheinlichkeit ist in beiden Fällen ziemlich hoch, dass bei einer anfänglich
generierten Lösung die jeweils neue benachbarte Lösung auch einen ähnlichen Wert bei der
Bewertungsfunktion hat. Ist dies der Fall, dann wirkt sich die Topologie hier ebenfalls in der
erläuterten Weise positiv aus; einzelne Singularitäten stören zwar das Konvergenzverhalten
kurzfristig, werden jedoch in ihrer negativen Wirkung sofort wieder aufgefangen, wenn die
nächsten Lösungen in der Bewertung wieder der Topologie des Lösungsraumes entsprechen.
Da die Boltzmann-Wahrscheinlichkeit, schlechtere Lösungen zu wählen, ja immer geringer
wird, spielen vereinzelte Singularitäten sehr bald praktisch keine Rolle mehr.
18
Daraus folgt dann auch, dass bei stark zerklüfteten Fitness-Landschaften elitistische Verfahren allge-
mein nicht günstig sein müssen.
Search WWH ::
Custom Search