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:遗传编程]]