Code World Models for Parameter Control in Evolutionary Algorithms

Cet article présente l'extension des Modèles Mondiaux de Code (CWM) aux problèmes d'optimisation combinatoire stochastiques, démontrant qu'un LLM peut synthétiser un simulateur des dynamiques d'un algorithme évolutionnaire pour contrôler efficacement ses paramètres et surpasser les méthodes d'apprentissage par renforcement et les approches adaptatives existantes.

L'essentiel

🌍 Le Grand Défi : Apprendre à conduire une voiture sans manuel

Imaginez que vous devez apprendre à conduire une voiture très spéciale (un algorithme d'optimisation) pour atteindre un but précis (trouver la meilleure solution à un problème). Le problème ? Vous n'avez pas de manuel d'utilisation, et la route est pleine de pièges invisibles.

Dans le monde de l'intelligence artificielle, on utilise souvent des règles fixes pour décider comment conduire (par exemple : "si ça ne va pas, tournez doucement à gauche"). Mais sur des terrains complexes, ces règles se trompent souvent.

C'est ici qu'intervient l'idée géniale de ce papier : Et si on demandait à un super-intelligent (une IA de type LLM, comme un Chatbot très avancé) de lire les traces des conducteurs précédents, de comprendre comment la voiture fonctionne, et d'écrire lui-même un nouveau manuel de conduite ?

🤖 La Méthode : Le "Modèle du Monde" en Code

Les chercheurs appellent cela les Code World Models (Modèles du Monde en Code). Voici comment ça marche, étape par étape, avec une analogie :

1. L'Observation (Le Stage) :
   Imaginez que vous laissez 200 stagiaires conduire cette voiture sur des circuits différents. Certains sont bons, d'autres sont moyens, et aucun ne connaît le chemin parfait. Vous enregistrez tout ce qu'ils font : où ils tournent, où ils bloquent, où ils accélèrent.
   Dans le papier : C'est la collecte de "trajectoires" (des données d'essais) avec des stratégies variées.

2. L'Écriture du Manuel (La Synthèse) :
   Vous prenez toutes ces vidéos de stagiaires et vous les montrez à un expert en mécanique (l'IA LLM). Vous lui dites : "Regarde ces données. Peux-tu écrire un petit programme Python qui explique comment cette voiture réagit quand on tourne le volant ?"
   L'IA ne se contente pas de copier les stagiaires. Elle comprend la physique de la voiture et écrit un simulateur. C'est comme si l'IA disait : "Ah, je vois que quand on est dans ce virage, il faut tourner fort, sinon on tombe dans le ravin."

3. Le Planificateur (La Conduite Intelligente) :
   Maintenant, au lieu de conduire au hasard, votre voiture utilise ce nouveau manuel écrit par l'IA. À chaque seconde, elle se demande : "Si je tourne un peu à gauche, où vais-je atterrir ? Et si je tourne à droite ?" Elle choisit la meilleure option instantanément.
   Dans le papier : C'est le "planificateur gourmand" qui choisit la force de mutation ($k$) idéale à chaque étape.

🏔️ Les Résultats : Pourquoi c'est impressionnant ?

Les chercheurs ont testé cette méthode sur quatre types de "terrains" (problèmes) :

• Les Collines Douces (LeadingOnes & OneMax) :
  C'est comme monter une pente régulière. Les méthodes classiques fonctionnent bien, mais notre IA a trouvé un chemin presque parfait, presque aussi bon que celui qu'un mathématicien aurait calculé à la main. Elle a appris la logique sans qu'on lui donne la réponse.

• Le Vallon Trompeur (Jumpk) : C'est le grand succès !
  Imaginez un canyon. Pour le traverser, il faut sauter très haut d'un coup.

  • Les méthodes classiques : Elles voient que le sol descend (le "canyon") et pensent qu'elles ont raté leur coup. Elles réduisent leur effort (elles sautent plus petit) et finissent par rester coincées au fond. Résultat : 0% de réussite.
  • Notre IA (CWM) : En lisant les données, elle a compris : "Attends, pour sortir de ce trou, il faut sauter très fort, même si ça semble dangereux !". Elle a écrit un code qui dit : "Au bord du canyon, saute à fond !"
  • Résultat : 100% de réussite. Elle a réussi là où tout le monde échouait, sans même connaître la taille exacte du canyon à l'avance.

• Le Terrain Accidenté (NK-Landscape) :
  C'est un terrain où chaque pierre bouge les autres. Il n'y a pas de formule mathématique pour le décrire.

  • L'IA a utilisé des statistiques empiriques (des tableaux de données réelles) pour écrire son simulateur. Résultat : Elle a battu toutes les autres méthodes, prouvant qu'elle peut apprendre même sans théorie mathématique, juste avec des données brutes.

🆚 IA vs Apprentissage par Renforcement (DQN)

Les chercheurs ont comparé leur méthode à une autre technique populaire (le DQN, un type d'apprentissage par renforcement).

• Le DQN est comme un chien qui apprend par essais et erreurs. Il faut lui faire faire des milliers de tours pour qu'il comprenne. Et s'il se trompe une fois sur un piège, il peut oublier comment le éviter.
• Le CWM (Notre méthode) est comme un ingénieur qui lit le manuel. Il a besoin de beaucoup moins d'essais (200 contre 500) et il généralise mieux. Si on change la taille du canyon, il comprend la logique et s'adapte, alors que le chien reste confus.

💡 La Conclusion Simple

Ce papier nous dit quelque chose de très important pour l'avenir de l'IA :

Au lieu de laisser l'IA être une "boîte noire" mystérieuse qui prend des décisions qu'on ne comprend pas, on peut lui demander d'écrire du code. Ce code devient un manuel de règles transparent et vérifiable.

L'IA ne remplace pas les mathématiques ; elle les complète. Elle prend des données imparfaites, trouve les motifs cachés, et écrit un petit programme qui nous dit comment résoudre le problème de manière optimale. C'est une façon de transformer l'expérience brute en sagesse codée.

En résumé : L'IA a appris à conduire une voiture dans des conditions extrêmes en écrivant son propre manuel de conduite, et elle s'est révélée être un meilleur conducteur que les experts humains sur les terrains les plus piégeux.

Résumé technique

1. Problématique

Le contrôle adaptatif des paramètres est un défi fondamental en calcul évolutionnaire. Pour l'algorithme (1+1)-RLS$_k$ (qui inverse exactement $k$ bits à chaque étape), la question centrale est : quelle valeur de $k$ (force de mutation) choisir à chaque étape pour optimiser la convergence ?

• Contexte : Sur des paysages unimodaux (comme LeadingOnes ou OneMax), des politiques optimales sont connues. Cependant, sur des paysages complexes et trompeurs (comme Jump$_k$ ou les paysages NK), les mécanismes d'adaptation existants (règles multiplicatives comme EA$\alpha$, auto-ajustement) échouent souvent. Ils ont tendance à réduire $k$ lors de stagnation, ce qui est contre-productif dans les vallées trompeuses où il faut au contraire augmenter $k$ pour sauter le fossé.
• Limites des approches actuelles : Les méthodes d'apprentissage par renforcement (RL) comme DQN souffrent d'un manque d'efficacité d'échantillonnage et d'une difficulté à généraliser sur des transitions rares (comme traverser une vallée). Les modèles analytiques fermés n'existent pas pour tous les problèmes.

2. Méthodologie : Modèles de Monde en Code (CWM)

Les auteurs étendent le concept de Code World Models (CWM), initialement conçu pour les jeux déterministes, à l'optimisation combinatoire stochastique. L'idée centrale est qu'un Grand Modèle de Langage (LLM) synthétise un programme Python qui agit comme un simulateur de la dynamique de l'optimiseur.

Le pipeline se déroule en trois étapes :

1. Collecte de trajectoires (Offline) :

   • L'algorithme (1+1)-RLS$_k$ est exécuté avec des politiques diverses (aléatoires, fixes, heuristiques) pour générer 200 à 300 trajectoires.
   • Contrainte clé : Aucune politique de collecte n'utilise la politique optimale ni la connaissance oracle du paramètre $k$ (ex: la taille du fossé dans Jump$_k$). Le modèle doit apprendre à partir de démonstrations sous-optimales.
   • Pour les problèmes complexes (Jump$_k$, NK), le prompt inclut non seulement la description mathématique, mais aussi un tableau de transitions empiriques (probabilité d'amélioration et gain moyen de fitness par paire (fitness, $k$)).

2. Synthèse du CWM par LLM :

   • Un LLM (Claude Sonnet 4) reçoit les données et génère une classe Python SynthesizedCWM.
   • Cette classe implémente des méthodes pour : prédire le prochain état (predict_next_state), évaluer l'état (evaluate_state), et lister les actions légales.
   • Une astuce clé est l'utilisation d'une fitness normalisée (espérance continue) pour discriminer les actions, permettant au modèle d'estimer le "drift" (gain espéré).
   • Le code généré est validé automatiquement et affiné (jusqu'à 5 tentatives).

3. Planification Greedy (En ligne) :

   • À chaque étape de l'optimisation, le planificateur interroge le CWM synthétisé.
   • Il effectue une recherche à un pas de regard (1-step lookahead) : pour chaque $k$ possible, il prédit le prochain état et choisit le $k$ qui maximise la fitness attendue.
   • Contrairement aux travaux précédents utilisant MCTS (Monte Carlo Tree Search), une approche greedy suffit ici car le problème est essentiellement markovien à horizon court.

3. Contributions Clés

1. Extension aux problèmes stochastiques : Passage des jeux déterministes à l'optimisation combinatoire stochastique, où le modèle de monde doit encoder des transitions probabilistes.
2. Efficacité de la planification Greedy : Démonstration que le MCTS (coûteux) est inutile dans ce contexte ; une simple recherche à un pas suffit.
3. Apprentissage sans politique optimale : Le LLM infère la stratégie correcte uniquement à partir de la structure du problème et de trajectoires sous-optimales, sans jamais voir la solution optimale.
4. Substitution des modèles fermés : Sur les paysages NK (sans modèle mathématique connu), l'utilisation de statistiques de transition empiriques dans le prompt permet au CWM de surpasser toutes les bases de référence.

4. Résultats Expérimentaux

Les expériences ont été menées sur $n=50$ (et généralisation jusqu'à $n=200$) sur quatre benchmarks :

• LeadingOnes & OneMax (Paysages unimodaux) :

  • Le CWM-greedy atteint 1,06 fois la performance optimale sur LeadingOnes (dans les 6% de l'optimum) et 1,02 fois sur OneMax.
  • Il surpasse significativement les règles adaptatives classiques (p < 0,0001).
  • Il capture correctement la "falaise" abrupte de la politique optimale sur OneMax (changement brutal de $k$), que les règles adaptatives lisses ne peuvent suivre.

• Jump$_k$ (Paysage trompeur) :

  • Résultat majeur : Taux de réussite de 100% pour le CWM, contre 0% pour toutes les bases adaptatives (EA$\alpha$, règles auto-ajustables) et DQN.
  • Les méthodes adaptatives échouent car elles réduisent $k$ lors de la stagnation dans la vallée, alors qu'il faut augmenter $k$ pour sauter. Le CWM, grâce aux statistiques empiriques, apprend à maintenir ou augmenter $k$ au bord de la vallée.
  • Efficacité d'échantillonnage : Le CWM atteint 100% de succès avec 200 trajectoires hors ligne, contre 58% pour DQN avec 500 épisodes en ligne (et 0% si on réduit les données).

• Paysages NK (Rugueux, sans modèle analytique) :

  • Sur 15 instances générées indépendamment, le CWM obtient la meilleure fitness moyenne (36,94 vs 36,32 pour le meilleur baseline), avec une signification statistique forte (p < 0,001).
  • Il généralise bien à des niveaux d'épistasie plus élevés ($K=3, 4$) sans ré-entraînement.

• Généralisation :

  • Le CWM entraîné sur $k=2$ pour Jump$_k$ généralise à $k=3$ avec un taux de réussite de 78% (contre 0% pour DQN et EA$\alpha$). Cela prouve que le modèle a appris la structure mathématique sous-jacente (distribution hypergéométrique) et non pas seulement mémorisé des données.

5. Signification et Conclusion

• Supériorité sur le RL classique : Le CWM bat DQN en efficacité d'échantillonnage, taux de réussite et capacité de généralisation. Il évite le surapprentissage au bruit d'exploration ($\epsilon$-greedy) qui piège les réseaux de neurones sur des transitions rares.
• Approche hybride : L'article propose une méthodologie où l'IA générative ne remplace pas l'analyse formelle, mais la complète. En forçant le LLM à exprimer sa connaissance sous forme de code Python auditable, le système transforme l'expérience statistique en heuristiques explicites.
• Faisabilité : La synthèse d'un CWM coûte environ 0,04 $ et prend ~30 secondes, rendant l'approche très pratique par rapport à l'entraînement long de modèles de RL.

En résumé, cette étude démontre que les LLMs peuvent apprendre à modéliser la dynamique d'optimiseurs stochastiques à partir de données limitées et sous-optimales, permettant de générer des politiques de contrôle de paramètres robustes et performantes, même sur des paysages d'optimisation complexes où les méthodes traditionnelles échouent.