Stratégies d'évolution

Stratégies d'évolution

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 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.

Sommaire

Algorithme canonique

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 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


  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

  • (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.


Ce document provient de « Strat%C3%A9gie d%27%C3%A9volution ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Stratégies d'évolution de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Evolution and the Theory of Games — [ISBN 0 521 28884 3] is a 1982 book by the British evolutionary biologist John Maynard Smith on evolutionary game theory. In it, Maynard Smith summarises work on evolutionary game theory that had developed in the 1970s, to which he made several… …   Wikipedia

  • Strategies for Engineered Negligible Senescence — (SENS) is the name Aubrey de Grey gives to his proposal to research regenerative medical procedures to periodically repair all the age related damage in the human body, thereby maintaining a youthful state indefinitely.[1][2] The term first… …   Wikipedia

  • Strategies generiques de Porter — Stratégies génériques de Porter Le modèle des stratégies génériques de Michael Porter, professeur de stratégie d entreprise, propose différentes façons dont une entreprise peut détenir un avantage concurrentiel sur son marché. Selon Porter, un… …   Wikipédia en Français

  • Strategies reproductives chez les macaques — Stratégies reproductives chez les macaques Sommaire 1 Introduction 2 Début de la reproduction 2.1 Maturation reproductive des mâles 2.2 Maturation reproductive des femelles …   Wikipédia en Français

  • Stratégies Génériques de Porter — Le modèle des stratégies génériques de Michael Porter, professeur de stratégie d entreprise, propose différentes façons dont une entreprise peut détenir un avantage concurrentiel sur son marché. Selon Porter, un avantage concurrentiel est durable …   Wikipédia en Français

  • Stratégies génériques de porter — Le modèle des stratégies génériques de Michael Porter, professeur de stratégie d entreprise, propose différentes façons dont une entreprise peut détenir un avantage concurrentiel sur son marché. Selon Porter, un avantage concurrentiel est durable …   Wikipédia en Français

  • Evolution of baseball player evaluation — has taken place over many years. Player evaluation is the process by which general managers and other baseball personnel judge the ability of a baseball player to contribute meaningfully to his team.Baseball has been around for a very long time.… …   Wikipedia

  • Evolution strategy — In computer science, evolution strategy (ES) is an optimization technique based on ideas of adaptation and evolution. It belongs to the general class of evolutionary computation or artificial evolution methodologies. Contents 1 History 2 Methods… …   Wikipedia

  • Stratégies CSR — La théorie des stratégies CSR fût énoncée par John Philip Grime en 1974[1]. Selon lui il existe trois stratégies végétales principales selectionnées en réponse à différents facteurs environnementaux (biotiques ou abiotiques) : la compétition …   Wikipédia en Français

  • Evolution window — It was observed in evolution strategies that significant progress toward the fitness/objective function s optimum, generally, only can happen in a narrow band of the mutation step size σ. That narrow band is called evolution window.There are… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”