Heuristik-Ansatz zur Touroptimierung

Einsatz Künstlicher Neuronaler Netze

Welcher Weg soll gewählt werden, damit die insgesamt zurückgelegte Entfernung so gering wie möglich ist? Diese Probleme aus der Praxis werden im Travelling Salesman Problem idealisiert:

Ein Handlungsreisender möchte eine Anzahl von Kunden in verschiedenen Orten besuchen.
Für die Entsorgung muss eine Sammeltour zusammengestellt werden.
Eine Spedition soll verschiedene Kunden in einer Rolltour anfahren.

Solche Probleme können mit verschiedenen Methoden berechnet werden. Klassisch sind deterministische Verfahren, bei denen das Problem zerlegt (top down) und die einzelnen Schritte in einem Computerprogramm algorithmisiert werden. Die oben beschriebenen Standardprobleme gehören zur Klasse der schwer lösbaren Probleme (d.h. NP-vollständig) und sind daher nur für kleine Ordnungen deterministisch exakt lösbar. Das folgende Programm berechnet alle möglichen Kombinationen mit einem rekursiven Algorithmus und liefert das optimale Ergebnis. Dies allerdings um den Preis exponentieller Rechenzeit.

Die Leistungen von bekannten Algorithmen lassen sich stark verbessern, wenn heuristische Eröffnungs- bzw. Verbesserungsverfahren eingeführt werden. Verständlich und sehr knapp stellt Janson betrachtet 3 Verfahren []. Dabei wird allerdings in Kauf genommen, dass statt der optimalen Lösung ein Suboptimum gefunden wird. Es ist also immer notwendig zwischen Präzision der Lösung und der Geschwindigkeit des Vorgehens zu unterscheiden.

Auf der Seite TSPvis.com findet ihr ein paar schöne Demoprogramme: "The goal of this site is to be an educational resource to help visualize, learn, and develop different algorithms for the traveling salesman problem in a way that's easily accessible. As you apply different algorithms, the current best path is saved and used as input to whatever you run next. (e.g. shortest path first -> branch and bound). The order in which you apply different algorithms to the problem is sometimes referred to the meta-heuristic strategy."

Hier können die einzelnen Aspekte unterschiedlicher Ansätze nur unvollständig herausgearbeitet werden. Die Arbeit von Michels [BibTeX] demonstriert einen verteilten Blackboard-Ansatz, der verschiedene Verfahren quasi parallel nutzt. Sind klassische und symbolorientierte weit verbreitet, so soll hier der Einsatz eines konnektionistischen Systems an einem Beispiel des Travelling Salesman Problems demonstriert werden. Insbesondere wird die Praxistauglichkeit im Hinblick auf Qualität der Lösung in Relation zum Aufwand betrachtet.

Wie funktioniert das Training der Tour?

Alle Städte für die Tour haben Koordinaten (x, y) in einer Landkarte. Die Koordinaten sind die Eingaben für das Neuronale Training. Somit benötigt die Selbstorganisierende Merkmalskarte zwei Eingabeneuronen. Die Neuronen in der Kartenschicht sind in einem geschlossenen Ring angeordnet.

Da genau zwei Eingabeneuronen vorhanden sind, sind die Gewichtsvektoren die Koordinaten der Neuronen in der Landkarte. Durchläuft man die Positionen der Neuronen im Ring nacheinander, so fährt man auf der Landkarte eine Rundtour. Die Idee besteht nun darin, dass die Positionen der Neuronen im Ring an die gewünschten Positionen angepasst werden.

Das Erlernen der Rundtour kann man sich gut an einem Gummiband veranschaulichen, dass nach und nach zu den einzelnen Positionen gezogen wird. In jedem Lernzyklus müssen die Positionen in einer zufälligen Reihenfolge gelernt werden.

Berechnung einer Tour durch 40 Positionen: Das Bild zeigt im dritten Lernzyklus die Adaption des Rings aus Neuronen zur gelben Position oben rechts. Das weiße Neuron liegt der aktuellen Position am nächsten und wird daher Reizzentrum. Es macht den größten Anpassungsschritt in Richtung auf die aktuelle Position. Der Ring verformt sich zur gewünschten Position.

Angefangen von einem glatten Ring mit wenigen Neuronen (nach 2 Lernzyklen) formt sich schon nach wenigen Lernzyklen eine Rundreise durch das gesamte Gebiet (4 Lernzyklen). In der mittleren Bildreihe sind mehr als 80 Neuronen vorhanden. Der Ring bekommt nach und nach immer mehr Dellen und Beulen, da sich die Neuronen immer mehr für einzelne Positionen spezialisieren. In der unteren Reihe werden es immer weniger Neuronen. Am Ende werden die Neuronen einfach den Position en zugeordnet und die Tour ist fertig.

Die Heuristik mittels Künstlicher Neuronaler Netze kann schnell berechnet werden und ist sowohl für kleine als auch für große Probleme ca. 3% ungünstiger als optimale Lösungen. Angefangen mit der ersten Publikation 1988 [1] über eigene Arbeiten in den 1990ern [2,3,4,5,6,7], wird dieser Ansatz immer wieder mal betrachtet [8,9,10]. Eine Implementierung in kommerzieller Software ist mir nicht bekannt.

Nachtrag vom 14.12.2020

Ich habe ein wenig weiter recherchiert. Interessanter weise gibt es immer wieder mal Veröffentlichungen auch in wissenschaftlichen Magazinen, die eigentlich wenig Neues bringen. Sehr häufig wird das excellente Abbruchverhalten, das Schäfer in seiner Dissertation schon 1991 beschreibt [2] nicht zitiert. Viele Arbeiten würde ich unter Reverse-Science verbuchen. Ist schon da gewesen, aber man kann ja noch mal eine Publikation damit machen. Bei vielen ist die Literatur dazu noch schwach.

Zitierhilfe

Wölker M (2020), "Heuristik-Ansatz zur Touroptimierung", Blog. Pirmasens, Germany, December, 2020. [BibTeX] [URL]

Quellen

Angéniol B, de la Croix Vaubois G and le Texier J (1988), "Self-Organizing Feature Maps and the Travelling Salesman Problem", Neural Networks. Vol. 1, pp. 289-293. [BibTeX]
Schäfer G (1991), "Beitrag zur Optimierung von Kommissionierfahrten in Hochregallagergassen mittels neuronaler Netze". Thesis at: Universität Dortmund, MB, LS Förder- und Lagerwesen.[BibTeX]
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]
Jünemann R and Wölker M (1992), "Jahrbuch der Logistik 1992" Düsseldorf Vol. 6, pp. 164 -167. Handelsblatt. [BibTeX]
Wölker M (1996), "Dem Denken abgeschaut, Neuronale Netze im praktischen Einsatz" Braunschweig, Wiesbaden , pp. 84 - 95. Vieweg, Facetten. [BibTeX] [URL]
Michels O (1995), "Entwicklung und Implementierung einer Plattform zur Lösung des Traveling Salesman Problems in einem Rechnernetz". Thesis at: Universität Dortmund. Dortmund, December, 1995.[BibTeX] [URL]
Wölker M (2000), "Analyse Logistischer Systeme mit Selbstorganisierenden Merkmalskarten". Thesis at: Universität Dortmund. Dortmund, Juni, 2000. Verlag Praxiswissen. [BibTeX] [URL]
Brocki £ and Koržinek D (2007), "Kohonen Self-Organizing Map for the Traveling Salesperson Problem", Recent Advances in Mechatronics. [BibTeX] [URL]
Vicente D (2018), "Using Self-Organizing Maps to solve the Traveling Salesman Problem", Webpage., January, 2018. [BibTeX] [URL]
Wikipedia, Die freie Enzyklopädie. „Selbstorganisierende Karte“. In: Bearbeitungsstand: 11. Januar 2020, 16:52 UTC. (Abgerufen: 12. Dezember 2020, 12:00 UTC) [URL]