🔢 mathematics

CoupleEvo: Evolving Heuristics for Coupled Optimization Problems Using Large Language Models

Dit artikel introduceert CoupleEvo, een door grote taalmodellen gedreven raamwerk dat drie evolutionaire coördinatiestrategieën hanteert om heuristieken te ontwerpen voor gekoppelde optimalisatieproblemen, en aantoont dat op decompositie gebaseerde benaderingen stabielere en kwalitatief betere oplossingen opleveren dan geïntegreerde evolutie.

Oorspronkelijke auteurs: Thomas Bömer, Bastian Amberg, Max Disselnmeyer, Anne Meyer

Gepubliceerd 2026-05-08

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Thomas Bömer, Bastian Amberg, Max Disselnmeyer, Anne Meyer

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je probeert een enorm, ingewikkeld puzzel op te lossen. Maar hier zit de adder onder het gras: dit is niet zomaar één puzzel; het zijn twee (of meer) puzzels die aan elkaar zijn gelijmd. Als je een stukje in Puzzel A verplaatst, kan dat een stukje in Puzzel B kapotmaken. Om te winnen, kun je ze niet apart oplossen; je moet ze samen oplossen, maar alles tegelijk doen is zo verwarrend dat je brein (of een computer) overbelast raakt.

Dit paper introduceert een nieuwe methode genaamd CoupleEvo. Het maakt gebruik van een zeer slimme AI (een Large Language Model, of LLM) om de "regels" of "strategieën" (zogenaamde heuristieken) te bedenken die nodig zijn om deze aan elkaar gelijmde puzzels op te lossen.

Hier is hoe het paper het uitlegt, met behulp van eenvoudige analogieën:

Het Probleem: De "Aangelijmde" Puzzels

In de echte wereld zijn veel problemen "gekoppeld".

Voorbeeld 1 (De Bezorgbesteller): Stel je een bedrijf voor dat zijn magazijnvoorraad moet beheren en vrachtwagens moet sturen om goederen te bezorgen. Als je het magazijn perfect inpakt maar de vrachtwagens te klein zijn om het te vervoeren, faal je. Als je de vrachtwagenroutes perfect plant maar de voorraad opraakt, faal je ook. Je moet beide tegelijk oplossen.
Voorbeeld 2 (Het Robotmagazijn): Stel je een magazijn vol dozen voor waar robots items moeten verplaatsen. Sommige dozen blokkeren andere. Een robot kan Doos A niet verplaatsen totdat het Doos B heeft verplaatst. De "zoektocht naar de juiste zet" en het "plannen van het pad van de robot" zijn twee verschillende taken die volledig van elkaar afhankelijk zijn.

De Oplossing: De AI-coach

In plaats van dat een menselijke programmeur de regels schrijft voor het oplossen van deze puzzels, laten de auteurs een AI-coach de regels schrijven. De AI genereert code (de "heuristiek") die de computer vertelt hoe het verschillende oplossingen moet verkennen.

De grote vraag die het paper stelt is: Hoe moeten we de AI leren deze regels te leren wanneer er twee aan elkaar gelijmde puzzels zijn?

De auteurs probeerden drie verschillende "leerstijlen" (Evolutionaire Coördinatiestrategieën):

1. De "Eén-Ding-Tegelijk"-Strategie (Sequentieel)

De Analogie: Stel je voor dat je leert om een duet op de piano te spelen. Eerst oefen je alleen de linkerhand een maand lang tot je perfect bent. Vervolgens schakel je over naar de rechterhand en oefen je die een maand lang, terwijl je de linkerhand precies laat zoals je hem hebt achtergelaten.
Wat er gebeurde: De AI werd zeer snel heel goed in het eerste deel. Maar toen het overschakelde naar het tweede deel, had het moeite om te verbeteren omdat het eerste deel al "in steen was gebeiteld". Het was alsof je probeerde een nieuwe melodie voor de rechterhand aan te passen aan een linkerhand-deel dat al te stijf was. Het werkte goed, maar het botste vroeg tegen een plafond.

2. De "Oever en Terug Schakelen"-Strategie (Iteratief)

De Analogie: Je oefent het duet, maar deze keer wissel je elke paar minuten van hand. Je speelt de linkerhand, dan de rechter, dan weer de linker. Je past de linkerhand aan om bij de rechter te passen, en pas je vervolgens de rechter aan om bij de linker te passen.
Wat er gebeurde: Dit was de meest stabiele en betrouwbare methode. De AI raakte niet zo snel vast. Door constant te controleren hoe de twee delen bij elkaar passen, maakte het gestage, kleine verbeteringen aan beide kanten. Het vond de beste algehele balans, zelfs als het niet zo snel als de eerste methode de "perfecte" score bereikte.

3. De "Alles Tegelijk"-Strategie (Geïntegreerd)

De Analogie: Je probeert het hele duet in één grote sprong perfect te leren. Je probeert in hetzelfde moment de linkerhand, de rechterhand en hoe ze met elkaar interageren uit te vinden.
Wat er gebeurde: Dit was het meest chaotisch. Soms had de AI geluk en vond het een geweldige oplossing. Op andere momenten raakte het volledig verdwaald en produceerde het vreselijke resultaten. Omdat de "zoekruimte" (het aantal mogelijkheden) zo enorm was, had de AI moeite om consequent een goed pad te vinden.

De Resultaten

De onderzoekers testten deze drie methoden op twee real-world problemen (de Bezorgbesteller en het Robotmagazijn).

De Winnaar: De "Oever en Terug Schakelen" (Iteratieve) strategie was het meest betrouwbaar. Het produceerde consequent oplossingen van hoge kwaliteit die zeer stabiel waren.
De Tweede: De "Eén-Ding-Tegelijk" (Sequentiële) strategie was goed, maar raakte soms vast.
De Verliezer: De "Alles Tegelijk" (Geïntegreerde) strategie was te riskant; het was te onvoorspelbaar.

De Conclusie

Het paper laat zien dat wanneer je een complex probleem hebt dat bestaat uit twee onderling afhankelijke delen, je ze niet allemaal tegelijk moet proberen op te lossen, maar ze ook niet volledig apart moet oplossen. Het gouden middenweg is om de oplossingen samen te laten evolueren, maar door constant je focus tussen de twee delen te wisselen.

De door AI gegenereerde strategieën waren goed genoeg om sommige traditionele, door mensen gemaakte methoden te verslaan en kwamen zeer dicht in de buurt van het verslaan van de allerbeste high-tech methoden die momenteel beschikbaar zijn, wat bewijst dat AI kan leren om zijn eigen "spelregels" te schrijven voor complexe, aan elkaar gelijmde problemen.

Technische Samenvatting: CoupleEvo

Probleemdefinitie

Optimaliseringssystemen in de echte wereld bestaan vaak uit meerdere nauw met elkaar verbonden deelvragen waarvoor oplossingen gecoördineerd moeten worden om een hoge algehele prestatie te bereiken. Deze gekoppelde problemen combineren regelmatig twee of meer NP-moeilijke deelvragen, zoals in het Voorraad-Routeerprobleem (IRP) of het Multi-robot Multi-bay Unit-load Pre-marshalling Probleem (MR-MUPMP). Hoewel het optimaliseren van deelvragen geïsoleerd vaak suboptimale globale resultaten oplevert, is volledig geïntegreerde simultane optimalisatie vaak computationeel onuitvoerbaar vanwege de combinatorische groei van de gezamenlijke oplossingsruimte.

Bestaande frameworks voor geautomatiseerd heuristisch ontwerp, aangedreven door Large Language Models (LLM), zijn momenteel beperkt tot situaties met één probleem, waarbij ze één heuristiek voor één doel evolueren. Er is een lacune in de literatuur met betrekking tot het systematische ontwerp van meerdere interactieve heuristieken voor gekoppelde optimaliseringsproblemen, met name het ontbreken van een evolutionaire coördinatiestrategie om de onderlinge afhankelijkheden tussen deelvragen te beheren.

Methodologie: CoupleEvo

De auteurs stellen CoupleEvo voor, het eerste door LLM-aangedreven framework voor geautomatiseerd heuristisch ontwerp in gekoppelde optimaliseringsproblemen. Het framework opereert binnen een iteratieve Large Neighborhood Search (LNS)-context, waarbij de LLM de taak heeft om vernietigingsheuristieken te genereren voor elke deelvraag, terwijl herstelheuristieken deterministisch blijven.

Evolutionaire Coördinatiestrategieën

CoupleEvo introduceert drie distincte strategieën om het evolutionaire zoekproces over onderling afhankelijke deelvragen te sturen:

Sequentiële Evolutie: Heuristieken worden voor deelvragen achtereenvolgens geëvolueerd. De evolutie van deelvraag $k$ verloopt voor een vast aantal generaties, terwijl alle andere deelvragen hun momenteel best presterende heuristieken gebruiken (vast). Dit biedt conceptuele eenvoud, maar riskeert voortijdige convergentie, waarbij de eerst geëvolueerde heuristiek de zoekruimte voor de daaropvolgende deelvragen beperkt.
Iteratieve Evolutie: De evolutie wisselt tussen deelvragen over meerdere controle-rondes. In elke ronde doorloopt het algoritme alle deelvragen en verfijnt hun heuristieken op basis van de beste presteerders uit de vorige ronde. Deze strategie beoogt overfitting op een enkele deelvraag te voorkomen en behoudt flexibiliteit voor coördinatie.
Geïntegreerde Evolutie: Heuristieken voor alle deelvragen worden simultaan geëvolueerd. De LLM wordt geprompt om een volledige heuristiek-tuple (code en gedachten voor alle deelvragen) in één stap te genereren. Hoewel dit onderlinge afhankelijkheden expliciet modelleert, verhoogt het de zoekcomplexiteit en legt het hogere eisen aan de generatieve capaciteiten van de LLM.

Implementatiedetails

LLM: Het framework maakt gebruik van het open-source model Qwen3-coder:30b.
Prompting: Het systeem hanteert een suite van promptstrategieën die zijn aangepast uit eerder werk (EoH, ReEvo), waaronder initialisatie (I1), exploratie (E1, E2) en modificatie (M1, M2) prompts.
Evaluatie: Fitness wordt berekend op basis van de doelwaarde van de gekoppelde probleeminstanties. Voor IRP is fitness de relatieve gap ten opzichte van een state-of-the-art HGS-baseline; voor MR-MUPMP is het de gemiddelde doelwaarde.
Experimentele Opstelling: Het framework werd getest op twee domeinen:
- IRP: Integratie van voorraadbeheer en voertuigrouting.
- MR-MUPMP: Integratie van verplaatsingszoekopdracht (herordening van verplaatsingen) en voertuigrouting met voorrangsbepalingen.
- Alle strategieën kregen een gelijke evolutionaire begroting toegewezen (40 totale generaties) om een eerlijke vergelijking te waarborgen.

Belangrijkste Bijdragen

CoupleEvo Framework: De formulering van het eerste door LLM-aangedreven framework dat geautomatiseerd heuristisch ontwerp uitbreidt van situaties met één probleem naar gekoppelde optimaliseringsproblemen met meerdere onderling afhankelijke NP-moeilijke deelvragen.
Evolutionaire Strategieën: Het voorstellen en systematisch onderzoeken van drie coördinatiestrategieën (Sequentieel, Iteratief, Geïntegreerd) die definiëren hoe heuristieken voor interactieve deelvragen worden gegenereerd en verfijnd.
Uitgebreide Evaluatie: Uitgebreide experimentele evaluatie op twee representatieve domeinen voor gekoppelde optimalisatie, waardoor empirische inzichten worden geboden in de afwegingen tussen convergentiestabiliteit, zoekcomplexiteit en oplossingskwaliteit.

Experimentele Resultaten

De studie evalueerde de drie strategieën over 6 runs per strategie voor zowel IRP als MR-MUPMP.

Decompositie versus Integratie: Op decompositie gebaseerde strategieën (Sequentieel en Iteratief) toonden consistent een stabielere convergentie en hogere oplossingskwaliteit dan de Geïntegreerde strategie.
Sequentiële Strategie: Toonde een snelle initiële fitnessverbetering bij het evolueren van de eerste deelvraag. De convergentie vertraagde of platte echter vaak af bij de overstap naar de tweede deelvraag, wat suggereert dat de eerst geëvolueerde heuristiek de zoekruimte beperkte. Het behaalde de beste gemiddelde prestatie voor MR-MUPMP.
Iteratieve Strategie: Toonde een geleidelijker maar consistent verbeterende traject. Door de focus af te wisselen, werd voortijdige overfitting gemitigeerd en bleef aanpassingsvermogen behouden. Het behaalde de beste minimum- en mediane fitnesswaarden voor MR-MUPMP en de meest stabiele resultaten (kleinste spreiding) voor IRP.
Geïntegreerde Strategie: Lijdt onder verhoogde zoekcomplexiteit en hoge variabiliteit. Hoewel sommige runs concurrerende resultaten behaalden, vertoonde de strategie over het algemeen zwakkere prestaties en grotere variantie, wat wijst op moeilijkheden bij het consistent verfijnen van hoogwaardige heuristiek-tuples voor gekoppelde problemen.

Benchmarking

De best presterende geëvolueerde heuristieken (CoupleLNS) werden vergeleken met gevestigde literatuur:

IRP: CoupleLNS presteerde gemiddeld 5,61% beter dan klassieke matheuristieken (MH). Het behaalde concurrerende resultaten tegenover state-of-the-art Hybrid Genetic Search (HGS), met een gemiddelde gap van 2,96%, zonder te vertrouwen op uitgebreide probleemspecifieke engineering.
MR-MUPMP: In vergelijking met een stap-voor-stap sequentiële aanpak (SBS) met gebruik van optimale A*, had CoupleLNS een iets lagere oplossingskwaliteit op oplosbare instanties, maar slaagde het er wel in om alle instanties binnen de tijdslimiet op te lossen, terwijl SBS bij sommige instanties faalde. Bij vergelijking met een aangepaste SBS* (met een door LLM-gestuurde heuristiek) overtrof CoupleLNS deze met gemiddeld 5,01%.

Betekenis en Beweringen

Het paper beweert dat CoupleEvo het potentieel demonstreert van door LLM-aangedreven geautomatiseerd heuristisch ontwerp voor complexe gekoppelde optimaliseringsproblemen. De belangrijkste bevinding is dat het coördineren van evolutionaire zoekopdrachten over onderling afhankelijke deelvragen cruciaal is; strategieën gebaseerd op decompositie (sequentieel en iteratief) zijn momenteel effectiever dan geïntegreerde evolutie voor deze specifieke probleemtypen.

De auteurs positioneren hun werk niet als een vervanging voor klassieke methoden, maar als een complementaire aanpak. Zij suggereren dat op LLM gebaseerde methoden sterk afgestemde, probleemspecifieke heuristische componenten kunnen evolueren die bestaande frameworks zoals LNS versterken. Het werk benadrukt dat hoewel geïntegreerde evolutie theoretisch aantrekkelijk is voor het vastleggen van interacties tussen componenten, de huidige LLM-capaciteiten en zoekcomplexiteit strategieën bevoordelen die het probleem decomponeren terwijl iteratieve coördinatie wordt behouden.

Toekomstige onderzoeksrichtingen die door de auteurs worden geïdentificeerd, omvatten het aanpassen van het framework aan problemen met meer dan twee deelvragen, het verbeteren van de stabiliteit van de geïntegreerde strategie, en het ontwikkelen van adaptieve coördinatiestrategieën die dynamisch schakelen tussen optimaliseringsproblemen.