Programmation génétique 1000310 29075314 2008-04-28T19:09:42Z Tenguryu 118814 {{ébauche|informatique}} La '''programmation génétique''' est une méthodologie automatique inspirée par la [[théorie de l'évolution]] telle qu'elle a été définie par [[Charles Darwin]] dans le cas particulier des mécanismes biologiques. Elle se fixe pour but de trouver par approximations successives des programmes répondant au mieux à une tâche donnée. == Description == On nomme programmation génétique une technique permettant à un programme informatique d'apprendre, par un algorithme évolutionniste, à optimiser peu à peu une population d'autres programmes pour augmenter leur degré d'adaptation (fitness) à réaliser une tâche demandée par un utilisateur. == Historique == Afin de bien comprendre d’où vient la programmation génétique, nous allons tout d’abord identifier quelques dates importantes pour cette recherche : • 1958 – Friedberg : Mutation aléatoire d’instruction dans un programme génétique • 1963 – Samuel : Utilisation du terme « machine learning » dans le sens de programmation automatique. • 1966 – Fogel, Owen & Walsh : Automates à états finis pour des tâches de prédiction, obtenus par sélection de parents efficaces auxquels on applique des mutation : « evolutionary programming » • 1985 – Cramer : Utilisation d’expression sous forme d’arbre. Cross-over entre sous-arbres. • 1986 – Hicklin : Evolution de programmes de jeux en LISP. Sélection des parents efficaces, combinaisons des sous-arbres communs ou présents dans un des parents et de sous-arbres aléatoires. • 1989/1992 – Koza : Systématisation et démonstration de l’intérêt de cette approche pour de nombreux problèmes.Definitions d’un paradigme standard dans le livre « Genetic programming. On the programming of computers by means of natural selection » [Koza, 1992]. Ce paradigme inclus plusieurs concepts : programmation structurée en expression arborescentes, définition d’une grammaire de langage, type de retour unique pour chaque fonction, définition des proportions de mutation et de cross-over pour chaque génération, etc. == Forces et faiblesses == La programmation génétique est coûteuse en temps de calcul machine, puisqu'elle met en concurrence de façon parallèle un grand nombre d'algorithmes voisins. A ses débuts, dans les années 1980, on la limita donc à résoudre des problèmes simples. A mesure que la puissance des processeurs se multiplia, la programmation génétique a commencé à donner des résultats plus puissants : fin 2004, par exemple, on comptait une quarantaine de résultats significatifs dans les domaines suivants : * [[calculateur quantique|calcul quantique]], * [[Conception assistée par ordinateur|CAO]] électronique (placement de composants) * résolution de jeux, tris, recherches. Ces résultats comprennent aussi la ré-invention ou l'infirmation de nombreuses inventions récentes et la production de 2 inventions brevetables.<ref>Koza, J.R., Keane, M.A., Streeter, M.J., Mydlowec, W., Yu, J., Lanza, G. (2003), Genetic Programming IV: Routine Human-Competitive Machine Intelligence, Kluwer Academic Publishers</ref> Jusqu'aux années 1990 la programmation génétique ne constituait qu'une [[heuristique]] et non une discipline à part entière. Après quelques avancées dans les années 2000 se développa une théorie à part entière à mesure que la technique s'en généralisait. Au point même qu'il est possible de faire des modèles probabilistes exacts de la programmation génétique et des [[Algorithme génétique|algorithmes génétiques]]. Aujourd'hui, en plus du logiciel, la programmation génétique est aussi appliquée à l'évolution du matériel. La Meta programmation génétique est la technique visant à faire évoluer un système de programmation génétique en utilisant la programmation génétique elle-même. '''Les phases de la programmation génétique''' Le principe de la programmation génétique présenté pour représenter des programmes répondant au problème donné. Voici un algorithme synthétique pour la PG : 1.Génération aléatoire de la population (1 individu = 1 programme) 2.Évaluation du fitness de chacun des individus de la population (évaluation de l'adéquation des programmes au problème à résoudre) 3.Application des opérateurs de croisement, mutation, reproduction sur la population afin de créer une nouvelle population (dans le cadre de la programmation génétique, ce processus correspond à de "subtiles" échanges de codes entre deux programmes.) 4.Sélection des individus les mieux adaptés à leur environnement (dans le cadre de la programmation génétique, cela correspond aux programmes répondant le mieux au problème posé) 5.Répéter les étapes 2 et 3 un certain nombre de fois == Bibliographie en langue anglaise == * Koza, J.R. (1990), Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems, Stanford University Computer Science Department technical report STAN-CS-90-1314. A thorough report, possibly used as a draft to his 1992 book. * Koza, J.R. (1992), Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press * Koza, J.R. (1994), Genetic Programming II: Automatic Discovery of Reusable Programs, MIT Press * Koza, J.R., Bennett, F.H., Andre, D., and Keane, M.A. (1999), Genetic Programming III: Darwinian Invention and Problem Solving, Morgan Kaufmann * Koza, J.R., Keane, M.A., Streeter, M.J., Mydlowec, W., Yu, J., Lanza, G. (2003), Genetic Programming IV: Routine Human-Competitive Machine Intelligence, Kluwer Academic Publishers *Langdon, W. B., Poli, R. (2002), ''Foundations of Genetic Programming'', Springer-Verlag *Poli, R., Langdon, W. B., McPhee, N. F. (2008), [http://www.gp-field-guide.org.uk/ ''A Field Guide to Genetic Programming''], freely available via Lulu.com. == Références == <references /> {{Portail informatique}} [[Catégorie:Intelligence artificielle]] [[ca:Programació genètica]] [[cs:Genetické programování]] [[de:Genetische Programmierung]] [[en:Genetic programming]] [[it:Programmazione genetica]] [[ja:遺伝的プログラミング]] [[pl:Programowanie genetyczne]] [[pt:Programação genética]] [[sl:Genetsko programiranje]] [[zh:遗传编程]]