Algorithme évolutionniste — Wikipédia

Algorithme évolutionniste

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.

Type	Algorithme d'optimisation, métaheuristique

modifier - modifier le code - modifier Wikidata

Les algorithmes évolutionnistes ou algorithmes évolutionnaires (evolutionary algorithms en anglais), sont une famille d'algorithmes dont le principe s'inspire de la théorie de l'évolution pour résoudre des problèmes divers. Ce sont donc des méthodes de calcul bioinspirées. L'idée est de faire évoluer un ensemble de solutions à un problème donné, dans l'optique de trouver les meilleurs résultats. Ce sont des algorithmes dits 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 computationnelle.

Ces algorithmes manipulent des populations de solutions.

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 individus sont plus ou moins adaptés à 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.

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 que plus la fitness d'un individu est élevée, plus il a de chances de transmettre son génotype au sein de la population.

À chaque étape, 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.

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

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 objective, à 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 en général à 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.

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 conçoivent 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èrement populaires.

Par la suite, ces différentes approches ont beaucoup évolué 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.

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.

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.

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.

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.

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.

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.

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

• 1952 : premiers travaux sur l’utilisation de méthodes stochastiques pour l’optimisation^[6].
• 1954 : Barricelli effectue les premières simulations du processus d’évolution et les utilise sur des problèmes d’optimisation généraux^[7].
• 1965 : Rechenberg conçoit le premier algorithme utilisant des stratégies d’évolution^[2].
• 1966 : Fogel, Owens et Walsh proposent la programmation évolutionnaire^[3].
• 1970 : John Horton Conway conçoit le jeu de la vie, l’automate cellulaire le plus connu à ce jour.
• 1975 : travaillant sur les automates cellulaires, Holland propose les premiers algorithmes génétiques^[3].
• 1980 : Smith utilise la programmation génétique ^[8].
• 1986 : Farmer, Packard et Perelson travaillent sur les systèmes immunitaire artificiels^[9].
• 1988 : la première conférence sur les algorithmes génétiques est organisée à l’université de l’Illinois à Urbana-Champaign.
• 1988 : Koza dépose son premier brevet sur la programmation génétique^[10].
• 1989 : Goldberg publie un des livres les plus connus sur les algorithmes génétiques^[3].
• 1989 : Evolver, le premier logiciel d’optimisation par algorithmes génétiques est publié par la société Axcelis.
• 1989 : le terme algorithme mémétique apparait^[11].
• 1993 : le terme « Evolutionary Computation » (« calcul évolutionnaire » en français) se répand, avec la parution de la revue éponyme, publiée par le Massachusetts Institute of Technology.
• 1996 : Mühlenbein et Paaß proposent les algorithmes à estimation de distribution^[12].
• 1997 : Storn et Price proposent un algorithme à évolution différentielle^[13].
• 2000 : premiers algorithmes génétiques interactifs^[14].

• (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, n^o 82, pages 1 à 6, 2002.

• Certains systèmes immunitaires artificiels peuvent être vus comme des algorithmes évolutionnaires et des métaheuristiques d'optimisation.
• Ils sont parfois également appelés algorithmes mémétiques, car les solutions mathématiques manipulées sont parfois plus proches de la culture que de la biologie.

v · m Apprentissage automatique et exploration de données
Paradigmes d'apprentissage	Apprentissage supervisé auto-supervisé semi-supervisé ou non supervisé Apprentissage par renforcement, par transfert ou incrémental
Problèmes	Classement Clustering Détection d'anomalies Optimisation en ligne Modèle génératif Régression Règle d'association Réduction de dimensions Analyse factorielle Sélection de caractéristique Extraction de caractéristique
Apprentissage supervisé	Classement Arbre de décision k-NN U-matrix CRF Régression logistique Régression Modèle linéaire généralisé Régression linéaire Régression de Poisson Modèle probit Analyse discriminante linéaire Machine à vecteurs de support Prédiction structurée Modèle graphique Classification naïve bayésienne Réseau bayésien Modèle de Markov caché Réseau de neurones artificiels récurrents (+ Rétropropagation à travers le temps) Calcul par réservoir à action directe (+ Rétropropagation du gradient) Apprentissage profond Perceptron Perceptron multicouche Réseau neuronal convolutif à impulsions
Apprentissage non supervisé et auto-supervisé	Clustering Regroupement hiérarchique K-means Algorithme espérance-maximisation DBSCAN OPTICS Réduction de dimensions ACP Analyse en composantes indépendantes Analyse canonique des corrélations t-SNE Réseau de neurones artificiels Auto-encodeur IA générative et Modèle génératif Réseau de neurones artificiels Réseaux antagonistes génératifs Réseau de Hopfield Machine de Boltzmann restreinte Cartes de Kohonen Transformeur
Métaheuristique d'optimisation	Algorithme évolutionniste et génétique NEAT HyperNEAT Essaims Apprentissage ensembliste Forêts aléatoires Boosting
Théorie	Apprentissage PAC Complexité de Rademacher Dilemme biais-variance Hypothèse de la variété Théorie de Vapnik-Chervonenkis pulvérisation Dimension de Vapnik-Chervonenkis Théorème de Cover
Logiciels	Keras Microsoft Cognitive Toolkit Scikit-learn TensorFlow Theano Weka PyTorch

v · m Optimisation: théorie et algorithmes
Non linéaire	Méthode du nombre d'or Recherche linéaire Méthode de Nelder-Mead Critères de Wolfe Méthode de Broyden-Fletcher-Goldfarb-Shanno Algorithme à régions de confiance Pénalisation Algorithme du gradient Algorithme du gradient stochastique Méthode de Newton Algorithme de Gauss-Newton Algorithme de Levenberg-Marquardt Algorithme du lagrangien augmenté
Convexe	Optimisation complètement positive Optimisation copositive Optimisation SDP Méthode des plans sécants Algorithme de Frank-Wolfe Méthode de l'ellipsoïde Linéaire Optimisation conique Algorithme du simplexe Méthodes de points intérieurs Décomposition de Benders Génération de colonnes Quadratique Optimisation quadratique successive
Combinatoire	Algorithme d'approximation Programmation dynamique Algorithme glouton Optimisation linéaire en nombres entiers
Métaheuristique	Algorithme évolutionniste Algorithme génétique Essaims Forêts aléatoires Boosting
Liste

• Portail de l'informatique théorique