Können gradientenbasierte Optimierungstechniken verwendet werden, um Travelling Salesperson zu lösen?

Können gradientenbasierte Optimierungstechniken verwendet werden, um das Problem des reisenden Verkäufers zu lösen?

Das Problem des reisenden Verkäufers ist ein bekanntes Optimierungsproblem, bei dem ein Verkäufer herausfinden muss, in welcher Reihenfolge er durch „n“ Städte reisen muss – so dass die zurückgelegte Gesamtstrecke minimal ist und jede Stadt einmal besucht wird.

Die „Zielfunktion“ in diesem Problem ist eine Funktion, die „unterschiedliche Städteordnungen“ auf die „Gesamtentfernung entsprechend dieser Städteordnung“ abbildet. Als Beispiel könnte die Zielfunktion etwa so aussehen:

Geben Sie hier die Bildbeschreibung ein

Meine Frage: Im Fall des Problems des reisenden Verkäufers - ist die Zielfunktion im gleichen Sinne "differenzierbar", wie die Gleichung einer Parabel (y = x ^ 2) differenzierbar ist?

Auf den ersten Blick scheint die Antwort offensichtlich „nein“ zu sein. Wie können wir schließlich die Ableitung der obigen Funktion bilden? Die obige Funktion ist nicht über einen kontinuierlichen Bereich definiert!

Können wir also sagen, dass im Fall des Problems des Handlungsreisenden (dh diskreter kombinatorischer Optimierungsprobleme) die Zielfunktionen „nicht differenzierbar“ sind? Wenn dies zutrifft – ist es dann „unmöglich, die verlaufsbasierte Optimierung für reisende Verkäufer zu verwenden“?

Oder können die Zielfunktionen auch in solchen Fällen noch als differenzierbar bezeichnet werden?

Kann sich bitte jemand dazu äußern?

Danke!

Vielleicht möchten Sie sich Vishnois „Algorithms for Convex Optimization“ ansehen. Es behandelt kontinuierliche Optimierungsalgorithmen für diskrete/kombinatorische Probleme.
@ VSeH: vielen Dank für deine Antwort! Ich habe Schwierigkeiten, diesen folgenden Punkt zu verstehen: Wenn die Zielfunktion diskret ist und nicht über eine kontinuierliche Domäne definiert ist, wird die Zielfunktion als "nicht differenzierbar" bezeichnet? Können wir gradientenbasierte Optimierungstechniken auf "nicht differenzierbare Zielfunktionen" anwenden?
Im Allgemeinen reicht ein einfacher Gradient nicht aus, um ein diskretes Problem zu lösen (in einigen besonderen Fällen kann es jedoch zu einer vollständigen Unimodularität kommen). Was oft getan wird, ist, die Variablen in der Formulierung auf reale Werte zu entspannen, dann die entspannte Formulierung zu lösen (im Fall der linearen Programmierung kann dies effizient über den Simplex-Algorithmus erfolgen - dies ist ein Gradienten-basierter Algorithmus) und dann eine Verzweigung verwenden & gebundener Algorithmus, um die Variablen auf Ganzzahlen festzulegen. Dies ergibt im Allgemeinen einen exponentiellen Algorithmus, kann aber sehr gute duale Grenzen liefern und in der Praxis sehr gut funktionieren.
Bitte nicht so laut schreien.
Nicht differenzierbar bedeutet, dass die Ableitung im Bereich des Ziels nicht existiert, was bei diskreten Problemen nicht der Fall sein muss, aber häufig vorkommt. Vishnoi erklärt das in seinem Buch ganz klar und weist auf einige neue Entwicklungen bezüglich der TSP hin, die konvexe Optimierung verwenden. Das Max-Flow-Problem ist ein Beispiel für ein kombinatorisches Problem, das mit Gradientenverfahren gelöst wird, und zwar effizienter.

Antworten (2)

Sicherlich nicht.

Die objektive Funktion des TSP ist nichts anderes als ein Feld lokaler Minima, in denen jedes kontinuierliche Verfahren (z. B. durch Interpolation erhalten) gefangen wäre. Und es wäre dumm, Zwischenkoordinaten zu versuchen, wenn Sie wissen, dass die Lösung an den angegebenen Datenpunkten auftritt.

TSP ist ein kombinatorisches Problem, Punkt.

Betrachten Sie als Analogie die Minimierung von

Sünde ⁡ X + ( X 1000 − 1 ) 2

Geben Sie hier die Bildbeschreibung ein

Ein besonderer Fall der kontinuierlichen Optimierung ist die lineare Programmierung (LP), bei der wir eine lineare Zielfunktion und eine Reihe von linearen Einschränkungen für Variablen haben (auf Realwert beschränkt). LPs sind konvex und können effizient über gradientenbasierte Algorithmen wie den Simplex-Algorithmus gelöst werden.
Ein verwandtes Problem ist die gemischt-ganzzahlige lineare Programmierung (MILP), bei der wir auch eine lineare Zielfunktion und einen Satz linearer Einschränkungen haben, aber dieses Mal können die Variablen auf Ganzzahlen beschränkt werden. Das bietet viel mehr Ausdruckskraft, und das können wir jedem leicht zeigen N P -Problem kann als (polynomiell kleines) MILP-Problem ausgedrückt werden. Es ist jedoch nicht mehr garantiert, dass die Gradientenverfahren zum Optimum konvergieren, da das Problem nun diskret ist. Aber wenn wir die Integritätsbedingungen für Variablen lockern, ergibt das Optimum oft eine starke duale Grenze für unser Problem. In Kombination mit der Baumsuche (über einen Zweig und eine Grenze) kann dies die Auflösung drastisch beschleunigen (obwohl die Komplexität exponentiell bleibt).

Es ist immer noch möglich, kombinatorische Probleme mit konvexen Funktionen auszudrücken. Unter Verwendung eines exponentiellen Satzes von Beschränkungen können wir das Problem des Handlungsreisenden als lineares Problem ausdrücken. Dies kann erreicht werden, indem das Problem als SAT-Instanz ausgedrückt wird. Die durch die entsprechenden binären Vektoren gebildete Menge von Punkten wird immer konvex sein, sodass wir alle Facetten der konvexen Hülle als Beschränkungen nehmen können. Leider ist bekannt, dass wir immer bei einer exponentiellen Anzahl von Facetten landen werden, egal wie wir das Problem des Handlungsreisenden modellieren. Tatsächlich kennen wir noch keinen polynomiellen Zeitalgorithmus für N P -schwere Probleme.

Der Simplex-Algorithmus ist nicht gradientenbasiert, sondern kombinatorisch. Interior-Point-Methoden sind gradientenbasiert (und tatsächlich 2. Ordnung). Außerdem bedeutet ein nichtkonvexes Problem nicht notwendigerweise, dass Gradienten-basierte Verfahren nicht funktionieren. So ziemlich das gesamte NN-Training ist nicht konvex und wird mit SGD durchgeführt.
Wikipedia definiert eine Gradientenmethode als einen Algorithmus, bei dem Suchrichtungen durch den Gradienten der Funktion am aktuellen Punkt definiert werden. Beim Simplex-Algorithmus wird der nächste Drehpunkt durch Analyse des Gradienten bestimmt. Aber ich stimme zu, dass innere Punktmethoden eher verlaufsartig sind. Im Allgemeinen ist der Gradient für eine nicht konvexe Funktion nur garantiert, um ein lokales Optimum zu finden, sodass das Problem streng genommen nicht "gelöst" wird.
Ich weiß nicht, woher Sie Ihre Informationen über LPs bekommen, aber die Simplex-Methode wählt keinen Drehpunkt, indem sie den Gradienten analysiert (und um pedantisch zu sein, keine Erwähnung von "Gradient" im Wiki-Artikel über LPs). Verweisen Sie jedoch ansonsten auf die entsprechende Referenz. Das Problem nicht "lösen" zu können, wie beim Auffinden des globalen Optimierers, ist nicht dasselbe wie "Gradientenmethoden funktionieren nicht mehr", wie in Ihrer Antwort angegeben.
Pivots werden entlang Variablen gewählt, für die die Ableitung des Ziels in Bezug auf diese Variable negativ ist (und oft als die steilste gewählt wird). Der Simplex ist einem Gradientenabstieg ziemlich ähnlich, außer dass er darauf beschränkt ist, sich an Kanten statt irgendwo im Polytop zu bewegen. Ich werde das "nicht mehr funktionieren" mit etwas Präziserem bearbeiten.
Tatsächlich ist dies kein Problem der Konvexität, sondern eher, dass das Problem nicht mehr kontinuierlich ist.
Ich stimme zu, und Sie haben völlig Recht, aber ich würde den Simplex-Algorithmus immer noch nicht als Beispiel für „gradientenbasiert“ verwenden, da der Gradient die Suchrichtung nicht gemäß der Wiki-Definition definiert, sondern sie „leitet“. suchen. Ferner ist das Simplex-Verfahren genau und kombinatorisch, im Gegensatz zu beispielsweise einem Gradientenabstieg. Aber ich schweife ab.
Können gradientenbasierte Optimierungstechniken verwendet werden, um Travelling Salesperson zu lösen?
AntwortenHierDatenschutz-Bestimmungen1y, 0v