Information Technology Reference
In-Depth Information
ter hinzugefügt wird. Die Mehrheit der Ameisen benutzt weiter den längeren Weg.
Nur in seltenen Fällen wird auf den kürzeren Weg gewechselt.
Wir gelangen von der natürlichen zur künstlichen Ameise durch Abstraktion der
Situation zu einer Suche nach einem bestenWeg in einem gewichteten Graphen. Das
Problem sind Kreise, die sich selbst verstärken. Durchläuft die Ameise einen Kreis,
erzeugt sie durch das abgelegte Pheromon eine Tendenz, den Kreis erneut zu durch-
laufen. Dies können wir verhindern, indem wir Pheromon erst nach Konstruktion
des ganzen Weges abgelegen und Kreise entfernen, bevor wir Pheromon abgelegen.
Gegebenenfalls konzentriert sich die Suche auf amAnfang konstruierte Lösungskan-
didaten, was einer vorzeitigen Konvergenz entspricht. Abhilfe schafft die
Pheromon-
verdunstung
, die in der Natur nur eine geringe Rolle spielt. Nützliche Erweiterungen
bzw. Verbesserungen sind, dass die abgelegte Pheromonmenge von der Lösungsgüte
abhängt, oder das Einbringen von Heuristiken in die Kantenwahl (z. B. ein Kanten-
gewicht).
Ameisenkolonieoptimierung kann z. B. für das Lösen des Problems des Hand-
lungsreisenden (siehe Abschnitt 11.1.2) benutzt werden. Dann müssen wir das Pro-
blem dafür nur durch eine
n
n
-Matrix
D
=(
d
ij
)
1
i
,
j
n
darstellen.
n
ist die Anzahl
der Städte und
d
ij
der Abstand der Städte
i
und
j
.Manmussbeachten,dass
D
asym-
metrisch sein kann, aber
i
{
1, . . . ,
n
}
:
d
ii
=
0. Die Pheromoninformation wird
als
n
n
Matrix
=(
ij
)
1
i
,
j
n
dargestellt. Ein Pheromonwert
ij
(
i
=
j
)
gibt an,
wie wünschenswert es ist, Stadt
j
direkt nach Stadt
i
zu besuchen (
ii
nicht benötigt).
Die Matrix muss nicht notwendig symmetrisch sein oder gehalten werden. Alle Ma-
trixelemente
ij
initialisieren wir mit dem gleichen kleinen Wert. Am Anfang liegt
auf allen Kanten die gleiche Menge Pheromon. Ameisen durchlaufen (mit Hilfe des
Pheromons) Hamiltonkreise. Sie markieren die Kanten des durchlaufenen Hamil-
tonkreises mit Pheromon, wobei die ausgebrachte Pheromonmenge der Qualität der
Lösung entspricht.
Ein Lösungskandidat wird wie folgt konstruiert. Jede Ameise hat als „Gedächt-
nis“ eine Menge
C
, die die Indizes der noch nicht besuchten Städte enthält. Jede
besuchte Stadt wird aus dieser Menge entfernt. Dieses Gedächtnis gibt es im biologi-
schen Vorbild natürlich nicht.
1. Eine Ameise wird in eine zufällig bestimmte Stadt gesetzt. Diese Stadt ist der
Anfang der Rundreise.
2. Die Ameise wählt eine noch nicht besuchte Stadt und begibt sich in diese. In
Stadt
i
wählt die Ameise die (unbesuchte) Stadt
j
mit der Wahrscheinlichkeit
ij
k
C
ik
p
ij
=
,
wobei
C
die Menge der Indizes der noch nicht besuchten Städte ist und
ij
die
Menge an Pheromon auf der Verbindung von Stadt
i
nach Stadt
j
.
3. Wiederhole Schritt 2, bis alle Städte besucht wurden.
Das Pheromon wird durch zwei Methoden aktualisiert. Zu allererst bewirkt die
Ve rduns t ung
bzw.
Evaporation
,dassallePheromonwerteumeinenBruchteil
(eva-
poration) verringert werden:
i
,
j
{
1, . . . ,
n
}
:
ij
=(
1
) ·
ij
.
