Case Study: SOM und Optimierung
Hier soll eine weitere Anwendungsmöglichkeit aus der Optimierung gezeigt werden, die bereits 1988 von Teuvo Kohonen - dem Erfinder der SOM - vorgeschlagen wurde: das Traveling Sales Man Problem.
Das Traveling Salesman Problem (TSP) ist ein Optimierungsproblem, bei dem ein Verkäufer
(Salesman) die kürzeste mögliche Rundreise
durch eine gegebene Anzahl von Städten finden soll, wobei jede Stadt genau einmal besucht wird
und er am Startpunkt endet.
Das TSP gehört zur Klasse der NP-schweren Probleme, was bedeutet, dass es keine bekannte
effiziente Lösung für große Problemgrößen gibt.
Alleine für die Lösung mit 50 Städten gibt es \(49! = 6.082 \cdot
10^{62}\) Möglichkeiten. Meist ist daher die Lösung nur über Heuristiken möglich,
d.h. über Algorithmen, die zwar eine gute Lösung finden, aber nicht zwingend die optimale.
Um mit SOMs ein Traveling Salesman Problem zu lösen, wird eine Ringtopologie angewandt, was der gewünschten Rundreise entspricht. D.h. man ordnet die Neuronen zunächst in einem Kreisring mit festem Radius. Anschließend werden immer zufällige Städte ausgewählt und das Neuron, deren Gewichte zu dieser Stadt am nächsten liegen (=Siegerneuron), wird über die Anpassung der Gewichte zu dieser Stadt hinbewegt. Die Lernrate gibt vor, wie stark diese Bewegung ist. Zudem werden zum Siegerneuron benachbarte Neuronen (gesteuert über ein sigma) ebenfalls zur ausgewählten Stadt bewegt. Lernrate und sigma werden im Zeitverlauf über Eine Abklingfunktion (decay) reduziert. Am Ende konvergiert der Algorithmus zu einer zulässigen Lösung, die meist besser als die Lösung anderer Heuristiken (z.B. Nearest Neighbor, Simulated Annealing) ist.
Das Traveling Salesman Problem hat viele praktische Bedeutungen. Ein Beispiel ist das Löten einer Platine. Um den Weg des Lötroboters zu Optimieren, muss die kürzeste geschlossen Kurve zwischen den Lötpunkten gefunden werden. Aber auch in der Logistik (z.B. Warenlager, Spedition etc.) ist das Problem von Bedeutung. Steigende Rechnerleistung, die Einbeziehung von Grafikkarten und die zunehmende Skalierbarkeit der Probleme, verhelfen den SOMs zu einer "Renaissance".
Für den nachfolgenden SOM-Algortihmus wurde das PyTorch-Paket "miniSOM_gpu" um eine Ringtopologie ergänzt. Ausgangspunkt ist eine Punktmenge (z.B. Lötpunkte, Städte, Positionen in einem Lager für eine Lieferung etc.). Ein selbstorganisierendes Netz soll für diese Punkte eigenständig einen Rundweg finden, der der optimalen Lösung möglichst nahe kommt. Zunächst sollen eine Anzahl von Daten generiert werden. Dabei ist Seed-Data der Seed des Zufallsalgorithmus. Verschiedene Seeds erzeugen vollkommen andere Datensätze. Mit einem gleichbleibenden Seed können die Daten repliziert werden.
Die generierten Datenpunkte sollen anschließend durch den SOM-Algorithmus so verbunden werden, dass der zurückzulegende Weg möglichst minimal ist. Dabei werden die Neuronen zum Start auf einen Kreis gelegt (gestrichelte Linie). In jedem Schritt wird ein Datenpunkt ausgewählt (über Seed Netz) und das zu ihm nächstliegende Neuron bestimmt (Siegerneuron). Dieses Neuron und seine Nachbarn (sigma), werden über die Lernrate in Richtung des ausgewählten Datenpunktes bewegt. Dies wird in jeder Simulation wiederholt, wobei sigma und die Lernrate über den decay-Wert reduziert werden.
TIP: Vor dem Start des Algorithmus sollte man sich selbst eine kürzeste Route überlegen, um die Leistungsfähigkeit eines SOM besser würdigen zu können.
Lernen:
