next up previous contents
Next: Zusammenfassung und Diskussion Up: Eigene Untersuchungen Previous: Programmlauf

Verschiedene Routen

In einem zweiten Beispiel wurden wieder 50 Städte gewählt. Es soll nun dargestellt werden, wie sich die vom neuronalen Netz gefundenen Wege unterscheiden. Bei dem hier verwendeten Algorithmus hängt der gefundene Weg bei gleicher Lage der Städte nur von dem Parameter und der Reihenfolge der Städte bei der Iteration ab. Die Auswirkungen bei einer Veränderung von wurden schon in Kapitel 4.1 beschrieben. Bei 50 Städten wirkt sich eine Veränderung kaum aus, nur die durchschnittliche Länge des Weges erhöht sich geringfügig. Um die Auswirkung, die im Bericht von [AVT88] beschrieben sind, darzustellen müßte man statistische Untersuchungen anstellen. Um verläßliche Ergebnisse zu bekommen, sind daher eine große Anzahl von Testläufen nötig (im Bericht von [AVT88] z.B. 20000). Dies war aus zeitlichen Gründen nicht möglich. Daher wurde die Untersuchung auf die Auswirkung unterschiedlicher Reihenfolgen beim Besuchen der Städte beschränkt. In Abb. 5 sind vier verschiedene Ergebnisse aufgetragen, wobei sich die Eingabe für das Netz nur in der Reihenfolge der Städte unterscheidet. Man kann die unterschiedlichen Wege erkennen, die das Netz gewählt hat. Dabei wird deutlich, daß bestimmte Teilrouten schon optimal sind, d.h. sie sind in jeder Route gleich und stellen den optimalen Weg für dieses Teilgebiet dar. In anderen Bereichen der Karte scheinen mehrere vollkommen verschiedene Wege kurze Routen zu ergeben. Das Problem für das neuronale Netz ist hier, daß viele teilweise sehr verschiedene Wege sehr gute Lösungen ergeben, wobei sich die Länge kaum unterscheidet. Die optimale Lösung ist dabei nur unwesentlich kürzer als die vielen suboptimalen. Energetisch bedeutet dies für das Netz, daß sehr viele lokale Minima vorhanden sind, die sich in der Tiefe kaum vom absolutem Minimum unterscheiden. Deswegen stabilisiert sich das Netz meist in einem lokalen Minimum, was zwar i.a. sehr gute Wege ergibt, aber selten den optimalen. Dies gilt vor allem bei einer großen Anzahl von Städten, bei der es natürlich viel mehr Lösungen gibt.

Ein Problem, das auch bei diesem Algorithmus auftreten kann, sind Überschneidungen der Wege. In Abb. 2 ist hierfür ein Beispiel mit 150 Städten. Mit weniger Städten, z.B. 100, sind bei einigen Versuchen keine Überschneidungen aufgetreten. Im rechten Weg sind zwei Überschneidungen enthalten. Diese Wege sind natürlich trotzdem korrekt, aber eine Überschneidung bedeutet immer einen Verlust im Vergleich zu einer anderen Streckenführung. Meist kann durch eine lokale Anpassung die Überschneidung aufgehoben werden, z.B. durch Vertauschung zweier Städte auf der Route, und die Strecke dadurch verkürzt werden. Es gibt einige Algorithmen auf heuristischer Basis, die auch nach diesem Prinzip verfahren.


next up previous contents
Next: Zusammenfassung und Diskussion Up: Eigene Untersuchungen Previous: Programmlauf



Marius Heuler
Thu Nov 23 00:27:57 GMT 1995