Self-Organizing Map 
Problem des Handlungsreisenden
 

Das Problem des Handlungsreisenden oder auch Travelling-salesman-Problem oder Ortsfolgeproblem ist ein kombinatorisches Optimierungsproblem des Operations Research, bei dem der minimale Weg (minimale Reisekosten) für die Rundreise eines Handelsreisenden gesucht ist. Von einem Ort ausgehend muß der Handelsreisende n-1 Orte mindestens einmal besuchen, um dann wieder in den Ausgangsort zurückzukehren. Die Entfernungen (Kosten) zwischen den Orten sind bekannt (Entfernungsmatrix). Mögliche Lösungsmethoden sind die ganzzahlige Optimierung,  Branch-and-Bound-Verfahren oder aber auch 1D-SOM. 
 
Abb.1 (= Abb.4) Quelle
Abb.2 Gewichtsraum
Abb.3 Bildauswertung
Beispiel 1; mögliche Lösung eines Ortsfolgeproblems mit 10 Ortschaften mit einer 10x1 SOM-Karte

 
Abb.4 (= Abb.1)  Quelle
Abb.5 Gewichtsraum
Abb.6 Bildauswertung
Beispiel 2; mögliche Lösung eines Ortsfolgeproblems mit 10 Ortschaften mit einer 10x1 SOM-Karte

Durch die Ballungsgebiete der Eingabevektoren (Abb.1 und Abb. 4) sollen Ortschaften und deren Lage angedeutet werden. Ich habe 10 "Ortschaften" aufgezeichent. Für jede Ortschaft habe ich ein Neuron reserviert. Der SOM-Algorithmus legt die Gewicht in die Ballungszentren (Abb.3 und Abb.6) der Eingabevektoren und erhält dabei die Nachbarschaftsbeziehung (Abb.2 und Abb.5). Der 1D-SOM liefert somit für das Ortsfolgeproblem eine mögliche gute Lösung, jedoch nicht die optimale. Das wird durch die beiden Abb. 2 und Abb.5 verdeutlicht.


Self-Organizing Map