LLM Driven Design of Continuous Optimization Problems with Controllable High-level Properties

Résumé Technique : Conception de problèmes d'optimisation continue pilotée par les LLM avec des propriétés de haut niveau contrôlables

Énoncé du problème
L'évaluation de référence (benchmarking) dans l'optimisation de boîtes noires continues est actuellement entravée par la diversité structurelle limitée des suites de tests existantes, telles que la suite BBOB (Black-Box Optimization Benchmarking). Comme l'indiquent des travaux antérieurs, ces suites ne couvrent souvent que des régions étroites de l'espace des problèmes, ce qui restreint la généralisation des modèles de sélection automatique d'algorithmes (AAS) et rend l'évaluation fortement dépendante des répartitions de données. Alors que des tentatives précédentes pour générer de nouveaux problèmes — comme des combinaisons affines de fonctions existantes ou des générateurs basés sur des arbres aléatoires — ont été proposées, celles-ci offrent soit une nouveauté limitée, soit manquent de la capacité de contrôler des propriétés de paysage de haut niveau spécifiques. Cet article étudie si les modèles de langage de grande taille (LLM), intégrés dans une boucle évolutive, peuvent être utilisés pour synthétiser automatiquement des problèmes d'optimisation présentant des caractéristiques de paysage de haut niveau clairement définies et interprétables.

Méthodologie
Les auteurs proposent un cadre étendant LLaMEA (Large Language Model–driven Evolutionary Algorithm), conçu à l'origine pour la génération d'algorithmes, au domaine de la génération de problèmes. La méthodologie suit un processus en trois étapes :

1. Définition du modèle de caractéristiques :
   Les auteurs ciblent cinq propriétés de haut niveau dérivées de l'analyse de paysage exploratoire (ELA) : la multimodalité, la séparabilité, l'homogénéité de la taille des bassins, l'homogénéité de l'espace de recherche et le contraste optima globaux-locaux. Des modèles d'apprentissage automatique (spécifiquement des régresseurs XGBoost) sont entraînés sur l'ensemble de données BBOB pour prédire ces propriétés à partir de caractéristiques ELA extraites d'échantillons de type hypercube latin. Pour la séparabilité, un test numérique direct utilisant des estimations de différences finies des interactions entre variables est employé à la place d'un modèle prédictif.

2. Génération de problèmes par LLM :
   Le cadre LLaMEA fait évoluer du code Python exécutable représentant des fonctions d'optimisation. Le LLM (plus précisément gpt5-nano a été sélectionné pour son équilibre entre performance et efficacité) reçoit des invites en langage naturel décrivant les propriétés cibles.

   • Évaluation de l'aptitude (Fitness) : Les candidats générés sont évalués par les modèles de prédiction de propriétés entraînés.
   • Mécanisme de diversité : Pour empêcher la population de converger vers des paysages redondants, les auteurs introduisent un mécanisme de partage d'aptitude dans l'espace ELA (ELA-space fitness-sharing). Ce mécanisme ajuste l'aptitude d'un individu en fonction de sa densité dans l'espace des caractéristiques ELA (en utilisant des distances de Manhattan normalisées par l'écart-type), pénalisant les solutions trop similaires aux autres et encourageant l'exploration de structures géométriques diverses. Un rayon de niche adaptatif assure la robustesse à travers les générations.

3. Vérification des propriétés :
   Parce que les modèles prédictifs sont des approximations, une étape de vérification rigoureuse est appliquée. Cela implique une analyse du bassin d'attraction (recherche itérative de chemins d'amélioration pour identifier les optima locaux et les tailles de bassins) et des tests statistiques. Cette étape est coûteuse en termes de calcul et est principalement appliquée à des instances en 2D pour confirmer que les fonctions générées présentent réellement les traits structurels voulus.

Principales contributions

• Première synthèse de problèmes pilotée par LLM : Ce travail présente le premier cas d'utilisation de l'évolution par LLM pour la synthèse automatique de problèmes d'optimisation avec des propriétés de haut niveau prescrites, allant au-delà de la génération de solveurs pour la génération d'instances de problèmes.
• Partage d'aptitude adaptatif : L'article étend le cadre LLaMEA avec un nouveau mécanisme de partage d'aptitude opérant dans l'espace des caractéristiques ELA afin de promouvoir la diversité parmi les paysages générés.
• Cadre de vérification : Les auteurs proposent et appliquent une approche de vérification multidimensionnelle combinant la modélisation prédictive, l'analyse du bassin d'attraction et l'inspection visuelle pour valider l'intégrité structurelle des problèmes générés.
• Bibliothèque ouverte : Le résultat est une bibliothèque reproductible et interprétable de problèmes de référence possédant des propriétés de haut niveau spécifiques, mise à disposition sous forme de bibliothèque Python.

Résultats

• Sélection de modèle : Des expériences préliminaires ont comparé cinq LLM. gpt5-nano a obtenu le taux de réussite le plus élevé (98,7 %) pour la génération de problèmes avec des combinaisons de propriétés spécifiques (par exemple, homogénéité de la taille des bassins et séparabilité) et a été sélectionné pour l'étude principale.
• Diversité : Le mécanisme de partage d'aptitude a montré qu'il augmentait significativement la diversité des paysages générés. Les distributions des distances de plus proches voisins dans l'espace ELA se sont déplacées vers des valeurs plus élevées lorsque le partage d'aptitude était actif, confirmant que le mécanisme dirige avec succès le générateur loin des solutions redondantes.
• Vérification des propriétés : L'analyse du bassin d'attraction a confirmé que de nombreuses fonctions générées présentaient les traits escomptés. Par exemple, les problèmes optimisés pour la multimodalité contenaient systématiquement plusieurs bassins d'attraction, et ceux optimisés pour un contraste élevé entre optima globaux et locaux montraient des différences de fitness significatives entre l'optimum global et les optima locaux.
• Expansion de l'espace des problèmes : Une visualisation t-SNE des problèmes générés par rapport à l'ensemble BBOB a démontré que les instances générées par LLM étendent l'espace des problèmes existant plutôt que de former un groupe sans rapport. Elles comblent les lacunes dans l'espace des caractéristiques, particulièrement dans les régions sous-représentées par les benchmarks standards.

Signification et affirmations
L'article affirme que la génération de problèmes pilotée par LLM est une « direction prometteuse et flexible » pour la création de benchmarks interprétables. En liant des groupes de caractéristiques ELA à des descriptions qualitatives lisibles par l'humain, l'approche permet la génération de paysages diversifiés et vérifiables sans nécessiter de connaissances d'expert pour sélectionner des cibles numériques de caractéristiques. La bibliothèque résultante offre un large ensemble de problèmes qui peuvent bénéficier de l'analyse de paysage et de tâches en aval comme la sélection automatique d'algorithmes. Les auteurs notent modestement que, bien que l'approche soit efficace, des travaux futurs sont nécessaires pour la comparer structurellement à d'autres générateurs, examiner systématiquement la sensibilité au choix du LLM et vérifier si ces instances améliorent la généralisation des sélecteurs d'algorithmes sur des ensembles de problèmes non vus.