Hopfield-Netze - Computational Intelligence - page 129

Stadt
1234

1 2

1000

1.
2.
3.
4.

0010
0001
0100

Station

3 4

Abbildung 8.9: Eine Rundreise durch vier Städte und eine sie darstellende binäre
4 4Matrix.

darin, für einen Handlungsreisenden eine möglichst kurze Rundreise durch eine ge-
gebene Menge von n Städten zu finden, so dass jede Stadt genau einmal besucht
wird. Um dieses Problem mit Hilfe eines Hopfield-Netzes zu lösen, verwenden wir
für die Neuronen die Aktivierungen 0 und 1, da uns dies das Aufstellen der Ener-
giefunktionen erleichtert. Dass wir zu dieser Abweichung von der anfangs gegebe-
nen Definition berechtigt sind, weil wir stets die Gewichte und Schwellenwerte auf
ein Hopfield-Netz mit den Aktivierungen 1 und 1umrechnenkönnen,zeigtAb-
schnitt A.3, in dem die benötigten Umrechnungsformeln abgeleitet werden.
Eine Rundreise durch die gegebenen n Städte kodieren wir wie folgt: Wir stel-
len eine binäre n n Matrix M =( m ij ) auf, deren Spalten den Städten und deren
Zeilen den Stationen der Rundreise entsprechen. Wir tragen in Zeile i und Spalte j
dieser Matrix eine 1 ein ( m ij = 1), wenn die Stadt j die i -te Station der Rundreise ist.
Anderenfalls tragen wir eine 0 ein ( m ij = 0). Z. B. beschreibt die in Abbildung 8.9
rechts gezeigte Matrix die in der gleichen Abbildung links gezeigte Rundreise durch
die vier Städte 1 bis 4. Man beachte, dass eine zyklische Vertauschung der Stationen
(Zeilen) die gleiche Rundreise beschreibt, da keine Startstadt festgelegt ist.
Das zu konstruierende Hopfield-Netz besitzt für jedes Element dieser n n Ma-
trix ein Neuron, das wir mit den Koordinaten ( i , j ) des zugehörigenMatrixelementes
bezeichnen und dessen Aktivierung dem Wert dieses Matrixelementes entspricht.
Damit können wir nach Abschluss der Berechnungen aus den Aktivierungen der
Neuronen die gefundene Rundreise ablesen. Man beachte, dass wir im folgenden
stets einen Index i zur Bezeichnung der Stationen und einen Index j zur Bezeich-
nung der Städte verwenden.
Mit Hilfe der Matrix M können wir die zur Lösung des Problems des Handlungs-
reisenden zu minimierende Funktion formulieren als

n
j 1 = 1

n
j 2 = 1

n
i = 1 d j 1 j 2

E 1 = · m ij 1 · m ( i mod n )+1, j 2 .

d j 1 j 2 ist die Entfernung zwischen Stadt j 1 und Stadt j 2 .DurchdiebeidenFaktoren,
die sich auf die Matrix M beziehen, wird sichergestellt, dass nur Entfernungen zwi-
schen Städten summiert werden, die in der Reiseroute aufeinanderfolgen, d. h., bei
denen die Stadt j 1 die i -te Station und die Stadt j 2 die (( i mod n )+ 1 ) -te Station der
Rundreise bildet. Nur in diesem Fall sind beide Matrixelemente 1. Wenn die Städ-
te dagegen nicht aufeinanderfolgen, ist mindestens eines der Matrixelemente und
damit der Summand 0.