Sym-NCO: Nutzung von Symmetrien für die neuronale kombinatorische Optimierung

Auf Deep Reinforcement Learning (DRL) basierende kombinatorische Optimierungsmethoden (d.h. DRL-NCO) haben im Vergleich zu herkömmlichen CO-Lösern signifikante Vorteile gezeigt, da DRL-NCO in der Lage ist, CO-Löser mit weniger Abhängigkeit von Problemspezifischem Expertenwissen (heuristische Methode) und überwachten beschrifteten Daten (überwachte Lernmethode) zu lernen. Diese Arbeit stellt ein neuartiges Trainingsschema, Sym-NCO, vor, das ein regularisierungsbasiertes Trainingsschema ist, das universelle Symmetrien in verschiedenen CO-Problemen und -Lösungen nutzt. Die Nutzung von Symmetrien wie Rotations- und Reflexionsinvarianz kann die Generalisierungsfähigkeit von DRL-NCO erheblich verbessern, da es dem gelernten Löser ermöglicht, die allgemein geteilten Symmetrien in derselben CO-Problemlasse auszunutzen. Unsere experimentellen Ergebnisse bestätigen, dass unser Sym-NCO die Leistung von DRL-NCO-Methoden in vier CO-Aufgaben, einschließlich des Handlungsreisendenproblems (TSP), des Kapazitätsroutenplanungsproblems (CVRP), des Preis-sammelnden TSP (PCTSP) und des Orientierungsproblems (OP), erheblich verbessert, ohne spezifisches Expertenwissen zu nutzen. Bemerkenswerterweise übertraf Sym-NCO nicht nur die bestehenden DRL-NCO-Methoden, sondern auch einen wettbewerbsfähigen herkömmlichen Löser, die iterative lokale Suche (ILS), im PCTSP bei 240-fach höherer Geschwindigkeit. Unser Quellcode ist verfügbar unter https://github.com/alstn12088/Sym-NCO.