Code World Models for Parameter Control in Evolutionary Algorithms

Die vorgestellte Arbeit zeigt, dass Code World Models, bei denen ein LLM aus suboptimalen Trajektorien einen Simulator für die Dynamik eines Evolutionären Algorithmus synthetisiert, in der Lage sind, die Mutationsstärke effizient zu steuern und dabei auf verschiedenen Optimierungsproblemen die Leistung theoretisch optimaler Strategien erreichen oder bestehende Baselines deutlich übertreffen.

Das Wesentliche

Das große Problem: Der blinde Sucher

Stell dir vor, du suchst den höchsten Punkt in einem riesigen, nebligen Bergland (das ist das Optimierungsproblem). Du hast einen Wanderer, der immer genau k Schritte in eine zufällige Richtung macht. Wenn er höher kommt, bleibt er dort; wenn nicht, geht er zurück.

Die große Frage ist: Wie groß sollen diese Schritte (k) sein?

• Sind die Schritte zu klein? Dann kommst du nie voran.
• Sind sie zu groß? Dann landest du vielleicht in einem Abgrund oder überspringst den Gipfel.

Bisher haben Algorithmen versucht, diese Schrittlänge automatisch anzupassen (z. B. "Wenn ich steige, mache ich größere Schritte; wenn ich falle, mache ich kleinere"). Das funktioniert gut auf einfachen, glatten Hügeln. Aber auf schwierigen, trügerischen Landschaften (wie einem Tal, das wie ein Berg aussieht, aber eigentlich ein Sumpf ist) versagen diese alten Regeln komplett. Der Wanderer bleibt stecken und gibt auf.

Die neue Lösung: Der "Code-Orakel"-Assistent

Die Forscher aus diesem Papier haben eine geniale Idee gehabt. Statt dem Wanderer eine starre Regel zu geben, haben sie einem Künstlichen Intelligenz-Modell (einem LLM, ähnlich wie ein sehr kluger Chatbot) eine neue Aufgabe gegeben:

"Lies die Geschichte von 200 Wanderern, die gescheitert sind, und schreibe ein kleines Computerprogramm, das vorhersagt, was als Nächstes passiert."

Das ist das Herzstück: Code World Models (CWM).

Stell dir vor, du hast einen alten, schmutzigen Fahrtenbuch (die Daten der gescheiterten Wanderer). Du gibst das Buch einem genialen Ingenieur (dem KI-Modell) und sagst: "Schreib mir ein kleines Skript, das simuliert, wie sich mein Wanderer verhält, wenn er verschiedene Schrittgrößen wählt."

Der Ingenieur schreibt ein Python-Programm. Dieses Programm ist wie ein Kristallkugel-Simulator:

1. Du sagst ihm: "Ich bin hier auf Höhe X und habe eine Schrittgröße von 5."
2. Der Simulator berechnet: "Mit Schrittgröße 5 hast du 10 % Chance, höher zu kommen. Mit Schrittgröße 2 hast du 80 % Chance."
3. Dein Wanderer wählt dann sofort die beste Option (hier: Schrittgröße 2).

Warum ist das so besonders?

Hier kommen die kreativen Vergleiche, um zu verstehen, warum das Papier so aufregend ist:

1. Der Trick mit dem "Trügerischen Tal" (Jumpk)

Stell dir vor, du bist in einem Tal, das aussieht wie ein Hügel, aber eigentlich ein Sumpf ist. Um herauszukommen, musst du genau 2 Schritte in eine ganz bestimmte Richtung machen.

• Die alten Regeln: Wenn der Wanderer nicht vorankommt, denkt er: "Oh, ich mache die Schritte zu groß!" und macht sie kleiner (z. B. auf 1). Aber mit 1 Schritt kommst du aus dem Sumpf nie raus. Er ertrinkt.
• Der KI-Assistent: Er hat die Geschichte der anderen Wanderer gelesen. Er weiß: "Aha! Wenn man in diesem Sumpf feststeckt, muss man die Schritte plötzlich vergrößern, um genau über den Rand zu springen."
• Das Ergebnis: Der KI-gesteuerte Wanderer schafft es zu 100 % aus dem Tal. Die alten Methoden schaffen es zu 0 %.

2. Der Unterschied zum "DQN" (Lernen durch Ausprobieren)

Es gibt eine andere Methode, bei der der Wanderer einfach blind herumtobt und lernt, was funktioniert (Deep Reinforcement Learning, DQN).

• Das Problem: Der Wanderer muss das "Sumpf-Überqueren" zufällig finden. Das passiert aber so selten, dass er es in 500 Versuchen nie lernt. Er bleibt stecken.
• Der KI-Ansatz: Der KI-Assistent muss nicht blind herumtoben. Er liest die Logik der Landschaft und schreibt ein Programm, das die Wahrscheinlichkeiten berechnet. Er braucht viel weniger Daten (200 Geschichten statt 500 Versuche) und ist viel schlauer.

3. Die "Unbekannte Landschaft" (NK-Landscape)

Manchmal gibt es gar keine mathematische Formel für den Berg. Es ist ein chaotisches Gestein.

• Hier kann der KI-Assistent nicht auf eine Formel zurückgreifen. Stattdessen gibt man ihm eine Tabelle mit Statistiken aus den gescheiterten Versuchen ("Wenn man bei Höhe 20 war und 5 Schritte gemacht hat, ist man oft gestolpert").
• Der Assistent schreibt ein Programm, das diese Tabelle wie eine Landkarte nutzt. Und das funktioniert überraschend gut! Er findet den Weg, auch wenn niemand die Formel des Berges kennt.

Das Fazit in einem Satz

Die Forscher haben gezeigt, dass man einer KI nicht sagt, wie sie einen Berg besteigen soll. Stattdessen lässt man sie ein kleines Computerprogramm schreiben, das die Regeln des Berges versteht. Mit diesem Programm kann der Wanderer dann jeden Schritt perfekt planen – und findet Lösungen, die für alle anderen Algorithmen unmöglich erscheinen.

Warum ist das toll?
Weil es die KI nicht als "Black Box" (ein undurchsichtiges Gehirn) benutzt, sondern sie zwingt, ihr Wissen in klaren, überprüfbaren Code zu gießen. Das ist wie ein Ingenieur, der nicht nur sagt "Ich glaube, das funktioniert", sondern einen Bauplan zeichnet, den man nachprüfen kann.

Das Papier beweist: Wenn man KI richtig einsetzt, kann sie nicht nur Daten analysieren, sondern neue Strategien erfinden, die wir Menschen mit unseren alten Regeln nie gefunden hätten.

Technische Zusammenfassung

1. Problemstellung

Ein fundamentales Problem in der evolutionären Berechnung ist die adaptive Parametersteuerung. Im Kontext des (1+1)-RLS$_k$-Algorithmus (ein Optimierer, der in jedem Schritt genau $k$ Bits eines Bitstrings umdreht) lautet die zentrale Frage: Welchen Wert für die Mutationsstärke $k$ sollte man in jedem Schritt wählen, um die Konvergenzgeschwindigkeit zu maximieren?

• Herausforderung: Während für einfache unimodale Landschaften (wie LeadingOnes und OneMax) die optimale adaptive Strategie $k^*(i)$ bekannt ist, existiert für komplexe, täuschende Landschaften (wie Jump$_k$ oder NK-Landschaften) keine geschlossene Formel.
• Versagen bestehender Methoden: Herkömmliche adaptive Regeln (z. B. EA$\alpha$, Selbstanpassung) funktionieren gut auf unimodalen Funktionen, indem sie $k$ bei Erfolg erhöhen und bei Stagnation verringern. Auf täuschenden Landschaften (deceptive landscapes) wie Jump$_k$ führt dies jedoch zum Scheitern: Da der Algorithmus in einem „Tal" (Valley) stagniert, wird $k$ verringert, obwohl gerade eine Erhöhung von $k$ notwendig wäre, um das Tal zu überwinden.
• Ziel: Entwicklung einer Methode, die aus suboptimalen Trajektorien lernt, ein Modell der Optimierungsdynamik zu erstellen und daraus eine optimale Parametersteuerung ableitet, ohne dass Oracle-Wissen (z. B. der genaue Wert von $k_{jump}$) vorliegt.

2. Methodik: Code World Models (CWMs)

Die Autoren erweitern das Konzept der Code World Models (CWMs), die ursprünglich für deterministische Spiele entwickelt wurden, auf stochastische kombinatorische Optimierung.

Der Workflow besteht aus drei Phasen:

1. Datensammlung (Offline):

   • Der (1+1)-RLS$_k$-Algorithmus wird mit diversen, nicht-optimalen Strategien (z. B. zufällig, festes $k$, $\sqrt{n}$) ausgeführt.
   • Es werden 200–300 Trajektorien gesammelt, die vollständige Übergangsdaten enthalten.
   • Wichtig: Keine der sammelnden Strategien nutzt Oracle-Wissen (z. B. den optimalen $k$-Wert oder $k_{jump}$).

2. Synthese des CWM durch ein LLM:

   • Ein Large Language Model (LLM, hier Claude Sonnet 4) erhält einen Prompt, der eine mathematische Problembeschreibung und Stichproben aus den gesammelten Trajektorien enthält.
   • Für schwierige Probleme (Jump$_k$, NK) wird der Prompt um eine empirische Übergangstabelle erweitert, die Wahrscheinlichkeiten $P(\text{Verbesserung} | \text{Fitness}, k)$ und mittlere Fitnessänderungen $\Delta f$ zusammenfasst.
   • Das LLM generiert einen kompakten Python-Code (SynthesizedCWM), der als Simulator fungiert. Dieser Code enthält Methoden zur Vorhersage des nächsten Zustands (predict_next_state), zur Bewertung von Zuständen (evaluate_state) und zur Bestimmung legaler Aktionen.
   • Ein entscheidender Trick ist die Verwendung von normalisierter Fitness (erwarteter kontinuierlicher Wert statt nur ganzzahliger Fitness), um die Drift $E[f(y) - f(x)]$ zwischen verschiedenen $k$-Werten zu unterscheiden.

3. Greedy-Planung (Online):

   • Während der eigentlichen Optimierung wird in jedem Schritt ein 1-Schritt-Lookahead durchgeführt.
   • Der Greedy-Planer fragt den generierten CWM für alle möglichen $k$-Werte ab: $k^* = \arg\max_k \text{evaluate}(\text{predict}(s, k))$.
   • Der Algorithmus führt dann den Schritt mit dem besten $k^*$ aus.
   • Im Gegensatz zu früheren CWM-Ansätzen ist hier kein Monte-Carlo-Baum-Suche (MCTS) notwendig; der einfache Greedy-Ansatz reicht aus, da das Problem effektiv markovsch mit einem Horizont von 1 ist.

3. Hauptbeiträge

1. Erweiterung auf stochastische Optimierung: CWMs werden erfolgreich von deterministischen Spielen auf stochastische kombinatorische Probleme übertragen.
2. Effizienz von Greedy-Planung: Es wird gezeigt, dass MCTS (mit 5.000 Rollouts) unnötig ist; ein einfacher Greedy-Planer über den CWM reicht aus und ist um den Faktor 100 effizienter.
3. Lernen ohne Oracle: Das System lernt korrekte Strategien allein aus der Problemstruktur und suboptimalen Demonstrationen, ohne jemals optimale Trajektorien gesehen zu haben.
4. Überwindung täuschender Landschaften: Auf Jump$_k$ erreicht die Methode 100% Erfolgsrate, wo alle adaptiven Baselines versagen.
5. Dateneffizienz und Generalisierung: CWMs übertreffen Deep Q-Networks (DQN) in Bezug auf Stichprobeneffizienz (200 Offline-Trajektorien vs. 500 Online-Episoden) und Generalisierungsfähigkeit auf neue Parameterwerte.

4. Ergebnisse

Die Studie wurde auf vier Benchmarks mit $n=50$ durchgeführt:

• LeadingOnes & OneMax (Unimodal):

  • LeadingOnes: CWM-greedy erreicht 1.06-fache der optimalen Laufzeit (innerhalb von 6% des Optimums) und schlägt alle adaptiven Baselines signifikant ($p < 0.0001$).
  • OneMax: CWM liegt innerhalb von 2% des Optimums und ist vergleichbar mit der einfachen RLS$_1$-Strategie.
  • Das CWM lernt die theoretisch optimale Strategie (z. B. den „Cliff" bei $n/2$ bei OneMax) korrekt aus den Daten.

• Jump$_k$ (Täuschende Landschaft):

  • Dies ist das kritischste Ergebnis. Alle adaptiven Baselines (EA$\alpha$, Selbstanpassung) scheitern mit 0% Erfolgsrate, da sie $k$ bei Stagnation verringern.
  • CWM-greedy erreicht 100% Erfolgsrate mit einer mittleren Schrittzahl von 1.342 (nahe dem theoretischen Optimum von 1.346).
  • Der CWM erkennt, dass am Talrand nur ein spezifisches $k$ (hier $k=2$) eine Verbesserung ermöglicht, und wählt dies konsequent.

• NK-Landschaft (Kein mathematisches Modell):

  • Da keine geschlossene Formel existiert, verlässt sich das CWM ausschließlich auf die empirische Übergangstabelle im Prompt.
  • CWM-greedy erreicht die beste Fitness (36.94) und rangiert in jedem einzelnen der 15 generierten Instanzen an erster Stelle (signifikant besser als alle Baselines, $p < 0.001$).
  • Dies beweist, dass strukturierte empirische Statistiken geschlossene Modelle ersetzen können.

• Vergleich mit DQN (Deep Q-Network):

  • Sample Efficiency: CWM benötigt nur 200 Offline-Trajektorien, DQN 500 Online-Episoden.
  • Performance: Auf Jump$_k$ erreicht CWM 100% Erfolgsrate, DQN nur 58%.
  • Generalisierung: Auf Jump$_k$ mit $k=3$ (nicht im Training gesehen) erreicht CWM 78% Erfolgsrate, während DQN und EA$\alpha$ auf 0% fallen. DQN überanpasst sich an den Explorationsrauschen ($\epsilon$-greedy) und lernt nicht die seltenen, kritischen Übergänge.

5. Bedeutung und Fazit

Das Paper demonstriert, dass Large Language Models nicht nur als Generatoren von Lösungen, sondern als Architekten von Weltmodellen eingesetzt werden können.

• Interpretierbarkeit: Im Gegensatz zu neuronalen Netzen (Black-Box) erzeugt das CWM einen auditorischen Python-Code, der die gelernte Heuristik explizit darstellt.
• Komplementär zur Theorie: Die Methode ersetzt nicht die formale Analyse, sondern ergänzt sie. Sie ermöglicht analytische Planung auch in Landschaften, für die keine geschlossenen Modelle existieren.
• Robustheit: Die Ergebnisse sind über mehrere unabhängige Synthesen hinweg stabil.
• Praktische Implikation: Die Methode zeigt, dass man durch die Kombination von mathematischem Wissen (oder empirischen Statistiken) mit der Code-Generierungsfähigkeit von LLMs hochleistungsfähige, adaptive Steuerungsstrategien für evolutionäre Algorithmen entwickeln kann, die komplexe, täuschende Probleme lösen, bei denen klassische Heuristiken versagen.

Zusammenfassend stellt das Paper einen Paradigmenwechsel dar: Statt manuell adaptive Regeln zu entwerfen, wird ein LLM genutzt, um ein Simulator-Modell zu synthetisieren, das dann zur optimalen Parameterwahl genutzt wird.