Résumé technique : Analyse de la convergence des stratégies d'évolution pour l'optimisation mixte-entière

Énoncé du problème

Les problèmes d'optimisation mixte-entière consistent à minimiser des fonctions objectif sur des domaines contenant à la fois des variables continues et des variables entières. Les stratégies d'évolution (SE), en particulier la SE à adaptation de matrice de covariance (CMA-ES), sont des outils puissants pour l'optimisation continue de boîtes noires. Pour les étendre aux domaines mixtes-entières, une approche courante consiste à échantillonner des vecteurs continus et à discrétiser des coordonnées sélectionnées pour générer des valeurs entières.

Un défi critique dans cette extension est d'empêcher la « convergence prématurée » des variables entières. Si l'écart-type ($\sigma$) de la distribution de recherche dans les dimensions entières devient trop petit par rapport aux intervalles entiers, les entiers générés peuvent se fixer sur une seule valeur, stoppant l'exploration. Pour contrer cela, les méthodes existantes (par exemple, la (1+1)-CMA-ES avec Marge) imposent une borne inférieure ($\sigma_{LB}$) sur l'écart-type des variables entières.

Cependant, l'impact théorique de cette borne inférieure sur la convergence des variables continues reste flou. Une grande $\sigma_{LB}$ empêche la fixation entière mais augmente la probabilité de muter des entiers optimaux vers des valeurs sous-optimales, dégradant potentiellement la convergence des variables continues. À l'inverse, une petite $\sigma_{LB}$ risque une fixation entière. Bien que des études empiriques suggèrent des compromis, il manque une analyse théorique rigoureuse sur la manière dont ces mécanismes de gestion des entiers affectent le taux de convergence du composant continu, en particulier dans des contextes de haute dimension.

Méthodologie

Les auteurs analysent deux variantes de l'algorithme (1+1)-ES appliquées aux espaces mixtes-entières, en se concentrant sur la phase d'optimisation après que les variables entières aient atteint leurs valeurs optimales.

1. Algorithmes analysés :

   • (1+1)-LB-ES : Une variante du (1+1)-ES qui impose une borne inférieure $\sigma_{LB}$ sur l'écart-type des variables entières pour empêcher la fixation.
   • (1+1)-LUB-ES : Une extension de la précédente qui introduit une borne supérieure sur l'écart-type pour les dimensions entières où la mutation entière n'a pas été couronnée de succès. Cette borne supérieure vise à empêcher le taux de mutation des entiers non optimaux d'augmenter inutilement, protégeant ainsi la convergence des variables continues.

2. Fonction de référence :
   Pour isoler les effets de la gestion des entiers sur la convergence continue, les auteurs introduisent LexicoSphereInt. Il s'agit d'une variante lexicographique de la fonction Sphere ($f(\mathbf{x}, \mathbf{z}) = \|\mathbf{x}\|^2 + \|\mathbf{z}\|^2$).

   • Les solutions sont classées d'abord selon la composante entière ($\|\mathbf{z}\|^2$) et ensuite selon la composante continue ($\|\mathbf{x}\|^2$).
   • Cette configuration garantit que, une fois le vecteur entier optimal trouvé, il reste optimal, permettant à l'analyse de se concentrer strictement sur la dynamique du vecteur moyen continu $\mathbf{m}_t$ et du pas $\sigma_t$.

3. Approche analytique :

   • L'analyse suppose que la partie entière de la solution élite est déjà optimale ($\boldsymbol{\mu}_t = 0$).
   • Les auteurs emploient une analyse de dérive (spécifiquement des théorèmes de dérive additive et tronquée) sur le logarithme du rapport entre la distance à l'optimum et le pas.
   • Ils utilisent les propriétés de la distribution normale pour borner la probabilité de générer des entiers optimaux par rapport à des entiers non optimaux sous différentes conditions de pas.
   • L'analyse considère la limite où le nombre de variables entières ($d_{in}$) est grand par rapport aux variables continues ($d_{co}$).

Contributions et résultats clés

1. Convergence prématurée du (1+1)-LB-ES

L'article démontre rigoureusement que le (1+1)-LB-ES souffre d'une convergence prématurée dans les problèmes mixtes-entières de haute dimension.

• Mécanisme : Lorsque le nombre de variables entières ($d_{in}$) est grand, la probabilité de générer le vecteur entier optimal diminue rapidement à mesure que le pas augmente. Par conséquent, l'algorithme subit fréquemment des mises à jour « infructueuses », ce qui entraîne une diminution du pas $\sigma_t$.
• Résultat : Le pas diminue plus rapidement que la distance à l'optimum ($\|\mathbf{m}_t\|$). Les auteurs prouvent qu'il existe une constante $C_{lower} > 0$ telle que la distance espérée à l'optimum reste minorée :
  $$E[\|\mathbf{m}_{s\tau}\|] \geq C_{lower} \cdot \|\mathbf{m}_0\|$$
  pour tout nombre d'itérations $\tau$. Cela implique que l'algorithme échoue à atteindre une convergence linéaire et stagne à une distance sous-optimale de la solution.

2. Convergence linéaire du (1+1)-LUB-ES

L'article démontre que le (1+1)-LUB-ES, qui intègre la borne supérieure sur l'écart-type pour les mutations entières infructueuses, atteint une convergence linéaire.

• Mécanisme : La borne supérieure empêche l'écart-type dans les dimensions entières de croître excessivement lorsque les mutations entières échouent. Cela stabilise l'adaptation du pas, permettant aux variables continues de continuer à s'optimiser même lorsque les mutations entières sont occasionnellement infructueuses.
• Résultat : Dans des conditions de paramètres appropriées (spécifiquement concernant le taux de succès cible $1/s$), le temps d'atteinte espéré pour trouver un $\epsilon$-voisinage de l'optimum est :
  $$E[T_\epsilon] \in \Theta(d_{co} \cdot \log(1/\epsilon))$$
  Cela correspond au taux de convergence du (1+1)-ES standard sur les fonctions Sphere continues, prouvant que la borne supérieure atténue efficacement l'impact négatif de la gestion des entiers.

3. Conditions sur les paramètres

L'analyse dérive une condition spécifique pour le paramètre de taux de succès cible $s$ nécessaire pour atteindre une convergence linéaire dans le (1+1)-LUB-ES :
$$s > \frac{2}{p_{succ, in, LB}}$$
où $p_{succ, in, LB}$ est la probabilité de générer le vecteur entier optimal lorsque l'écart-type est à la borne inférieure. Cela fournit un guide théorique pour le réglage de $s$ en fonction de la dimensionnalité du problème.

Importance et affirmations

L'article prétend fournir le premier compte rendu théorique rigoureux de la manière dont les mécanismes de gestion des entiers impactent la convergence des variables continues dans les stratégies d'évolution mixtes-entières.

• Insight théorique : Il clarifie que l'imposition simple d'une borne inférieure sur l'écart-type (une pratique courante pour empêcher la fixation entière) est insuffisante pour les problèmes de haute dimension et peut activement entraver l'optimisation continue.
• Orientation de conception : Les résultats suggèrent que le mécanisme de borne supérieure (empêchant des pas excessifs dans les dimensions où les mutations entières ont échoué) est essentiel pour atteindre une convergence linéaire dans les domaines mixtes-entières.
• Implication pratique : La condition dérivée pour le paramètre de taux de succès $s$ offre une méthode concrète et théoriquement fondée pour le réglage des hyperparamètres dans les algorithmes SE mixtes-entières, dépassant les heuristiques purement empiriques.

Les auteurs notent que leur analyse se concentre sur la phase où les variables entières sont déjà optimisées. Des travaux futurs sont suggérés pour analyser le temps d'exécution nécessaire à l'optimisation des variables entières elles-mêmes et pour étendre ces résultats aux problèmes d'optimisation mixte-catégorielle.