🤖 AI

ImprovEvolve: Basin-Hopping Meets LLM-Guided Evolutionary Search

ImprovEvolve introduit une recherche évolutive guidée par un LLM qui fait évoluer des opérateurs spécialisés d'initialisation, d'amélioration et de perturbation pour piloter un processus de saut de bassin (basin-hopping), découvrant avec succès de nouvelles solutions de pointe pour le compactage d'hexagones, les inégalités d'autocorrélation et les codes sphériques, tout en réduisant considérablement la charge cognitive imposée au modèle de langage.

Auteurs originaux : Alexey Kravatskiy, Valentin Khrulkov, Ivan Oseledets

Publié 2026-06-30

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Alexey Kravatskiy, Valentin Khrulkov, Ivan Oseledets

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 de résoudre un casse-tête incroyablement difficile, comme faire entrer un nombre spécifique d'hexagones de formes irrégulières dans un contenant sans qu'ils ne se chevauchent, ou trouver la courbe mathématique parfaite qui maximise une certaine valeur. Ce sont des « problèmes d'optimisation », et ils sont notoirement difficiles car le paysage des solutions possibles est rempli de petites collines et de vallées profondes (optima locaux). Si vous faites un mauvais pas, vous pourriez rester coincé dans une vallée peu profonde et ne jamais trouver la plus profonde.

Pendant longtemps, les chercheurs ont essayé d'apprendre à l'Intelligence Artificielle (spécifiquement aux Grands Modèles de Langage, ou LLM) à résoudre ces casse-têtes en lui demandant d'écrire un seul, immense programme qui fait tout à la fois : il doit déterminer où commencer, comment bouger et quand s'arrêter. C'est comme demander à un chef non seulement de cuisiner un repas, mais aussi de concevoir la cuisine, d'inventer de nouveaux ustensiles et d'écrire le livre de recettes, le tout en une seule fois. Le papier appelle cette approche « AlphaEvolve ». Bien qu'elle fonctionne parfois, elle submerge souvent l'IA, menant à des solutions maladrouses ou incomplètes.

La Nouvelle Idée : ImprovEvolve

Les auteurs de ce papier, Alexey Kravatskiy et ses collègues, proposent une méthode plus intelligente appelée ImprovEvolve. Au lieu de demander à l'IA de construire l'intégralité du « super-optimiseur » à partir de zéro, ils décomposent le travail en trois petites tâches gérables. Ils demandent à l'IA d'écrire une « boîte à outils » contenant trois outils spécifiques :

Le Démarreur (generate_config) : un outil qui crée simplement un point de départ aléatoire et valide pour le casse-tête.
Le Polisseur (improve) : un outil qui prend une solution désordonnée et l'améliore légèrement, en lissant les bords.
Le Secoueur (perturb) : un outil qui secoue aléatoirement la solution pour voir si le fait de la secouer aide à la faire tomber dans une vallée plus profonde et meilleure.

La Danse du « Basin-Hopping »

Une fois que l'IA a construit cette boîte à outils, les chercheurs ne se contentent pas de l'exécuter une seule fois. Ils utilisent une stratégie mathématique classique appelée Basin-Hopping (saut de bassin). Pensez à un randonneur essayant de trouver le point le plus bas dans une chaîne de montagnes embrumée :

Départ : Le randonneur dépose un point aléatoire (en utilisant le Démarreur).
Polissage : Il descend la pente vers le fond de la vallée la plus proche (en utilisant le Polisseur).
Secousse : Il fait un grand bond aléatoire (en utilisant le Secoueur) vers un nouvel endroit, espérant atterrir dans une vallée différente et plus profonde.
Répétition : Si le nouvel endroit est plus bas, il y reste. Sinon, il peut essayer à nouveau. Il fait cela encore et encore, en faisant progressivement des bonds de plus en plus petits à mesure qu'il s'approche du fond.

En séparant la « réflexion » (ce que fait l'IA) de la « recherche » (la boucle de Basin-Hopping), l'IA n'a qu'à se concentrer sur une tâche spécifique à la fois. Cela réduit la « charge cognitive » de l'IA, un peu comme un humain est plus apte à résoudre un problème complexe s'il le décompose en petites étapes plutôt que d'essayer de tout garder en tête à la fois.

Les Résultats : De Nouveaux Records

Le papier teste cette méthode sur trois défis mathématiques très difficiles :

Empilement d'hexagones : Imaginez essayer de faire entrer 11, 12 ou même 23 hexagones dans la plus petite boîte hexagonale possible. La nouvelle méthode a trouvé de nouveaux records mondiaux d'empilement pour plusieurs de ces nombres, battant les records précédents établis par d'autres systèmes d'IA et même par des experts humains.
L'inégalité d'autocorrélation : Il s'agit d'un problème mathématique complexe concernant la recherche de la forme parfaite d'une onde. L'IA a amélioré la limite mathématique connue (la « borne inférieure ») de 0,96102 à 0,96258. Cela a été réalisé en prenant une bonne solution trouvée par une IA précédente et en utilisant le nouvel outil « Polisseur » pour l'affiner davantage.
Codes Sphériques : Cela consiste à disposer des points sur une sphère de manière à ce qu'ils soient aussi éloignés les uns des autres que possible (comme des graines dans une grenade). La nouvelle méthode a amélioré la disposition pour la majorité de 90 cas de test, trouvant des configurations légèrement plus efficaces que tout ce qui était connu auparavant.

La Touche Humaine

Il est intéressant de noter que, bien que l'IA ait fait le plus gros du travail, un expert humain a apporté quelques ajustements infimes au code (comme changer un paramètre spécifique ou remplacer un outil mathématique) pour obtenir les meilleurs résultats possibles. Cela suggère que les meilleurs résultats proviennent d'un partenariat : l'IA génère la structure et la logique de base, et l'humain fournit le « réglage fin » final que l'IA pourrait manquer.

En Résumé

Le papier soutient qu'au lieu de demander à une IA d'être un « super-génie » capable de résoudre tout un problème d'un coup, nous devrions lui demander d'être un « spécialiste » capable de construire un ensemble d'outils. Ensuite, nous utilisons ces outils dans une boucle itérative intelligente (Basin-Hopping) pour explorer l'espace des solutions. Cette approche, ImprovEvolve, s'est avérée plus efficace, plus robuste et plus capable de trouver de nouveaux records mathématiques que les méthodes précédentes qui essayaient de tout faire en même temps.

Résumé technique : ImprovEvolve : Quand le Basin-Hopping rencontre la recherche évolutive guidée par les LLM

Énoncé du problème

Le papier traite du défi consistant à utiliser les modèles de langage de grande taille (LLM) pour résoudre des problèmes d'optimisation mathématique complexes, particulièrement ceux présentant des paysages rugueux, non convexes et non lisses (par exemple, les problèmes de compactage, les inégalités fonctionnelles et les codes sphériques). Des travaux antérieurs comme AlphaEvolve ont réussi à faire évoluer des programmes monolithiques produisant directement des solutions candidates, mais les auteurs soutiennent que cette approche impose une charge cognitive excessive au LLM. Le modèle doit simultanément concevoir un schéma d'initialisation, une stratégie de recherche et des critères de terminaison, ce qui conduit souvent à des programmes générés qui reposent sur des routines prêtes à l'emploi (comme L-BFGS-B) qui échouent à gérer efficacement les contraintes spécifiques et la non-convexité du problème. Par conséquent, les solutions générées par les LLM mélangent souvent l'intuition mathématique avec des heuristiques plutôt que de résoudre rigoureusement la tâche d'optimisation, et elles peinent à se généraliser à des tailles de problèmes inédites ou à améliorer les solutions construites par des experts.

Méthodologie : ImprovEvolve

Les auteurs proposent ImprovEvolve, une alternative algorithmique qui décompose la tâche d'optimisation en sous-programmes spécialisés, intégrant efficacement les techniques d'optimisation globale de type Basin-Hopping avec une recherche évolutive guidée par LLM.

Décomposition centrale

Au lieu de faire évoluer une fonction unique qui produit une solution, ImprovEvolve fait évoluer une classe Python implémentant trois opérateurs distincts :

generate_config(seed) : Initialise une solution réalisable à partir d'une graine aléatoire.
improve(x) : Effectue une optimisation locale pour affiner une configuration $x$ , renvoyant une solution $x'$ dont le fitness est au moins aussi bon que celui de $x$ .
perturb(x, \sigma) : Explore aléatoirement l'espace de recherche à une intensité spécifique $\sigma$ .

Schéma de validation (Basin-Hopping)

La classe évoluée est utilisée dans un schéma de validation en deux étapes (Algorithme 1) qui imite le Monotonic Basin-Hopping ( $T=0$ ) :

Étape A (Initialisation) : Plusieurs configurations initiales sont générées et affinées via improve. Le meilleur résultat est sélectionné comme point de départ $x^*$ .
Étape B (Recherche itérative) : L'algorithme effectue $R$ $R$ cycles de perturbation et d'amélioration. Dans chaque cycle, l'intensité de la perturbation $\sigma$ $σ$ décroît géométriquement de $\sigma_{max}$ $σ_{ma x}$ à $\sigma_{min}$ $σ_{min}$ . Le processus implique :
1. Perturber la meilleure solution actuelle : $x' = \text{perturb}(x^*, \sigma)$ .
2. Affiner la solution perturbée : $x'' = \text{improve}(x')$ .
3. Acceptation monotone : $x^*$ est mis à jour vers $x''$ uniquement si le fitness s'améliore strictement.

Cette décomposition déplace la tâche du LLM de la conception d'un optimiseur de bout en bout vers l'encodage d'heuristiques spécifiques au domaine pour l'initialisation, la recherche locale et l'exploration, qui sont ensuite orchestrées par le cadre classique de Basin-Hopping.

Cadre évolutif

Le système utilise le cadre GigaEvo avec une boucle MAP-Elites. Le fitness d'un programme candidat est déterminé en exécutant le schéma de validation complet en deux étapes sur celui-ci. Le LLM (Gemini 3 Pro pour l'initialisation, Gemini 3 Flash pour l'évolution) mute le code de la classe Improv, guidé par le feedback de fitness et les informations de lignée.

Contributions clés et résultats

1. Compactage d'hexagones (HEX $n$ )

Tâche : Compacter $n$ hexagones réguliers unitaires dans le plus petit hexagone régulier englobant.
Résultats :
- Pour $n=11$ , ImprovEvolve a découvert un nouvel état de l'art (SOTA) de compactage avec un côté $L=3.9245$ , améliorant le $3.9301$ d'AlphaEvolve et le précédent record humain de $3.9434$.
- Le programme évolué s'est généralisé à des tailles de problèmes inédites ( $11 \le n \le 24$ ) sans ré-évolution, trouvant de nouveaux compactages SOTA pour $n=12, 15, 16$ .
- ImprovEvolve+E : Avec de légères éditions humaines (changement d'optimiseurs, ajustement des poids de pénalité), le système a trouvé de nouveaux compactages SOTA pour $n=14, 17, 23$ et a fourni des compactages structurés pour $n=25-30$ là où aucun résultat préalable n'existait.
Comparaison : ImprovEvolve a nettement surpassé la ligne de base GigaEvo (approche monolithique), qui a échoué à se généraliser à $n > 11$ en raison d'erreurs de chevauchement.

2. Deuxième inégalité d'autocorrélation (ACI 2)

Tâche : Trouver une fonction non négative $f$ qui maximise la constante $C_2$ dans l'inégalité $\|f * f\|_2^2 \le C_2 \|f * f\|_1 \|f * f\|_\infty$ .
Résultats :
- Le programme de base ImprovEvolve a atteint $C(f) = 0.9512$ , surpassant les bases open-source mais restant en deçà du $0.96102$ d'AlphaEvolve.
- ImprovEvolve+E : En reprenant l'optimisation à partir de la solution d'AlphaEvo et en appliant des éditions guidées par l'humain (augmentation progressive de la résolution jusqu'à 1,6M d'étapes, suppression du clipping inférieur), le système a atteint une nouvelle borne inférieure SOTA de $C(f) = 0.96258$ .
Signification : Cela démontre la capacité du cadre à affiner les solutions de haute qualité fournies par des experts ou d'autres modèles, une capacité que les approches monolithiques de LLM peinent à maîtriser.

3. Codes sphériques

Tâche : Disposer $N$ points sur une sphère unité $S^{d-1}$ pour minimiser le produit scalaire maximal (cohérence).
Résultats :
- Évalué sur 90 configurations diverses du catalogue de Cohn ( $d \in [8, 16]$ ).
- ImprovEvolve++ (un amélineur général calibré et évolué sur plusieurs dimensions) a strictement abaissé le cosinus maximal pour 53 des 90 configurations, atteignant une amélioration relative moyenne de 0,1765 %.
- Cela représente une amélioration de 2,35 $\times$ par rapport au meilleur programme précédent (ImprovEvolve).
- Les diagnostics (UMAP et distributions de produits scalaires) ont montré qu'ImprovEvolve++ effectuait des réarrangements structurels globaux, déplaçant les points dans des régions distinctes de l'espace de recherche, tandis que les autres variantes ne faisaient que des ajustements locaux.

Robustesse statistique

Des études multi-exécutions ont confirmé que les améliorations d'ImprovEvolve sont statistiquement significatives ( $p < 0,05$ ) par rapport à la ligne de base GigaEvo, validant que la décomposition modulaire offre un avantage reproductible sur l'apprentissage d'un optimiseur monolithique.

Signification et affirmations

Le papier affirme que la décomposition des tâches d'optimisation en sous-problèmes modulaires est un principe critique pour la découverte guidée par les LLM.

Réduction de la charge cognitive : En séparant l'initialisation, l'amélioration locale et la perturbation, le LLM se concentre sur l'encodage de la structure mathématique et des heuristiques plutôt que sur l'orchestration de l'ensemble du processus de recherche.
Collaboration Humain-LLM : L'interface modulaire permet aux experts du domaine d'appliquer des éditions ciblées et minimales (par exemple, changer les optimiseurs, ajuster les calendriers de résolution) pour augmenter considérablement les performances, comblant ainsi l'écart entre le code généré par le LLM et le réglage de niveau expert.
Généralisation : L'interface improve/perturb permet aux programmes évolués de se généraliser à des tailles de problèmes inédites et de reprendre l'optimisation à partir de solutions fournies par des experts, surmontant ainsi la fragilité des programmes monolithiques de bout en bout.

Les auteurs positionnent ce travail comme une étape vers le passage à l'échelle de la découverte mathématique pilotée par les LLM, suggérant que les futurs systèmes devraient combiner de telles décompositions sur mesure avec des flux de travail agentiques capables de décider de manière autonome quels modules affiner. Le papier reste modeste quant à la généralisabilité plus large, notant que l'évaluation quantitative est actuellement limitée à ces trois domaines d'optimisation spécifiques.