Stratégie d'évolution (CMA-ES) — Adaptation de la matrice de covariance
- Introduite par
- Nikolaus Hansen & Andreas Ostermeier
- Année
- 2001
- Type
- Derivative-free continuous black-box optimizer
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
CMA-ES, abréviation de Covariance Matrix Adaptation Evolution Strategy, est un optimiseur moderne sans dérivée pour les fonctions continues boîte noire, introduit par Hansen et Ostermeier en 2001.
Il maintient une population de solutions candidates tirées d'une distribution normale multivariée et met à jour itérativement la moyenne, la taille du pas et la matrice de covariance complète de la distribution pour orienter la recherche vers de meilleures régions de l'espace des paramètres. Il est devenu le standard de facto pour l'optimisation continue boîte noire et est largement utilisé dans la recherche d'architecture neuronale et l'optimisation de politiques d'apprentissage par renforcement.
L’intuition derrière la méthode
Imaginez que vous cherchez le point le plus bas dans un paysage vallonné, mais que vous ne pouvez pas voir le terrain — vous ne pouvez sonder que des emplacements individuels et connaître leurs altitudes. CMA-ES fonctionne comme un essaim guidé : il dépose un nuage de sondes autour d'une meilleure estimation actuelle, mesure la qualité de chaque sonde, puis remodèle le nuage pour le tour suivant. Le nuage n'est pas une simple sphère — il apprend la forme allongée et inclinée de la vallée dans laquelle il descend en se souvenant des directions qui ont conduit à une amélioration. Au fil des générations successives, le nuage se rétrécit et s'incline pour s'aligner sur la courbure de la surface de perte, permettant à l'algorithme de naviguer dans de longues vallées étroites qui piégeraient des méthodes plus simples.
Histoire
Les stratégies d'évolution ont été introduites dans les années 1960 et 1970 comme une famille d'optimiseurs basés sur la population, inspirés par l'évolution biologique. Le mécanisme d'adaptation de la matrice de covariance a été développé par Hansen et Ostermeier et entièrement décrit dans leur article de 2001 sur l'Évolution Computationnelle, qui a démontré qu'une auto-adaptation complètement dé-aléatoire — apprenant la géométrie complète du second ordre du paysage de recherche à partir de l'historique des pas réussis — surpassait considérablement les stratégies d'évolution antérieures sur les problèmes mal conditionnés et non séparables. Le tutoriel de Hansen en 2016 a consolidé l'algorithme et ses propriétés théoriques, faisant de CMA-ES la méthode de référence standard pour l'évaluation comparative de l'optimisation continue boîte noire.
Quand l’utiliser
CMA-ES est approprié lorsque la fonction objectif est continue, potentiellement non convexe, multimodale ou bruitée, et lorsque les informations de gradient sont indisponibles ou trop coûteuses à calculer. La plage de dimensionnalité idéale est d'environ 10 à 1000 paramètres ; en dessous de 10 dimensions, des méthodes plus simples sont souvent suffisantes, et au-delà de 1000, le coût mémoire quadratique de la matrice de covariance peut devenir prohibitif. Il n'y a pas d'exigence minimale de taille d'échantillon au sens statistique — l'algorithme génère lui-même ses propres points d'évaluation. CMA-ES est un choix naturel pour le réglage des hyperparamètres, la recherche d'architecture neuronale, l'optimisation de politiques d'apprentissage par renforcement et les problèmes de conception d'ingénierie où le simulateur ne fournit que des sorties boîte noire.
Limites et points d’attention
- Le coût mémoire quadratique et le coût de calcul par génération en fonction du nombre de dimensions limitent l'applicabilité au-delà d'environ 1000 paramètres sans variantes de réduction de dimensionnalité.
- Converge vers un optimum local en l'absence de redémarrages ; pour les paysages très multimodaux, des redémarrages multiples (IPOP-CMA-ES ou BIPOP-CMA-ES) sont nécessaires.
- Ne convient pas aux espaces de recherche discrets ou combinatoires — la méthode est intrinsèquement définie sur des vecteurs continus à valeurs réelles.
Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.
Points forts
- Ne nécessite aucune information de gradient — fonctionne sur toute fonction objectif appelable, y compris celles bruitées ou basées sur des simulations.
- Apprend la courbure locale du paysage de recherche grâce à l'adaptation de la covariance, lui permettant de naviguer dans des espaces de recherche allongés et mal conditionnés qui défont les méthodes sans gradient avec des distributions de recherche fixes.
- Invariant aux transformations préservant l'ordre de la fonction objectif et aux rotations de l'espace de recherche, ce qui le rend robuste sur une grande variété de géométries de problèmes.
- Bien adapté aux problèmes continus de dimensionnalité modérée à élevée (10 à 1000 paramètres) avec un seul hyperparamètre réglable — la taille de pas initiale.
Applications
- Réglage des hyperparamètres pour les modèles d'apprentissage automatique, y compris les architectures de réseaux neuronaux et les agents d'apprentissage par renforcement.
- Recherche d'architecture neuronale — optimisation des paramètres d'architecture encodés de manière discrète via une relaxation continue.
- Optimisation de politiques d'apprentissage par renforcement lorsque la politique est paramétrée par un vecteur continu.
- Optimisation de conception d'ingénierie, telle que l'optimisation de forme aérodynamique et l'ajustement de paramètres structurels, où seuls les sorties du simulateur sont disponibles.
- Calibration de modèles scientifiques — ajustement de modèles de simulation à des données expérimentales lorsque la vraisemblance est non différentiable ou coûteuse en calcul.
Comment ça marche
Comment ça marche
L'algorithme est initialisé avec un vecteur de solution initial et une taille de pas initiale (sigma). La matrice de covariance commence comme la matrice identité — un nuage de recherche parfaitement sphérique. La taille de la population est fixée, généralement autour de 4 + floor(3 * ln(dimension)).
À chaque génération, une population de solutions candidates est échantillonnée à partir de la distribution normale multivariée actuelle définie par le vecteur moyen, la taille du pas et la matrice de covariance. Comme la distribution est normale multivariée, les échantillons reflètent à la fois la meilleure estimation actuelle et la forme apprise de l'espace de recherche.
Chaque solution candidate est passée à la fonction objectif et reçoit un score de fitness. Aucune information de gradient n'est requise — seule la valeur scalaire de l'objectif à chaque point échantillonné est nécessaire. Cela rend CMA-ES adapté aux objectifs bruités, non différentiables et basés sur des simulations.
La moyenne est déplacée vers les solutions les mieux classées. La matrice de covariance et la taille du pas sont mises à jour à l'aide de deux chemins d'adaptation complémentaires — mises à jour de rang un et de rang mu — de sorte que les directions qui ont produit de bonnes améliorations deviennent plus probables lors de la génération suivante. C'est le mécanisme central par lequel CMA-ES apprend la géométrie locale du paysage.
L'algorithme répète le cycle échantillonner–évaluer–mettre à jour jusqu'à ce qu'un critère d'arrêt soit atteint : un nombre maximum d'évaluations de fonction, une tolérance sur le changement de la moyenne ou de la taille du pas, ou une dégénérescence détectée de la matrice de covariance. La meilleure solution trouvée sur toutes les générations est retournée.
Pièges courants
- Définir la taille de pas initiale sigma trop petite piège la recherche dans un voisinage étroit et empêche l'exploration ; trop grande, et les premières générations gaspillent des évaluations loin de l'optimum. Une règle empirique courante est de régler sigma de sorte que l'optimum attendu se situe à environ trois sigma du point de départ.
- Appliquer CMA-ES à des problèmes de très faible dimensionnalité (moins de cinq paramètres) est généralement un gaspillage — une recherche par grille plus simple ou Nelder-Mead suffit, et la surcharge de population de CMA-ES n'apporte aucun bénéfice.
- Exécuter une seule instance CMA-ES sur un paysage multimodal risque de manquer l'optimum global ; utiliser des stratégies de redémarrage multi-départ ou basées sur la population (IPOP/BIPOP) lorsque le paysage est connu pour être très multimodal.
- Traiter la meilleure solution retournée comme le véritable optimum global sans vérification de redémarrage est une erreur courante — toujours confirmer avec plusieurs exécutions indépendantes lorsque l'objectif est très non convexe.
Questions fréquentes
Comment CMA-ES diffère-t-il d'un algorithme génétique simple ?
Un algorithme génétique classique maintient une population et applique des opérateurs de croisement et de mutation fixes. CMA-ES modélise plutôt la population comme des échantillons d'une distribution normale multivariée et adapte continuellement cette distribution — sa moyenne, sa taille de pas et sa matrice de covariance complète — en fonction des solutions qui ont été fructueuses. Cela permet à CMA-ES d'apprendre la forme du paysage de perte et de naviguer dans des espaces corrélés et mal conditionnés beaucoup plus efficacement qu'un algorithme génétique avec des opérateurs fixes.
CMA-ES garantit-il de trouver l'optimum global ?
Non. CMA-ES est une méthode de recherche locale dans le sens où une seule exécution peut converger vers un optimum local. Pour les paysages multimodaux, des redémarrages indépendants multiples — éventuellement avec des tailles de population croissantes (IPOP-CMA-ES) — sont recommandés pour améliorer la couverture de l'espace de recherche.
Quel est l'hyperparamètre le plus important à régler ?
La taille de pas initiale sigma est l'hyperparamètre le plus influent. Une bonne heuristique consiste à la régler de sorte que l'optimum attendu se situe à environ trois sigma du point de départ. La taille de la population et le nombre maximum d'évaluations sont des contrôles secondaires ; la formule par défaut de taille de population (4 + floor(3 * ln(dimension))) fonctionne bien en pratique.
CMA-ES peut-il gérer des fonctions objectif bruitées ?
Oui. Parce que CMA-ES n'utilise que des informations de classement de la population — et non des valeurs de fonction absolues — il est relativement robuste au bruit. Pour des évaluations très bruitées, augmenter la taille de la population ou moyenner plusieurs évaluations par candidat peut encore améliorer la robustesse.
Méthodes associées
Sources
Hansen, N. & Ostermeier, A. (2001). Completely Derandomized Self-Adaptation in Evolutionary Strategies. Evolutionary Computation, 9(2), 159-195.
Ouvrir la référence DOICopié.Hansen, N. (2016). The CMA Evolution Strategy: A Tutorial. arXiv:1604.00772.
Ouvrir la référence de la publicationCopié.