Studie 01 · Reinforcement Learning · Graph-Neuronale Netze

Graphmodell zur Erstellung eines TSP-Pfades mit Reinforcement Learning

2018.09–2021.06 · Forschungsstudent im Bachelorstudium

Ich habe ein graphbasiertes TSP-Suchprogramm implementiert, das mit Reinforcement Learning die nächste einzufügende Stadt auswählt.

1Grafische Darstellung
Stadt, Entfernung, Besuchsstatus
2Structure2Vec + Q-learning
Berechnung der Q-Werte für jede Stadt
3Städteauswahl und Pfadeinfügung
Fügen Sie die vom Modell mithilfe von Heuristiken ausgewählte Stadt ein.

Aufbau des Reinforcement Learning

Zustand: Verbindungen zwischen Städten (Adjazenzmatrix), Entfernungen und bereits in der Route enthaltene Städte
Aktion: Die nächste Stadt für die Route auswählen
Belohnung: Die zusätzliche Routenlänge durch die neue Stadt wird direkt abgezogen

Implementierung unter Bezugnahme auf die Forschung zur Graphkombinationsoptimierung von NeurIPS 2017

Reinforcement learningStructure2VecDeep Q-learningGraph neural networkTensorFlowNumPy

Direkt zugewiesene Rolle und Ergebnis

Forschungsziel: Beim TSP wächst die Zahl möglicher Routen mit jeder weiteren Stadt rasant. Ziel war es, schneller als bestehende Algorithmen kurze Routen zu finden. Gemeinsam mit meinem betreuenden Professor bin ich das Problem mit Reinforcement Learning angegangen.
Zugewiesene Rolle: Basierend auf der Graphdarstellung und den Q-Learning-Konzepten aus der Referenzveröffentlichung habe ich experimentellen Code implementiert, der die TSP-Umgebung, das Modell, die Lernschleife und die Einfügeregel verbindet.
Ergebnisse: Ich habe ein Suchprogramm erstellt, das Standort, Entfernung und Besuchsstatus der Städte als Graph einliest und die vom Modell gewählte Stadt mit einer Einfügeheuristik in die Route aufnimmt. In Vergleichsexperimenten des öffentlichen Codes mit Baselines habe ich auch ermittelt, warum das Lernen nicht wie vorgesehen funktionierte.

Was ich intern implementiert und analysiert habe

Graphenumgebung mit Knoten, Kanten, Besuchsstatus und Pfadkosten
Structure2Vec-Einbettung und Q-Wert-Bewertung
Erkundungsschleife mit mehrstufiger Belohnungsakkumulation und Erfahrungssammlung
Eine Struktur, in der das Modell die Städte auswählt und die Einfügeheuristik die Einfügeposition bestimmt.

Basierend auf Forschungs-/öffentlichem Modell

NeurIPS 2017 Structure2Vec/Reinforcement Learning-Ansatz für die Forschung zur kombinatorischen Optimierung von Graphen

Experimentergebnisse und Fehlversuche

Im Vergleich zur zufälligen Einfügung wurde beim Kurzschlusslernen keine Verbesserung festgestellt.

Nach dem Training mit den Originaleinstellungen lieferte die Strategie für alle Städte und für die in numerischer Reihenfolge ausgewählten Städte denselben Q-Wert.

TensorFlow 2.15
3 Zufallsstarts
Episoden: 10.000 → 100

Animation der Lernstrategie und des optimalen Einfügepfads beim Erstellen von Pfaden für jeweils eine Stadt in 50 identischen Städten. Die Lernstrategie wählt die Städte in numerischer Reihenfolge aus und erstellt einen Pfad, der 1,12-mal länger ist als der von OR-Tools, während die längste Kanteneinfügung einen 1,08-mal längeren Pfad erzeugt. — Der Pfadgenerierungsprozess für ein Problem mit 50 Städten. Die Lernstrategie (links) wählte die Städte in numerischer Reihenfolge aus und erzeugte einen Pfad, der 1,12-mal länger war als die OR-Tools-Lösung. Die Methode der maximalen Einfügung (rechts) erzeugte einen 1,08-mal längeren Pfad. Die folgende Tabelle zeigt den Durchschnitt mehrerer Probleme.

+12%Das obige 50-Grad-Beispiel · Länger als OR-Tools Pfad
Verbesserung nicht bestätigtVerkürzte Lernzeit im Vergleich zum Einfügen in zufälliger Reihenfolge
2 DingeUrsache im Code gefunden

Erwartung
Die Städte, in denen der gelernte Q-Wert den kürzesten Weg ergibt. Auswählen
Damalige Einschätzung
Die Routenkosten sanken mit dem Training, erreichten aber nie das Optimum; ich führte das auf zu wenig Exploration bei vielen Städten zurück
Tatsächlich
Alle Städte haben denselben Q-Wert und wurden daher in numerischer Reihenfolge ausgewählt.
Ursache
Der Wert stieg bei unnormalisierter Nachbarsumme sprunghaft an, und das TD-Ziel berücksichtigte nur die Startstadt.

Problem und Lösung

ProblemDie Matrixgröße hängt von der Anzahl der Städte ab, daher ließ sie sich nicht direkt in ein neuronales Netz mit fester Eingabegröße geben.
Gelöst.Structure2Vec erzeugt für jede Stadt eine Einbettung, und ein Bewertungsnetz vergibt jeder noch nicht besuchten Stadt einen Q-Wert.
ProblemDie Auswahl der nächsten Stadt allein bestimmt nicht deren Position auf dem Pfad.
Gelöst.Das Lernmodell übernimmt die Städteauswahl, während eine Heuristik die Einfügungsposition findet, die die Pfadlängenzunahme minimiert. Beides wird kombiniert.
ProblemSelbst wenn ein kurzer Weg erscheint, ist es schwer zu erkennen, ob dies auf einen Lerneffekt zurückzuführen ist. oder der Effekt der Einfügeregel.
Analyse und VerifizierungWir haben dieselbe Einfügeregel auf eine zufällige Städtereihenfolge angewendet, um einen Vergleich zu ermöglichen, und die Berechnung der Q-Werte und TD-Zielwerte verfolgt. Wir konnten keine Verbesserung der Lernstrategie im Kurzschlusslernverfahren feststellen.

Vergleich der Experimente und detaillierte Ergebnisse

Die von der Lernstrategie und OR-Tools für dieselben 50 Städte erstellten Pfade. Der Lernpfad ist 1,12-mal länger, wobei sich die langen Kanten links kreuzen. — Dies sind die beiden abgeschlossenen Pfade. Der Pfad der Lernrichtlinie (links) ist 1,12-mal länger als der Pfad der OR-Tools, und die langen Kanten schneiden sich.

Vier Szenen, die das Stapeln von Pfaden im 20-Städte-Problem zeigen. Ausgewählte Städte, unterbrochene Kanten und neue Kanten werden angezeigt. — Dies ist die Methode zum Erstellen von Pfaden. Wenn die Richtlinie die nächste Stadt (oranger Punkt) auswählt, schneidet die Einfügefunktion die Kante (gestrichelte Linie) an der Stelle, an der sich der Pfad am wenigsten ausdehnt, und verbindet sie mit einer neuen Kante.

Verhältnis der durchschnittlichen Pfadlängen nach Methode im 50-Städte- und 100-Städte-Problem. Lernstrategien 1.13 und 1.12, zufällige Einfügung 1.14 und 1.13, maximale Einfügung 1.05 und 1.06. — Durchschnittliche Pfadlänge mit OR-Tools auf 1,00 eingestellt. Die Lernrichtlinie war fast die gleiche wie bei der zufälligen geordneten Einfügung und war länger als die einfache engste Einfügung.

Durchschnittliche Routenlänge im Verhältnis zur OR-Tools-Lösung · Trainingsbereich 30–400 Städte · Die gelernte Strategie lieferte mit allen drei Seeds dieselbe Route
Anzahl der Städte (Anzahl der Probleme)	Trainingsstrategie	Zufällige Reihenfolge + Einfügen	Neu einfügen	Nächste Nachbarn	Trainingsstrategie vs. Zufall (Wilcoxon-Test)
20 (100) · Außerhalb des Lernbereichs	1.11	1.11	1.03	1.18	0.96
50 (50)	1.13	1.14	1.05	1.21	0.24
100 (30)	1.12	1.13	1.06	1.22	0.38

Beobachtete Ursachen und verbleibende Aufgaben

Der Q-Wert explodiert
Bei unnormalisierter Gesamtgraphsumme wuchs der Q-Wert auf Millionen, und der Aktualisierungsverlust erreichte 10¹⁵ Einheiten.
TD-Zielfehler
Der Zielwert wurde stets anhand des Q-Werts der Startstadt anstatt des Q-Werts der verbleibenden Stadt berechnet, und der Zustand nach dem n-ten Schritt war ebenfalls um einen Schritt verschoben.
Auf Folge 100 reduziert
Da der große Graph etwa 45 Sekunden pro Episode umfasst, würden 10.000 Iterationen über 5 Tage pro Seed dauern. Ich habe die Anzahl der Iterationen reduziert und die übrigen Einstellungen beibehalten.

Kriterien für das Lesen der Ergebnisse

Keine direkte Reproduktion des Originalartikels (kein Zielnetzwerk, anderes n-Schritt-Verfahren)
Lernen Sie nur 1 % der konfigurierten Episoden kennen.
Leistung nach vollständigem Training Unbekannt

Verbesserungspunkte für das nächste Experiment

Vergleiche die Antwort zuerst mit der Antwort der kleinen Aufgabe.
Nachbarsummennormalisierung und Zielwertkorrektur
Zufällige Reihenfolge als Basiswert festlegen

Verbindungen zu aktuellen Projekten

In diesem Projekt habe ich zum ersten Mal selbst ein neuronales Netz in Code umgesetzt. Die Erfahrung, Graphelemente und ihre Beziehungen als Lerneingaben darzustellen, führte zu meiner heutigen Forschung zur Erkennung von Möbelpaneelen und Flächen.

KI zur Erkennung von Möbelpaneelen und Berechnung von Größenänderungen