🤖 AI

LLaMEA-SAGE: Guiding Automated Algorithm Design with Structural Feedback from Explainable AI

Cet article introduit LLaMEA-SAGE, un nouveau cadre qui améliore la conception automatisée d'algorithmes en exploitant l'IA explicable pour extraire des caractéristiques structurelles du code généré et les traduire en directives en langage naturel, accélérant ainsi la convergence et atteignant une performance supérieure par rapport aux méthodes existantes.

Auteurs originaux : Niki van Stein, Anna V. Kononova, Lars Kotthoff, Thomas Bäck

Publié 2026-01-30

📖 4 min de lecture☕ Lecture pause café

CC BY 4.0

Auteurs originaux : Niki van Stein, Anna V. Kononova, Lars Kotthoff, Thomas Bäck

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez d'enseigner à un apprenti chef très talentueux, mais un peu éparpillé (l'IA), comment inventer une toute nouvelle recette pour le gâteau parfait.

L'Ancienne Méthode (Vanilla LLaMEA)
Dans le passé, vous disiez à l'apprenti : « Fais un gâteau. » Il préparait quelque chose, vous le goûtiez, et vous disiez : « Bof, pas assez sucré. » L'apprenti devinait alors : « D'accord, je vais ajouter plus de sucre », préparait un nouveau gâteau, et vous le goûtiez à nouveau. C'est un jeu de « chaud et froid » basé uniquement sur le goût final (le score). L'apprenti avance à l'aveugle, devine de manière aléatoire et perd souvent du temps à faire des gâteaux qui sont structurellement terribles (trop d'ingrédients, étapes confuses), même s'ils ont un bon goût par accident.

La Nouvelle Méthode (LLaMEA-SAGE)
L'article introduit une nouvelle méthode appelée LLaMEA-SAGE. Au lieu de simplement goûter le gâteau, cette méthode examine le plan de la recette avant même qu'elle ne soit cuite.

Voici comment cela fonctionne, étape par étape :

La Vérification du Plan (Analyse Structurelle) : Chaque fois que l'apprenti écrit une nouvelle recette, le système ne regarde pas seulement les ingrédients ; il analyse la structure des instructions. Il compte le nombre d'étapes, la complexité de la logique et la façon dont les instructions sont connectées entre elles. Imaginez que cela consiste à mesurer la « complexité cyclomatique » (à quel point les instructions sont emmêlées) ou à compter le nombre total de mots utilisés.
Le Coach Intelligent (Modèle de Substitution) : Le système conserve un grand carnet de notes (une archive) de chaque recette essayée, de ses statistiques structurelles et de son goût. Il utilise un « coach » (un modèle d'apprentissage automatique) pour trouver des modèles. Par exemple, le coach pourrait remarquer : « Hé, chaque fois que la recette comporte moins de 20 étapes et utilise un type spécifique d'instruction de mélange, le gâteau est meilleur. »
L'Indice Explicable (XAI) : Au lieu de simplement dire « fais mieux », le système utilise un outil spécial (SHAP) pour identifier précisément quelle partie du plan pose problème. Il traduit cela en un indice simple, en langage naturel, pour l'apprenti : « Sur la base de nos notes, essayez d'augmenter le nombre d'étapes de mélange dans votre prochaine recette. »
La Devinette Guidée : L'apprenti reçoit cet indice spécifique en même temps que la commande habituelle « fais un gâteau ». Il n'est pas obligé de le suivre aveuglément, mais cela le dirige pour l'éloigner de la création de recettes désordonnées et confuses, et vers la construction de recettes plus propres et plus efficaces.

Les Résultats
Les auteurs ont mené deux tests principaux pour voir si ce « Coach de Plan » aidait réellement l'apprenti :

Le Test de Vitesse : Dans une petite expérience contrôlée, l'apprenti guidé (LLaMEA-SAGE) a trouvé un gâteau très savoureux beaucoup plus rapidement que l'apprenti non guidé. Il a atteint le même score élevé en moins de tentatives.
Le Grand Tournoi : Ils ont inscrit l'apprenti guidé dans une compétition majeure (MA-BBOB) contre d'autres chefs IA de haut niveau. L'apprenti guidé n'a pas seulement gagné ; il a systématiquement surpassé les autres meilleures méthodes. Il a trouvé de meilleures solutions plus rapidement et était plus stable (moins susceptible d'avoir un « mauvais jour » où les résultats variaient considérablement).

Points Clés à Retenir

La Structure Compte : Il ne suffit pas de savoir si une solution fonctionne ; savoir pourquoi elle fonctionne grâce à sa structure interne aide à trouver de meilleures solutions plus rapidement.
Pas de Règles Rigides : Le système ne force pas l'IA à suivre un modèle rigide. Il lui donne simplement un coup de pouce dans la bonne direction, laissant la créativité de l'IA s'exprimer.
Efficacité : La méthode n'a pas coûté beaucoup plus de puissance informatique ou de « tokens » (la monnaie des conversations d'IA) par rapport à l'ancienne méthode. C'était une mise à niveau intelligente, pas une surcharge lourde.

En résumé, LLaMEA-SAGE est comme si l'on donnait à une IA une loupe pour examiner son propre travail pendant qu'il est en cours de création, lui permettant d'apprendre de la forme de ses erreurs, et pas seulement du résultat final. Cela comble le fossé entre le code désordonné que l'IA écrit et le retour clair et compréhensible dont un humain (ou un coach intelligent) a besoin pour guider.

Résumé Technique : LLaMEA-SAGE

Énoncé du Problème

La conception automatisée d'algorithmes (AAD - Automated Algorithm Design) utilisant les grands modèles de langage (LLM) est devenue un paradigme prometteur pour la découverte d'algorithmes d'optimisation directement à partir de prompts en langage naturel. Cependant, les approches existantes basées sur les LLM, telles que LLaMEA, reposent presque exclusivement sur le feedback de fitness (performance sur des benchmarks) pour guider la recherche évolutive. Cette boucle de rétroaction en « boîte noire » laisse une quantité substantielle d'informations contenues dans le code généré inutilisée. Par conséquent, les stratégies de recherche peinent souvent à équilibrer l'exploration et l'exploitation dans de vastes espaces de code hétérogènes, ce qui conduit à une stagnation prématurée ou à une utilisation inefficace des requêtes coûteuses aux LLM. De plus, la compréhension de la manière de améliorer systématiquement les algorithmes générés par LLM après la génération initiale, et la comparaison de ces améliorations avec les méthodes de pointe (SOTA) sous des benchmarks contrôlés, reste limitée.

Méthodologie : LLaMEA-SAGE

Le papier propose LLaMEA-SAGE, un cadre qui intègre un feedback d'IA explicable (XAI) structuré dans le processus de conception d'algorithmes évolutifs de LLaMEA. Le mécanisme central consiste à extraire des caractéristiques structurelles du code des algorithmes candidats et à les utiliser pour guider les mutations ultérieures.

1. Extraction de Caractéristiques Structurelles

Chaque algorithme candidat est représenté sous forme de code Python exécutable. Le système analyse le code en un arbre de syntaxe abstraite (AST - Abstract Syntax Tree) pour construire un graphe orienté. À partir de ce grapque, le système extrait un ensemble riche de caractéristiques, incluant :

Statistiques de théorie des graphes : Nombre de nœuds/arêtes, statistiques de degré (moyenne, variance, entropie), profondeur de l'arbre, coefficients de regroupement (clustering coefficients) et métriques basées sur les chemins (diamètre, chemin moyen le plus court).
Indicateurs de complexité : Complexité cyclomatique, nombre de tokens de fonctions et nombre de paramètres agrégés par fonction.

2. Modélisation de Substitut Basée sur une Archive

Pendant le processus évolutif, toutes les solutions évaluées, leurs scores de fitness et leurs caractéristiques de code extraites sont stockés dans une archive. Une fois qu'une taille d'archive minimale est atteinte, un modèle d'arbre de régression boosté par gradient (XGBoost) est entraîné pour approximer la relation entre les caractéristiques du code et la fitness observée. Ce modèle de substitut apprend les relations non linéaires entre la structure algorithmique et la performance.

3. IA Explicable (SHAP) pour le Guidage

Pour dériver des instructions exploitables, le système applique SHAP (SHapley Additive exPlanations) au modèle de substitut entraîné. Les valeurs SHAP quantifient la contribution de chaque caractéristique à la fitness prédite. La caractéristique ayant la plus grande attribution absolue est sélectionnée, et le signe de sa valeur SHAP détermine si la valeur de la caractéristique doit être augmentée ou diminuée pour améliorer la performance.

4. Prompting de Mutation Guidé

Le guidage structurel est traduit en une instruction en langage naturel qui augmente le prompt de mutation standard fourni au LLM. Par exemple, si l'analyse suggère qu'augmenter la complexité cyclomatique est corrélé à une meilleure performance, le prompt est modifié en : « Sur la base de l'analyse de l'archive, essayez d'augmenter la complexité cyclomatique totale de la solution. »
Crucialement, ce guidage biaise la génération du LLM vers des régions structurelles empiriquement bénéfiques sans imposer de contraintes syntaxiques rigides ou de modèles prédéfinis, préservant ainsi la capacité d'expression du LLM.

Contributions Clés

Cadre LLaMEA-SAGE : La proposition d'un nouveau mécanisme qui guide l'AAD en utilisant un feedback piloté par les caractéristiques dérivées de l'AST et de l'analyse de complexité, médiatisé par un modèle de substitut et l'analyse SHAP.
Benchmarking Systématique : Une comparaison expérimentale complète par rapport aux méthodes de conception d'heuristiques basées sur les LLM de pointe (SOTA), spécifiquement MCTS-AHD (Recherche en arbre de Monte Carlo pour la conception d'heuristiques d'algorithmes) et LHNS (Recherche de voisinage d'heuristiques pilotée par LLM), ainsi qu'avec la ligne de base LLaMEA vanilla.
Validation Empirique : Démonstration que le guidage structuré améliore la qualité et la robustesse des algorithmes sur des benchmarks d'optimisation boîte noire, soutenue par une analyse approfondie via des graphes d'évolution de code (CEG - Code Evolution Graphs) et des tests statistiques.

Résultats Expérimentaux

Les auteurs ont évalué LLaMEA-SAGE à travers deux expériences principales utilisant l'outil de benchmarking IOH-BLADE.

Expérience 1 : Comparaison Contrôlée (SBOX-COST)

Configuration : Comparaison de LLaMEA vanilla contre LLaMEA-SAGE sur un sous-ensemble de la suite SBOX-COST (10 dimensions, 5 instances).
Résultats : LLaMEA-SAGE a obtenu de meilleures performances plus rapidement que LLaMEA vanilla, particulièrement dans les premières étapes du processus évolutif. Bien que les deux méthodes atteignent une performance finale similaire dans le budget imparti, l'approche guidée montre moins de variance entre les exécutions.
Signification Statistique : LLaMEA-SAGE a montré une amélioration moyenne de 11,1 unités de l'Aire Sous la Courbe de Convergence (AUC) avec une taille d'effet importante (Cliff's $\delta$ = 0,60). Cependant, en raison du nombre limité d'exécutions indépendantes (5 graines/seeds), la différence n'a pas atteint la signification statistique ( $p=0,44$ ).
Analyse Comportementale : Les graphes d'évolution de code ont révélé que le guidage a réussi à biaiser l'exploration structurelle. Notamment, le prompt « refine » (affiner) a conduit à une augmentation de la complexité du code lorsqu'il était guidé, tandis que le prompt « random new » (nouveau aléatoire) ignorait souvent le guidage ou résultait en une complexité moindre.

Expérience 2 : Benchmark à Grande Échelle (MA-BBOB)

Configuration : Évaluation sur la suite Many Affine BBOB (MA-BBOB), un standard pour les compétitions GECCO, comparant LLaMEA-SAGE à LLaMEA vanilla, MCTS-AHD et LHNS.
Résultats : LLaMEA-SAGE a systématiquement surpassé toutes les bases de référence, y compris les méthodes SOTA MCTS-AHD et LHNS. Il a atteint des niveaux de fitness que LLaMEA vanilla ne pouvait atteindre même après le budget d'évaluation complet.
Efficacité : En termes d'utilisation de tokens, LLaMEA-SAGE est légèrement plus coûteux que LLaMEA vanilla mais nettement plus efficace que MCTS-AHD (qui interroge le LLM plusieurs fois par solution).
Généralisation : La validation finale sur des instances non vues (dimensions et instances de problèmes différentes) a montré que le meilleur algorithme découvert par LLaMEA-SAGE surpassait les autres algorithmes conçus automatiquement et le vainqueur de la compétition MA-BBOB 2025 sur les tâches de 10 et 20 dimensions, bien qu'il n'ait pas dépassé le vainqueur de la compétition optimisé pour la tâche de 5 dimensions.

Signification et Revendications

Le papier affirme que LLaMEA-SAGE parvient à combler le fossé entre la structure du code et le feedback de performance compréhensible par l'humain dans la conception automatisée d'algorithmes. En traduisant les signaux structurels en langage naturel, la méthode fournit un biais inductif basé sur les données qui oriente l'évolution pilotée par LLM sans restreindre la capacité créative du modèle.

Les auteurs soulignent que même des corrélations imparfaites et bruitées dérivées des caractéristiques du code sont suffisantes pour biaiser avantageusement l'exploration dans les premières étapes de l'AAD. Ce travail démontre que les signaux dérivés du code peuvent efficacement améliorer l'efficacité et la stabilité de la découverte d'algorithmes, offrant une alternative scalable et sans modèle (template-free) aux approches centrées sur les heuristiques existantes.

Limites et Travaux Futurs

Les auteurs notent modestement plusieurs limites :

Dépendance au LLM : Les expériences ont été menées avec un seul moteur LLM (GPT-5-mini), bien que l'ablation préliminaire sur Gemini ait montré des tendances cohérentes.
Portée : L'évaluation a été limitée à l'optimisation boîte noire continue à des dimensions modérées ; la généralisation aux dimensions élevées, bruitées ou à des classes de problèmes fondamentalement différentes reste une question ouverte.
Analyse Statique : L'ensemble actuel de caractéristiques capture uniquement des propriétés structurelles statiques, ignorant le comportement d'exécution dynamique ou les effets d'interaction pendant les cycles d'optimisation.

Des travaux futurs sont proposés pour combiner les caractéristiques structurelles avec des descripteurs d'exécution, explorer un guidage adaptatif multi-caractéristiques et intégrer le mécanisme dans d'autres cadres d'AAD basés sur les LLM.