- Programmation génétique
-
La programmation génétique est une méthode automatique inspirée par le mécanisme de la sélection naturelle tel qu'il a été établi par Charles Darwin pour expliquer l'adaptation plus ou moins optimale des organismes à leur milieu. Elle a pour but de trouver par approximations successives des programmes répondant au mieux à une tâche donnée.
Sommaire
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 mutations : « 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. Définitions d’un paradigme standard dans le livre « Genetic programming. On the programming of computers by means of natural selection » [Koza, 1992]. Ce paradigme inclut 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 :
- calcul quantique,
- 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[1].
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 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 "subtils" é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
- Brameier, M. (2004), On Linear Genetic Programming
- 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), A Field Guide to Genetic Programming, freely available via Lulu.com.
- Weise, T., Global Optimization Algorithms - Theory and Application
Liens externes
Implémentations en langue française :
- Programmation génétique pour Weka (Java)
- La ferme numérique - élevage de programmes par programmation génétique (PHP/Javascript)
Références
- 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
Wikimedia Foundation. 2010.
