Information Technology Reference
In-Depth Information
zusammen, wobei wir die Faktoren
a
,
b
,
c
IR
+
so wählen müssen, dass es nicht
möglich ist, eine Verkleinerung der Energiefunktion durch Verletzung der Nebenbe-
dingungen zu erkaufen. Das ist sicherlich dann der Fall, wenn
b
a
=
c
a
>
2 ax
(
j
1
,
j
2
){
1,...,
n
}
2
d
j
1
j
2
,
wenn also die größtmögliche Verbesserung, die durch eine (lokale) Änderung der
Reiseroute erzielt werden kann, kleiner ist als die minimale Verschlechterung, die
sich aus einer Verletzung einer Nebenbedingung ergibt.
Da die Matrixeinträge
m
ij
den Aktivierungen act
(
i
,
j
)
der Neuronen
(
i
,
j
)
des Hop-
field-Netzes entsprechen, lesen wir aus der Gesamtenergiefunktion
E
die folgenden
Gewichte und Schwellenwerte ab:
w
(
i
1
,
j
1
)(
i
2
,
j
2
)
=
ad
j
1
j
2
· (
(
i
1
mod
n
)+
1,
i
2
+
i
1
,
(
i
2
mod
n
)+
1
)
2
b
j
1
j
2
aus
E
2
2
c
i
1
i
2
aus
E
3
,
aus
E
1
(
i
,
j
)
= 0
a
2
b
aus
E
2
2
c
aus
E
3
= 2(
b
+
c
).
aus
E
1
Das so konstruierte Hopfield-Netz wird anschließend zufällig initialisiert, und die
Aktivierungen der Neuronen so lange neu berechnet, bis ein stabiler Zustand er-
reicht ist. Aus diesem Zustand kann die Lösung abgelesen werden.
Man beachte allerdings, dass der vorgestellte Ansatz zur Lösung des Problems
des Handlungsreisenden trotz seiner Plausibilität für die Praxis doch nur sehr einge-
schränkt tauglich ist. Eines der Hauptprobleme besteht darin, dass es demHopfield-
Netz nicht möglich ist, von einer gefundenen Rundreise zu einer anderen mit ge-
ringerer Länge überzugehen. Denn um eine Matrix, die eine Rundreise darstellt, in
eine Matrix zu überführen, die eine andere Rundreise darstellt, müssen mindestens
vier Neuronen (Matrixelemente) ihre Aktivierungen ändern. (Werden etwa die Po-
sitionen zweier Städte in der Rundreise vertauscht, so müssen zwei Neuronen ihre
Aktivierung von 1 auf 0 und zwei weitere ihre Aktivierung von 0 auf 1 ändern.) Jede
der vier Änderungen, allein ausgeführt, verletzt jedoch mindestens eine der beiden
Nebenbedingungen und führt daher zu einer Energieerhöhung. Erst alle vier Än-
derungen zusammen können zu einer Energieverminderung führen. Folglich kann
durch die normalen Berechnungen nie von einer bereits gefundenen Rundreise zu
einer anderen übergegangen werden, auch wenn dieser Übergang nur eine geringfü-
gige Änderung der Reiseroute erfordert. Es ist daher sehr wahrscheinlich, dass das
Hopfield-Netz in einem lokalen Minimum der Energiefunktion hängen bleibt. Ein
solches Hängenbleiben in einem lokalen Minimum kann natürlich nie ausgeschlos-
sen werden, doch ist es hier besonders unangenehm, da es auch Situationen betrifft,
in denen die Änderungen, die gegebenenfalls zur Verbesserung der Rundreise nötig
sind, sozusagen „offensichtlich“ sind (wie z. B. das Vertauschen einer Stadt mit einer
anderen).
Die Lage ist jedoch noch viel schlimmer. Obwohl wir durch die Energiefunktio-
nen
E
1
und
E
2
die Nebenbedingungen für eine gültige Reiseroute berücksichtigt ha-
ben, ist nicht sichergestellt, dass der erreichte stabile Zustand eine gültige Reiseroute
