Neues Framework G-LNS revolutioniert das Automatisierte Heuristik-Design mit LLMs

Die Optimierung kombinatorischer Probleme ist eine zentrale Herausforderung in zahlreichen Industriezweigen, von der Fertigung bis zur Logistik. Traditionell werden diese Probleme oft mithilfe von handgefertigten Heuristiken gelöst. Diese Ansätze erfordern jedoch tiefgreifendes Fachwissen und sind häufig nur auf spezifische Problemstrukturen zugeschnitten, was ihre Generalisierbarkeit einschränkt. Mit dem Aufkommen von Large Language Models (LLMs) hat sich das Feld des Automatisierten Heuristik-Designs (AHD) dynamisch weiterentwickelt. Eine aktuelle Entwicklung, das Generative Large Neighborhood Search (G-LNS)-Framework, verspricht hierbei einen Paradigmenwechsel.

Die Evolution des Automatisierten Heuristik-Designs durch LLMs

Die Integration von LLMs in das AHD hat in den letzten Jahren vielversprechende Fortschritte gezeigt. Ansätze wie FunSearch und EoH haben das "Thought-Code"-Paradigma etabliert, bei dem LLMs algorithmischen Code generieren und verfeinern, um leistungsstarke Heuristiken zu finden. Diese Methoden konzentrierten sich jedoch oft auf konstruktive Prioritätsregeln oder die Parameterabstimmung innerhalb fester lokaler Suchrahmen. Dies führte zu einer strukturellen Engstelle, da der Suchraum auf vorgegebene heuristische Formen beschränkt blieb und die Fähigkeit zur strukturellen Erkundung limitierte. Solche Einschränkungen erschweren das Entkommen aus tiefen lokalen Optima in komplexen kombinatorischen Optimierungsproblemen (COPs).

Die strukturelle Lücke in bestehenden AHD-Methoden

Bisherige AHD-Methoden, die auf konstruktiven Heuristiken basieren, folgen einer irreversiblen Entscheidungsfindung. Fehler, die früh im Prozess gemacht werden, sind schwer durch spätere Anpassungen zu korrigieren. Bei lokalen Suchansätzen, die iterativ Lösungen verfeinern, sind die Nachbarschaftsstrukturen oft fest vorgegeben. LLMs werden hierbei primär zur Parameteroptimierung eingesetzt, nicht aber zur grundlegenden algorithmischen Innovation. Dies limitiert die Fähigkeit, strukturelle Veränderungen in der Lösungsfindung vorzunehmen.

G-LNS: Ein generativer Ansatz für die Nachbarschaftssuche

Um diese Einschränkungen zu überwinden, wurde G-LNS entwickelt. Dieses Framework ist inspiriert von der Large Neighborhood Search (LNS), einer Meta-Heuristik, die durch abwechselnde "Destroy"- und "Repair"-Operationen eine starke strukturelle Umgestaltung ermöglicht. Der Erfolg von LNS hängt maßgeblich von der engen Kopplung dieser beiden Operatoren ab: Die "Destroy"-Phase muss gezielte strukturelle Störungen in die Lösung einführen, die die "Repair"-Phase spezifisch wiederherstellen kann. Diese starke Interdependenz macht den automatisierten Entwurf von LNS-Operatoren besonders anspruchsvoll.

Kernerkenntnisse und Beiträge von G-LNS

• Generative LNS für AHD: G-LNS ist ein evolutionäres Framework, das LLM-basiertes AHD auf den automatisierten Entwurf von LNS-Operatoren erweitert. Dies ermöglicht strukturelle Lösungsstörungen, die über konstruktive Regeln und feste lokale Schritte hinausgehen.
• Synergie-bewusste Ko-Evolution: Ein kooperativer Bewertungsmechanismus mit einer Synergie-Matrix erfasst und nutzt explizit die Kopplung zwischen "Destroy"- und "Repair"-Operatoren während der Evolution.
• Empirische Effektivität und Generalisierung: Umfassende Experimente an COPs wie dem Traveling Salesman Problem (TSP) und dem Capacitated Vehicle Routing Problem (CVRP) zeigen, dass G-LNS sowohl LLM-basierte AHD-Methoden als auch klassische Solver übertrifft. Es erzielt nahezu optimale Lösungen bei deutlich reduziertem Rechenaufwand und demonstriert eine robuste Generalisierung über diverse und ungesehene Instanzverteilungen hinweg.

Methodologie des G-LNS Frameworks

G-LNS strukturiert den heuristischen Entwurf als einen evolutionären Prozess über algorithmische Strukturen. LLMs agieren dabei als intelligente Variationsoperatoren, die den Raum der algorithmischen Logik jenseits fixer heuristischer Templates erkunden. Das Framework durchläuft vier Hauptphasen:

1. Initialisierung

G-LNS nutzt eine Dual-Population-Architektur, die separate Repositories für "Destroy"-Operatoren (Pd) und "Repair"-Operatoren (Pr) verwaltet. Jede Population hat eine Kapazität N. Die Initialisierungsphase beginnt mit der Einspeisung klassischer domänenspezifischer Heuristiken als Startpunkte, beispielsweise "Random Removal" und "Worst Removal" für Pd sowie "Greedy Insertion" für Pr bei TSP/VRP-Aufgaben. Diese Startpunkte dienen als Grundlage und als In-Context-Beispiele, um das LLM auf die spezifische Aufgabenlogik auszurichten. Um die Pools vollständig zu füllen, wenn die Anzahl der Startpunkte unter N liegt, wird das LLM angewiesen, neue algorithmische Logik zu konzipieren und in ausführbaren Python-Code zu übersetzen, was die Diversität des Suchraums von Anfang an sicherstellt.

Gleichzeitig werden drei Metrikstrukturen initialisiert, um den evolutionären Prozess zu steuern:

• Globale Fitnesswerte (F): Vektoren, die die kumulative Leistung jedes Operators verfolgen.
• Synergie-Matrix (S): Eine Matrix, die die kooperative Leistung spezifischer Operatorpaare (di, rj) erfasst.
• Adaptive Gewichte (W): Gewichte, die innerhalb jeder Bewertungs-Episode die Auswahlwahrscheinlichkeiten steuern.

2. Bewertungsphase

Ziel dieser Phase ist es, den individuellen Beitrag jedes Operators für das Populationsmanagement zu quantifizieren und die Kopplungseffektivität zwischen "Destroy"- und "Repair"-Operatoren für eine synergistische Evolution zu erfassen. Es werden K unabhängige Bewertungs-Episoden durchgeführt, wobei jede Episode mit einer zufälligen Ausgangslösung beginnt und T Iterationen durchläuft. Die adaptiven Gewichte W werden zu Beginn jeder Episode auf 1 zurückgesetzt, um eine unabhängige Exploration zu gewährleisten, während globale Fitness F und Synergie-Matrix S Statistiken über alle K Episoden akkumulieren, um robuste Leistungskennzahlen zu erhalten.

Die Auswahl der Operatoren erfolgt über ein Roulette-Rad-Verfahren basierend auf ihren aktuellen Gewichten. Die Leistungsbewertung eines Operatorpaares (di, rj) erfolgt hierarchisch: Verbesserungen der global besten Lösung, der aktuellen Lösung oder akzeptierte Verschlechterungen führen zu unterschiedlichen Belohnungen. Diese Belohnungen werden zur Aktualisierung der adaptiven Gewichte, zur Akkumulation der globalen Fitness und zur Aufzeichnung der Synergie in der Synergie-Matrix verwendet.

3. Populationsmanagement

Nach Abschluss jeder Bewertungsphase werden die Operatoren in Pd und Pr basierend auf ihrer akkumulierten globalen Fitness F gerankt. Die M schlechtesten Operatoren aus jedem Pool werden entfernt, um Platz für neue, potenziell überlegene Logik zu schaffen. Anschließend werden F und S auf Null zurückgesetzt, um eine faire Konkurrenz in der nächsten Runde zu gewährleisten.

4. LLM-gesteuerter Evolutionsmechanismus

Diese Phase nutzt die Code-Generierungsfähigkeiten von LLMs, um die freien Plätze in den Populationen wieder aufzufüllen. Dies geschieht durch eine Kombination aus drei gezielten evolutionären Strategien:

• Mutation (Lokale Exploitation): Hierbei wird ein einzelner Parent-Operator aus dem Elite-Pool modifiziert. Die spezifische Mutationsstrategie (Logik-Evolution für niedrigere Ränge, Parameterkalibrierung für höhere Ränge) wird adaptiv basierend auf dem Rang des Operators ausgewählt.
• Homogenes Crossover (Feature-Rekombination): Zwei Parent-Operatoren desselben Typs werden ausgewählt, und das LLM fusioniert ihre logischen Stärken, um einen neuen Hybrid-Operator zu synthetisieren.
• Synergistisches Joint Crossover (Strukturelle Kopplung): Dies ist eine Kerninnovation von G-LNS. Das "Destroy-Repair"-Paar mit dem höchsten Synergie-Score wird ausgewählt. Das LLM wird angewiesen, dieses Paar als eine Einheit zu entwickeln, um sicherzustellen, dass der "Repair"-Operator spezifisch auf die vom "Destroy"-Operator eingeführten strukturellen Defekte zugeschnitten ist.

Um das Risiko von "Halluzinationen" durch LLMs zu mindern, werden alle generierten Operatoren einem Pre-Evaluation-Filter unterzogen. Nur fehlerfreie Operatoren, die die Zeitkomplexitätsbeschränkungen erfüllen, werden in die Population aufgenommen.

Experimentelle Ergebnisse und Leistungsanalyse

G-LNS wurde auf drei unterschiedlichen Domänen evaluiert: Traveling Salesman Problem (TSP), Capacitated Vehicle Routing Problem (CVRP) und Open Vehicle Routing Problem (OVRP). Die Experimente zeigten, dass G-LNS konsistent die niedrigsten Optimalitätslücken unter allen LLM-gesteuerten Methoden über alle Problemgrößen hinweg erreichte.

Überlegene Leistung und Skalierbarkeit

Bei großen Instanzen wie TSP100 und TSP200 übertraf G-LNS sowohl Evo-MCTS als auch MCTS-AHD(ACO) signifikant. Dies wurde auf die Evolution zustandsabhängiger "Destroy"- und "Repair"-Logik zurückgeführt, die es G-LNS ermöglicht, lokale Optima effektiver zu überwinden. Insbesondere für CVRP-Aufgaben zeigte G-LNS eine bemerkenswerte Skalierbarkeit und Robustheit gegenüber komplexen Kapazitätsbeschränkungen. Bei den größten Instanzen (CVRP100/200) übertraf G-LNS nicht nur alle LLM-basierten Baselines, sondern identifizierte auch Lösungen, die denen des OR-Tools-Solvers überlegen waren.

Recheneffizienz

G-LNS erreichte eine überlegene Lösungsqualität bei deutlich höherer Recheneffizienz. Zum Beispiel benötigte G-LNS für CVRP200 nur 280,91 Sekunden für 500 Iterationen, während MCTS-AHD 2407,14 Sekunden benötigte. Dies unterstreicht den praktischen Wert der entwickelten Heuristiken für zeitkritische Anwendungen.

Robuste Generalisierung

Die Fähigkeit von G-LNS zur Generalisierung wurde auch auf realen Benchmarks wie TSPLib und CVRPLib bewertet. G-LNS zeigte eine überlegene Generalisierungsleistung im Vergleich zu anderen AHD-Methoden, einschließlich der starken Baseline EoH-S. Die entwickelten "Destroy"- und "Repair"-Operatoren erfassen intrinsische strukturelle Eigenschaften kombinatorischer Probleme, anstatt sich nur an die Trainingsverteilung anzupassen.

Ablationsstudien

Ablationsstudien bestätigten die Notwendigkeit jeder evolutionären Strategie innerhalb des G-LNS-Frameworks. Das Entfernen von Mutation, homogenem Crossover oder synergistischem Joint Crossover führte zu einer deutlichen Verschlechterung der Leistung, was die Bedeutung der Logik-Feinabstimmung, Feature-Rekombination und insbesondere der strukturellen Kopplung zwischen "Destroy"- und "Repair"-Operatoren unterstreicht.

Fazit und Ausblick

G-LNS stellt einen bedeutenden Fortschritt im Bereich des Automatisierten Heuristik-Designs dar, indem es die strukturellen Einschränkungen bestehender LLM-basierter Ansätze überwindet. Durch die Ko-Evolution eng gekoppelter "Destroy"- und "Repair"-Operatoren und einen synergie-bewussten Bewertungsmechanismus ist G-LNS in der Lage, anspruchsvolle heuristische Logik zu entdecken, die führende Baselines und klassische Solver bei komplexen Routing-Problemen übertrifft. Die überlegene Generalisierungsfähigkeit und Recheneffizienz machen G-LNS zu einem vielversprechenden Werkzeug für die Lösung realer Optimierungsprobleme.

Zukünftige Arbeiten könnten die Erweiterung von G-LNS auf multi-objektive Optimierungsprobleme und die Anwendung auf ein breiteres Spektrum kombinatorischer Probleme jenseits von Routing-Aufgaben umfassen. Die Fähigkeit von LLMs, nicht nur Parameter zu optimieren, sondern die grundlegenden strukturellen Komponenten von Solvern zu entwerfen, eröffnet neue Möglichkeiten für die algorithmische Entdeckung.

Bibliography

- Zhao, B., Wang, H., & Zeng, L. (2026). G-LNS: Generative Large Neighborhood Search for LLM-Based Automatic Heuristic Design. arXiv preprint arXiv:2602.08253. - Hugging Face Daily Papers (2026). G-LNS: Generative Large Neighborhood Search for LLM-Based Automatic Heuristic Design. - Ye, H., Wang, J., Cao, Z., Berto, F., Hua, C., Kim, H., Park, J., & Song, G. (2024). ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution. Advances in Neural Information Processing Systems, 37, 43571-43608. - Ye, H., Xu, H., Yan, A., & Cheng, Y. (2025). Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems. In Forty-second International Conference on Machine Learning. - Liu, F., Tong, X., Yuan, M., Lin, X., Luo, F., Wang, Z., Lu, Z., & Zhang, Q. (2024). Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model. arXiv preprint arXiv:2401.02051. - The Moonlight.io (n.d.). [Literature Review] G-LNS: Generative Large Neighborhood Search for LLM-Based Automatic Heuristic Design. Retrieved from https://www.themoonlight.io/en/review/g-lns-generative-large-neighborhood-search-for-llm-based-automatic-heuristic-design. - Xie, Z., Liu, F., Wang, Z., & Zhang, Q. (2025). LLM-Driven Neighborhood Search for Efficient Heuristic Design. In 2025 IEEE Congress on Evolutionary Computation (CEC) (pp. 1-8). IEEE.