Programmation génétique

Un article de Wikipédia, l'encyclopédie libre.

La programmation génétique est une méthodologie automatique inspirée par la théorie de l'Evolution telle qu'elle a été définie par 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.

Sommaire 1 Description 2 Historique 3 Forces et faiblesses 4 Voir aussi 5 Bibliographie en langue anglaise

[modifier] 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.

[modifier] Historique

La première expérience de programmation génétique fut reportée par Stephen F. Smith (1980) et Nichael L. Cramer (1985), comme indiqué dans l'ouvrage d'origine et de référence : Genetic Programming: On the Programming of Computers by Means of Natural Selection, par John Koza (1992).

Les algorithmes génétiques n'imposent pas de langage informatique particulier. L'organisation arborescente des informations a favorisé au début des langages comme Lisp (Forza). Par la suite, on a également utilisé des représentations linéaires manipulables par n'importe quel langage..

[modifier] 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ésultatsplus puissants : fin 2004, par exemple, on comptait une quarantaine de résultats significatifs dans les domaines suivants :

• calcul quantique,
• CAO électronique (placement de composants)
• résolution de jeux, tris, recherches.

Ces résultats comprendraient aussi (??? Source ?) la ré-invention ou l'infirmation de nombreuses inventions récentes et même la production de 2 inventions brevetables.

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 probabilistiques exacts de la programmation génétique et des 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.

[modifier] Voir aussi

Algorithme génétique

[modifier] 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