Inhalt:

1. Einführung
2. Mathematische Betrachtung
3. Kohonen - Netz
4. Bedienungshinweise
5. Java Applet
6. Java Doc
7. Source Code
8. Quellenangaben

1. Einführung

2. Mathematische Betrachtung

Mit wachsendem n wird die Kapazität einer von Neumann - Maschine allerdings schnell überschritten, da es sich hierbei um einen NP - Algorithmus handelt. Dieser ist nicht in polynomialer Zeit lösbar bzw. können die nötigen Rechenschritte für ein wachsendes n nicht durch ein Polynom (a₀ + a₁*x + a₂*x² + ...) beschrieben werden. So gibt es bei n Städten (n-1)! verschiedene Wege bzw. (n-1)! / 2 verschiedene Wege, wenn man berücksichtigt, daß Hin- u. Rückweg vom Streckenverlauf identisch sind.

Bei 10 Städten gibt es schon über 180000 Möglichkeiten, bei 24 Städten etwa 1.3*10²² usw. Eine kombinatorische Lösung des Problems scheidet somit aus. Bei einer Rundreise durch 120 Städte gibt es mit ca. 6*10¹⁹⁶ möglichen Reisen mehr Rundreisen als Elementarteilchen im Universum. Deshalb rücken für die praktische Anwendung Verfahren in den Mittelpunkt des Interesses, die nicht unbedingt nach langer Rechenzeit die kürzeste überhaupt mögliche Rundreise (Optimum) finden, sondern bereits nach kurzer Zeit eine noch nicht ganz so gute Reise (Suboptimum) anbieten.
 

3. Kohonen - Netz

Als Ausgangsposition für das Netz wurde für jedes einzelne Neuron eine zufällige Position gewählt. Die Städte ziehen die Neuronen unterschiedlich stark an. Das Neuron, welches sich einer Stadt am nächsten befindet, wird als Siegerneuron ausgewählt und darf sich auf die Stadt zubewegen. Die Nachbarneuronen werden ebenfalls verschoben. Jedes Neuron e_i hat ein Erregungsfeld mit dem Schwerpunkt y_i und dem Durchmesser K. Beim Lernen wandern die Felder auf die Städte zu, die ihnen am nächsten liegen. Da der Durchmesser dabei gegen Null konvergiert, liegt zum Schluß jede Stadt im Erregungsfeld einer Zelle.

In unserem Fall gelten folgende Vereinbarungen:

• Das Kohonen Netz wird durch einen Ring repräsentiert.
• Der Ring besitzt sehr viele Neuronen.
• Die Position der Städte wird auf die gleiche Karte übertragen, in dem die Position des Ringes festgehalten wird.
• Von den einzelnen Städten gehen Reize aus.
• Das Neuron, welches den kürzesten Abstand auf der Karte zu einer Stadt besitzt, wird zum Gewinner gekürt und von der Stadt angezogen.
• Somit werden auch die Nachbarneuronen an die Nachbarstädte angenähert.

Folgender Zyklus führt zur Stabilität des Netzes:

• Initialisieren aller Gewichte mit Zufallswerten
• Auswählen einer Stadt, dazu deren X- u. Y-Koordinaten in Eingangsneuronen übertragen
• Neuron j herausfunden, welches der Stadt am nächsten liegt:

(X_i - w_xi)² + (y_i - w_yi)² = min
Modifikation der Geichte:
w_xi = w_xi * eta * r_ij * (x_i - w_xi)
w_yi = w_yi * eta * r_ij * (y_i - w_yi)
eta ... Lernrate
w_xi , w_yi ... Gewicht des Neurons

Neuberechnung der Gewichte
• Veränderung der Lernrate
• Anpassung der Nachbarschaft
  

4. Bedienungshinweise

Die einzelnen Städte werden an zufällig gewählten Koordinaten positioniert. Mit dem Betätigen des Start Buttons wird die Animation angestoßen. Der New Map Button startet eine neue Animation mit selbst eingestellten Werten oder mit den Vorgabewerten (Default).

Es können folgende (Start-) Werte eingestellt werden:

• Anzahl der Städte, Neuronen und Durchläufe
  
  
Das Travelling Salesman Problem macht mit mindestens 4 Städten erst Sinn. Dennoch kann zur Veranschaulichung ein Mindestwert von einer Stadt angegeben werden. Die Anzahl der Neuronen sollte um ein Vielfaches höher liegen als die Anzahl der Städte. Sind sehr viele Neuronen und Städte am TSP-Problem beteiligt, empfiehlt sich eine hohe Anzahl von Durchläufen.

• Bereich der Lernrate eta und der Nachbarschaft sigma
  
  eta sollte zwischen 0 und 1 liegen. sigma muß lediglich größer als 0 sein. Die optimalen Einstellungen können durch Versuche annähernd bestimmt werden und hängen von verschiedenen Faktoren wie Anzahl der Städte und Neuronen ab.
  

• Anzeige der Animation aller n Durchläufe
  
  n ist standardmäßig bei 100 eingestellt. Die Animation dient lediglich dem Verständnis der Lernprozesses des Kohonen-Netzes. Die Graphikausgabe beansprucht verglichen mit der eigentlichen Berechnung des SOM-Netzes sehr viel Zeit und kann daher abgeschalten werden.
  
  

5. Java Applet

6. Java Doc

• TSP
• TSP.GO

7. Source Code

8. Quellenangaben

1. Scherer, Andreas: Neuronale Netze  Grundlagen und Anwendungen. Braunschweig: Vieweg, 1997
2. Hoffmann, Norbert: Neuronale Netze  Anwendungsorientiertes Wissen. Braunschweig: Vieweg, 1993
3. Lawrence, Jeanette: Neuronale Netze  Computersimulation. München: Systhema, 1992
4. Brause, Rüdiger: Neuronale Netze  Eine Einführung in die Neuroinformatik. Stuttgart: Teubner, 1995
5. Kohonen, Teuvo: Self Organizing Maps. Heidelberg: Springer, 1995
6. Haykin, Simon: Neural Networks  A comprehensive Foundation. Macmillan: NJ USA, 1994
7. Zell, Andreas: Simulation Neuronaler Netze. Oldenbourg: Muenchen, 1997