Beyond Numerical Features: CNN-Driven Algorithm Selection via Contour Plots for Continuous Black-Box Optimization

Résumé Technique : Sélection d'Algorithmes Pilotée par CNN via des Cartes de Contour

Énoncé du Problème
L'optimisation en boîte noire continue (BBO) consiste à minimiser ou maximiser des fonctions objectif sans information sur les gradients, en se fiant uniquement aux évaluations de la fonction. Bien que les solveurs sans dérivées (par exemple, les variantes de CMA-ES) obtiennent de bons résultats, le théorème « No Free Lunch » stipule qu'aucun algorithme unique ne surpasse universellement les autres sur toutes les instances de problèmes. Par conséquent, la Sélection Automatique d'Algorithmes (AAS) vise à choisir le solveur le plus adapté parmi un portefeuille fixe pour une instance de problème spécifique.

Les approches AAS existantes en BBO continue reposent principalement sur l'Analyse Exploratoire du Paysage (ELA), qui construit des vecteurs de caractéristiques numériques (par exemple, courbure, séparabilité) à partir d'évaluations sondées, ou sur le Deep-ELA, qui utilise des plongements appris à partir de transformateurs préentraînés. Les auteurs soutiennent que ces descripteurs numériques peuvent échouer à capturer la structure spatiale évidente dans les paysages visualisés. Bien que l'AAS basée sur les CNN ait été explorée dans des domaines discrets avec des encodages directs d'instances, son application au BBO continu — où les représentations doivent être construites par sondage — reste sous-exploitée.

Méthodologie
L'article propose une approche AAS pilotée par la représentation qui traite les paysages sondés comme des images plutôt que comme des vecteurs numériques.

1. Représentation de l'Instance (Cartes de Contour) :

   • Mono-objectif (SOO) : Chaque instance de problème est rendue sous forme de carte de contour en niveaux de gris 2D en évaluant la fonction objectif sur une grille fixe de $300 \times 300$. Pour les dimensions $d > 2$, une tranche 2D est créée en sélectionnant aléatoirement deux coordonnées pour définir un sous-espace, tout en fixant les autres à zéro (en exploitant le domaine symétrique de BBOB).
   • Multi-objectif (MOO) : Pour les problèmes bi-objectifs ($d=2, m=2$), une stratégie d'échantillonnage de sous-contours est utilisée. Cinq fenêtres rectangulaires alignées sur les axes sont échantillonnées dans le domaine pour chaque objectif, générant plusieurs vues afin de réduire la dépendance à un rendu global unique.
   • Variantes d'Entrée : Pour étudier la fidélité de l'entrée, les tracés sont redimensionnés à des résolutions $r \in \{64, 128, 300\}$.

2. Architectures CNN :
   Deux variantes de modèles sont proposées pour prédire la performance relative (Temps d'Exécution Attendu pour SOO, Hypervolume relatif pour MOO) des algorithmes d'un portefeuille :

   • Modèle Combiné : Les cinq vues spécifiques à l'instance (ou échantillons de fenêtres) sont empilées le long de la dimension des canaux et alimentées directement dans un encodeur CNN.
   • Modèle Séparé : Chaque vue est traitée individuellement par un encodeur à poids partagés, et les vecteurs de caractéristiques résultants sont concaténés avant d'être transmis à une tête de régression.
   • Architecture SOO : Un encodeur CNN à trois couches.
   • Architecture MOO : Un encodeur ResNet-18 en raison de besoins représentatifs plus élevés.

3. Mécanisme de Sélection :
   Le modèle prédit la métrique de performance (par exemple, ERT relative) pour chaque algorithme du portefeuille. Le solveur présentant la meilleure valeur prédite (ERT minimale ou HV maximale) est sélectionné.

Contributions Clés

1. Représentation d'Image Basée sur le Sondage : Les auteurs introduisent une nouvelle formulation AAS pour le BBO continu qui utilise les rendus de cartes de contour de paysages sondés comme représentations d'instances, éliminant ainsi le besoin de caractéristiques ELA conçues à la main.
2. Évaluation Empirique : L'étude fournit une analyse complète sur les benchmarks mono-objectifs BBOB 2009 standards et sur un cadre bi-objectif suivant le protocole Deep-ELA. Elle analyse les effets de l'agrégation des vues (Combiné vs Séparé) et de la résolution d'entrée.
3. Étalonnage des Performances : Le travail positionne la sélection basée sur les contours par rapport à des bases de référence établies basées sur les caractéristiques (ELA avec MLP/RF et variantes Deep-ELA).

Résultats Expérimentaux

• Optimisation Mono-objectif (SOO) :
  • Sur le benchmark BBOB 2009 (96 configurations), le CNN Combiné avec une résolution d'entrée de $300 \times 300$ surpasse significativement le Meilleur Solveur Unique (SBS), réduisant l'ERT relative moyenne de 30,37 (SBS) à 5,60.
  • L'approche CNN est compétitive par rapport aux bases de référence les plus fortes basées sur les caractéristiques (ELA-MLP : 5,72 ; Deep-ELA Medium-kNN : 6,04).
  • Les performances s'améliorent généralement avec une résolution d'entrée plus élevée ($r=300$), bien que cela augmente les coûts d'entraînement.
  • La méthode montre des gains importants sur les groupes de fonctions F1–F19, tandis que les performances sur le groupe le plus difficile (F20–F24) restent mitigées par rapport aux méthodes basées sur les caractéristiques.
• Optimisation Multi-objectif (MOO) :
  • Dans le cadre d'évaluation Deep-ELA, les sélecteurs basés sur CNN sont compétitifs par rapport aux bases de référence Deep-ELA.
  • Le CNN Séparé obtient les meilleurs scores d'Hypervolume relatif moyens (0,971–0,974), surpassant les variantes Deep-ELA (0,904).
  • La méthode est particulièrement efficace sur les instances ZDT (obtenant des scores quasi parfaits), tandis que les résultats sur DTLZ et MMF sont solides mais légèrement inférieurs aux meilleurs réglages Deep-ELA.

Signification et Revendications
L'article revendique que des modèles de vision simples peuvent exploiter la structure spatiale des paysages sondés pour la sélection d'algorithmes sans dépendre de caractéristiques ELA conçues à la main. Les résultats suggèrent que les visualisations de cartes de contour contiennent un signal suffisant pour piloter une AAS efficace en BBO continu, offrant une représentation complémentaire aux descripteurs numériques.

Limites et Portée
Les auteurs notent explicitement plusieurs limitations :

• Budget de Sondage : L'approche actuelle nécessite un budget de sondage substantiel (cinq cartes de $300 \times 300$ par configuration), la rendant adaptée à une analyse hors ligne mais pas à un déploiement en ligne strict à faible budget.
• Représentation de Haute Dimension : Pour $d > 2$, la représentation par tranche 2D est une vue partielle du paysage, ce qui peut contribuer à des performances plus faibles sur les groupes de fonctions les plus difficiles.
• Protocoles Fixes : L'évaluation est liée à des portefeuilles et des protocoles spécifiques (incluant l'échantillonnage de fenêtres pour MOO), et l'étude MOO est limitée à $d=2, m=2$.

Le travail est présenté comme une preuve de concept démontrant la faisabilité des représentations basées sur les images, avec des orientations futures pointant vers un sondage sensible aux coûts, des conceptions multi-vues et des caractéristiques hybrides visuelles-numériques.