Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Algorithme génétique
Résumé
Les algorithmes génétiques appartiennent à la famille des algorithmes évolutionnistes. Leur but est d'obtenir une solution approchée à un problème d'optimisation, lorsqu'il n'existe pas de méthode exacte (ou que la solution est inconnue) pour le résoudre en un temps raisonnable. Les algorithmes génétiques utilisent la notion de sélection naturelle et l'appliquent à une population de solutions potentielles au problème donné. La solution est approchée par « bonds » successifs, comme dans une procédure de séparation et évaluation (branch & bound), à ceci près que ce sont des formules qui sont recherchées et non plus directement des valeurs.
L'utilisation d'algorithmes génétiques, dans la résolution de problèmes, est à l'origine le fruit des recherches de John Holland et de ses collègues et élèves de l'Université du Michigan qui ont, dès 1960, travaillé sur ce sujet.
La nouveauté introduite par ce groupe de chercheurs a été la prise en compte de l'opérateur d'enjambement (cross-over) en complément des mutations. Et c'est cet opérateur qui permet le plus souvent de se rapprocher de l'optimum d'une fonction en combinant les gènes contenus dans les différents individus de la population.
Le premier aboutissement de ces recherches a été la publication en 1975 de Adaptation in Natural and Artificial System.
La popularisation des algorithmes génétiques sera l'œuvre de David Goldberg à travers son livre Genetic Algorithms in Search, Optimization, and Machine Learning (1989). Ce livre est encore édité aujourd'hui. En Europe, la première conférence sur ce type de sujet fut l'European Conference on Artificial Life en 1991 (elle a fêté ses 20 ans en 2011), coorganisée par Francisco Varela et Paul Bourgine. Un des premiers ouvrages à présenter en Français les algorithmes génétiques sera le livre Intelligence Artificielle et Informatique Théorique qui lui consacrera un chapitre dès 1993. La première conférence francophone avec actes sur le sujet sera organisée en 1994 par Jean-Marc Alliot (IRIT), Evelyne Lutton (INRIA), Marc Schoenauer (INRIA) et Edmund Ronald.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.