Technische Samenvatting: CoEvo-AHD voor Bi-Component Gekoppelde Combinatorische Optimalisatie

1. Probleemdefinitie

Het artikel behandelt Bi-Component Gekoppelde Combinatorische Optimalisatie (CO) problemen, waarbij een oplossing bestaat uit twee semantisch verschillende maar onderling afhankelijke beslissingscomponenten. De kernuitdaging is dat de haalbaarheid of de objectieve waarde van het wijzigen van één component volledig afhangt van de staat van de andere component. Bijgevolg is de bruikbaarheid van een operator relationeel in plaats van intrinsiek; een operator die in isolatie goed presteert, kan de globale oplossing verslechteren wanneer deze gekoppeld wordt aan een suboptimale staat van de tweede component.

De auteurs passen dit framework toe op twee representatieve problemen:

• Traveling Thief Problem (TTP): Koppelt routing (Traveling Salesman Problem) met verpakking (0–1 Knapsack Problem). De volgorde van de tour beïnvloedt de reissnelheid op basis van de meegevoerde lading, terwijl het verpakkingsplan bepaalt welke lading op elk moment wordt meegedragen.
• Traveling Purchaser Problem (TPP): Koppelt marktselectie/routing met inkoopbeslissingen. De volgorde van bezoeken en de marktselectie bepalen de haalbare inkoopopties en kosten, terwijl inkoopbeslissingen de waarde van het bezoeken van specifieke markten beïnvloeden.

Bestaande door Large Language Models (LLM) gedreven methoden voor Automated Heuristic Design (AHD) evolueren heuristieken doorgaans als geïsoleerde algoritmische eenheden of zoekstrategieën (bijv. constructie versus reparatie). Deze methoden slagen er niet in om de door de probleemstructuur geïnduceerde complementariteit te vangen die vereist is voor bi-component gekoppelde problemen, waarbij operators gecocoëvolueerd moeten worden om synergetisch te functioneren over heterogene oplossingscomponenten.

2. Methodologie: CoEvo-AHD

De auteurs stellen CoEvo-AHD voor, een LLM-gestuurd dual-population co-evolutionair framework ontworpen om paren van component-operators automatisch te ontdekken en te verfijnen. Het framework werkt via vier stadia:

2.1 Dual-Population Initialisatie

Twee aparte operator-populaties worden onderhouden: $P_A$ voor component A (bijv. route-operators) en $P_B$ voor component B (bijv. verpakkings-operators).

• Initialisatie: Populaties starten met een mix van handmatig gespecificeerde seed-operators en door LLM gegenereerde operators.
• Validatie: Alle gegenereerde operators ondergaan syntaxis-, interface-, begrensde executie- en component-haalbaarheidsvalidatie voordat ze de populatie betreden.
• Interface: Operators geven alleen kandidaat-updates terug voor hun specifieke component, waarbij ze vertrouwen op een gedeeld informatiegeheugen en externe tools voor de globale context.

2.2 Coöperatieve Evaluatie

In tegen tegenstelling tot traditionele methoden die operators in isolatie scoren, evalueert CoEvo-AHD operators via gepaarde executie op volledige oplossingen.

• Selectie: Een lokale Thompson Sampling-strategie selecteert één operator uit $P_A$ en één uit $P_B$ voor elke zoekherstart.
• Alternerende Optimalisatie: Het geselecteerde paar wordt afwisselend aangeroepen binnen een zoektraject. Bijvoorbeeld, een route-operator stelt een permutatie van steden voor, die vervolgens wordt doorgegeven aan een verpakkings-operator (of vice versa).
• Reparatie & Reconstructie: Omdat componenten gekoppeld zijn, kunnen tussenliggende kandidaten onhaalbaar zijn. Het framework maakt gebruik van een tool-augmented probleemomgeving om haalbaarheidsreparatie, reconstructie en volledige objectieve evaluatie uit te voeren.
• Gedeelde Informatie: Een mutabele dictionary (shared_info) stelt operators in staat om zachte zoeksignalen uit te wisselen (bijv. laadprofielen, aanwijzingen voor kandidaat-insertie) zonder direct de logica van de andere component te overschrijven.

2.3 Populatiebeheer & Evolutie

Het framework hanteert een co-evolutionaire lus om de populaties te verfijnen:

• Scoring: Beloningen worden berekend op basis van de verbetering van de volledige gekoppelde oplossing. Deze beloningen updaten drie statistieken: individuele scores voor $o_A$ en $o_B$, en een pairwise synergy score ($S_{ij}$) voor het specifieke operatorpaar.
• Pruning: Slecht presterende operators worden verwijderd uit hun respectievelijke populaties.
• LLM-gestuurde Evolutie: Vacatures worden ingevuld via drie evolutionaire operaties:
  1. Intra-component Mutatie: Verfijnt een enkele ouder-operator.
  2. Intra-component Homogene Crossover: Combineert twee operators uit dezelfde populatie.
  3. Cross-Component Joint Crossover: Selecteert het best presterende paar $(o_A^*, o_B^*)$ op basis van synergie-scores en vraagt de LLM om hen te herschrijven als een verenigde, gecoördineerde entiteit. Dit stimuleert de generatie van operators met compatibele communicatieprotocollen en complementaire zoekveronderstellingen.

2.4 Tool-Augmented Omgeving

Om te voorkomen dat LLM's inefficiënte of foutgevoelige low-level code genereren, kapselt het framework kernoperaties (bijv. berekening van local-search delta's, greedy reconstructie, haalbaarheidscontroles) in gestandaardiseerde aanroepbare tools. Dit stelt LLM-gegenereerde operators in staat zich te concentreren op high-level neighborhood design en cross-component coördinatie.

3. Belangrijkste Bijdragen

1. Probleemformulering: Het artikel formuleert LLM-gestuurde AHD specifiek voor bi-component gekoppelde CO, waarbij de nuttigheid van een operator als relationeel wordt gedefinieerd en gezamenlijke beoordeling over heterogene oplossingscomponenten vereist.
2. CoEvo-AHD Framework: Een nieuw co-evolutionair architectuur met:
   • Component-specifieke operator-populaties.
   • Evaluatie gebaseerd op gepaard uitgevoerde executie om cross-component interacties te vangen.
   • Pairwise synergie-scoring om de selectie van complementaire operatorparen te sturen.
   • Cross-component joint crossover om wederzijds compatibele operators te evolueren.
3. Gestructureerde Communicatie & Tooling: De introductie van een gestructureerd inter-component communicatieprotocol en een tool-augmented omgeving die probleem-specifieke operaties standaardiseert, waardoor LLM's robuuste, high-level heuristische logica kunnen genereren.

4. Experimentele Resultaten

Het framework werd geëvalueerd op TTP- en TPP-benchmarks tegen state-of-the-art traditionele heuristieken en recente LLM-gebaseerde baselines.

• Traveling Thief Problem (TTP):

  • CoEvo-AHD behaalde de beste resultaten op kleine tot middelgrote instanties (TTP20, TTP50), waarbij het baselines zoals MATLS, S5 en CoCo overtrof.
  • Op grotere instanties (TTP100, TTP200) behaalde het de op één na beste gemiddelde score, waarbij het slechts achter CoCo bleef, maar significant beter presteerde dan MATLS en S5.
  • Dit suggereert dat het framework koppeling effectief vangt in kleinere zoekruimtes, maar uitdagingen ervaart met de zoekdiepte voor zeer grote instanties.

• Traveling Purchaser Problem (TPP):

  • CoEvo-AHD toonde een duidelijk algemeen voordeel, waarbij het de beste resultaten behaalde op vijf instantie-schalen (inclusclusief grote schalen zoals 150×100 en 150×150) en de op één na beste op drie andere.
  • Het verminderde de gemiddelde objectieve waarde met ongeveer 2,76% vergeleken met de op één na beste baseline (TA) en tot wel 11,42% vergeleken met ALNS.
  • De resultaten geven aan dat het framework bijzonder effectief is in het exploiteren van de synergie tussen routing en inkoopbeslissingen in TPP.

• Ablatie-studies:

  • Het verwijderen van de dual-population co-evolutie (het evolueren van slechts één component) veroorzaakte aanzienlijke prestatievermindering (bijv. ~11% daling op TPP), wat bevestigt dat het optimaliseren van componenten in isolatie onvoldoende is.
  • Het verwijderen van de tool-augmented omgeving leidde ook tot prestatiedalingen (~5,5% op TTP), wat het belang van gestandaardiseerde interfaces voor betrouwbaarheid en efficiëntie benadrukt.

5. Betekenis en Claims

Het artikel claimt dat CoEvo-AHD een verschuiving vertegenwoordigt in LLM-gestuurde AHD van het genereren van geïsoleerde algoritmische rollen naar het modelleren van door de probleemstructuur geïnduceerde operator-complementariteit. Door heterogene operator-populaties expliciet co-evolutionair te ontwikkelen en ze te evalueren via gezamenlijke executie, adresseert het framework de beperking van bestaande methoden die niet in staat zijn sterke koppeling tussen beslissingssubstructuren te verwerken.

De auteurs positioneren dit werk als een stap naar meer generaliseerbare geautomatiseerde heuristiek-ontwerp voor complexe, real-world optimalisatieproblemen waarbij oplossingscomponenten diep onderling afhankelijk zijn. Ze merken bescheiden op dat hoewel het framework zeer competitief is, er nog ruimte is voor verbetering in zoekdiepte en robuustheid voor zeer grootschalige instanties, en toekomstig werk zal gericht zijn op het uitbreiden van het framework naar problemen met meer dan twee gekoppelde componenten.