Programmation génétique

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 :

Références

  1. 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.

Contenu soumis à la licence CC-BY-SA. Source : Article Programmation génétique de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Programmation Génétique — 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… …   Wikipédia en Français

  • Programmation genetique — Programmation génétique 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 …   Wikipédia en Français

  • Programmation évolutionnaire — Programmation génétique 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 …   Wikipédia en Français

  • PROGRAMMATION — Un ordinateur est une machine universelle pour le traitement de l’information. Il doit pouvoir être utilisé aussi bien pour des calculs numériques que pour la gestion d’un stock de pièces détachées ou des travaux de secrétariat. Il est donc… …   Encyclopédie Universelle

  • Programmation (homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Informatique La programmation informatique est l ensemble des activités qui permettent l écriture des programmes informatiques. On distingue… …   Wikipédia en Français

  • Algorithme génétique — 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… …   Wikipédia en Français

  • Algorithme Génétique — Les algorithmes génétiques appartiennent à la famille des algorithmes évolutionnistes (un sous ensemble des métaheuristiques). Leur but est d obtenir une solution approchée, en un temps correct, à un problème d optimisation, lorsqu il n existe… …   Wikipédia en Français

  • Algorithme genetique — Algorithme génétique Les algorithmes génétiques appartiennent à la famille des algorithmes évolutionnistes (un sous ensemble des métaheuristiques). Leur but est d obtenir une solution approchée, en un temps correct, à un problème d optimisation,… …   Wikipédia en Français

  • Semantique des langages de programmation — Sémantique des langages de programmation En informatique théorique, la sémantique formelle (des langages de programmation) est l’étude de la signification des programmes informatiques vus en tant qu’objets mathématiques. Sommaire 1 Lien avec la… …   Wikipédia en Français

  • Sémantique des langages de programmation — En informatique théorique, la sémantique formelle (des langages de programmation) est l’étude de la signification des programmes informatiques vus en tant qu’objets mathématiques. Sommaire 1 Lien avec la linguistique 2 Sémantiques usuelles d’un… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”