Neurale TSP‑Modelle liefern neue Entscheidungsunterstützung

In einer kürzlich veröffentlichten Studie auf arXiv wird gezeigt, dass neuronale Modelle, die für das Traveling Salesman Problem (TSP) trainiert wurden, nicht nur gute Touren erzeugen, sondern auch wertvolle interne Repräsentationen besitzen, die für andere Optimierungsaufgaben nutzbar sind.

Die Forscher haben mehrere auf Attention basierende TSP‑Policies trainiert und deren interne Aktivierungen gesammelt. Anschließend wurden sogenannte „Probes“ auf die Knoten‑ und Kanteneinbettungen angewendet, um zwei praxisnahe, NP‑schwere Aufgaben zu lösen: die Identifikation des einflussreichsten Knotens zum Entfernen (node‑removal sensitivity) und die Erkennung der kritischsten Kante, die beibehalten werden muss (edge‑forbid sensitivity).

Auf einem Euclidean TSP‑100‑Modell erwiesen sich die Probes für beide Aufgaben als mit bestehenden Baselines vergleichbar. Durch die Kombination der Probe‑Signale mit geometrischen Merkmalen erzielten die Autoren sogar bessere Ergebnisse: 65 % Top‑1‑Genauigkeit gegen 58 % bei der besten Knotenauswahl und 73 % Top‑1‑Genauigkeit gegen 67 % bei der schlechtesten Kantenauswahl. Diese Leistung macht sie zum ersten Team, das neuronale TSP‑Solver als übertragbare Encoder für preskriptive „What‑If“-Entscheidungsunterstützung untersucht.

Ein weiterer interessanter Befund ist, dass die Transfer‑Genauigkeit mit der Qualität des TSP‑Solvers und der Modellgröße steigt. Das bedeutet, dass stärkere neuronale Kombinatorische Optimierungsmodelle nicht nur bessere Touren liefern, sondern auch nützlichere Repräsentationen für ergänzende Optimierungsaufgaben erzeugen. Der komplette Code ist öffentlich verfügbar unter github.com/ReubenNarad/tsp_prescriptive_probe.