Stratégie d’évolution avec adaptation de la matrice de covariance

La stratégie d’évolution avec adaptation de la matrice de covariance, souvent désignée par l’acronyme anglais CMA-ES pour Covariance Matrix Adaptation Evolution Strategy, est une méthode d’optimisation de type stratégie d'évolution. Les stratégies d’évolution sont des méthodes stochastiques, sans dérivées, utilisées pour l’optimisation de fonctions non linéaires, non convexes ou difficiles à traiter par des méthodes classiques.

La CMA-ES appartient à la famille des algorithmes évolutionnaires. Elle repose sur une analogie avec l’évolution biologique : à chaque itération, de nouvelles solutions candidates sont générées à partir d’une distribution de recherche, puis évaluées selon une fonction objectif. Les meilleures candidates sont ensuite utilisées pour mettre à jour les paramètres de cette distribution.

Dans une stratégie d’évolution, les nouvelles solutions sont généralement échantillonnées selon une loi normale multidimensionnelle dans un espace réel de dimension . La recombinaison correspond à la mise à jour de la moyenne de cette distribution, tandis que la mutation correspond à l’ajout d’une perturbation aléatoire. Les dépendances entre les variables sont représentées par une matrice de covariance. L’adaptation de cette matrice constitue l’élément central de la CMA-ES : elle permet à l’algorithme d’apprendre progressivement la géométrie du problème, en particulier lorsque la fonction objectif est mal conditionnée.

L’adaptation de la matrice de covariance peut être interprétée comme l’apprentissage d’un modèle de second ordre de la fonction objectif, de manière comparable à l’approximation de l’inverse de la matrice hessienne dans les méthodes de quasi-Newton. Contrairement à de nombreuses méthodes classiques d’optimisation, la CMA-ES ne requiert pas le calcul de dérivées. Elle utilise principalement le classement des solutions candidates selon leur valeur de fonction objectif.

Principes Deux principes sont utilisés dans la CMA-ES pour adapter les paramètres de la distribution de recherche.

Le premier repose sur une idée de maximum de vraisemblance. Les solutions ou directions de recherche qui ont été efficaces dans les itérations précédentes doivent devenir plus probables dans les itérations suivantes. La moyenne de la distribution est donc déplacée vers les meilleures solutions candidates, tandis que la matrice de covariance est modifiée de façon à augmenter la probabilité d’échantillonner à nouveau des directions de recherche favorables. Cette mise à jour peut aussi être interprétée comme une forme de descente selon le gradient naturel.

Le second principe utilise des trajectoires dites chemins d’évolution. Ces chemins enregistrent l’évolution de la moyenne de la distribution au cours du temps. Lorsque plusieurs déplacements successifs ont lieu dans des directions similaires, le chemin d’évolution devient long, ce qui fournit une information sur la corrélation entre les étapes successives. Ces chemins sont utilisés à la fois pour adapter la matrice de covariance et pour contrôler la taille du pas de recherche.

Le contrôle de la taille du pas vise à éviter une convergence prématurée tout en permettant une convergence rapide vers un optimum. Il ajuste l’échelle globale de la distribution de recherche, tandis que la matrice de covariance ajuste sa forme et son orientation.

Fonctionnement général

À chaque itération, la CMA-ES génère une population de solutions candidates à partir d’une loi normale multidimensionnelle. Ces solutions sont évaluées par la fonction objectif, puis triées selon leur performance. Les meilleures solutions servent à mettre à jour la moyenne de la distribution, la matrice de covariance et la taille du pas.

La version la plus courante est notée -CMA-ES. À chaque itération, solutions candidates sont générées, puis les meilleures sont combinées avec des poids de recombinaison afin de produire une nouvelle moyenne. Les poids sont généralement choisis de façon à donner plus d’importance aux meilleures solutions.

La taille de la population n’est pas fixée. De petites valeurs favorisent une recherche plus locale, tandis que des valeurs plus grandes rendent la recherche plus globale. Dans certaines variantes, l’algorithme est redémarré plusieurs fois avec une population croissante, afin d’améliorer sa capacité à trouver des optima globaux.

Fondements théoriques La distribution normale multidimensionnelle utilisée par la CMA-ES peut être vue comme la distribution de probabilité de maximum d'entropie sur lorsque seuls la moyenne, les variances et les covariances sont spécifiées. Cette propriété justifie son emploi comme distribution de recherche dans un contexte où peu d’informations a priori sont disponibles sur la fonction objectif.

Métrique variable La CMA-ES peut être interprétée comme une méthode stochastique à métrique variable. Dans le cas particulier d’une fonction objectif quadratique convexe, la matrice de covariance tend à s’adapter à l’inverse de la matrice hessienne, à un facteur scalaire près. Cette propriété rapproche la CMA-ES des méthodes de quasi-Newton, tout en conservant un fonctionnement sans dérivées.

Pour certaines stratégies d’évolution, la relation entre covariance et hessienne a été étudiée formellement dans le cadre d’une approximation quadratique.

Maximum de vraisemblance et gradient naturel Les mises à jour de la moyenne et de la matrice de covariance peuvent être reliées à des principes de maximum de vraisemblance. La moyenne est déplacée vers les solutions les mieux classées, tandis que la covariance est adaptée pour augmenter la probabilité d’échantillonner des directions similaires à celles qui ont été efficaces.

Plusieurs travaux ont également relié la CMA-ES aux stratégies évolutionnaires. Akimoto et al. et Glasmachers et al. ont montré indépendamment que certaines mises à jour de la CMA-ES peuvent être vues comme une approximation d’une descente selon le gradient naturel dans l’espace des distributions de probabilité.

Ollivier et al. ont proposé une dérivation plus générale des algorithmes d’optimisation information-géométriques, fournissant un cadre unifié pour comprendre ces méthodes et leurs invariances.

Invariance La CMA-ES possède plusieurs propriétés d’invariance importantes. Elle est invariante par transformation strictement croissante de la fonction objectif, car elle n’utilise que le classement des solutions et non leurs valeurs absolues. Elle est également invariante par changement d’échelle approprié et, sous certaines conditions d’initialisation, par rotation de l’espace de recherche.

Ces propriétés facilitent la généralisation des résultats expérimentaux obtenus sur une fonction donnée. Elles constituent l’un des avantages de la méthode par rapport à de nombreux algorithmes d’optimisation plus sensibles au système de coordonnées choisi.

Convergence Des arguments théoriques et de nombreux résultats empiriques suggèrent que la CMA-ES converge rapidement sur une large classe de fonctions. Sur certaines fonctions, la convergence vers l’optimum global peut avoir lieu avec probabilité un. Sur d’autres, la probabilité de succès dépend notamment de la moyenne initiale et de la taille du pas initiale.

La convergence linéaire de la CMA-ES avec probabilité un a été démontrée pour les fonctions quadratiques convexes.

Interprétation comme changement de coordonnées L’utilisation d’une matrice de covariance non triviale peut être interprétée comme une transformation du système de coordonnées. La matrice de covariance définit une transformation linéaire de l’espace de recherche, de sorte qu’un échantillonnage anisotrope dans l’espace original peut être vu comme un échantillonnage isotrope dans un espace transformé.

Cette interprétation relie la CMA-ES à une procédure d’encodage adaptatif, dans laquelle l’algorithme apprend progressivement un système de coordonnées mieux adapté au problème traité.

Performance en pratique Du point de vue de l’utilisateur, la CMA-ES est souvent considérée comme nécessitant peu de paramètres. Il faut principalement choisir un point initial, une taille de pas initiale et, éventuellement, la taille de la population. Les conditions d’arrêt peuvent aussi être ajustées selon le problème.

La méthode s’est révélée efficace dans de nombreuses applications, en particulier pour des fonctions non convexes, non séparables, mal conditionnées, multimodales ou bruitées. Une étude comparative sur l’optimisation boîte noire a montré qu’elle obtenait de bons résultats par rapport à de nombreux autres algorithmes, notamment sur des fonctions difficiles ou dans des espaces de grande dimension.

La CMA-ES est généralement utilisée pour des dimensions allant de quelques variables à quelques centaines. Dans un contexte d’optimisation boîte noire, où les gradients sont indisponibles, coûteux ou peu informatifs, elle peut néanmoins être moins efficace que d’autres méthodes dans certains cas :

pour des fonctions de très faible dimension, où des méthodes comme Nelder-Mead ou des méthodes à modèles de substitution peuvent être plus rapides ; pour des fonctions séparables, en particulier en grande dimension ; pour des fonctions presque quadratiques convexes et bien conditionnées, où des méthodes comme BFGS ou NEWUOA peuvent être nettement plus rapides ; lorsque le problème peut être résolu avec un très petit nombre d’évaluations de la fonction objectif.

En revanche, pour des fonctions non séparables, mal conditionnées, bruitées ou nécessitant un grand nombre d’évaluations, la CMA-ES est souvent compétitive, voire supérieure.

Variantes et extensions La variante (1+1)-CMA-ES génère une seule nouvelle solution à chaque itération. Cette solution devient la nouvelle moyenne de la distribution si elle est meilleure que la solution courante.

Certaines variantes des stratégies évolutionnaires sont proches de la CMA-ES, avec des choix particuliers de paramètres et une formalisation différente des mises à jour de covariance. La CMA-ES a aussi été étendue à l’optimisation multiobjectif sous le nom MO-CMA-ES.

Une autre extension importante est l’ajout d’une mise à jour négative de la matrice de covariance, appelée active CMA. Cette variante est aujourd’hui souvent considérée comme la version par défaut de la CMA-ES.

Voir aussi Bibliographie Hansen N, Ostermeier A (2001). Completely derandomized self-adaptation in evolution strategies. Evolutionary Computation, 9(2) . Hansen N, Müller SD, Koumoutsakos P (2003). Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Evolutionary Computation, 11(1) . Hansen N, Kern S (2004). Evaluating the CMA evolution strategy on multimodal test functions. In Xin Yao et al., editors, Parallel Problem Solving from Nature – PPSN VIII, , Springer. Igel C, Hansen N, Roth S (2007). Covariance Matrix Adaptation for Multi-objective Optimization. Evolutionary Computation, 15(1) .

Liens externes Introduction courte à la CMA-ES par N. Hansen The CMA Evolution Strategy: A Tutorial Page de code source de la CMA-ES

Références

Catégorie:Algorithme d'optimisation