Stratégie d'évolution

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

Des fonctions de densités de lois normales, µ indique la moyenne et σ2 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 ces parents entre eux pour former un unique individu,
    3. faire muter cet individu,
  3. sélectionner les µ meilleurs individus.

CMA-ES[modifier | modifier le code]

É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[modifier | modifier le code]

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

Principes de mise en œuvre[modifier | modifier le code]

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.

Références[modifier | modifier le code]

Sources[modifier | modifier le code]


  1. Rechenberg, I., Cybernetic Solution Path of an Experimental Problem, Royal Aircraft Establishment Library Translation, 1965
  2. A. Auger, S. Kern, N. Hansen, A Restart CMA Evolution Strategy with Increasing Population Size, Special Session on Real-Parameter Optimization, Conference on Evolutionary Computation, CEC-05, Edinburgh, UK, 2-5 septembre 2005.

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • (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, no 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, no 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[modifier | modifier le code]