Evolutionäre Basisalgorithmen - Computational Intelligence - page 225

der besten m Lösungen der letzten Iteration ab (und eventuell auf der besten bisher
gefundenen Lösung). Die Pheromonmenge hängt somit vom Rang der Lösung ab.
Mit einem strengen Eliteprinzipien können wir ebenfalls arbeiten: Wir legen dann nur
Pheromon auf der besten Lösung der letzten Iteration ab. Eine minimale bzw. maxima-
le Pheromonmenge begrenzt dabei die Pheromonmenge einer Kante nach unten bzw.
oben. Dies führt zu einer Mindest- bzw. Maximalwahrscheinlichkeit für die Wahl ei-
ner Kante und somit zu einer besseren Erforschung des Suchraums, allerdings auch
zu gegebenenfalls schlechteren Konvergenzeigenschaften. Mit einer eingeschränkten
Ve rduns t ung bzw. Ev ap o r a t i on verdunstet Pheromon nur von Kanten, die in der Itera-
tion benutzt wurden, was ebenfalls zu einer besseren Erforschung des Suchraums
führt.
Lokale Verbesserungen der Rundreise in Verbindung mit den genannten Erweite-
rungen sind oft vorteilhaft. Vor der Pheromonaktualisierung optimieren wir eine er-
zeugte Rundreise lokal, indem einfache Modifikationen auf Verbesserung überprüft
werden. Lokale Optimierungsansätze können z. B. folgende Operationen benutzen:
Rekombination nach Entfernen von zwei Kanten (entspricht dem „Umdrehen“ einer
Te i l -Rundre i sen) , Rekomb i na t i on na ch Ent f e rnen von dre i Kant en ( ent spr i cht dem
„Umdrehen“ zweier Teil-Rundreisen), eingeschränkte Rekombination, Austausch be-
nachbarter Städte, Permutation benachbarter Triplets. „Teure“ lokale Optimierungen
sollte man nur auf die beste gefundene Lösung oder die in einer Iteration beste Lö-
sung anwenden.
Die allgemeine Anwendung der Ameisenkolonieoptimierung auf beliebige Opti-
mierungsprobleme ist beschränkt. Es muss sich dabei um ein kombinatorisches Opti-
mierungsproblem handeln. Auch muss es eine konstruktive Methode geben, um Lö-
sungskandidaten zu erzeugen. Sind beide Voraussetzungen erfüllt, können wir wie
folgt vorgehen. Lösungen werden mit Hilfe einer Folge von Zufallsentscheidungen
konstruiert, wobei jede Entscheidung eine Teillösung erweitert. Die Entscheidungs-
folge können wir als Pfad in einem Entscheidungsgraphen (auch: Konstruktionsgra-
phen) interpretieren. Die Ameisen sollen Pfade durch den Entscheidungsgraphen
erkunden und den besten (kürzesten, billigsten) Weg finden. Dabei markieren die
Ameisen die benutzten Kanten des Graphen mit Pheromon. Dadurch werden an-
dere Ameisen zu guten Lösungen geleitet. Pheromon verdunstet in jeder Iteration,
damit einmal ausgebrachtes Pheromon das System nicht zu lange beeinflusst, was
einem „Vergessen“ veralteter Information gleichkommt.
Betrachten wir das „Standardverfahren“ mit den folgenden Eigenschaften, so
lässt sich etwas über die Konvergenz der Suche sagen. Die Eigenschaften sind, dass
das Pheromon mit einem konstanten Faktor von allen Kanten verdunstet, nur auf
den Kanten des besten, bisher gefundenen Lösungskandidaten Pheromon abgelegt
wird (strenges Eliteprinzip), und es eine Untergrenze min für die Pheromonwer-
te der Kanten gibt, die nicht unterschritten werden darf. Dieses Standardverfahren
konvergiert in Wahrscheinlichkeit gegen die Lösung. D. h., mit gegen unendlich ge-
hender Zahl der berechneten Schritte geht die Wahrscheinlichkeit, dass die Lösung
gefunden wird, gegen 1. Geht die Untergrenze min für die Pheromonwerte „genü-
gend langsam“ gegen 0 ( min =

c

ln( t +1) mit Schrittzahl t und Konstante c ), kann sogar
gezeigt werden, dass für eine gegen unendlich gehende Schrittzahl jede Ameise der
Kolonie die Lösung mit gegen 1 gehender Wahrscheinlichkeit konstruiert.