Travelling Salesman Problem mit dem neuronalen Netz

7

Ich war neugierig, ob es neue Entwicklungen bei der Lösung des Problems der Handlungsreisenden mit einem wiederkehrenden neuronalen Hopfield-Netzwerk gab. Ich habe das Gefühl, dass ich etwas über die jüngste Forschung gesehen habe, die hier einen Durchbruch erzielt hat, aber ich kann die wissenschaftlichen Arbeiten nirgendwo finden. Ist jemandem eine neue, neuartige Entwicklung in diesem Bereich bekannt?

rauben
quelle
Welche Recherchen haben Sie durchgeführt? Haben Sie in Google Scholar gesucht?
DW
Ich habe das Papier über Stack LSTMs gelesen, von dem mir gesagt wurde, dass es helfen könnte: arxiv.org/pdf/1506.02516.pdf , aber ich sehe den Zusammenhang nicht.
Rob
Schauen Sie

Antworten:

4

Dieser mittlere Beitrag listet die neuesten (natürlich nicht vollständigen) Studien im Bereich der kombinatorischen Optimierung auf. Alle drei Artikel verwenden Deep Reinforcement Learning, für das kein Trainingssatz erforderlich ist, das jedoch vollständig aus eigenen Erfahrungen gelernt wird.

Ich arbeite seit einiger Zeit an dem ersten Papier und die Inferenzzeit liegt im Millisekundenbereich. Ihren Experimenten zufolge beträgt das Approximationsverhältnis (eine Metrik, mit der sie ihre eigene Methode vergleichen) für 1000-1200 Testfälle 1,11.

Tahsin Kose
quelle
7

Es gibt viele Artikel über die Verwendung künstlicher neuronaler Netze zur Lösung von TSP, einschließlich wiederkehrender und Hopfield-Netze, und sie "gelingen" im groben Sinne, aber bisher scheint es keine Beweise dafür zu geben, dass die Techniken in irgendeiner Weise (stark?) sind. anderen algorithmischen Ansätzen überlegen, daher ist es im Moment eher eine Art Forschungskuriosität. Die Verwendung von ANNs für dieses Problem ist in der Tat aus der Sicht der kombinatorischen Algorithmusik nicht intuitiv, und die Mechanismen, mit denen die Ein- / Ausgänge des Problems codiert werden, sind neu und variieren tendenziell und sind möglicherweise noch nicht so standardisiert. Die Autoren scheinen vielleicht mehr daran interessiert zu sein, "Proof of Concept" zu demonstrieren, und ein Vergleich mit anderen Algorithmus-Typen scheint seltener zu sein (es gibt einige im letzten Artikel). siehe zB

vzn
quelle
3
Ich glaube, dass es neuronalen Netzen möglich sein wird, innerhalb eines Konfidenzintervalls mit einer gewissen Konsistenz zu lösen. Wie in a top 5% solution 85% of the timewar ich nur neugierig zu erfahren, wie diese Art von Problem mit einem neuronalen Netzwerk gelöst wurde, weil ich gerade das Deepmind-Papier über neuronale Stapel gelesen habe. Es scheint, dass neuronale Netze, insbesondere Deep Reinforcement-Lernnetzwerke, jedes Problem lösen können, das ein genetischer Algorithmus in der Vergangenheit hatte. Das war also der Fortschritt in meinem Kopf.
Rob
3

Ich habe dies zu einer anderen Antwort kommentiert, aber ich denke, es verdient eine eigene Antwort. Einige Google Brain-Stipendiaten stellten in der Veröffentlichung NEURAL COMBINATORIAL OPTIMIZATION WITH REINFORCEMENT LEARNING 2017 eine Methode zur Lösung von TSP unter Verwendung einer Architektur vor, die an seq2seq erinnert . In der Einleitung rufen sie ein (1985) Papier heraus, das Hopfield-Netzwerke verwendet, um TSP zu lösen. Diese Idee gibt es also schon eine Weile.

Eine andere Antwort erwähnte das Papier "Pointer Networks" von 2015. Es hat etwas Ähnliches wie dieses Papier gemacht, aber es war ein überwachter Algorithmus - es brauchte beschriftete Daten. Das Papier von 2017 erfordert dies nicht (durch Verwendung einer negativen Tourlänge als Belohnungssignal in einem Verstärkungslernalgorithmus).

Die Heuristik "Immer auf neuronale Netze setzen" hat mich nicht enttäuscht (aber andererseits habe ich noch nie einen KI-Winter durchgemacht).

Sam H.
quelle
1
Achtung: Das Papier macht deutlich, dass ihre Ergebnisse bei der Lösung von TSP "weit vom Stand der Technik entfernt" sind. Es ist ein bisschen wie einen tanzenden Hund zu bestaunen. Der Punkt ist nicht, dass es besonders gut tanzt; Das Erstaunliche ist, dass es alles kann, was sich dem Tanzen nähert.
DW
Vielen Dank für Ihre Antwort. Ich freue mich, diese Neugier wieder aufgreifen zu können!
Rob
Ich kenne DW nicht, ich erinnere mich, als Deep Learning der tanzende Hund der Bilderkennung war ... und Sprachmodellierung ... und Schach ... und Go ...
Sam H.
0

Ich sehe keinen Grund zu der Annahme, dass wiederkehrende neuronale Netze von Hopfield bei dem Problem der reisenden Verkäufer helfen.

Neuronale Netze sind eine Form des maschinellen Lernens und sie sind effektiv, wenn wir einen gekennzeichneten Trainingssatz haben: eine Reihe von Instanzen, in denen wir jeweils die Eingabe (den Merkmalsvektor) und die richtige Bezeichnung / Klassifizierung / Ausgabe kennen. Maschinelles Lernen ist oft nützlich, um Muster zu finden, wenn wir nicht genau wissen, wie wir die richtige Ausgabe definieren sollen. "Wir wissen es, wenn wir es sehen".

Im Gegensatz dazu ist das Problem des Handlungsreisenden ein kombinatorisches Problem: Wir möchten den kürzesten Weg durch eine Grafik kennen. Es ist kein Problem, die richtige Ausgabe zu definieren oder anzugeben: Es ist ein genau definiertes mathematisches Problem. Es gibt keinen offensichtlichen Grund zu der Annahme, dass maschinelles Lernen für das Problem der reisenden Verkäufer nützlich wäre.

DW
quelle
In diesem Dokument wird auf den Versuch verwiesen, ein neuronales Netzwerk auf das Problem des Handlungsreisenden anzuwenden: arxiv.org/pdf/1506.03134.pdf . Ich bin also nicht ganz verrückt. Meine Neugier auf das Thema war, wie es genutzt werden könnte, weil ich mir keinen Weg vorstellen konnte. Ich weiß es zu schätzen, dass Sie sich die Zeit genommen haben, und wenn Sie den Artikel durchsehen, würde ich gerne hören, was Sie denken.
Rob
In diesem Artikel wird auch auf die Verwendung eines Hopfield-Netzwerks zur Lösung des Problems der reisenden Verkäufer cdn.intechopen.com/pdfs-wm/4612.pdf verwiesen , also nicht auf das totale Schlagwort Bingo ;-)
Rob
@Rob, dass jemand etwas geschrieben und auf arXiv gepostet hat, heißt nicht, dass es nicht weit weg ist. Wenn dies nicht ernsthaft überprüft wird, wäre ich sehr vorsichtig.
vonbrand
1
Einige Doktoranden von UC Berkeley, die für Google arbeiten, klingen für mich wie ein seriöses Team .....
Rob
Hier ist das Google Brain-Team, das die TSP-Optimierung anhand eines seq2seq-Modells zeigt. Openreview.net/pdf?id=rJY3vK9eg "Wir konzentrieren uns auf das Problem des Handlungsreisenden (TSP) und trainieren ein wiederkehrendes neuronales Netzwerk, das bei einer Reihe von Stadtkoordinaten a vorhersagt Verteilung über verschiedene Stadtpermutationen. Mit der negativen Tourlänge als Belohnungssignal optimieren wir die Parameter des wiederkehrenden neuronalen Netzwerks mithilfe einer Policy-Gradient-Methode. "
Sam H.