Die lange Geschichte des TSP mit SOM

am

Wie schon △ hier geschrieben: Mit selbstorganisierenden Merkmalskarten (SOM) kann das Traveling Salesman Problem (TSP) angegangen werden. Die SOM wird von allen Autoren erläutert, so auch von mir in  ⧉ meiner Diss [1]. 

Das Verfahren wurde von Angéniol et. al. 1988 [2] beschrieben und wird im Folgenden als SOM-Angéniol bezeichnet. Germar Schäfer hat damit 1991 an der FLW promoviert [3]; so bin ich dazu gekommen. Im vorigen Blogeintrag "△ Der selbstorganisierende Handlungsreisende - TSP mit SOM" habe ich meine "Jedermann-SOM" veröffentlicht und beschrieben [6]. Mit Excel und VBA ist nun wirklich jeder in der Lage, eigene Experimente durchzuführen und alles, was ich geschrieben habe, nachzuvollziehen.

Review zu TSP mit SOM

In den fast 35 Jahren finden sich immer wieder Veröffentlichungen; bereits 1999 zitiert der Review von Kate A. Smith 202 Quellen [14]. Allen gemeinsam sind die recht guten Ergebnisse dieser Heuristik und die schnelle Berechnung, natürlich immer bezogen auf den Zeitpunkt der Veröffentlichung. Das habe ich natürlich auch getan [4, 5]. Im Folgenden betrachte ich verschiedene Varianten, um Unterschiede und auch Gemeinsamkeiten zu verstehen.


"Der Handlungsreisende"
Wölker/DallE2 01-2013

Jan Faigl schrieb 2011 "Several SOM approaches have been proposed in the history of the SOM application to the TSP. In these approaches, the adaptation rules have been modified, heuristics have been considered, and combinations with genetic algorithms, memetic or immune system approaches have been proposed." [7], was er mit zahlreichen Quellen belegt.Andere hybride Verfahren verwenden 2-Opt zur Nachbearbeitung [8], andere lokale Optimierungen [11] oder eben meine Variante mit local-6-Opt [6] Ich gehe davon aus, dass noch viele weitere Verfahren zur Vor- und/oder Nachbearbeitung untersucht wurden.

Faigl weiter "Even though these new approaches improve the performance of SOM for the TSP, SOM is still not competitive with the combinatorial approaches to the TSP in both aspects: the solution quality and required computational time {12}." Tinarut and Leksakul [11] "the  quality  of  the  solution  obtained  from  the  proposed algorithm is lower than the algorithm from the previous research." Bei Brocki heißt es "It seems that SOM-2opt hybrid is not a very powerful algorithm for the TSP. It has been outperformed by both: EA and Lin-Kerninghan algorithms. It's speed might be impressive, but it still is slower than Lin-Kerninghan." [8]

1996 stellte Budinich fest, dass der SOM-TSP-Algorithmus dem Vergleich mit Simulated Annealing standhält [10]. Die von Faigl zitierten Autoren schreiben: "By incorporating the standard SOM into an evolutionary algorithm, the approach extends and improves its application to the Euclidean TSP. It improves the solution quality compared to previous SOM-based approaches in literature on standard test problems of sizes from 29 to 85,900 cities, with a similar or possibly less computation time." [9]. 

Also keine eindeutige Aussage. Damit aber forschungsrelevant; fast alle Arbeiten betrachten den Aufwand in Rechenzeit und den Nutzen als Abweichung von der optimalen bzw. besten bekannten Tour. Die Angabe von Rechenzeiten in Minuten und Sekunden ist aber abhängig von der Umgebung, der Implementierung und natürlich der Hardware [22], was in einigen Publikationen auch angegeben wird. [7,8,9,11,16,18] All dies hat sich in den 35 Jahren seit Angéniol rasant weiterentwickelt. Daher ist es fast unmöglich, die Leistungsdaten verschiedener Publikationen miteinander zu vergleichen.

Um ehrlich zu sein, müssten alle Algorithmen mit ihren Varianten implementiert werden. Dann kann der Entwickler seine Idee dagegen setzen. Besser wären Analysen der Laufzeitkomplexität der verschiedenen Ansätze, was empirisch leicht möglich ist. Leider werden in den von mir gesichteten Arbeiten immer nur wenige Ansätze verglichen. Und wenig überraschend ist der eigene Ansatz (fast) immer ein Fortschritt. Das muss so sein, sonst würde es nicht veröffentlicht.

Das Rechenzeitproblem der SOM

Der Algorithmus ist für alle Quellen vergleichbar. Dies erlaubt uns, die Laufzeitkomplexität abzuschätzen. Die Problemgröße n, d.h. die Anzahl der zu besuchenden Städte, ist natürlich allen gemeinsam.
  1. Auswahl eines Problems
    1. Vorverarbeitung des Problems 
    2. Wiederhole 
      1. Für alle Städte
        1. Wähle eine Stadt zufällig
        2. Suche das Winner-Neuron
        3. Erzeuge ggf. neue Neuronen
        4. Adaptiere Winner und seine Nachbarn
      2. einmal
      3. Lösche "tote" Neuronen
    3. bis die Adaption abgeschlossen ist
    4. Feststellen der Lösung
    5. Optimieren der Lösung
    6. Statistische Daten erfassen
  2.  Bis jedes Problem "oft genug" bearbeitet wurde
Die verschiedenen Einflussfaktoren
  • Netzstruktur
    • Da jedes der Neuronen jeder Stadt präsentiert wird, ist die Zahl m der aktiven Neuronen relevant. 
      m < 2n  [2], m ~ 2n [3] =2.5n [7], 2-16 [12], < 3n [16], = 5n [18] = n [20] <=600 [11]
    • In jeder Publikation suche ich, ob die Neuronenzahl statisch oder dynamisch ist, da dynamische Neuronen natürliche auch verwaltet werden müssen.
      dynamisch [2, 3, 8, 16], nur erzeugen [7], statisch [10, 11, 12, 18, 20]
    • Topologische Defekte sind (fast) unvermeidlich.
      Defektvermeidung [10] Zerlegen in Teillösungen und Rekombinieren [18] 
  • Das Training selbst
    • Zahl der Zyklen z, bis die Lösung erreicht ist oder sich der Lösung asymptotisch annähert. 
      z < 200 [3], z=500.000 [11], < 200 variabel [7] = 100.000 [12], =100 [20]
    • Dabei ist wichtig, ob das Abbruchkriterium "hart" ist und damit planbar wird
      keine Dynamik = STOP [3] 100 Zyklen = STOP [20]
    • n <= 1000 [3], n > 500 [10] 50 < n < 200 [12] 50< n < 200 [13] n < 1000 [11] n < 2.500 [20]
  • Statistische Auswertung der Trainingsläufe
    • Hinweise auf die Relevanz einer Publikation liefern die Anzahl der Probleme p, die in der Untersuchung enthalten sind
      aus [19] für [2], ~500 [3] p = 20 TSPLIB [11] TSPLIB [13]  =2000 random [12] =21 random mit Varianten [16], = 5 TSPLIB [18] =25 [20], =20 [9]
    • und deren Wiederholungen w für statistische Auswertungen [in 2, 3]
      w > 2.400 [2] w= 1.000 [3], = 100 [11] = 10 [10] = 50 [8] =20 [12] =50 [16] =16 mit 1-4 Clustern [18] w =10 [20] =20 [11] w=10 [9]
    • Optimale Lösungen für Test können auch konstruiert werden [17]. Das habe ich nur bei Angéniol et.al gefunden [3] 
  • Laufzeitkomplexität
    • Aussagen zu Laufzeitkomplexität finden sich in seltenen Fällen
      O (n²) [10][13][20] 3n² [16]
    • empirische Prüfung der Laufzeitkomplexität 
      Kapitel 6.5 [3]

Eine Systematik ist somit nicht wirklich erkennbar und die Validität ist aufgrund der meist geringen Stichproben eher in Frage zu stellen. In einigen Arbeiten werden auch Statistiken beschrieben [z.B. 2,3,9]. Kriterien, nach denen Grenzwerte festgelegt oder Wiederholungszahlen bestimmt werden, sind nur in Ansätzen erkennbar.

Sicherlich ist der Parameterraum sehr groß und ich bin überzeugt, dass es noch viele weitere Varianten gibt. Ich halte dies aber für schwache Argumente, da es nur um Rechenzeit geht, die Experimente beliebig wiederholbar, parallelisierbar und vollständig automatisierbar sind [3].

Außerdem ist der verwendete Code nur bei Schäfer [3] verfügbar. In [20] wird ein Link angegeben, der nicht funktioniert. Es wäre ein Leichtes, einen persistenten Download anzubieten, damit die Experimente reproduziert werden können. Als Physiker bin ich da ein wesentlich höheres Niveau gewohnt, was Schäfer, der auch Diplom-Physiker ist, in seiner Dissertation auch umgesetzt hat.

Zwischen-Resümee

So komme ich zu dem Schluss, dass die vielen Veröffentlichungen zwar nützlich sind, aber kein gültiges oder verifiziertes Wissen darstellen. Offensichtlich gibt es etwas Interessantes zu untersuchen, aber die Arbeiten stochern im Nebel der vielen Möglichkeiten. Nun, das ist genau das, was ich gerade getan habe, und in der Tat ist meine Arbeit konsistent mit dem, was andere Autoren beschreiben. Aber das ist kein Beweis.

Und nun zu etwas Grundsätzlichem

"It should also be noted that all of the above mentioned SOM approaches consider only the Euclidean variant of the TSP, i.e., distances between cities are Euclidean, while combinatorial approaches generally work with graphs." [7] In zwei Arbeiten werden spezielle nicht euklidische Varianten behandelt: Hindernisse umgehen [7] price collecting [16]. 

Offensichtlich wird viel Aufwand in diesen Ansatz gesteckt. Keiner der Autoren nennt eine konkrete Anwendung, wo auch immer. Vielleicht gibt es eine Anwendung, aber ich habe sie nicht gefunden. Das hat mich nicht überrascht, denn echte TSP sind nie euklidisch.

Also alles akademisches Geplänkel ohne praktischen Output.
Aber immer spannend und gut für Publikationen.

Ergänzung 21.01.2023

Mein Hauptkritikpunkt ist die geringe experimentelle Qualität, die dann natürlich auch die Validität der Ergebnisse beeinträchtigt. Da die "Experimente" schwer zu reproduzieren sind, ist eine Verifizierung kaum möglich.


"The ↪ Concorde solver uses the cutting-plane method, iteratively solving linear programming relaxations of the TSP." by William Cook

Dazu muss ein geeignetes experimentelles Umfeld geschaffen werden. William Cook, Professor für Combinatorics and Optimization an der University of Waterloo, hat auf seiner ↪ TSP-Seite viel zur Verfügung gestellt. Mit dem Programm Concorde für TSP werde ich geeignete Testszenarien erstellen. Die nächste Version meines VBA-Skripts wird dann dazu in der Lage sein.

[20] ergänzt

23.01.2023

   Text mit DeepL Write Beta überarbeitet.

29.01.2023

   TSPlib Universität Heidelberg [21] ergänzt. 

1.2.2023

   [9] noch ein paar Daten rausgezogen. [22] ergänzt.

4.5.2025

ResearchRabbit Collection veröffentlicht, auf Roboto umgestellt und mit DeepL-Write bearbeitet.

The ResearchRabbit Collection: Several SOM approaches have been proposed in the history of the SOM application to the TSP

ResearchRabbit is a research platform that enables you to discover and visualize relevant literature and scholars, create alerts for awesome newly-published papers, share collections with colleagues and the world, and so much more!

Quellen

  1. Wölker M (2000), "Analyse Logistischer Systeme mit Selbstorganisierenden Merkmalskarten". Thesis at: Universität Dortmund. Dortmund, Juni, 2000. Verlag Praxiswissen. [BibTeX] [URL]
  2. B. Angéniol, G. de la, C. Vaubois, J-Y L. Texier, Self-organizing feature maps and the travelling salesman problem, Neural Netw. 1 (1988) 289–293.
  3. G. Schäfer, Beitrag zur Optimierung von Kommissionierfahrten in Hochregallagergassen mittels neuronaler Netze,  Universität Dortmund, MB - FLW, 1991
  4. Jünemann R and Wölker M (1991), "Selbstlernende Systeme in der Kommissioniertechnik, Einsatz von Neuronalen Netzen", In Trends in Materialsflußsystemen, Tagungsband 9. Dortmunder Gespräche, pp. 251 - 259. TüV Rheinland. [BibTeX] [URL]
  5. Wölker M (1996), "Dem Denken abgeschaut, Neuronale Netze im praktischen Einsatz" Braunschweig, Wiesbaden , pp. 84 - 95. Vieweg, Facetten. [BibTeX] [URL]
  6. Martin Wölker, Blog: https://martins-wahre-logistik.blogspot.com/2023/01/der-selbstrganisierte-handlungsreisende.html, Pirmasens, Germany, 2018-2022, ausgelesen am: 17.1.2023, 18:06:08
  7. Jan Faigl, On the performance of self-organizing maps for the non-Euclidean Traveling Salesman Problem in the polygonal domain, Information Sciences 181 (2011) 4214–4229, Elsevier, doi:10.1016/j.ins.2011.05.019
  8. Lucas Brocki, Kohonen Self-Organizing Map for the Traveling Salesperson Problem, Polish-Japanese Institute of InformationTechnology, Warsaw, Poland, 2005 (aus PDF)
  9. Jean-Charles Créput, Abderrafiaa Koukam, A memetic neural network for the Euclidean traveling salesman problem, Neurocomputing 72 (4–6) (2009) 1250–1264. DOI 10.1016/j.neucom.2008.01.023
  10. Marco  Budinich, A Self-Organising Neural Network for the Travelling Salesman Problem that is Competitive with Simulated Annealing, Neural Computation Volume 8, Issue 2 - February  5, 1996  
  11. Pongpinyo Tinarut and Komgrit Leksakul, Hybrid Self-Organizing Map Approach for Traveling Salesman Problem, CMU J. Nat. Sci. (2019) Vol. 18(1) 27, DOI 10.12982/CMUJNS.2019.0003
  12. Joao P. A. Dantas, Andre N. Costa, Marcos R. O. A. Maximo, Takashi Yoneyama, Enhanced Self-Organizing Map Solution for the Traveling Salesman Problem, Sao Jose dos Campos – SP – Brazil, 2011, arXiv:2201.07208v1  [cs.NE]
  13. Hui-Dong Jin, Kwong-Sak Leung and Man-Leung Wong, An Integrated Self-Organizing Map for the Traveling Salesman Problem,  Hong Kong, P.R. CHINA, 2001
  14.  K. A. Smith, \Neural networks for combinatorial optimization: A review of more than a decade of research," INFORMS Journal on Computing, vol. 11, no. 1, pp. 15{34, 1999
  15. Jan Faigl and Geoffrey A. Hollinger, Self-Organizing Map for the Prize-Collecting Traveling Salesman Problem
  16. Faigl, J., Hollinger, G.A. (2014). Self-Organizing Map for the Prize-Collecting Traveling Salesman Problem. In: Villmann, T., Schleif, FM., Kaden, M., Lange, M. (eds) Advances in Self-Organizing Maps and Learning Vector Quantization. Advances in Intelligent Systems and Computing, vol 295. Springer, Cham. DOI 10.1007/978-3-319-07695-9_27
  17. E.L. Lawlar, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys. The Travelling Salesman Problem. John Wiley and Sons, Chichester, 1987.
  18. Bihter Avşar, Danial Esmaeili Aliabadi, Parallelized neural network system for solving Euclidean traveling salesman problem, Istanbul, Turkey, Applied Soft Computing, 1 September 2015
  19. Durbin, R., Willshaw, D. An analogue approach to the travelling salesman problem using an elastic net method. Nature 326, 689–691 (1987). doi 10.1038/326689a0
  20. Kwong-Sak Leunga, Hui-Dong Jin, Zong-Ben Xuc, An expanding self-organizing neural network for the traveling salesman problem,Neurocomputing 62 (2004) 267 – 292, doi:10.1016/j.neucom.2004.02.006
  21. Gerhard Reinelt, TSPLIB 95, Universität Heidelberg, Institut für Angewandte Mathematik, 2016
  22. Jack J. Dongarra (2006) Performance of various computers using standard linear equations software. In: Technical Report CS-89-85, Department of Computer Science, University of Tennessee, USA, http://www.netlib.org/benchmark/performance.ps


Blog: , Seite:
Version: 1.3 Mai 2023, Kontakt: E-Mail Martin Wölker
Pirmasens, Germany, 2018-, ausgelesen am: , Licence CC BY-NC-SA

Kommentare

Kommentar veröffentlichen