Stratégies d'évolution

Les stratégies d'évolution forment une famille de métaheuristiques d'optimisation. Elles sont inspirées de la théorie de l'évolution, et appartiennent à ce titre à la classe des algorithmes évolutionnaires.

La méthode fut initialement proposée par Ingo Rencherberg, en 1965^[1], à l'université technique de Berlin, en Allemagne. Elle est, à ce titre, la première véritable métaheuristique et le premier algorithme évolutionnaire, bien avant le recuit simulé ou les algorithmes génétiques. La méthode fut ensuite développée durant la fin des années 1960, principalement par les travaux de Ingo Rechenberg, P. Bienert et Hans-Paul Schwefel sur la conception de profils aérodynamiques.

Par la suite, les stratégies d'évolutions (evolution strategies, en anglais, Evolutionsstrategie en allemand, abrégé ES), furent utilisées sur des problèmes d'optimisation continus, discrets, contraints, multi-objectifs, etc.

Dans sa version de base, l'algorithme manipule itérativement un ensemble de vecteurs de variables réelles, à l'aide d'opérateurs de mutation et de sélection. L'étape de mutation est classiquement effectuée par l'ajout d'une valeur aléatoire, tirée au sein d'une distribution normale. La sélection s'effectue par un choix déterministe des meilleurs individus, selon l'échelle de valeur de la fonction objectif.

Algorithme canonique

Des fonctions de densités de lois normales, µ indique la moyenne et σ² la variance.

Les stratégies d'évolutions utilisent un ensemble de µ « parents » pour produire λ « enfants ». Pour produire chaque enfant, ρ parents se « recombinent ». Une fois produits, les enfants sont mutés, généralement par ajout d'une variable aléatoire suivant une loi normale. L'étape de sélection peut s'appliquer, soit uniquement aux enfants (sélection « virgule »), soit à l'ensemble enfants + parents (sélection « plus »). Dans le premier cas, l'algorithme est noté (µ/ρ,λ)-ES, dans le second (µ/ρ+λ)-ES.

À l'origine, l'étape de recombinaison était inexistante, les algorithmes étant alors notés (µ,λ)-ES ou (µ+λ)-ES. Les méthode contemporaines utilisent l'opérateur de recombinaison, comme les autres algorithmes évolutionnaires, afin d'éviter d'être piégé dans des optimums locaux.

Ainsi, un algorithme (µ/1,+)-ES n'utilisera pas de « recombinaison », mais construira la génération suivante à partir des meilleurs individus, qu'ils soient parents ou enfants. Un algorithme (µ/ρ+1)-ES produira uniquement un enfant par génération, et supprimera le plus mauvais individu à chaque itération. Cette dernière méthode porte le nom de stratégies d'évolution à états constants (steady states ES en anglais).

Une itération de l'algorithme général procède comme suit:

1. À partir d'un ensemble de µ parents,
2. produire une population de λ enfants :
   1. choisir ρ parents,
   2. recombiner ses parents entre-eux pour former un unique individu,
   3. faire muter cet individu,
3. sélectionner les µ meilleurs individus.

CMA-ES

Échantillon obtenu à partir d'une distribution multi-normale de variances 1 et de covariance -1/2.

La dénomination « CMA-ES » est un acronyme pour l'anglais Covariance Matrix Adaptation Evolution Strategies, qu'il est possible de traduire en stratégies d'évolution avec adaptation de matrice de covariance. La méthode a été proposée par A. Gawelczyk, N. Hansen, et A. Ostermeier à la fin des années 1990. En 2005, cette méthode était l'une des meilleures métaheuristiques pour les problèmes continus^[2].

L'algorithme CMA-ES repose sur l'adaptation, au cours des itérations, de la matrice de variance-covariance de la distribution multi-normale utilisée pour la mutation.

Autres variantes

Il existe des stratégies d'évolution hierarchiques, appelées Meta-ES ou Nested-ED en anglais.

Principes d'implémentation

D'après Hans-Georg Beyer, un certains nombre de bonnes pratiques sont nécessaires pour garantir l'efficacité des stratégies d'évolution :

• Le ratio de sélection µ/λ pour une sélection virgule sur des problèmes continus doit se situer entre 1/7 et 1/2 ;
• l'utilisation de la sélection plus est recommandée pour les problèmes combinatoires ;
• l'opérateur de mutation est la principale source de variation, il doit être quasi-ergodique (qui permet de construire n'importe quel point dans l'espace de recherche en un nombre fini d'itération) ;
• l'utilisation d'une sélection plus avec un opérateur de mutation ergodique garantie la convergence ;
• la recombinaison doit être appliquée autant que possible.

Références

Sources

• (en) H.-G. Beyer et H.-P. Schwefel, Evolution Strategies: A Comprehensive Introduction, Natural Computing, volume 1, numéro 1, pages 3-52, 2002.
• (en) H.-G. Beyer, Evolution Strategies, Scholarpedia, version du 16 décembre 2006.

Voir aussi

• (en) N. Hansen, S.D. Müller et P. Koumoutsakos, Reducing the Time Complexity of the Derandomized Evolution Strategy with Covariance Matrix Adaptation (CMA-ES), Evolutionary Computation, volume 11, numéro 1, pages 1-18, 2003.
• (en) H.-G. Beyer, The Theory of Evolution Strategies, Natural Computing Series, Springer, 2001.
• (en) N. Hansen et A. Ostermeier, Completely Derandomized Self-Adaptation in Evolution Strategies, Evolutionary Computation, volume 9, numéro 1, pages 159-195, 2001.
• (en) H.-P. Schwefel, Evolution and Optimum Seeking, Wiley & Sons, 1995.
• (de) I. Rechenberg, Evolutionsstrategie'94, Frommann-Holzboog Verlag, Stuttgart, 1994.
• (en) J. Klockgether et H. P. Schwefel, Two-Phase Nozzle And Hollow Core Jet Experiments, AEG-Forschungsinstitut. MDH Staustrahlrohr Project Group. Berlin, Allemagne, 11th Symposium on Engineering Aspects of Magneto-Hydrodynamics, Caltech, Pasadena, 1970.

• Sur le site de l'équipe Bionik de l'université technologique de Berlin :
  • Building on Bio-Evolution, tutoriel d'Ingo Rechenberg.
  • Résultats de la comparaison de métaheuristiques effectuée lors de CEC'05.
  • Evolution Strategies Animations et applications à des problèmes réels.
  • Introduction à CMA-ES.
• Une interview de Hans-Paul Schwefel
• Le site de Nikolaus Hansen, informations sur CMA-ES.
• Optimisation dynamique avec un (15,100)-ES.