Stratégie 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 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 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 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 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.



Wikimedia Foundation. 2010.

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

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Strategie d'evolution — 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… …   Wikipédia en Français

  • Evolution: Die Vögel —   Wie kann eine schuppige Haut plötzlich zum Federkleid werden? Wie kann sich ein plumpes Reptil in die Luft erheben? Wie können wechselwarme Lebewesen auf einmal zu gleichwarmen werden, die ihre Körpertemperatur konstant halten? Die Antwort… …   Universal-Lexikon

  • Strategie evolutionnairement stable — Stratégie évolutivement stable Les mécanismes de l évolution biologique Mécanismes non aléatoires: sélection naturelle sélection utilitaire sélection sexuelle sélection de parentèle sélection de groupe …   Wikipédia en Français

  • Stratégie évolutionnairement stable — Stratégie évolutivement stable Les mécanismes de l évolution biologique Mécanismes non aléatoires: sélection naturelle sélection utilitaire sélection sexuelle sélection de parentèle sélection de groupe …   Wikipédia en Français

  • Strategie d'entreprise — Stratégie d entreprise La stratégie d entreprise (ou management stratégique ou politique générale) est le pilotage des modifications de relations du système entreprise avec son environnement et de la frontière de ce système avec ce qui n est pas… …   Wikipédia en Français

  • Evolution (biologie) — Évolution (biologie) Pour les articles homonymes, voir Évolution. Arbre phylogénétique hypothétique de tous les organismes vivants. L arbre est basé sur des séquences de l …   Wikipédia en Français

  • Évolution (biologique) — Évolution (biologie) Pour les articles homonymes, voir Évolution. Arbre phylogénétique hypothétique de tous les organismes vivants. L arbre est basé sur des séquences de l …   Wikipédia en Français

  • Évolution biologique — Évolution (biologie) Pour les articles homonymes, voir Évolution. Arbre phylogénétique hypothétique de tous les organismes vivants. L arbre est basé sur des séquences de l …   Wikipédia en Français

  • Évolution des espèces — Évolution (biologie) Pour les articles homonymes, voir Évolution. Arbre phylogénétique hypothétique de tous les organismes vivants. L arbre est basé sur des séquences de l …   Wikipédia en Français

  • stratégie — [ strateʒi ] n. f. • 1803; « gouvernement militaire » 1562; gr. stratêgia→ stratège 1 ♦ (Opposé à tactique) Art de faire évoluer une armée sur un théâtre d opérations jusqu au moment où elle entre en contact avec l ennemi. « la tactique ruine la… …   Encyclopédie Universelle

Share the article and excerpts

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