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. 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. 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 : Évolution 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.