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 selbstorganisierte Handlungsreisende - TSP using SOM" habe ich meine "Jedermann-SOM" veröffentlicht und beschrieben [6]. Mit Excel und VBA ist nun wirklich jeder in der Lage, seine eigenen Experimente zu machen und all das nachzuvollziehen, was ich geschrieben habe.

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 Autoren, die von Faigl zitiert werden, 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 with regard to the previous SOM-based approaches of the literature on standard test problems of sizes from 29 to 85 900 cities, with a similar or a possibly less computation time." [9]. 

Also keine eindeutige Aussage. Damit aber forschungsrelevant; fast jede Arbeit betrachtet den Aufwand in Rechenzeit und den Nutzen als Abweichung von der optimalen bzw. besten bekannten Tour. Aber Angaben von Rechenzeiten in Minuten und Sekunden sind nun mal abhängig von der Umgebung, der Implementierung und natürlich der Hardware [22], was einige Publikationen auch angeben. [7,8,9,11,16,18] All dies hat sich in den 35 Jahren seit Angéniol rasant weiterentwickelt. Damit ist es fast unmöglich Performancemessungen verschiedener Publikationen miteinander zu vergleichen.

Bei ehrlicher Betrachtung müssten alle Algorithmen mit ihren Varianten implementiert werden. Dann kann der Entwickler seine Idee dagegen stellen. Besser wären Analysen der Laufzeitkomplexität der verschiedenen Ansätze, das ist empirisch leicht möglich. 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 auch so sein, sonst würde es nicht veröffentlicht werden.

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 also nicht wirklich erkennbar und die Validität ist angesichts der meist geringen Stichproben eher in Frage zu stellen. Einige Arbeiten beschreiben auch die Statistiken [z.B. 2,3,9]. Kriterien, nach denen Grenzwerte festgelegt oder Wiederholungszahlen bestimmt werden, sind nur in Ansätzen erkennbar.

Sicherlich ist der Raum der Parameter sehr groß und ich bin der Überzeugung, dass noch viele weitere Varianten vorhanden sind. 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 sehr 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 Veröffentlichungen.

Ergänzung 21.01.2023

Die geringe experimentelle Qualität, die dann natürlich auch die Validität der Ergebnisse beeinträchtigt, ist mein Hauptkritikpunkt. 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.


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