Information Technology Reference
In-Depth Information
voraus.
M.a.W., es muss möglich sein, die verschiedenen Vektoren danach zu ordnen, dass von
zwei Vektoren V und W immer entschieden werden kann, ob V besser ist als W oder um-
gekehrt oder ob beide gleich gut sind. Das Schwierige beim Einsatz eines GA für bestimmte
Zwecke ist somit häufig die Konstruktion einer problemadäquaten Bewertungsfunktion. An-
ders gesagt: Wenn man für ein Problem eine geeignete Bewertungsfunktion gefunden hat, dann
kann man das Problem im Rahmen der Leistungsfähigkeit eines GA gewöhnlich relativ leicht
lösen. Aber dafür gibt es keine allgemeine Konstruktionsregel.
Bei einem GA und einer ES kann noch folgende Unterscheidung wichtig sein: Die bisherigen
Definitionen gingen immer davon aus, dass die Vektoren jeweils gesamt bewertet werden -
siehe die beiden Beispiele. Man kann auch festlegen, dass die einzelnen Komponenten in den
Vektoren bewertet werden, sozusagen eine individuelle Fitness, und die Bewertung des gesam-
ten Vektors sich aus den Werten der Komponenten ergibt; dieses Verfahren hat ja Michalewicz
bei seinem Konvergenzbeweis verwendet. In derartigen Fällen wird häufig eine Unterschei-
dung zwischen Fitness- und Bewertungsfunktion vorgenommen, um die doppelte Bewertung
von Vektoren und Komponenten mit ggf. unterschiedlichen Funktionen zu betonen. In den
meisten Fällen spielt diese Unterscheidung jedoch keine Rolle und wir werden im Folgenden
weiter nur von Bewertungsfunktion reden.
(5) Heiratsschema und Selektion: Der von Holland entwickelte Standard-GA orientierte sich in
dem Sinne an der biologischen Evolution, dass, wie oben bemerkt, die Auswahl der zu
rekombinierenden Vektoren nach deren jeweiliger „Fitness“ erfolgt. Entweder werden immer
nur die besten „Eltern“ zur Rekombination herangezogen (siehe die Beispiele oben) oder es
wird mit Rekombinationswahrscheinlichkeiten gearbeitet, wobei die Wahrscheinlichkeit pro-
portional zur jeweiligen Fitness ist; die Wahrscheinlichkeit, ausgewählt zu werden, ist dem-
nach für den besten Vektor am größten. In der Praxis bietet es sich auch fast immer an, mit
einem derartigen Heiratsschema zu arbeiten, da dies eine relativ rasche Konvergenz sichert -
mit den obigen Einschränkungen natürlich. Der Vollständigkeit wegen muss jedoch erwähnt
werden, dass es auch andere Möglichkeiten gibt. Einige seien hier kurz erwähnt:
Das so genannte Roulette-Wheel-Verfahren operiert nach einem reinen Zufallsprinzip, d. h.
ohne Rücksicht auf die Fitness der jeweiligen Elternvektoren. Damit ähnelt es im Prinzip den
Monte-Carlo-Verfahren. Der Vorteil dieses Schemas ist natürlich, dass eine zu rasche Konver-
genz in einem lokalen Optimum kaum vorkommen kann; der ebenso evidente Nachteil ist, dass
sehr viele Möglichkeiten durchgerechnet werden müssen. Im Grunde fällt hier das biologische
Prinzip der Selektion weitgehend aus.
Eine Kombination zwischen dem streng selektiv operierenden Standardschema und dem Rou-
lette-Wheel-Schema besteht darin, dass einige der besten Vektoren für das Crossover selektiert
werden und zusätzlich aus den schlechtesten Vektoren per Zufall eine entsprechende Anzahl.
Hat man z. B. 20 Vektoren, dann kann man bei diesem Schema etwa die fünf Besten nehmen
und nach Zufall aus den zehn Schlechtesten wieder fünf Vektoren auswählen. Diese werden
dann rekombiniert, um wieder 20 Vektoren zu erhalten. Dies Schema verhindert ebenfalls zu
rasche Konvergenz, erfordert aber natürlich auch mehr Rechenzeit als das Standardschema.
Eine zusätzliche Möglichkeit orientiert sich an dem Verfahren des Simulated Annealing (siehe
unten). Wie beim Roulette-Wheel wird aus allen Vektoren per Zufall eine Auswahl getroffen.
Allerdings sinkt die Wahrscheinlichkeit, schlechte Vektoren auszuwählen mit jeder Generati-
on, so dass nach einer bestimmten Zeit, abhängig vom so genannten „Abkühlverfahren“, prak-
tisch nur noch die Besten ausgewählt werden. Auch hier wird eine zu rasche Konvergenz ver-
hindert, wobei am Ende wieder eine strenge Selektion vorgenommen wird.
Search WWH ::
Custom Search