Article interactif

1 - ALGORITHMES GÉNÉTIQUES, ÉVOLUTIONNAIRES, DARWINISME ARTIFICIEL

2 - PROGRAMMER ET UTILISER UN ALGORITHME ÉVOLUTIONNAIRE

3 - APERÇU THÉORIQUE : POURQUOI ET COMMENT ÇA MARCHE ?

4 - EXTENSIONS DU MODÈLE

5 - EXEMPLES D’APPLICATION

6 - CONCLUSION

7 - REMERCIEMENTS

8 - GLOSSAIRE

9 - SIGLES, NOTATIONS ET SYMBOLES

Article de référence | Réf : S7218 v2

Algorithmes génétiques, algorithmes évolutionnaires

Auteur(s) : Évelyne LUTTON

Relu et validé le 05 janv. 2021

Pour explorer cet article
Télécharger l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !

Sommaire

Présentation

NOTE DE L'ÉDITEUR

Cet article est la version actualisée de l’article S7218 intitulé Algorithmes génétiques et algorithmes évolutionnaires rédigé par Évelyne LUTTON et paru en 2006

05/01/2021

RÉSUMÉ

Les principes de base des algorithmes évolutionnaires (AE), dont les plus connus sont les algorithmes génétiques (AG), sont directement inspirés de la théorie de l’évolution selon Darwin. Ces méthodes de résolution de problèmes, d’optimisation stochastique, copient de façon très simplifiée la capacité de populations d’organismes vivants à s’adapter à leur environnement à l’aide de mécanismes de sélection et d’héritage génétique. Cet article donne un panorama rapide du « darwinisme artificiel » et de la variété de ses applications.

Lire cet article issu d'une ressource documentaire complète, actualisée et validée par des comités scientifiques.

Lire l’article

ABSTRACT

Genetic and evolutionary algorithms

Evolutionary Algorithms (EA), including the most famous ones, Genetic Algorithms (GA), are based on Darwin’s theory. These problem-solving or stochastic optimization methods mimic in a very simplified manner the capabilities of populations of living organisms to adapt to their environments thanks to selection and genetic inheritance mechanisms. This paper provides a brief panorama of artificial Darwinism and its varied and numerous applications.

Auteur(s)

  • Évelyne LUTTON : Directrice de recherche INRAE - UMR MIA 518, AgroParisTech/INRAE - Institut des systèmes complexes, 113 rue Nationale, 75013, Paris, France.

INTRODUCTION

Depuis les années 1970, de nombreuses méthodes d’optimisation stochastique ont été développées sur la base de principes simplifiés d’évolution darwinienne. L’anglicisme « algorithmes évolutionnaires (AE) » choisi pour désigner ces méthodes est intentionnel : la communauté française employant ces méthodes a jugé important de distinguer les travaux évolutionnistes, portant sur des modèles biologiques très complexes, des approches évolutionnaires, utilisant des modèles informatiques ultra-simplifiés.

Actuellement, les algorithmes dits « génétiques » (AG) sont les plus médiatisés parmi ces techniques, mais il en existe d’autres (programmation génétique, stratégies d’évolution, évolution grammaticale, par exemple) qui diffèrent par leur interprétation des principes darwiniens. La composante commune de ces techniques est qu’elles font évoluer des populations organisées en générations – qui représentent par exemple des points d’un espace de recherche quand on souhaite optimiser une fonction – sous l’action conjuguée de deux catégories d’opérateurs stochastiques produisant :

  •  une pression de sélection permettant de sélectionner des individus autorisés à se reproduire : « les meilleurs » au regard d’une fonction définie sur l’espace de recherche considéré, dite « fonction d’évaluation », « fonction de performance », ou « fitness », et qui traduit le problème que l’on cherche à résoudre ;

  •  des variations aléatoires qui produisent de nouveaux individus, afin de constituer la génération suivante : croisement par échange d’informations entre plusieurs points, mutation par perturbation locale sur un point, pour faire un parallèle avec la génétique.

L’efficacité de ce schéma est fondée sur l’hypothèse que l’action des opérateurs génétiques sur des individus sélectionnés produit statistiquement des individus de plus en plus proches de la solution recherchée. En d’autres termes, le processus stochastique figuré par les populations successives doit être correctement calibré et paramétré pour converger vers ce que l’on souhaite, c’est-à-dire le plus souvent l’optimum global de la fonction de performance. Une grande part des recherches théoriques sur les algorithmes évolutionnaires est consacrée à cet épineux problème de convergence et à celui de savoir ce qui rend la tâche aisée ou difficile pour un algorithme évolutionnaire (notion d’AE-difficulté). Comme nous le verrons dans ce panorama, des réponses théoriques rassurantes existent (oui, cela converge, si l’on respecte certaines hypothèses), mais d’autres questions cruciales d’un point de vue pratique restent ouvertes (vitesses de convergence, notamment). On peut cependant dire que les résultats théoriques justifient l’efficacité des algorithmes évolutionnaires en tant qu’heuristiques de recherche aléatoire, confortant ainsi leur large usage empirique.

Du point de vue de l’optimisation, le grand intérêt des algorithmes évolutionnaires est que ce sont des méthodes stochastiques d’ordre 0, c’est-à-dire que seule la connaissance des valeurs de la fonction à optimiser aux points d’échantillonnage est nécessaire (il n’y a pas nécessité de connaître des dérivées), ce qui en fait des méthodes d’optimisation utilisables pour des fonctions très irrégulières, mal conditionnées ou complexes à calculer. En revanche, un algorithme évolutionnaire a un coût calculatoire qui peut devenir important. Ces deux caractéristiques en font des méthodes adaptées aux cas où les méthodes standard plus rapides du point de vue du calcul (par exemple, des méthodes de gradient requérant l’existence et le calcul de dérivées) ne sont plus applicables, du fait qu’elles se trouvent trop rapidement piégées dans des optima locaux : espace de recherche trop vaste, fonctions trop irrégulières, jeu de variables mixtes, par exemple. Nous verrons plus loin que d’autres problèmes – comme les problèmes dynamiques ou les problèmes interactifs – peuvent être traités à l’aide d’une approche évolutionnaire. Enfin, il est souvent avantageux d’hybrider les approches évolutionnaires avec d’autres approches d’optimisation (descente de gradient, recherche Tabou, recuit simulé, etc.).

Malgré l’apparente simplicité d’un processus évolutionnaire (ce qui a conduit de nombreux programmeurs à écrire très vite « leur » algorithme génétique, parfois bien décevant), fabriquer un algorithme évolutionnaire efficace est une tâche difficile, car les processus évolutionnaires sont très sensibles aux choix algorithmiques et paramétriques, aux représentations du problème notamment. Le design des ingrédients de base d’un algorithme évolutionnaire efficace n’est pas si simple et l’expérience prouve que les grandes réussites sont fondées sur une très bonne connaissance du problème à traiter, sur une bonne compréhension des mécanismes évolutionnaires et sur une bonne dose de créativité. Il est tout bonnement hasardeux de considérer ces techniques en « boîte noire », comme un « optimiseur universel », que l’on utilise sans faire aucun réglage.

Cela dit, les « success-stories » sont nombreuses, et les techniques évolutionnaires font partie de notre quotidien ; il suffit par exemple de suivre ce qui se fait dans les conférences internationales du domaine (EvoStar, CEC, GECCO, PPSN, EA) pour s’en convaincre. En effet, le champ d’application des algorithmes évolutionnaires est très large : il va des applications réelles complexes comme le contrôle du flux de pipelines de gaz, le design de profils d’ailes, le routage aérien ou la planification de trajectoires de robots, à des problèmes plus théoriques et combinatoires, en théorie des jeux, en modélisation économique, en finance, en commande de processus et en apprentissage.

Cet article est réservé aux abonnés.
Il vous reste 93% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

KEYWORDS

Evolutionary algorithms   |   Genetic algorithms   |   Stochastic optimisation   |   Artificial darwinism

VERSIONS

Il existe d'autres versions de cet article :

DOI (Digital Object Identifier)

https://doi.org/10.51257/a-v2-s7218


Cet article fait partie de l’offre

Automatique et ingénierie système

(140 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS

Cet article est réservé aux abonnés.
Il vous reste 93% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

TEST DE VALIDATION ET CERTIFICATION CerT.I. :

Cet article vous permet de préparer une certification CerT.I.

Le test de validation des connaissances pour obtenir cette certification de Techniques de l’Ingénieur est disponible dans le module CerT.I.

Obtenez CerT.I., la certification
de Techniques de l’Ingénieur !
Acheter le module

Cet article fait partie de l’offre

Automatique et ingénierie système

(140 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS

Sommaire
Sommaire

BIBLIOGRAPHIE

  • (1) - ALTENBERG (L.) -   Evolutionary Computation Models from Population Genetics, Part 2: An Historical Toolbox,  -  in Congress on Evolutionary Computation (2000).

  • (2) - ANGELINE (P.J.), POLLACK (J.B.) -   Competitive Environments Evolve Better Solutions for Complex Tasks,  -  in Proceedings of the Fifth International Conference on Genetic Algorithms, San Mateo, California: Morgan Kaufmann (1993).

  • (3) - GOERTZEL (B.) -   Fractal image compression with the genetic algorithm,  -  Complexity International, 1 (1994).

  • (4) - BAECK (T.), HOFFMEISTER (F.), SCHWEFEL (H.P.) -   A Survey of Evolution Strategies,  -  in International Conference on Genetic Algorithms, pp. 2-10 (1991).

  • (5) - BANZHAF (W.) -   Handbook of Evolutionary Computation,  -  in Oxford University Press (1997).

  • (6) - BEN HAMIDA (S.) -   Algorithmes...

1 Outils logiciels

Inspyred, bibliothèque dalgorithmes bioinspirés en langage python

https://pythonhosted.org/inspyred/

GAlib - C++ Genetic Algorithms Library

https://sourceforge.net/projects/galib/

Matlab Global Optimization Toolbox (inclut des algorithmes génétiques)

https://fr.mathworks.com/help/gads/genetic-algorithm.html

GPLAB, A Genetic Programming Toolbox for MATLAB

http://gplab.sourceforge.net

DEAP, Genetic Programming in Python

https://deap.readthedocs.io/en/master/

Evolving Objects (EO), a template-based, ANSI-C++ evolutionary computation

http://eodev.sourceforge.net

Langage de spécification EASEA, multi plates-formes

http://easea.unistra.fr/index.php/EASEA_platform

HAUT DE PAGE

2 Sites Internet

Association Évolution artificielle

Elle regroupe les chercheurs français de ce domaine et organise conférences internationales (EA), journées et écoles

http://ea.inria.fr...

Cet article est réservé aux abonnés.
Il vous reste 92% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Automatique et ingénierie système

(140 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS

Sommaire

QUIZ ET TEST DE VALIDATION PRÉSENTS DANS CET ARTICLE

1/ Quiz d'entraînement

Entraînez vous autant que vous le voulez avec les quiz d'entraînement.

2/ Test de validation

Lorsque vous êtes prêt, vous passez le test de validation. Vous avez deux passages possibles dans un laps de temps de 30 jours.

Entre les deux essais, vous pouvez consulter l’article et réutiliser les quiz d'entraînement pour progresser. L’attestation vous est délivrée pour un score minimum de 70 %.


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Automatique et ingénierie système

(140 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS