Evolutionäre Basisalgorithmen - Computational Intelligence - page 202

Alle Modifikationen der Anfangsrundreise und das globale Optimum sind mit
den dazugehörigen Fitnesswerten in Abbildung 12.6 aufgelistet. Uns fällt auf, dass
alleModifikationen der Anfangsrundreise zu Rundreisen führen, die schlechter sind.
Das globale Optimum kann daher, ausgehend von dieser Rundreise, mit einem rei-
nen Zufallsaufstieg nicht gefunden werden. Beim simulierten Ausglühen akzeptie-
ren wir dagegen mitunter auch schlechtere Lösungen, sodass das globale Optimum
erreicht werden kann. Natürlich gibt es auch beim simulierten Ausglühen wie bei
allen Metaheuristiken keine Garantie, dass dies auch tatsächlich geschieht.
Wir merken an, dass es von den erlaubten Operationen abhängen kann, ob die Su-
che in einem lokalen Optimum hängenbleiben kann. Lassen wir als weitere Operati-
on zu, dass die Position einer Stadt in der Rundreise geändert wird (durch Entfernen
von der aktuellen Position und Einfügen an einer anderen), so tritt im betrachteten
Beispiel kein Hängenbleiben mehr auf. Auch für diese Operatormenge können wir
jedoch ein Beispiel konstruieren, in dem die Suche in einem lokalen Minimum hän-
genbleibt.
Alle bisher betrachteten Verfahren suchen im weitesten Sinne lokal nach einer
Lösung im Suchraum .Dasbedeutet,dassstetsnureinaktuellerLösungskandi-
dat betrachtet wird. Der aktuelle Lösungskandidat wird nur geringfügig verändert.
Dies hat zum Nachteil, dass wir u. U. nur einen kleinen Teil des Suchraums betrach-
ten. Abhilfe schaffen mehrere Läufe des Verfahrens mit verschiedenen Startpunkten.
Allerdings bleibt ein Nachteil, nämlich dass keine Informationsübertragung von ei-
nem Lauf zum nächsten erfolgen kann. Dabei muss man beachten, dass große Ver-
änderungen des Lösungskandidaten, bis hin zu völliger Neuberechnung, nicht sinn-
voll sind, da dann zu wenig oder gar keine Information von einem Lösungskandi-
daten zum nächsten weitergegeben wird. Im Extremfall könnten wir auch einfach
eine Menge von Lösungskandidaten zufällig erzeugen und den Besten auswählen.
Wichtig zur Vermeidung dieses Problems sind demnach der Zusammenhang der Lö-
sungskandidaten sowie eine großräumigere Abdeckung des Suchraums .
12.3 Evolutionsstrategien
Bisher haben wir beliebige (auch diskrete) Optimierungsprobleme behandelt. Wenn
wir lediglich Probleme der numerischen Optimierung betrachten, so können wir al-
ternative evolutionäre Algorithmen, die sogenannten Evolutionsstrategien ,benutzen.
Gegeben sei also eine Funktion f :IR n IR u n d g e s u c h t w i r d e i n M i n i m u m o d e r
Maximum von f .FolglichsinddieChromosomen Ve k t o r en r e e l l e r Zah l en .Die Muta-
tion besteht in der Addition eines normalverteilten Zufallsvektors r .JedesElement
r i des Zufallsvektors ist die Realisierung einer normalverteilten Zufallsvariable mit
Erwartungswert 0 (unabhängig vom Elementindex i )undVarianz i bzw. Standard-
abweichung i .WirkönnendieVarianz i abhängig oder unabhängig vom Elemen-
tindex i und abhängig oder unabhängig von der Generationsnummer t wählen. Auf
Crossover (die Rekombination zweier Vektoren) wird oft verzichtet.