Code World Models for Parameter Control in Evolutionary Algorithms

Dit onderzoek toont aan dat Code World Models, waarbij een LLM de dynamiek van een evolutionair algoritme leert simuleren op basis van suboptimale trajecten, de mutatiesterkte effectief kan sturen om superieure prestaties te behalen op diverse combinatorische optimalisatieproblemen vergeleken met bestaande adaptieve methoden en DQN.

De kern

Stel je voor dat je een grote puzzel moet oplossen, zoals een Sudoku of een legpuzzel met duizend stukjes. Je hebt een robot die stukjes verplaatst om de puzzel op te lossen. Maar hier is het probleem: de robot weet niet precies hoe hij de stukjes moet verplaatsen. Soms moet hij één stukje verschuiven, soms tien, en soms moet hij er twintig tegelijk verplaatsen.

De vraag is: Hoeveel stukjes moet de robot per keer verplaatsen om de puzzel het snelst op te lossen?

In de wereld van computerwetenschappen noemen ze dit "parameter control" (het regelen van de instellingen). Meestal gebruiken mensen vaste regels of slimme algoritmen om dit te bepalen, maar die regels werken niet altijd goed, vooral als de puzzel een "val" heeft waar de robot in vastloopt.

Dit artikel introduceert een nieuwe, slimme manier om dit op te lossen met behulp van een AI-chatbot (een Large Language Model, of LLM).

Hier is hoe het werkt, vertaald naar alledaagse taal:

1. De "Gids" die de AI zelf schrijft

Stel je voor dat je een nieuwe stad binnenkomt en je wilt de snelste route naar het centrum vinden. Normaal gesproken zou je een kaart gebruiken of iemand vragen.
In dit onderzoek laten ze de AI (de chatbot) echter zelf een kaart tekenen.

• De training: De AI kijkt eerst naar een paar honderd voorbeelden van hoe de robot de puzzel probeerde op te lossen. Sommige pogingen waren slordig, sommige waren slim, maar geen enkele was perfect.
• De synthese: De AI schrijft vervolgens een klein computerprogramma (een "wereldmodel"). Dit programma is als een simulator: het kan voorspellen wat er gebeurt als de robot 1 stukje verplaatst, of 10, of 20.
• Het resultaat: De AI heeft nu een "gids" in zijn hoofd die zegt: "Als we nu op dit punt zijn, is het slim om 3 stukjes te verplaatsen, want dan komen we dichter bij de oplossing."

2. De "Valse Val" (De Jump-probleem)

Sommige puzzels hebben een valstrik. Stel je voor dat je bijna klaar bent met je legpuzzel, maar er zit een gat in het midden. Als je probeert het gat te overbruggen door één stukje te verplaatsen, mislukt het. Je moet precies 2 stukjes tegelijk verplaatsen om eroverheen te springen.

• De oude robots: De traditionele algoritmen zien dat het niet lukt en denken: "Oh, ik moet voorzichtig zijn. Ik ga maar één stukje verplaatsen." Daardoor blijven ze voor eeuwig in de val zitten.
• De nieuwe AI-robot: Omdat de AI zelf de kaart heeft getekend, ziet hij de valstrik in zijn simulator. Hij denkt: "Ah, ik zie dat ik hier een grote sprong moet maken!" en verplaatst direct 2 stukjes.
• Het resultaat: De oude robots halen het nooit (0% succes), maar de nieuwe AI haalt het 100% van de tijd.

3. Waarom is dit zo speciaal?

Er zijn twee grote voordelen aan deze methode:

• Het is niet "zwart doos": Veel moderne AI's (zoals Deep Learning) zijn als een magische doos: je stopt data erin en er komt een antwoord uit, maar je weet niet waarom. Hier schrijft de AI echter echt Python-code. Je kunt die code lezen en zien: "Ah, de AI heeft besloten om hier 2 stukjes te verplaatsen omdat de kans op succes dan het grootst is." Het is transparant en controleerbaar.
• Het leert van weinig data: Om een traditioneel AI-systeem (zoals DQN) te trainen, moet je duizenden keren proberen en falen. Deze AI heeft maar een paar honderd voorbeelden nodig om een goede kaart te tekenen. Het is alsof je iemand die maar één keer door een stad is gelopen, laat zien hoe je een perfecte navigatie-app bouwt.

4. Wat hebben ze ontdekt?

De onderzoekers hebben dit getest op verschillende soorten "puzzels":

1. Simpele puzzels: De AI deed het net zo goed als de beste bekende methoden.
2. Tricky puzzels (Jump): Waar alle andere methoden faalden, slaagde de AI.
3. Chaos-puzzels (NK-landschap): Puzzels waar geen vaste regels voor bestaan. Hier gebruikte de AI statistieken uit de data om een kaart te maken en deed het weer beter dan iedereen.

Conclusie

Dit artikel laat zien dat je geen menselijke expert nodig hebt om de beste regels voor een robot te bedenken. Als je een slimme AI vraagt om een simulator te schrijven op basis van wat hij heeft gezien, kan die AI zelf de beste strategie bedenken.

Het is alsof je een student vraagt om een handleiding te schrijven voor het oplossen van een puzzel, gebaseerd op het kijken naar anderen die het proberen. De student schrijft de handleiding, en die handleiding blijkt beter te werken dan de handleidingen van de oude experts. En het mooiste is: je kunt de handleiding lezen en begrijpen wat er gebeurt.

Technische samenvatting

Titel: Code World Models voor Parametercontrole in Evolutionaire Algoritmen

Auteurs: Camilo Chacón Sartori en Guillem Rodríguez Corominas

---

1. Het Probleem

Een fundamentele uitdaging in evolutionair computationeel onderzoek is parametercontrole: het bepalen van de optimale instellingen voor een algoritme tijdens de uitvoering.

• Specifiek probleem: Voor het $(1+1)$-RLS$_k$-algoritme (een mutatie-only optimizer die een bitstring manipuleert), moet op elk tijdstip worden bepaald hoeveel bits ($k$) er precies moeten worden omgekeerd.
• Uitdaging: De optimale adaptieve strategie $k^*(i)$ is bekend voor eenvoudige, unimodale landschappen (zoals LeadingOnes en OneMax), maar niet voor complexe, misleidende landschappen zoals Jump$_k$ (waar een "vallei" van lage fitness de optimalisatie blokkeert) of NK-landschappen (waar geen gesloten wiskundig model bestaat).
• Bestaande beperkingen: Traditionele adaptieve regels (zoals multiplicative update rules) werken goed op gladde landschappen, maar falen op misleidende landschappen omdat ze $k$ verkleinen tijdens stagnatie, terwijl juist een vergroting van $k$ nodig is om de vallei te overbruggen.

2. Methodologie: Code World Models (CWM)

De auteurs passen Code World Models (CWM) toe, oorspronkelijk ontwikkeld voor deterministische spellen, op stochastische combinatorische optimalisatie. In plaats van een neurale netwerkbasis te gebruiken, synthetiseert een Large Language Model (LLM) een Python-programma dat de dynamiek van de optimizer simuleert.

Het proces verloopt in drie fasen:

1. Trajectcollectie: Er worden 200–300 suboptimale trajecten gegenereerd door $(1+1)$-RLS$_k$ te draaien met diverse, niet-optimale beleidsregels (bijv. willekeurig, vast $k=1$, of $\sqrt{n}$). Geen enkel traject bevat kennis van de optimale strategie of de "gap" parameter ($k_{jump}$).
2. CWM-synthese: Een LLM (Claude Sonnet 4) ontvangt een prompt met:
   • Een wiskundige beschrijving van het probleem.
   • Een steekproef van de trajecten.
   • Cruciaal: Voor moeilijke problemen (Jump$_k$, NK) wordt de prompt verrijkt met een empirische transitietabel (statistieken over $P(\text{verbetering} | \text{fitness}, k)$ en gemiddelde $\Delta f$).
   • De LLM genereert een Python-klasse (SynthesizedCWM) met methoden om de volgende staat te voorspellen en de waarde van een actie te evalueren.
3. Greedy Planning: Tijdens de online fase gebruikt het algoritme het gegenereerde CWM voor een één-stap lookahead. Op elke stap wordt $k^*$ gekozen die de verwachte fitness van de volgende staat maximaliseert:
   $$k^* = \arg \max_k \text{evaluate\_state}(\text{predict\_next\_state}(s, k))$$
   Opmerking: In tegenstelling tot de originele CWM-werkzaamheden die Monte Carlo Tree Search (MCTS) gebruikten, volstaat hier een simpele greedy planning omdat het probleem grotendeels Markoviaan is met een horizon van 1.

3. Belangrijkste Bijdragen

1. Extensie naar Stochastische Optimalisatie: CWM's worden succesvol toegepast op probabilistische combinatorische problemen in plaats van alleen deterministische games.
2. Efficiëntie van Greedy Planning: Het paper toont aan dat complexe zoekalgoritmen (MCTS) overbodig zijn; een simpele greedy planner op het gegenereerde model is voldoende en veel efficiënter.
3. Overwinning op Misleidende Landschappen: Op het Jump$_k$-probleem, waar alle bestaande adaptieve baselines falen (0% succes), bereikt CWM-greedy een 100% succesratio zonder ooit de waarde van $k_{jump}$ te hebben gezien.
4. Vervanging van Gesloten Modellen: Voor NK-landschappen (waar geen wiskundig model bestaat) bewijst het paper dat gestructureerde empirische statistieken in de prompt voldoende zijn om een superieur model te synthetiseren.
5. Superioriteit t.o.v. Deep Reinforcement Learning (DQN): CWM is aanzienlijk stoffiënter (200 offline trajecten vs. 500 online episodes), heeft een hogere succesratio en generaliseert beter dan DQN.

4. Resultaten

Benchmark	Resultaat CWM-greedy	Vergelijking met Baselines
LeadingOnes	1,045 stappen (6% van optimaal)	Significant beter dan alle adaptieve regels ($p < 0.0001$).
OneMax	190 stappen (2% van optimaal)	Vergelijkbaar met de beste heuristiek (RLS_1), maar mist de scherpe "cliff" in het beleid niet.
Jump$_k$	100% succesratio	Alle adaptieve baselines (EA$\alpha$, self-adjusting) falen (0% succes). CWM infereert correct dat $k$ moet worden verhoogd in de vallei.
NK-Landschap	36,94 (gemiddelde beste fitness)	Beste resultaat op alle 15 gegenereerde instanties ($p < 0.001$). Werkt zonder wiskundig model, alleen met data.
Generalisatie	78% succes op $k=3$ (getraind op $k=2$)	DQN en EA$\alpha$ dalen naar 0% succes bij $k=3$. CWM generaliseert omdat het het onderliggende wiskundige model (hypergeometrisch) heeft geleerd.
Efficiëntie	100% succes met 200 trajecten	DQN heeft 500 episodes nodig en bereikt slechts 58% succes.

Analyse van DQN-falen: DQN overfitte op de exploratie-noise ($\epsilon$-greedy) tijdens het trainen en leert de zeldzame, kritieke "vallei-overgang" niet te herkennen. CWM encodeert de probleemstructuur expliciet in code, wat robuustheid biedt.

5. Betekenis en Conclusie

Dit paper biedt een pragmatische oplossing voor het integreren van generatieve AI in evolutionaire algoritmen:

• Van Black-box naar Auditable Code: In plaats van een ondoorzichtig neurale netwerkgewichten te gebruiken, produceert de LLM leesbare Python-code die als wereldmodel fungeert. Dit maakt het proces controleerbaar en combineert statistische ervaring met formele analyse.
• Data-efficiëntie: CWM leert effectief uit beperkte, suboptimale data en vereist geen dure online training zoals RL.
• Complementaire Rol: CWM vervangt niet de wiskundige theorie, maar vult deze aan. Het kan strategieën afleiden voor problemen waarvoor geen gesloten-formule oplossing bestaat, door gestructureerde data te vertalen naar een voorspellend model.

De auteurs concluderen dat Code World Models een krachtige nieuwe richting zijn voor adaptieve parametercontrole, vooral in complexe, misleidende optimalisatieruimtes waar traditionele methoden en standaard RL falen.