🤖 machine learning

Regularized Large Neighborhood Search

Dieses Paper führt die Regularized Large Neighborhood Search (RLNS) ein, ein neuartiges Framework, das die LNS-Heuristik durch Regularisierung in einen effizienten MCMC-Sampler transformiert und so das End-to-End-Lernen von kombinatorischen Optimierungsschichten ermöglicht, ohne auf rechentechnisch unpraktikabel komplexe globale Solver angewiesen zu sein.

Ursprüngliche Autoren: Germain Vivier-Ardisson, Laurent Demonet, Axel Parmentier, Mathieu Blondel

Veröffentlicht 2026-06-02

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Germain Vivier-Ardisson, Laurent Demonet, Axel Parmentier, Mathieu Blondel

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, ein massives, unglaublich komplexes Puzzle zu lösen. Sie haben tausende Teile, und sie müssen perfekt zusammenpassen, um eine Reihe strenger Regeln zu erfüllen. In der Welt der Mathematik und Informatik wird dies als kombinatorisches Optimierungsproblem bezeichnet.

Jahrzehntelang haben Experten (Operations Researchler) einen cleveren Trick namens Large Neighborhood Search (LNS) verwendet, um diese Puzzles zu lösen. Denken Sie an LNS wie an einen meisterhaften Lektor, der an einem Roman arbeitet. Anstatt zu versuchen, das ganze Buch auf einmal umzuschreiben (was unmöglich ist), friert der Lektor 90 % der Geschichte ein und schreibt nur ein kleines Kapitel nach dem anderen um. Er findet die beste Version dieses Kapitels, sperrt sie ein, geht zum nächsten Kapitel über und wiederholt den Vorgang. Dies ist schnell und skalierbar, ist aber eine „Heuristik“ – eine Methode der besten Schätzung, die keine perfekte globale Lösung garantiert, sondern lediglich eine sehr gute.

Auf der anderen Seite des Raumes versuchen Forscher im Bereich Maschinelles Lernen, Computer darauf zu trainieren, diese Puzzles durch das Betrachten von Beispielen zu lösen. Sie wollen ein „neuronales Netz“ (eine Art KI) bauen, das die Regeln des Puzzles lernt und die Lösung ausgibt. Um die KI jedoch zu trainieren, muss der Computer genau wissen, wie er seine „Knöpfe“ (Gradienten) justieren muss, um ein besseres Ergebnis zu erzielen. Dies erfordert normalerweise einen exakten globalen Solver – eine Methode, die jedes einzelne Mal die perfekte Lösung findet.

Das Problem:
Für riesige, reale Puzzles (wie die Planung von Lieferwagen oder die Zuweisung von Aufgaben) ist das Finden dieser perfekten globalen Lösung rechnerisch unmöglich. Es würde länger dauern als das Alter des Universums. Daher funktionieren die „perfekten“ Solver, die für das Training von KI verwendet werden, nicht für die großen Probleme, mit denen LNS-Experten im Alltag konfrontiert sind.

Die Lösung: Regularisierte LNS (RLNS)
Die Autoren dieser Arbeit schließen diese Lücke. Sie haben eine neue Methode entwickelt, die Regularisierte Large Neighborhood Search (RLNS) genannt wird.

Hier ist, wie sie dies unter Verwendung einiger Analogien umgesetzt haben:

1. Der „glatte“ Lektor

Standard-LNS ist starr: Es wählt einen kleinen Teil des Puzzles aus und findet den einzigen besten Weg, diesen zu korrigieren.
RLNS fügt dem Prozess eine „Temperatur“ oder „Rauschen“ hinzu. Stellen Sie sich vor, der Lektor sucht nicht nur nach dem einen besten Satz, sondern darf auch einige wenige, leicht unterschiedliche, „gut genuge“ Sätze basierend auf einer Wahrscheinlichkeit ausprobieren.

Die Magie: Durch das Hinzufügen dieser Zufälligkeit (Regularisierung) hört der Lektor auf, nur zu „raten“, und beginnt, wie ein wissenschaftlicher Sampler zu agieren. Er sucht nicht mehr nur nach einem lokalen Gipfel, sondern erkundet die Landschaft so, dass er im Laufe der Zeit die statistische Verteilung aller möglichen guten Lösungen perfekt nachahmt.

2. Der „Block-Gibbs“-Tanz

Die Arbeit beweist, dass RLNS zu einem Block-Gibbs-Sampler wird, wenn man eine bestimmte Art von „Rauschen“ (genannt entropische Regularisierung) verwendet.

Die Analogie: Stellen Sie sich eine Tanzfläche mit tausenden Menschen (mögliche Lösungen) vor. Sie möchten wissen, wo sich die Menge am wahrscheinlichsten aufhält.
- Der alte Weg: Sie versuchen, jeden einzelnen Menschen im gesamten Raum auf einmal zu zählen (Globaler Solver). Unmöglich für eine riesige Menge.
- Der RLNS-Weg: Sie frieren 90 % der Tänzer ein. Sie bitten die verbleibenden 10 %, sich umzubewegen und die besten Plätze für sie selbst zu finden, basierend darauf, wo die anderen stehen. Dann frieren Sie einen anderen Teil von 90 % ein und lassen die neuen 10 % herumwirbeln.
- Das Ergebnis: Die Arbeit beweist, dass die Menge, wenn man diesen „Shuffle-and-Freeze“-Tanz fortsetzt, schließlich genau dasselbe Muster annimmt, als hätte man jeden Einzelnen perfekt gezählt. Man erhält die statistische Wahrheit, ohne die unmögliche globale Zählung zu benötigen.

3. Lernen ohne den „perfekten“ Solver

Der größte Durchbruch ist, wie dies dem KI-Lernen hilft.

Das alte Problem: Um eine KI zu trainieren, muss man normalerweise die „perfekte“ Antwort kennen, um den Fehler zu berechnen. Wenn man die perfekte Antwort nicht finden kann, kann man die KI nicht trainieren.
Der RLNS-Fix: Die Autoren zeigen, dass man die KI allein durch diese „lokalen Verschiebungen“ trainieren kann.
- Wenn man einen Shuffle durchführt (K=1), lernt die KI basierend auf der „Pseudolikelihood“ (einer lokalen Annäherung). Das ist schnell und kostengünstig.
- Wenn man viele Shuffles durchführt (K=100), lernt die KI näher an der „exakten Maximum-Likelihood“ (der globalen Wahrheit).
- Der Vorteil: Man kann einen Regler nutzen, um zwischen Geschwindigkeit und Genauigkeit abzuwägen. Man benötigt keinen globalen Solver mehr; man braucht nur den lokalen „Lektor“ (LNS), den Operations Researchler bereits verwenden.

4. Reale Tests

Die Autoren haben dies auf drei Arten von Puzzles getestet:

Auswahl einer Teilmenge von Objekten: Wie das Auswählen von genau 500 Artikeln aus 1.000.
Generalisierte Zuweisung: Wie die Zuweisung von 50 Paketen an 5 LKWs mit begrenztem Platz.
Fahrzeugplanung: Wie das Routen von Lieferwagen durch eine Stadt mit unsicheren Verkehrsverzögerungen.

In allen Fällen funktionierte RLNS. Es lernte, gute Lösungen schneller und effizienter vorherzusagen als Methoden, die versuchten, „Black-Box“-Approximationen zu nutzen oder unmögliche globale Berechnungen erforderten.

Zusammenfassung

Die Arbeit stellt RLNS vor, eine Methode, die eine Standard-„Local Search“-Heuristik (die normalerweise nur eine gute Antwort findet) in ein rigoroses statistisches Werkzeug verwandelt, das zur Trainierung von KI-Modellen verwendet werden kann.

Sie ermöglicht es Machine-Learning-Modellen, zu lernen, wie man massive, komplexe, reale Puzzles (wie Logistik und Planung) löst, ohne zuerst die „perfekte“ Version des Puzzles lösen zu müssen. Es besagt effektiv: „Wir müssen nicht den ganzen Wald sehen, um zu lernen, wie man ihn durchquert; wir müssen nur wissen, wie man die Bäume direkt vor uns navigiert, und das oft genug tun.“

Technisches Resümee: Regularisierte Large Neighborhood Search (RLNS)

Problemstellung

Die Integration kombinatorischer Optimierungsschichten in neuronale Netze hat sich als leistungsfähiges Paradigma für die strukturierte Prädiktion etabliert, das es Modellen ermöglicht, diskrete Entscheidungen auszugeben, welche komplexe Nebenbedingungen erfüllen. Die Standardformulierung umfasst eine Schicht, die durch $\hat{y}(\theta) \triangleq \arg \max_{y \in \mathcal{Y}} \langle \theta, y \rangle$ definiert ist, wobei $\mathcal{Y}$ eine endliche, aber kombinatorisch große Menge zulässiger Ausgaben darstellt.

Die grundlegende Herausforderung in diesem Kontext ist die Differenzierbarkeit. Da der $\arg \max$ -Operator fast überall Null-Gradienten liefert, verlassen sich bestehende Ansätze typischerweise auf Regularisierung, um eine kontinuierliche, differenzierbare Relaxation zu erzeugen. Die meisten aktuellen Methoden (z. B. Fenchel-Young-Verluste, perturbierte Optimierer) setzen jedoch grundlegend den Zugriff auf einen globalen exakten Solver (ein globales MAP-Orakel) oder ein Marginal-Orakel voraus, um Erwartungswerte der Gibbs-Verteilung zu berechnen. Für NP-schwere Optimierungsprobleme, wie sie in der Operations Research üblich sind, ist der Aufruf eines globalen Orakels bei jedem Trainingsschritt rechnerisch nicht handhabbar. Infolgedessen greifen Praktiker auf skalierbare Heuristiken wie die Large Neighborhood Search (LNS) zurück, die Lösungen iterativ verfeinert, indem sie Teilmengen von Variablen einfriert und den Rest neu optimiert. Das Fehlen eines fundierten Rahmens zur Nutzung von LNS als differenzierbare kombinatorische Schicht bleibt ein kritischer Engpass.

Methodik: Regularisierte LNS (RLNS)

Die Autoren führen die Regularisierte Large Neighborhood Search (RLNS) ein, eine stochastische Version der LNS, die die Lücke zwischen skalierbaren Heuristiken und differenzierbaren Optimierungsschichten schließt. Der Kern der Idee besteht darin, die lokalen Teilprobleme innerhalb des LNS-Frameworks zu regularisieren oder zu perturbieren, wodurch die Heuristik in einen effizienten Markov-Chain-Monte-Carlo (MCMC)-Sampler über der kombinatorischen Menge zulässiger Lösungen transformiert wird.

1. Framework und lokale Regularisierung

RLNS definiert eine Familie lokaler Regularisierungsfunktionen, die aus einem globalen Regularisierer $\Omega$ abgeleitet sind. Für eine Teilmenge von Lösungen $\mathcal{Z} \subseteq \mathcal{Y}$ ist ein lokaler Regularisierer $\Omega_{\mathcal{Z}}$ über eine Inklusionsabbildung definiert. Anstatt das globale regularisierte Problem zu lösen, sampelt RLNS iterativ aus lokal regularisierten Verteilungen $p_{\Omega_{\mathcal{Y}(k)}}((s_\theta)[\mathcal{Y}(k)])$ , wobei $\mathcal{Y}(k)$ die lokale Nachbarschaft ist, die durch das Einfrieren einer Teilmenge von Koordinaten $S^{(k)}$ definiert wird.

2. Entropische Regularisierung und Block-Gibbs-Sampling

Wenn der globale Regularisierer die negative Shannon-Entropie ist ( $\Omega = -\gamma H_s$ ), beweisen die Autoren, dass RLNS exaktes Block-Gibbs-Sampling durchführt. Speziell entspricht die lokal regularisierte Verteilung der global regularisierten Gibbs-Verteilung unter der Bedingung der fixierten Variablen:
$p_{\Omega_{\mathcal{Y}(k)}}((s_\theta)[\mathcal{Y}(k)])(y) = p_{\Omega}(s_\theta)(y \mid y^{(k)}_{[S^{(k)}]})$
Unter einem irreduziblen Variablenwahlverfahren konvergiert die stationäre Verteilung der RLNS-Iterationen exakt gegen die global regularisierte Gibbs-Verteilung. Dieses Ergebnis ist einzigartig für die entropische Regularisierung; Proposition 2 charakterisiert die Shannon-Entropie als den einzigen separierbaren Regularisierer, der diese Exaktheit garantiert.

3. Perturbationsbasierte Regularisierung

In Szenarien, in denen lokale Marginal-Orakel (die für das entropische Sampling erforderlich sind) unhandlich, aber lokale MAP-Orakel verfügbar sind, schlagen die Autoren die Verwendung von perturbationsbasierter Regularisierung vor. Durch das Hinzufügen von Rauschen $\epsilon Z$ zu den lokalen Scores und das Lösen des perturbierten lokalen Maximierungsproblems kann RLNS aus der lokal regularisierten Verteilung sampeln. Dieser Ansatz nutzt Standard-LNS-Orakel (z. B. Dynamische Programmierung für Knapsack-Teilprobleme), ohne dass Ablehnungsmechanismen (wie beim Metropolis-Hastings-basierten Local Search) erforderlich sind.

4. Lernen und Interpolation

Das Paper stellt eine Verbindung zwischen der Anzahl der RLNS-Iterationen ( $K$ ) und der Lernzielgröße her:

$K=1$ (Lokaler Fenchel-Young-Verlust): Ein einziger Schritt von RLNS liefert einen unverzerrten Schätzer für einen lokalen Fenchel-Young-Verlust. Im entropischen Fall entspricht dies dem Pseudolikelihood-Ziel (zusammengesetztes Likelihood-Verfahren), welches die Likelihood von Teilmengen von Variablen maximiert, die unter der Bedingung der restlichen Variablen stehen.
$K \to \infty$ (Globaler Fenchel-Young-Verlust): Mit zunehmenden Iterationen konvergiert der Schätzer gegen den Gradienten des globalen Fenchel-Young-Verlusts und approximiert die exakte Maximum-Likelihood-Schätzung.
Dies ermöglicht es Praktikern, zwischen Pseudolikelihood und exakter Maximum-Likelihood-Schätzung durch die Abstimmung von $K$ zu interpolieren, was ein End-to-End-Lernen ohne globale Solver ermöglicht.

Zentrale Beiträge

RLNS-Framework: Einführung eines stochastischen, regularisierten RLNS, das lokale Regularisierung in LNS-Teilprobleme integriert und so eine differenzierbare kombinatorische Schicht schafft.
Theoretische Äquivalenz: Beweis, dass RLNS unter entropischer Regularisierung ein exaktes Block-Gibbs-Sampling implementiert, dessen stationäre Verteilung mit der global regularisierten Gibbs-Verteilung übereinstimmt.
Handhabbarkeit durch Perturbation: Demonstration, dass die perturbationsbasierte Regularisierung es RLNS ermöglicht, Standard-LNS-MAP-Orakel zu nutzen, was die Handhabbarkeit sicherstellt, wann immer Standard-LNS handhabbar ist.
Interpolation von Lernparadigmen: Theoretische und empirische Demonstration, dass die Anzahl der RLNS-Iterationen die Interpolation zwischen Pseudolikelihood und exakter Maximum-Likelihood-Schätzung ermöglicht.
Empirische Validierung: Evaluierung auf drei distinkten Problemen:
- $\kappa$ -hot Vektoren: Kontrollierte Schätzaufgabe zur Validierung der Konvergenz gegenüber der Grundwahrheit.
- Generalized Assignment Problem (GAP): Lernen zur Vorhersage von Zuweisungen, bei denen die lokalen Teilprobleme 0/1-Knapsack-Probleme sind.
- Stochastische Fahrzeugplanung: Ein Realwelt-Benchmark, bei dem RLNS-1 die Blackbox-Differenzierung und Binary-Cross-Entropy-Baselines übertrifft, während es deutlich weniger Rechenleistung als globale Solver benötigt.

Ergebnisse

Konvergenz: Im $\kappa$ -hot Vektor-Experiment konvergiert RLNS schneller als Local Search MCMC und erreicht einen geringeren mittleren absoluten Fehler (MAE) als die Monte-Carlo-Schätzung bei gleicher Anzahl an Samples, insbesondere wenn ein hoher Anteil der Variablen frei bleibt.
Skalierbarkeit: In den GAP-Experimenten sind die von RLNS genutzten lokalen MAP-Orakel um Größenordnungen schneller als globale MILP-Solver, insbesondere mit zunehmender Skalierung des Problems.
Performance: In der stochastischen Fahrzeugplanung erreicht RLNS-1 (mit einer einzigen Iteration) nahezu die Leistung von globalem perturbiertem Fenchel-Young (PFY) Lernen hinsichtlich der Verzögerungskosten, während es lediglich erfordert, dass der Solver Teilprobleme verarbeitet, die etwa ein Drittel der ursprünglichen Größe haben. Es übertrifft die Blackbox-Differenzierung (DBB) und die Binary-Cross-Entropy (BCE) Baselines signifikant.
Bias-Analyse: Theoretische Grenzen zeigen, dass der Approximationsfehler mit der Anzahl der gemeinsamen Nebenbedingungen (Cut-Constraints) zwischen fixierten und freien Variablen skaliert, was die Wahl von Variablen-Selektionsschemata motiviert, die diese Kreuzabhängigkeiten minimieren (z. B. Min-Cut-Selektion).

Bedeutung und Ansprüche

Das Paper beansprucht, eine kritische Lücke in der Literatur zu schließen, indem es die Verwendung hochskalierbarer Heuristiken (LNS) als differenzierbare Schichten in neuronalen Netzen ermöglicht und damit die Abhängigkeit von rechnerisch nicht handhabbaren globalen Solvern aufhebt. Durch die Etablierung einer rigorosen Verbindung zwischen LNS und Gibbs-Sampling bietet die Arbeit einen fundierten Rahmen zur Differenzierung durch kombinatorische Optimierungsschichten unter Verwendung lediglich lokaler Orakel. Die Autoren positionieren RLNS als praktische Lösung für das End-to-End-Lernen in strukturierten Vorhersageaufgaben mit NP-schweren Nebenbedingungen, die einen abstimmbaren Trade-off zwischen Rechenkosten und statistischer Genauigkeit über die Iterationszahl $K$ bietet.