Large Language Model-Driven Full-Component Evolution of Adaptive Large Neighborhood Search

Deze paper introduceert een gesloten-lus, door grote taalmodellen aangedreven evolutionair kader dat alle componenten van Adaptive Large Neighborhood Search (ALNS) automatisch herbouwt en zo, met name op grote schaal, aanzienlijk betere oplossingskwaliteit en strategische diversiteit bereikt dan handmatig ontworpen ALNS-baselines.

De kern

Stel je voor dat je een zeer ervaren kok bent die elke dag een perfecte maaltijd moet bereiden voor duizenden gasten. Je hebt een recept (een algoritme) dat al jaren werkt, maar het is niet perfect. Soms is het eten te zout, soms te droog, en soms duurt het te lang om klaar te maken.

Vroeger moest je als kok zelf proberen om het recept te verbeteren. Je proefde, deed er een snufje peper bij, probeerde een andere kooktemperatuur, en hoopte dat het beter werd. Dit proces heet in de wereld van computers "handmatig ontwerpen" en het is traag, duur en afhankelijk van hoe slim of creatief jij als kok bent.

Wat doen deze onderzoekers?
De auteurs van dit paper hebben een slimme nieuwe kok bedacht: een Grote Taalmodel (LLM), zoals een super-geavanceerde AI die alles over koken (en wiskunde) weet. Maar ze hebben deze AI niet gevraagd om één ding te verbeteren. Ze hebben de hele keuken opgebroken in zeven verschillende onderdelen en de AI gevraagd om elk onderdeel van het recept volledig opnieuw uit te vinden.

Hier is hoe het werkt, vertaald naar alledaagse taal:

1. De Zeven Delen van de Keuken (De ALNS)

Het recept waar ze mee werken heet "Adaptive Large Neighborhood Search" (ALNS). In het Nederlands kunnen we dit zien als een slimme manier om de beste route te vinden (bijvoorbeeld voor een vrachtwagen die pakketten moet bezorgen). De onderzoekers hebben dit recept opgedeeld in zeven onderdelen:

1. De Vernietiger: Wie haalt er dingen uit de route? (Bijvoorbeeld: "Haal de 5 langste stukken weg").
2. De Reparaat: Wie zet ze er weer in? (Bijvoorbeeld: "Zet ze op de snelste plekken").
3. De Keuzemaker: Welk onderdeel gebruiken we vandaag?
4. De Scorekeeper: Wie houdt bij wat goed werkt?
5. De Start: Hoe beginnen we met de route?
6. De Beslissingsregels: Accepteren we een slechtere route om later iets beters te vinden?
7. De Krachtregelaar: Hoe hard gaan we "vernietigen" en herbouwen?

In het verleden stelde een mens al deze regels in. Nu laat de AI deze zeven onderdelen evolutionair verbeteren. Het is alsof je 7 verschillende chefs hebt die elk hun eigen onderdeel van het recept duizenden keren herschrijven, proberen, en de beste versie bewaren.

2. De "Genenpoel" (MAP-Elites)

De AI werkt niet zomaar. Ze gebruiken een slim systeem dat ze "MAP-Elites" noemen.

• Stel je een bibliotheek voor: In plaats van alleen het "beste" recept te bewaren, houden ze een bibliotheek bij van alle goede recepten.
• Verscheidenheid: Ze bewaren niet alleen het snelste recept, maar ook het meest creatieve, het meest stabiele, en het recept dat goed werkt bij regenachtig weer.
• Waarom? Soms is het recept dat er het "raarst" uitziet, juist het beste voor een heel groot probleem. Door een grote "genenpoel" van verschillende ideeën te houden, vinden ze oplossingen die een mens nooit zou bedenken.

3. Het Resultaat: Een Super-Kok

Ze hebben dit getest op de beroemde "Travelling Salesman Problem" (de verkoper die zo snel mogelijk bij alle steden moet zijn).

• De oude manier (Mens): De verkoper reed 100 kilometer extra en deed er uren over.
• De nieuwe manier (AI): De verkoper reed bijna de perfecte route en was veel sneller klaar.
• Het verschil: Op grote problemen (veel steden) was de verbetering enorm. De "foutmarge" (hoe ver ze van de perfecte route zaten) daalde van 3,18% naar 0,74%. Dat is alsof je een reis van 1000 km opeens 24 kilometer korter maakt zonder extra brandstof.

4. De Verassende Ontdekkingen

Het leukste deel is dat de AI dingen bedacht die voor mensen tegennatuurlijk lijken, maar wel werken:

• Soms is "slecht" goed: De AI bedacht een regel die zegt: "Als je een slechte stap zet, krijg je een straf, zelfs als de computer dat normaal gesproken accepteert." Dit klinkt raar, maar het voorkomt dat de AI in een slecht patroon blijft hangen.
• De "Momentum"-regel: De AI leerde dat je niet alleen moet kijken naar wie nu goed presteert, maar ook naar wie snel verbetert. Het is alsof je een speler kiest die niet de beste is, maar wel de snelste leerling.
• De "Tolerantie": De AI bedacht dat je kleine foutjes moet negeren, maar grote fouten streng moet straffen. Dit helpt om uit moeilijke situaties te komen zonder te panikeren.

5. Welke AI is de beste kok?

Ze hebben verschillende AI-modellen (zoals GPT, Grok, DeepSeek) tegen elkaar laten strijden.

• Sommige AI's waren snel in het vinden van een goed antwoord.
• Andere AI's (zoals GPT-5.2 en Grok) waren beter in het vinden van het perfecte antwoord als ze genoeg tijd kregen.
• Dit leert ons dat niet elke AI even goed is voor elke taak, net zoals niet elke kok even goed is in het bakken van taart versus het grillen van vlees.

Conclusie

Kort samengevat: Deze paper laat zien dat we niet langer hoeven te wachten tot een menselijke expert duizenden uren besteedt aan het perfectioneren van een algoritme. We kunnen een AI de hele keuken laten overnemen, hem laten experimenteren met duizenden variaties, en hem laten ontdekken dat de beste oplossing soms juist ligt in een regel die voor een mens "raar" klinkt.

Het is alsof we de sleutel hebben gevonden om elke logistieke uitdaging (van pakketjes bezorgen tot chipontwerp) veel sneller, goedkoper en slimmer op te lossen. De AI is niet langer alleen een assistent; hij is nu de hoofdchef die het recept herschrijft.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Large Language Model–Driven Full-Component Evolution of Adaptive Large Neighborhood Search" in het Nederlands.

Probleemstelling

Adaptive Large Neighborhood Search (ALNS) is een prominente metaheuristiek voor optimalisatieproblemen in productie en logistiek (zoals het Traveling Salesman Problem - TSP). Traditioneel wordt ALNS echter ontwikkeld via handmatige ontwerpprocessen die sterk afhankelijk zijn van de ervaring van experts. Dit leidt tot:

• Lange ontwikkelcycli en hoge kosten.
• Een gebrek aan aanpassingsvermogen aan nieuwe probleemstructuren.
• Een beperking tot intuïtieve, maar niet noodzakelijk optimale, logische patronen (bijv. statische gewichtsupdates of vaste acceptatieregels).

Bestaande automatiseringspogingen met Large Language Models (LLMs) focussen vaak slechts op het optimaliseren van individuele operatoren ("operator level"), terwijl de beslissingslagen (gewichtsupdates) en controlelagen (acceptatiecriteria) statisch blijven. Dit creëert een "ongelijkmatige evolutie" waarbij de prestaties worden beperkt door de zwakste schakel in de algoritmeketen.

Methodologie

De auteurs stellen een gesloten-lus, LLM-gedreven evolutionair framework voor dat ALNS volledig automatiseert door alle componenten te ontleden en opnieuw te ontwerpen.

1. Decoupling en Architectuur:
Het ALNS-algoritme wordt opgesplitst in zeven onafhankelijke, maar samenwerkende modules die elk apart worden geëvolueerd:

• Oplossingsoperatoren: Destroy-operators, Repair-operators, en Initial Solution Generator.
• Adaptieve Mechanismen: Operator Selector en Weight Updater.
• Globale Controle: Acceptance Rule en Destruction-rate Controller.

2. Evolutionair Framework:

• LLM als Mutator: De LLM fungeert als een "intelligente mutatie-operator" die code herschrijft en optimaliseert op basis van een gestructureerde prompt (rol, taak, harde constraints).
• MAP-Elites Mechanisme: Om zowel kwaliteit als diversiteit te waarborgen, wordt een multi-dimensionale elite-archief gebruikt. Oplossingen worden gemapt op gedragskenmerken (bijv. oplossingskwaliteit vs. stabiliteit, of diversiteit vs. efficiëntie). Dit voorkomt dat de evolutie vastloopt in één lokaal optimum en bevordert het ontdekken van diverse strategieën.
• Isolatie Evaluatie: Om de bijdrage van elke component nauwkeurig te meten, worden andere componenten vastgehouden op hun klassieke implementaties tijdens de evaluatie van een specifieke module (gecontroleerde variabelen).

3. Evaluatiemetrics:
De kwaliteit van een gegenereerde component wordt beoordeeld op basis van een gewogen som van:

• Oplossingskloof (Gap): Afwijking van de beste bekende oplossing.
• Stabiliteit: Standaarddeviatie van de prestaties over verschillende instanties.
• Straf/Beloning: Factoren voor uitvoeringstijd en operator-diversiteit.

Belangrijkste Bijdragen

1. Volledige Component Co-evolutie: Het eerste framework dat ALNS niet alleen op operator-niveau, maar systematisch over alle zeven kerncomponenten (van lage tot hoge niveaus) opnieuw ontwerpt.
2. Ontdekking van Niet-Intuïtieve Patronen: Het framework heeft efficiënte, maar tegen-intuïtieve logische structuren ontdekt die door menselijke experts vaak worden over het hoofd gezien.
3. Gedetailleerde Analyse van LLM-architecturen: Een vergelijking van verschillende LLM's (GPT-5.2, Grok-Code, DeepSeek-v3.2, MiniMax-m2) om inzicht te geven in hoe modelkeuze de evolutionaire uitkomst beïnvloedt.

Resultaten

De experimenten zijn uitgevoerd op TSPLIB-benchmarks (TSP) met een evolutionair dataset en een onafhankelijke testset.

• Prestatieverbetering: De geëvolueerde algoritmen (voornamelijk met GPT-5.2) presteren consistent beter dan handmatig ontworpen baselines (Baseline-ALNS).
  • Bij een vast iteratiebudget (1.000 iteraties) daalde de gemiddelde optimaliteitskloof op grote testinstanties van 4,18% naar 2,41%.
  • Bij een uitgebreid budget (25.000 iteraties) daalde de kloof op grote instanties van 3,18% naar 0,74%.
  • De verbetering was ook significant onder tijdsbeperkingen (60 seconden), wat wijst op betere computationele efficiëntie.
• Ablatie-studie: De grootste bijdrage aan de verbetering kwam van de Destroy/Repair-operators en de Destruction-rate Controller. Het vervangen van de geëvolueerde destroy-operator door de basisversie leidde tot een prestatiedaling van meer dan 136%.
• LLM-Vergelijking:
  • GPT-5.2 leverde de meest consistente resultaten op, vooral bij lange zoektijden en hoge iteratiebudgetten.
  • DeepSeek-v3.2 en MiniMax-m2 presteerden soms beter onder strikte tijdsbeperkingen (snellere convergentie in vroege fasen), maar misten de lange-termijn convergentie van GPT-5.2.
• Statistische Significantie: De Wilcoxon signed-rank tests bevestigden dat de verbeteringen statistisch significant zijn (p < 0,001) ten opzichte van de baseline.

Significantie en Inzicht

Het onderzoek toont aan dat LLM's in staat zijn om complexe metaheuristische algoritmen volledig te herontwerpen, waardoor de afhankelijkheid van menselijke expertise wordt doorbroken.

Ontdekte Mechanismen (Qualitative Analysis):
De geëvolueerde code onthulde innovatieve strategieën, zoals:

• Momentum-based Bayesian Bandit: Een operator-selectie die niet alleen kijkt naar huidige prestaties, maar ook naar de snelheid van verbetering, en recent gebruikte operators bewust straft om path-dependency te doorbreken.
• Adaptieve Tolerantie in Acceptatie: In plaats van elke verslechtering te straffen, introduceert het algoritme een dynamische drempel ($t_a$). Kleine verslechteringen worden als "ruis" geaccepteerd, terwijl grote verslechteringen streng worden gestraft. Dit helpt het algoritme om makkelijker uit lokale optima te ontsnappen zonder de stabiliteit te verliezen.
• Hybride Regret-Insertie: Een combinatie van "Regret" (kansverlies) en directe kosten om een balans te vinden tussen structurele noodzaak en kostenminimalisatie.

Conclusie:
Dit werk markeert een verschuiving van "menselijk ontworpen" naar "automatisch geëvolueerde" algoritmen. Het biedt een blauwdruk voor het ontwikkelen van robuuste, schaalbare en efficiënte optimalisatieoplossingen die beter presteren dan traditionele methoden, met name op complexe, grote schaalproblemen. Toekomstig werk richt zich op het uitbreiden naar VRP-varianten met complexere constraints en het co-evolueren van sterk gekoppelde modules.