Die Grenzen erlernter Heuristiken für die lokale Suche aufdecken: Sind Sie der Mächtigste unter den Sanftmütigen?

Linktabelle

Zusammenfassung & Einleitung

Verwandte Arbeiten

Auswertung für Max-Cut

Bewertung für SAT

Zusammenfassung und Ausblick, Referenzen

Zusatzmaterialien

Abstrakt

In den letzten Jahren ist die Kombination neuronaler Netze mit lokalen Suchheuristiken im Bereich der kombinatorischen Optimierung populär geworden. Trotz des erheblichen Rechenaufwands hat dieser Ansatz mit minimalem manuellen Aufwand vielversprechende Ergebnisse gezeigt. Wir haben jedoch drei kritische Einschränkungen bei der empirischen Bewertung dieser Integrationsversuche festgestellt. Erstens stellen Instanzen mit mäßiger Komplexität und schwachen Basislinien eine Herausforderung für die genaue Bewertung der Wirksamkeit lernbasierter Ansätze dar. Zweitens macht es das Fehlen einer Ablationsstudie schwierig, Verbesserungen zu quantifizieren und der Deep-Learning-Architektur genau zuzuschreiben. Schließlich ist die Verallgemeinerung erlernter Heuristiken über verschiedene Verteilungen hinweg noch wenig erforscht. In dieser Studie führen wir eine umfassende Untersuchung dieser festgestellten Einschränkungen durch. Überraschenderweise zeigen wir, dass eine einfache erlernte Heuristik auf Basis von Tabu Search die modernsten erlernten Heuristiken (SOTA) in Bezug auf Leistung und Verallgemeinerbarkeit übertrifft. Unsere Ergebnisse stellen vorherrschende Annahmen in Frage und eröffnen spannende Wege für zukünftige Forschung und Innovation in der kombinatorischen Optimierung.

1. EINLEITUNG

Das Entwerfen effektiver Heuristiken oder Approximationsalgorithmen für NP-schwere kombinatorische Optimierungsprobleme (CO) ist eine anspruchsvolle Aufgabe, die oft Fachwissen und umfangreiches Ausprobieren erfordert. Daher hat die Idee, diesen anspruchsvollen und langwierigen Entwurfsprozess durch maschinelles Lernen zu automatisieren, um Algorithmen zu erlernen, die die inhärente Struktur eines Problems ausnutzen, bei Forschern großes Interesse geweckt (Bello et al., 2016; Khalil et al., 2017; Bengio et al., 2021; Dong et al., 2021). Insbesondere ein beträchtlicher Teil dieser Arbeiten (Khalil et al., 2017; Barrett et al., 2020; Yolcu und P´oczos, 2019) konzentrierte sich auf den Einsatz von Graph Neural Networks (GNNs) für CO-Probleme. Trotz der Rechenleistungsanforderungen haben diese GNN-basierten Ansätze eine konkurrenzfähige Leistung im Vergleich zu auf spezifische Probleme zugeschnittenen SOTA-Heuristiken gezeigt.

Diese potenziellen Fortschritte sind zwar sehr vielversprechend, es bleiben jedoch einige Bedenken bestehen. Die überlegene Leistung der erlernten Heuristiken kann auf die Auswahl bestimmter Instanzen und Baselines zurückgeführt werden. Insbesondere wenn die Baselines schwach sind, können die erlernten Heuristiken diese leicht übertreffen. Ohne harte Instanzen und die richtige Auswahl der Baselines können die erlernten Heuristiken leicht eine vergleichbare Leistung wie die SOTA-Heuristiken aufweisen, was zu einer Überschätzung der tatsächlichen Fähigkeiten der erlernten Heuristiken führen kann. Darüber hinaus werden Vergleiche mit SOTA-Heuristiken gelegentlich aufgrund von Skalierbarkeitsproblemen bei Deep-Learning-Architekturen ausgelassen.

Eine Untergruppe lernbasierter Ansätze (Khalil et al., 2017; Yolcu und P´oczos, 2019; Barrett et al., 2020, 2022) integriert die Funktionalität oder das Verhalten traditioneller Heuristiken und bietet potenziell eine verbesserte oder gesteigerte Leistung durch die Integration heuristischer Prinzipien mit Komponenten des maschinellen Lernens. Wenn ein umfassender Vergleich mit den integrierten Heuristiken und eine Ablationsstudie der Deep-Learning-Architektur fehlen, wird es schwierig, den spezifischen Beitrag der Deep-Learning-Architektur zu bestimmen. Wenn die integrierten Heuristiken robust sind, können die erlernten Heuristiken die Basisheuristiken daher problemlos übertreffen, während die Deep-Learning-Architektur eine geringe Rolle spielt.

Eine weitere große Leistung erlernter Heuristiken (Khalil et al., 2017; Barrett et al., 2020; Toenshof et al., 2019), die zunächst an kleineren und spezifischen Instanzen aus einer bestimmten Verteilung trainiert wurden, zeigen eine beeindruckende Leistung, wenn sie an größeren Instanzen aus verschiedenen Verteilungen getestet werden. Diese Leistung ist eine bedeutende Errungenschaft und steht im Einklang mit dem Kernziel des Einsatzes lernbasierter Ansätze: die Notwendigkeit umfassender Anpassungen und domänenspezifischer Kenntnisse zu verringern, die Heuristiken oft erfordern. Obwohl klassische Heuristiken mit Hyperparametern auch auf Herausforderungen stoßen können, wenn sie für eine bestimmte Verteilung fein abgestimmt werden, können sie auch auf verschiedene Verteilungen verallgemeinert werden. Die Hauptfrage dreht sich darum, ob die erlernten Heuristiken im Vergleich zu klassischen Heuristiken tatsächlich eine bessere Generalisierbarkeit aufweisen. Ein gründlicher und aufschlussreicher Vergleich erlernter Heuristiken mit klassischen Heuristiken bietet wertvolle Einblicke in die Generalisierbarkeit erlernter Heuristiken.

Gelernten Heuristiken fehlen oft theoretische Garantien, sodass die empirische Bewertung die einzige Methode ist, um die Stärken und Grenzen der vorgeschlagenen Methoden zu verstehen. Wir glauben, dass bei der empirischen Bewertung dieser Arbeiten mehrere grundlegende, aber entscheidende Fragen unerforscht bleiben. Obwohl diese Fragen für alle Arten von gelernten Heuristiken relevant sind, stellen und beantworten wir sie, indem wir häufig zitierte und aktuelle, von Experten begutachtete Veröffentlichungen analysieren, die sich auf das Erlernen lokaler Suchheuristiken konzentrieren. Unser Ziel ist es nicht, erschöpfende Benchmarks für die in unserer Arbeit diskutierten CO-Probleme bereitzustellen, sondern vielmehr zukünftigen Forschern bei der Bewertung ihrer Forschung zu helfen.

Konkret stellen und beantworten wir folgende Fragen:

1. Können erlernte Heuristiken überparametrisiert werden? Absolut. Indem wir das GNN in ECO-DQN durch lineare Regression ersetzen und eine Teilmenge von Funktionen aus ECO-DQN (Barrett et al., 2020) verwenden, die mit Tabu Search (Glover, 1990) verknüpft ist, führen wir eine beschnittene Version von ECO-DQN ein, die wir SoftTabu nennen. Unsere Studie zeigt, dass SoftTabu im Vergleich zu ECO-DQN für das NPhard Maximum-Cut (Max-Cut)-Problem eine bessere Leistung und Generalisierbarkeit aufweist.

2. Kann die Baseline-Verzerrung auf die bessere Leistung erlernter Heuristiken zurückgeführt werden? Ja, wir zeigen, dass SoftTabu, eine einfache erlernte Heuristik, S2V-DQN (Khalil et al., 2017) beim Max-Cut-Problem und GNNSAT (Yolcu und P´oczos, 2019) bei der Boolean Satisfiability (SAT) übertreffen kann.

*3. Können erlernte Heuristiken aufgrund von Instanzauswahlverzerrungen eine bessere Generalisierbarkeit aufweisen?*Ja, wir zeigen, dass ECO-DQN bei schwierigeren Instanzen eine schlechte Generalisierbarkeit aufweist und leicht im Suchraum gefangen wird.