Stratégie 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 est initialement proposée par Ingo Rencherberg en 1965, à 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 est 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 (anglais : evolution strategies, allemand : Evolutionsstrategie, abrégé ES) sont 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éthodes 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 (anglais : steady states ES).

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 ces 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 est proposée par A. Gawelczyk, N. Hansen, et A. Ostermeier à la fin des années 1990. En 2005, cette méthode est l'une des meilleures métaheuristiques pour les problèmes continus.

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 de mise en œuvre

D'après Hans-Georg Beyer, un certain 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 garantit la convergence ;
• la recombinaison doit être appliquée autant que possible.

Voir aussi

Bibliographie

 : document utilisé comme source pour la rédaction de cet article.

• (en) H.-G. Beyer et H.-P. Schwefel, « Evolution Strategies : A Comprehensive Introduction », Natural Computing, vol. 1, n^o 1,‎ 2002, p. 3-52. .
• (en) H.-G. Beyer, « Evolution Strategies », sur Scholarpedia (consulté le 16 décembre 2006), version du 16 décembre 2006.

• (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, vol. 11, n^o 1,‎ 2003, p. 1-18.
• (en) H.-G. Beyer, The Theory of Evolution Strategies, Springer, coll. « Natural Computing Series », 2001.
• (en) N. Hansen et A. Ostermeier, « Completely Derandomized Self-Adaptation in Evolution Strategies », Evolutionary Computation, vol. 9, n^o 1,‎ 2001, p. 159-195.
• (en) H.-P. Schwefel, Evolution and Optimum Seeking, Wiley & Sons, 1995.
• (de) I. Rechenberg, Evolutionsstrategie'94, Stuttgart, Frommann-Holzboog Verlag, 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.

Liens externes

• Sur le site de l'équipe Bionik de l'université technologique de Berlin :
  • Building on Bio-Evolution, tutoriel d'Ingo Rechenberg.
• Optimisation dynamique avec un (15,100)-ES.