Programmation évolutionnaire

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 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 "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), A Field Guide to Genetic Programming, freely available via Lulu.com.
  • Weise, T., Global Optimization Algorithms - Theory and Application

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
  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Programmation g%C3%A9n%C3%A9tique ».

Wikimedia Foundation. 2010.

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

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Algorithme évolutionnaire — Algorithme évolutionniste Les algorithmes évolutionnistes ou algorithmes évolutionnaires (evolutionary computation en anglais), sont une famille d algorithmes s inspirant de la théorie de l évolution pour résoudre des problèmes divers. Ils font… …   Wikipédia en Français

  • Psychologie évolutionnaire — Psychologie évolutionniste La psychologie évolutionniste est un courant de la psychologie culturelle, dont l objectif est d expliquer les mécanismes de la pensée humaine à partir de la théorie de l évolution biologique. Elle repose sur l… …   Wikipédia en Français

  • Algorithme evolutionniste — Algorithme évolutionniste Les algorithmes évolutionnistes ou algorithmes évolutionnaires (evolutionary computation en anglais), sont une famille d algorithmes s inspirant de la théorie de l évolution pour résoudre des problèmes divers. Ils font… …   Wikipédia en Français

  • Algorithme Évolutionniste — Les algorithmes évolutionnistes ou algorithmes évolutionnaires (evolutionary computation en anglais), sont une famille d algorithmes s inspirant de la théorie de l évolution pour résoudre des problèmes divers. Ils font ainsi évoluer un ensemble… …   Wikipédia en Français

  • Algorithme évolutif — Algorithme évolutionniste Les algorithmes évolutionnistes ou algorithmes évolutionnaires (evolutionary computation en anglais), sont une famille d algorithmes s inspirant de la théorie de l évolution pour résoudre des problèmes divers. Ils font… …   Wikipédia en Français

  • Algorithme évolutioniste — Algorithme évolutionniste Les algorithmes évolutionnistes ou algorithmes évolutionnaires (evolutionary computation en anglais), sont une famille d algorithmes s inspirant de la théorie de l évolution pour résoudre des problèmes divers. Ils font… …   Wikipédia en Français

  • Algorithme évolutionniste — Les algorithmes évolutionnistes ou algorithmes évolutionnaires (evolutionary computation en anglais), sont une famille d algorithmes s inspirant de la théorie de l évolution pour résoudre des problèmes divers. Ils font ainsi évoluer un ensemble… …   Wikipédia en Français

  • Metaheuristique — Métaheuristique Les métaheuristiques forment une famille d’algorithmes d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l ingénierie ou de l intelligence… …   Wikipédia en Français

  • Méta-heuristique — Métaheuristique Les métaheuristiques forment une famille d’algorithmes d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l ingénierie ou de l intelligence… …   Wikipédia en Français

  • Métaheuristique — Une métaheuristique est un algorithme d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l ingénierie ou de l intelligence artificielle) pour lesquels on ne… …   Wikipédia en Français

Share the article and excerpts

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