Algorithme Évolutionniste

Algorithme Évolutionniste

Algorithme évolutionniste

Les algorithmes évolutionnistes ou algorithmes évolutionnaires (evolutionary computation en anglais), sont une famille d'algorithmes s'inspirant de la théorie de l'évolution pour résoudre des problèmes divers. Ils font ainsi évoluer un ensemble de solutions à un problème donné, dans l'optique de trouver les meilleurs résultats. Ce sont des algorithmes stochastiques, car ils utilisent itérativement des processus aléatoires.

La grande majorité de ces méthodes sont utilisées pour résoudre des problèmes d'optimisation, elles sont en cela des métaheuristiques, bien que le cadre général ne soit pas nécessairement dédié aux algorithmes d'optimisation au sens strict[1]. On les classe également parmi les méthodes d'intelligence calculatoire (Computational intelligence en anglais).

Un algorithme évolutionnaire utilise itérativement des opérateurs de sélections (en bleu) et de variation (en jaune). i : initialisation, f(X) : évaluation, ? : critère d'arrêt, Se : sélection, Cr : croisement, Mu : mutation, Re : remplacement, X* : optimum.

Sommaire

Paradigme

Ces algorithmes manipulent des populations de solutions.

L'« arbre de la vie », tel que le représente Charles Darwin dans son ouvrage L'Origine des espèces, où il présente ses théories sur l'évolution des êtres vivants.

Les algorithmes évolutionnaires s'inspirent de l'évolution des êtres vivants, en considérant que celle-ci tend à produire des organismes plus adaptés à leur environnement.

Selon la théorie de l'évolution, plusieurs mécanismes sont à l'œuvre pour ce faire. Schématiquement :

  • Les caractéristiques d'un organisme sont en grande partie codées dans ses gènes,
  • chaque population d'organismes est composée d'individus tous différents,
  • les différences entre individus leur confèrent une adaptation plus ou moins grande à leur environnement,
  • les organismes transmettent une partie de leurs caractéristiques à leurs descendants,
  • les individus les plus adaptés se reproduisent plus « efficacement », leurs caractéristiques ont donc tendance à davantage se répandre dans la population.

Principes de bases

Terminologie

Tous les algorithmes évolutionnaires font évoluer un ensemble (une « population ») de solutions (les « individus »). Les individus sont représentés par leur génotype, qui s'exprime sous la forme d'un phénotype, auxquels on associe une qualité (la « fitness »). Les algorithmes sont conçus de façon à ce que plus la fitness d'un individu est elevée, plus il doit avoir de chances de transmettre son génotype au sein de la population.

À chaque étape de l'algorithme est associé un « opérateur », qui décrit la façon de manipuler les individus. On regroupe parfois les différents opérateurs sous des termes génériques :

  • opérateurs de sélection pour la sélection et le remplacement,
  • opérateurs de variation pour la mutation et le croisement.

Algorithme

Pour ce faire, on utilise l'algorithme général suivant :

construction et évaluation d'une population initiale ;
Jusqu'à atteindre un critère d'arrêt :
  sélection d'une partie de la population,
  reproduction des individus sélectionnés,
  mutation de la descendance,
  évaluation du degrés d'adaptation de chaque individu,
  remplacement de la population initiale par une nouvelle population.

Après avoir initialisé une première population d'individus, on itère un nombre fini de fois, jusqu'à atteindre un critère d'arrêt (par exemple un nombre maximum de générations). La première étape de sélection permet de séparer les individus qui participeront à la reproduction de ce qui n'y participeront pas. Les individus sélectionnés (les « parents ») se reproduisent (on dit aussi que l'on effectue des croisements), donnant un ensemble d'« enfants » partageant une partie des caractéristiques de leurs ascendants. Ces enfants subissent alors une étape de mutation, qui modifie aléatoirement leur génotype. Les nouveaux individus sont alors évalués (on met à jour leur valeur en faisant appel à la fonction objectif). Enfin, on choisit un nombre d'individus déterminé parmi l'ensemble parents + enfants, pour former la génération suivante.

Généralités

Les notions d'intensification (ou exploitation), de diversification (ou exploration) et de processus aléatoires sont au cœur du comportement des opérateurs utilisés par les algorithmes évolutionnaires.

Il existe toujours au moins un opérateur utilisant un processus aléatoire, au minimum pour la construction de la population initiale et pour la mutation, mais souvent pour la sélection et la reproduction également. Selon les méthodes, on met l'accent sur l'un ou l'autre des opérateurs.

Une pratique courante reste de maintenir suffisamment longtemps la « diversité génétique » de la population, afin d'éviter une convergence prématurée. Quand un algorithme évolutionnaire utilise une procédure de recherche locale à chaque individu, il est appelé « algorithme mémétique ».

Dans la terminologie historique, on cherche à maximiser la valeur de la fonction objectif, à l'aide d'opérateurs montrant des comportements d’exploitations ou d’exploration. Ces termes correspondent aux notions d'intensification et à la diversification, plutôt utilisés dans le domaine des métaheuristiques, où l'on cherche par ailleurs à minimiser la valeur de la fonction objectif. Néanmoins, ces deux domaines sont tout à fait similaires, les algorithmes évolutionnaires ayant tendance à être classés parmi les métaheuristiques.

Principales familles

Historiquement, trois grandes familles d'algorithmes ont été développées indépendamment, entre la moitié des années 1960 et 70. Les premières méthodes furent les stratégies d'évolution[2]., proposées par I. Rechenberg en 1965, pour résoudre des problèmes d'optimisations continus. L'année suivante, Fogel, Owens et Walsh concoivent la programmation évolutionnaire[3] comme une méthode d'intelligence artificielle pour la conception d'automates à états finis. Enfin, en 1975, J. H. Holland propose les premiers algorithmes génétiques[4], pour l'optimisation combinatoire. La parution en 1989 du livre de D. E. Goldberg sur les algorithmes génétiques[5] rendra ceux-ci particulièrements populaires.

Par la suite, ces différentes approches ont beaucoup évoluées et se sont rapprochées, pour finir par êtres regroupées sous le terme générique d'algorithmes évolutionnaires. Aujourd'hui, la littérature sur le sujet est extrêmement abondante, et ces algorithmes sont considérés comme un domaine de recherche très prolifique.

Stratégies d'évolution

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. La sélection s'effectue par un choix déterministe des meilleurs individus, selon l'échelle de valeur de la fonction objectif. L'étape de mutation est classiquement effectuée par l'ajout d'une valeur aléatoire, tirée au sein d'une distribution normale. Une particularité caractéristique de ces algorithmes est l'auto-adaptation de la matrice de variance-covariance de la distribution normale.

Article détaillé : Stratégies d'évolution.

Un algorithme représentatif des stratégies d'évolution est l'évolution différentielle. Dans cette classe de méthode, on utilise la différence pondérée entre sous-populations pour biaiser un opérateur de mutation différentiel.

Programmation évolutionnaire

Historiquement, ces algorithmes étaient conçus pour des problèmes d'apprentissage à partir d'automates à états finis et n'utilisaient que des opérateurs de mutation et de remplacement. Cependant, aujourd'hui ils ne se limitent plus à une représentation, mais n'utilisent toujours pas d'opérateur de croisement. Ils diffèrent des stratégies d'évolution en ce qu'ils privilégient des opérateurs de remplacement stochastiques.

Article détaillé : Programmation évolutionnaire.

Algorithmes génétiques

Les algorithmes génétiques sont les plus populaires des algorithmes évolutionnaires. Ils différencient explicitement le génotype du phénotype, le génotype étant généralement codé de façon binaire. Le choix du codage du génotype (la façon dont il est relié au phénotype) est crucial pour un algorithme génétique. Classiquement, ils utilisent un opérateur de sélection proportionnel, un remplacement générationnel et l'opérateur de croisement est l'opérateur principal.

Des algorithmes évolutionnaires utilisant d'autres représentations et opérateurs sont souvent appelés algorithmes génétiques, bien que les spécialistes évitent cet abus de langage.

Article détaillé : Algorithme génétique.

Programmation génétique

Ces algorithmes utilisent une représentation en arbres d'expressions logiques, du fait qu'ils sont historiquement appliqués à l'apprentissage statistique et la modélisation. Ils utilisent pour ce faire le même algorithme de base que les algorithmes génétiques. Cependant, la programmation génétique s'intéresse spécifiquement à la construction automatique de programmes.

Article détaillé : Programmation génétique.

Algorithmes à estimation de distribution

Contrairement aux algorithmes évolutionnaires « classiques », le cœur de ces méthodes consiste à estimer les relations entre les différentes variables d'un problème d'optimisation, grâce à l'estimation d'une distribution de probabilité, associée à chaque point de l'échantillon. Ils n'emploient donc pas d'opérateurs de croisement ou de mutation, l'échantillon étant directement construit à partir des paramètres de distribution, estimés à l'itération précédente.

Historique

Chronologie des principales métaheuristiques, le nom est indiqué suivi de l’acronyme anglais entre parenthèses.

Références

Sources

  • (fr) Johann Dréo, Alain Petrowski, Éric Taillard, Patrick Siarry, Métaheuristiques pour l’optimisation difficile, Français, Éd. Eyrolles, Paris, septembre 2003, Broché, 356 pages, ISBN 2-212-11368-4.
  • (en) A. E. Eiben, M. Schoenauer, Evolutionary computing, Information Processing Letters, no 82, pages 1 à 6, 2002.
  1. K. A. DeJong, Are genetic algorithms function optimizers?, Actes de PPSN 2, R. Manner, B. Manderick (éditeurs), pages 3 à 13, 1992.
  2. a  et b Rechenberg, I., Cybernetic Solution Path of an Experimental Problem, Royal Aircraft Establishment Library Translation, 1965
  3. Fogel, L., Owens, A.J., Walsh, M.J., Artificial Intelligence through Simulated Evolution, Wiley, 1966
  4. Holland, John H., Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975
  5. Goldberg, David E., Genetic Algorithms in Search, Optimization and Machine Learning, Kluwer Academic Publishers, Boston, MA., 1989
  6. Robbins, H. and Monro, S., A Stochastic Approximation Method, Annals of Mathematical Statistics, vol. 22, pp. 400-407, 1951
  7. Barricelli, Nils Aall, Esempi numerici di processi di evoluzione, Methodos, pp. 45-68, 1954
  8. Fogel, L., Owens, A.J., Walsh, M.J., Artificial Intelligence through Simulated Evolution, Wiley, 1966
  9. Holland, John H., Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975
  10. Smith, S.F., A Learning System Based on Genetic Adaptive Algorithms, PhD dissertation (University of Pittsburgh), 1980
  11. J.D. Farmer, N. Packard and A. Perelson, The immune system, adaptation and machine learning, Physica D, vol. 22, pp. 187--204, 1986
  12. Koza, John R. Non-Linear Genetic Algorithms for Solving Problems. United States Patent 4,935,877. Filed May 20, 1988. Issued June 19, 1990
  13. Goldberg, David E., Genetic Algorithms in Search, Optimization and Machine Learning, Kluwer Academic Publishers, Boston, MA., 1989
  14. P. Moscato, On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts : Towards Memetic Algorithms, Caltech Concurrent Computation Program, C3P Report 826, 1989.
  15. Mülhenbein, H., Paaß, G., From recombination of genes to the estimation of distribution I. Binary parameters, Lectures Notes in Computer Science 1411: Parallel Problem Solving from Nature, tome PPSN IV, pages 178--187, 1996
  16. Rainer Storn, Kenneth Price, Differential Evolution – A Simple and Efficient Heuristic for global Optimization over Continuous Spaces, Journal of Global Optimization, volume 11, no 4, pages 341-359, 1997
  17. Takagi, H., Active user intervention in an EC Search, Proceesings of the JCIS 2000

Voir aussi

  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Algorithme %C3%A9volutionniste ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme Évolutionniste de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Algorithme evolutionniste — Algorithme évolutionniste Les algorithmes évolutionnistes ou algorithmes évolutionnaires (evolutionary computation en anglais), sont une famille d algorithmes s inspirant de la théorie de l évolution pour résoudre des problèmes divers. Ils font… …   Wikipédia en Français

  • Algorithme évolutionniste — Les algorithmes évolutionnistes ou algorithmes évolutionnaires (evolutionary computation en anglais), sont une famille d algorithmes s inspirant de la théorie de l évolution pour résoudre des problèmes divers. Ils font ainsi évoluer un ensemble… …   Wikipédia en Français

  • Algorithme évolutif — Algorithme évolutionniste Les algorithmes évolutionnistes ou algorithmes évolutionnaires (evolutionary computation en anglais), sont une famille d algorithmes s inspirant de la théorie de l évolution pour résoudre des problèmes divers. Ils font… …   Wikipédia en Français

  • Algorithme évolutioniste — Algorithme évolutionniste Les algorithmes évolutionnistes ou algorithmes évolutionnaires (evolutionary computation en anglais), sont une famille d algorithmes s inspirant de la théorie de l évolution pour résoudre des problèmes divers. Ils font… …   Wikipédia en Français

  • Algorithme évolutionnaire — Algorithme évolutionniste Les algorithmes évolutionnistes ou algorithmes évolutionnaires (evolutionary computation en anglais), sont une famille d algorithmes s inspirant de la théorie de l évolution pour résoudre des problèmes divers. Ils font… …   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

  • Processus bilogique — É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

  • Theories de l'evolution — É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

  • Théorie darwinienne — É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

  • Théorie de l'evolution — É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

Share the article and excerpts

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