ReVEL: Multi-Turn Reflective LLM-Guided Heuristic Evolution via Structured Performance Feedback

Het artikel introduceert ReVEL, een hybride framework dat grote taalmodellen (LLM's) via multi-turn reflectie en gestructureerde prestatiefeedback integreert in een evolutionair algoritme om robuustere en effectievere heuristieken voor NP-moeilijke combinatorische optimalisatieproblemen te genereren dan bestaande eenmalige code-synthesemethoden.

De kern

Stel je voor dat je een super slimme, maar soms wat ongeduldige chef-kok hebt. Deze chef (een Groot Taalmodel of LLM) kan recepten schrijven die enorm ingewikkeld zijn. Maar als je hem vraagt om het perfecte recept voor een lastig gerecht (zoals het vinden van de snelste route voor een vrachtwagen of het inpakken van dozen in een container), geeft hij je vaak maar één keer een recept.

Soms is dat recept goed, maar vaak is het niet perfect. En als het mislukt, zegt de chef: "Nou, hier is een nieuw recept," zonder echt te kijken waarom het vorige mislukt is. Hij probeert het gewoon opnieuw, hopend op geluk.

ReVEL is een nieuwe manier om met deze chef te werken. Het is alsof je een ervaren sous-chef (een evolutionair algoritme) aanstelt die samenwerkt met de chef-kok.

Hier is hoe het werkt, in simpele termen:

1. De "Kookwedstrijd" (De Evolutie)

In plaats van dat de chef één recept stuurt, laat ReVEL hem een hele groep recepten maken.

• De Sous-chef kijkt naar de resultaten: Hij proeft al deze gerechten. Sommige zijn te zout, andere zijn te droog, en een paar zijn heel lekker.
• Groeperen: De sous-chef deelt de recepten in. Hij zegt: "Deze drie recepten zijn allemaal te zout (groep A), en deze twee zijn te droog (groep B)."

2. De "Reflectie" (Het Bespreken)

Dit is het magische deel. In plaats van dat de chef gewoon een nieuw recept schrijft, krijgt hij een gesprek met de sous-chef.

• De sous-chef zegt: "Kijk, in groep A (de zoute gerechten) zien we dat als je minder zout gebruikt, het beter wordt. Maar in groep B (de droge gerechten) werkt dat niet."
• De chef-kok denkt hier dan even over na (dit noemen ze multi-turn reasoning). Hij zegt: "Ah, ik snap het! Ik moet niet alleen het zout aanpassen, maar ook de kooktijd veranderen voor de droge gerechten."
• Hij past zijn recepten aan op basis van deze specifieke feedback.

3. De "Proefronde" (Selectie)

De chef maakt nu een nieuwe versie van de recepten. De sous-chef proeft ze weer.

• Als het beter is, houden we het recept.
• Als het slechter is, gooien we het weg.
• Dit proces herhaalt zich steeds. De chef wordt steeds slimmer door te leren van de fouten van de vorige ronde, net zoals een mens die een puzzel oplost door stap voor stap te kijken wat wel en wat niet werkt.

Waarom is dit zo goed?

De oude methoden waren als een loterij: "Ik probeer 1000 recepten en hoop dat er één goed is."
ReVEL is als een meesterkok die leert van zijn fouten:

• Het ziet patronen: Het merkt op dat bepaalde fouten vaak terugkomen in bepaalde groepen recepten.
• Het is geduldig: Het geeft de chef de tijd om na te denken en zijn strategie aan te passen, in plaats van hem te laten panikeren en snel iets nieuws te gooien.
• Het werkt voor alles: Of het nu gaat om het inpakken van dozen (Bin Packing) of het plannen van een rondrit voor een vrachtwagen (Traveling Salesman), deze methode maakt de oplossingen slimmer en robuuster.

Kortom: ReVEL is een slimme samenwerking tussen een creatieve AI (de chef) en een kritische evaluator (de sous-chef). Door samen te werken in kleine groepjes en steeds terug te kijken naar wat er misging, vinden ze veel sneller de perfecte oplossing dan wanneer ze het alleen zouden proberen. Het is het verschil tussen "gokken" en "leren".

Technische samenvatting

1. Probleemstelling

Het ontwerpen van effectieve heuristieken voor NP-hard combinatorische optimalisatieproblemen (zoals het Travelling Salesman Problem - TSP, en het Bin Packing Problem - BPP) is traditioneel een arbeidsintensieve taak die veel expertise vereist. Bestaande methoden hebben beperkingen:

• Classische heuristieken: Zijn vaak handmatig ontworpen en gebaseerd op vaste regels, wat hun aanpassingsvermogen beperkt.
• Hyper-heuristieken: Selecteren of combineren bestaande componenten uit een vooraf gedefinieerde pool, maar ontdekken zelden fundamenteel nieuwe structuren.
• LLM-gebaseerde benaderingen (huidige staat): Methoden zoals EoH (Evolution of Heuristics) en ReEvo gebruiken Large Language Models (LLMs) vaak voor "one-shot" code-synthese of beperkte reflectie. Ze missen een gestructureerd mechanisme voor iteratief, multi-turn redeneren op basis van geaggregeerde prestatiefeedback. Hierdoor worden verbeteringen vertraagd en ontvangt het LLM slechts grove signalen over de prestaties van heuristieken.

Het centrale probleem is hoe men LLMs kan integreren in evolutionaire algoritmen (EA) zodat ze niet alleen code genereren, maar ook reflecteren op groepsprestaties om gerichte, iteratieve verbeteringen door te voeren.

2. Methodologie: ReVEL

De auteurs stellen ReVEL voor: een hybride framework dat een evolutionair algoritme combineert met een LLM via reflectieve, multi-turn interactie. Het framework bestaat uit drie kernfasen:

A. Groepering en Gedragsclustering (Structured Performance Feedback)

In plaats van heuristieken individueel te evalueren, worden ze gegroepeerd om de feedback voor het LLM informatiever en compacter te maken.

• Performance-Profile Vector: Elke heuristiek $h$ wordt vertegenwoordigd door een genormaliseerde vector $z(h)$ op basis van prestaties op een reeks testinstances.
• Homogene Groepen: Heuristieken met vergelijkbaar gedrag (gemeten via cosine similarity op prestatie en CodeBLEU voor semantische gelijkenis) worden gegroepeerd. Dit stelt het LLM in staat om fijne, contextuele vergelijkingen te maken binnen een coherent gezin van oplossingen.
• Heterogene Groepen: Groepen worden samengesteld uit diverse homogene clusters om de semantische diversiteit te maximaliseren. Dit stimuleert creatieve synthese en het ontdekken van nieuwe strategieën.
• Entropie-gewogen sampling: De diversiteit van clusters wordt gemeten via entropie; clusters met hogere entropie (meer diversiteit) krijgen een hogere kans om in een heterogene groep te worden opgenomen.

B. Reflectieve Multi-Turn Verfijning

Het LLM fungeert niet als statische generator, maar als een adaptieve redeneerder binnen een lus van Observeer $\rightarrow$ Redeneer $\rightarrow$ Acteert.

• State Representation: Het LLM ontvangt een compacte staat $S_t$ die diagnostische kenmerken van de groep (kosten, verbeteringsdelta's) en de geschiedenis bevat.
• Adaptieve Strategie: Het model kiest dynamisch tussen twee modi:
  • Exploratie: Wordt geactiveerd bij stagnatie; het LLM stelt nieuwe, divergente heuristieken voor (bijv. nieuwe operatoren).
  • Exploitatie: Wordt geactiveerd bij veelbelovende kandidaten; het LLM voert gerichte verfijningen uit (parameter tuning, patching).
• Feedback Loop: Na elke generatie wordt de feedback geüpdatet met nieuwe prestatieobservaties, waardoor het LLM zijn redenering kan baseren op geaccumuleerde bewijzen in plaats van geïsoleerde pogingen.

C. Evolutionaire Meta-Controller

Een EA-basise controller selecteert de beste heuristieken uit de gegenereerde kandidaten en balanceert exploratie en exploitatie over de generaties heen.

3. Belangrijkste Bijdragen

1. Reflectief LLM-EA Framework: ReVEL transformeert heuristische ontdekking van een reeks onafhankelijke generaties naar een coherente verfijningscyclus door multi-turn redenering te integreren.
2. Prestatiebewuste Groepering: Een nieuw mechanisme dat reflectieve feedback structureert rondom gedragscoherente clusters, wat leidt tot meer informatieve analyses en generaliseerbare verbeteringen.
3. Gestuurde Multi-Turn Prompting: Een strategie die de trade-off tussen exploratie en exploitatie principieel regelt binnen de evolutionaire lus.
4. Empirische Validatie: Uitgebreide experimenten tonen aan dat ReVEL robuustere en diversere heuristieken produceert dan bestaande state-of-the-art methoden.

4. Resultaten

De methode werd getest op standaard benchmarks: TSP (10 tot 200 steden) en Online Bin Packing (capaciteiten 100-500, items tot 10k).

• Superieure Prestaties: ReVEL overtreft consistent sterke baselines zoals EoH en ReEvo, evenals klassieke heuristieken (First-Fit, Best-Fit).
  • Bin Packing: Bij een capaciteit van 300 bereikte ReVEL een overschot van <0,3% op lange stromen, terwijl andere methoden varieerden tussen 0,2% en 0,6%.
  • TSP: ReVEL behaalde lagere optimaliteitsgaten (gap) dan LLM-baselines over alle instanciegroottes.
• Robuustheid t.o.v. LLM Backbone: De prestaties van ReVEL zijn stabiel over verschillende LLM-modellen (DeepSeek V3, Kimi, Qwen, GLM), wat aantoont dat het succes voortkomt uit het framework en niet alleen uit de kracht van het onderliggende model.
• Ablatie-studie: Het verwijderen van de multi-turn verfijning of de groeperingsmechanismen leidde tot een drastische prestatiedaling (bijv. van 9,20% gap naar 17,18% bij TSP50), wat de noodzaak van beide componenten bevestigt.
• Analyse van Redeneergedrag: De analyse toont aan dat ReVEL een "explore-then-exploit" traject volgt, waarbij de meeste prestatiewinst wordt behaald door gefocuste verfijning in de midden-fase van de iteraties.

5. Betekenis en Conclusie

ReVEL introduceert een principieel paradigma voor geautomatiseerd heuristisch ontwerp. Door LLMs te positioneren als adaptieve probleemoplossers die structurele feedback analyseren in plaats van statische code-generators, overwint het de beperkingen van eerdere methoden.

• Wetenschappelijke Impact: Het paper toont aan dat gestructureerde, multi-turn reflectie essentieel is om de redeneercapaciteit van LLMs volledig te benutten voor complexe optimalisatieproblemen.
• Praktische Toepassing: Het framework biedt een schaalbare en sample-efficiënte route voor het ontwikkelen van heuristieken in logistiek, supply chain management en andere domeinen waar combinatorische optimalisatie cruciaal is.
• Toekomstperspectief: Hoewel de methode momenteel beperkt is tot specifieke benchmarks, suggereert de generalisatie over verschillende probleemtypen (TSP, BPP, CVRP) dat het een veelzijdig instrument is voor de toekomst van AI-gedreven algoritmisch ontwerp.

Kortom, ReVEL bewijst dat het combineren van evolutionaire algoritmen met gestructureerde, reflectieve LLM-interactie leidt tot significante doorbraken in de kwaliteit en diversiteit van gegenereerde optimalisatie-heuristieken.