Information Technology Reference
In-Depth Information
Zweitens bewirkt die
Ve r s t ä r kung k ons t ru i e r t e r Lö sung en
,dassdieKantenderkon-
struierten Lösungen mit einer zusätzlichen Menge an Pheromon belegt werden, die
der Lösungsqualität entspricht:
t
:
(
i
)
((
i
mod
n
)+1)
=
(
i
)
((
i
mod
n
)+1)
+
Q
(
),
wobei
t
die Menge der im Schritt
t
konstruierten Rundreisen (Permutationen) ist.
Als Qualitätsfunktion können wir z. B. die inverse Reiselänge
1
n
i
=
i
d
(
i
)
((
i
mod
n
)+
1
)
Q
(
)=
c
·
verwenden. Das bedeutet anschaulich, je besser die Lösung, umso mehr Pheromon
erhalten die Kanten. Algorithmus 19 stellt den Pseudocode zum Lösen des Problems
des Handlungsreisenden dar.
Algorithmus 19
A
MEISENKOLONIEOPTIMIERUNG
-TSP
1: initialisiere alle Matrixelemente
ij
,1
i
,
j
n
,aufkleinenWert
2:
repeat
3:
for all
Ameise
do
// k o n s
r u i e r
e
L ö s u n g s k a n d i d a
e n
4:
C
{
1, . . . ,
n
}
// M e n g e
d e
r
z u
b e s u c h e n d e n
S t ä d t e
5:
i
wähle zufällig Anfangsstadt aus
C
6:
C
C
\{
i
}
// e n t
f e r n e
s i e
a u s
d e n
u n b e
s u c h t
e n
S t ä d t
e n
7:
while
C
=
do
// s o l a n g e
n i
c h t
a
l e
S t ä d t
e
b e
s u c h t w u r d e n
8:
j
wähle nächste Stadt der Reise aus
C
mit Wahrscheinlichkeit
p
ij
9:
C
C
\{
j
}
// e n t
f e r n e
s i e
a u s
d e n
u n b e
s u c h t
e n
S t ä d t
e n
10:
i
j
// u n d
g e h e
i n
d i e
a u s g e w ä h l
e
S t a d t
11:
end while
12:
end for
13: aktualisiere Pheromon-Matrix nach Lösungsgüte
14:
until
Terminierungskriterium ist nicht erfüllt
Dieser einfache Algorithmus bietet viele Alternativen und lässt sich um einige
Merkmale erweitern. So könnten wir analog zur Nächster-Nachbar-Heuristik
nahe
Städte bevorzugen
:GehevonStadt
i
zu Stadt
j
mit Wahrscheinlichkeit
ij
ij
k
C
ik
ik
p
ij
=
,
wobei
C
Menge der Indizes der unbesuchten Städte und
ij
=
d
1
ij
ist. Eine “greedy”-
Va r i ant e de s Al gor i thmus i s t da s
Te nd i e r e n z u r Wa h l d e r b e s t e n Ka n t e :
Mit Wahrschein-
lichkeit
p
exploit
soll von Stadt
i
zur Stadt
j
best
gegangen werden mit
j
best
=
argmax
j
C
ij
bzw.
j
best
=
argmax
j
C
ij
ij
und dabei soll
p
ij
mit Wahrscheinlichkeit 1
p
exploit
benutzt werden. Zusätzlich kön-
nen wir auch ein Eliteprinzip mit der
Ve r s t ä r kung d e r b e s t en b e k ann t en Rund r e i s e
an-
wenden: Wir legen zusätzliches Pheromon auf der besten bisher bekannten Rundrei-
se ab. Es kann z. B. als Bruchteil Ameisen angegeben werden, die sie zusätzlich ab-
laufen. Bei einer
rangbasierten Aktualisierung
legen wir Pheromon nur auf den Kanten
