Hopfield-Netze - Computational Intelligence - page 133

3 3

2 4

2 2

3

1 1

1 5

1 234 5 1 234 5

Abbildung 8.10: Ein sehr einfaches Problem des Handlungsreisenden mit 5 Städten
und seine Lösung.

darstellt. Denn es gibt auch Situationen, in denen von einer Matrix, die keine gülti-
ge Reiseroute darstellt, nur über eine zwischenzeitliche Energieerhöhung zu einer
Matrix übergegangen werden kann, die eine gültige Reiseroute darstellt. Wenn etwa
eine Spalte der Matrix zwei Einsen enthält (also die erste Nebenbedingung verletzt
ist), diese beiden Einsen aber die einzigen Einsen in ihren jeweiligen Zeilen sind,
so kann die Verletzung der ersten Nebenbedingung nur unter Verletzung der zwei-
ten Nebenbedingung aufgehoben werden. Da beide Bedingungen gleichwertig sind,
kommt es zu keiner Änderung.

Die gerade angestellten Überlegungen können mit Hilfe des Programms tsp.c ,
das auf der WWW-Seite zu diesemBuch zur Verfügung steht, nachvollzogen werden.
Dieses Programm versucht das in Abbildung 8.10 gezeigte sehr einfache 5-Städte-
Problem mit Hilfe eines Hopfield-Netzes zu lösen. Die erzeugte Lösung ist nicht
immer eine gültige Reiseroute, und selbst wenn sie gültig ist, erscheint sie völlig
zufällig ausgewählt.

Ein Hopfield-Netz zu verwenden, um das Problem des Handlungsreisenden zu
lösen, ist daher in der Tat nicht empfehlenswert. Wir haben hier dieses Problem den-
noch verwendet, weil man an ihm sehr schön das Vorgehen beim Aufstellen der
Energiefunktionen verdeutlichen kann. Die hier auftretenden Probleme sind jedoch
auch bei der Anwendung von Hopfield-Netzen auf andere Optimierungsprobleme
zu berücksichtigen.

Eine gewisse Verbesserung lässt sich allerdings dadurch erreichen, dass man von
diskreten Hopfield-Netzen mit nur zwei möglichen Aktivierungszuständen je Neuron,
wie wir sie bisher betrachtet haben, zu kontinuierlichen Hopfield-Netzen übergeht, bei
denen jedes Neuron als Aktivierung eine beliebige Zahl aus [ 1, 1 ] bzw. [ 0, 1 ] haben
kann. Dieser Übergang entspricht in etwa der Verallgemeinerung der Aktivierungs-
funktion, wie wir sie beimÜbergang von Schwellenwertelementen zu den Neuronen
eines mehrschichtigen Perzeptrons betrachtet haben (siehe Abbildung 5.2 auf Sei-
te 45). Mit kontinuierlichen Hopfield-Netzen, die außerdem den Vorteil haben, dass
sie sich gut für eine Hardware-Implementierung mit Hilfe eines elektrischen Schalt-
kreises eignen, wurden gewisse Erfolge bei der Lösung des Problems des Handlungs-
reisenden erzielt [Hopfield u. Tank 1985].