Programmation génétique
From Wikipedia, the free encyclopedia
La programmation génétique est un algorithme s'inspirant de la sélection naturelle décrite par Charles Darwin qui permet de créer un programme résolvant un problème donné. La population, constituée de programmes informatiques, évolue sur plusieurs générations afin de finalement obtenir un programme capable de répondre à la tâche prédéfinie.
Cet article est une ébauche concernant l’informatique.
Cette évolution, permettant de passer d'une génération à une autre, se caractérise par deux opérations génétiques. La première est le croisement de deux individus et peut se comparer à la reproduction. En effet, lors de cette étape, deux programmes vont engendrer un nouveau programme qui appartiendra à la génération suivante. La deuxième opération, appelée mutation, modifie aléatoirement une partie d'un individu.
Un score est attribué à chaque programme en fonction de sa performance vis-à-vis du problème. Ainsi, les programmes avec les meilleurs scores vont générer la nouvelle génération grâce aux opérations génétiques décrites précédemment.
Le point clé est qu'en moyenne, à travers les générations, les scores des programmes augmentent. Par conséquent, après un certains nombre de générations, on peut s'attendre à obtenir un programme adapté au problème.
Origine
Une des premières descriptions du concept de programmation génétique est due à Friedberg. En 1958, il décrivit comment utiliser un algorithme génétique pour trouver un programme approximant une fonction.
Plus tard, en 1966 Fogel, Owen & Walsh utilisèrent des automates à états finis pour exécuter des tâches. Il les fit évoluer en appliquant des mutations à une sélection de parents efficaces.
20 ans plus tard, les premières représentations des programmes sous forme d'arbre ont vu le jour notamment avec les travaux de Cramer.
Enfin, à travers le livre "Genetic programming. On the programming of computers by means of natural selection" écrit par John Koza en 1992, l'intérêt de la programmation génétique fut démontré.
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 se 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.
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
Fonctionnement
Représentation
Le plus souvent, les programmes sont représentés sous forme d'arbre. Les feuilles sont les variables et les constantes (x,y ou 10 par exemple) tandis que les nœuds internes sont des fonctions (+,*, max, cos,...). Pour un nœud interne représentant une fonction f, les enfants du nœud correspondent aux arguments de f. Le programme représenté par l'arbre peut facilement être déduit de manière récursive. Les nœuds peuvent également décrire des fonctions de type if b then a1 else a2 avec b, a1, a2 les enfants du nœud.
Il existe également d'autres représentations. Par exemple, on peut représenter les programmes par des graphes, les arbres en sont donc un sous-cas. On peut également décrire les programmes par une suite d'instructions, c'est la représentation linéaire.
Initialisation
Comme dans la plupart des algorithmes de ce type, les programmes composant la population initiale sont choisis aléatoirement. Il existe deux différentes méthodes :
- La méthode croissante : à chaque nœud, on tire aléatoirement entre une fonction et une variable ou une constante. Les arbres obtenus ont donc des profondeurs différentes. Cependant, une profondeur maximale est choisie à l'avance et lorsqu'elle est atteinte, le nœud ne peut pas représenter une fonction.
- La méthode complète : les nœuds sont tous représentés par des fonctions tirées aléatoirement sauf ceux de la profondeur maximale, qui sont alors décrits par une variable ou une constante. Ainsi, les arbres obtenus ont tous la même profondeur, mais pas forcément la même taille si les fonctions ne prennent pas toutes le même nombre d'arguments.
Cependant, ces deux méthodes prises individuellement ne fournissent pas une population très diversifiée. Ainsi, la plupart du temps, une moitié de la population initiale est créée en utilisant la méthode croissante et l'autre moitié avec la méthode complète avec à chaque fois des profondeurs maximales différentes.
Sélection
Afin de faire évoluer notre population, il faut sélectionner des individus et appliquer les opérations génétiques décrites dans l'introduction. Pour que les générations deviennent meilleures, il faut que ces individus soient les meilleures de la population. Cependant, pour ne pas converger trop vite vers un extremum local, il faut conserver certains individus prometteurs afin d'explorer différents types de solutions. Les deux principales méthodes de sélection sont :
- Sélection par tournoi : pour réaliser un tournoi, n individus sont tirés aléatoirement et le meilleur d'entre eux sera utilisé lors des étapes des mutations et croisement. Il y a autant de tournois réalisés que d'individus à repêcher. Avec cette méthode, les meilleurs éléments de la population auront beaucoup de chances d'être choisis, mais les éléments prometteurs ont une probabilité non nulle d'être sélectionnés.
- Sélection par roulette : pour chaque individu, la probabilité d'être choisi est proportionnelle à son score. Ainsi, les meilleurs éléments auront plus de chance d'être pris que les autres, mais chaque individu a une probabilité non nulle d'être sélectionné.
Croisement
L'opération génétique du croisement consiste à créer un nouvel individu à partir de deux parents. Au cours de cette opération, lorsque les programmes sont représentés sous forme d'arbres, un nœud du premier parent est aléatoirement choisi et est remplacé par un sous-arbre du second parent (également choisi aléatoirement). Les nœuds sélectionnés sont coloriés en jaune dans l'animation.
Il existe d'autres moyens de faire des croisements. Par exemple, dans plusieurs variantes, les nœuds ne sont pas choisis aléatoirement de manière uniforme, mais certaines règles poussent à choisir un nœud plutôt qu'un autre. Ces règles peuvent permettre d'éviter qu'un arbre devienne trop grand ou qu'une branche soit beaucoup plus grosse que les autres.
Mutation
L'idée de cette opération génétique est de modifier aléatoirement une petite partie d'un individu. Les mutations ne sont pas obligatoires mais accélèrent significativement la convergence. Par conséquent, il est peu fréquent de voir cette opération négligée.
Encore une fois, il existe de multiples méthodes pour faire muter un individu. Par exemple, une feuille ou un nœud interne peuvent être modifié. On peut également choisir un nœud et remplacer son sous-arbre pour un arbre aléatoire de la même façon que lors de l'initialisation.
Réplication
Afin de ne pas perdre les meilleurs individus d'une génération à une autre, certains sont copiés sans ne subir la moindre modification. Ainsi, les meilleurs programmes de chaque génération ne peuvent que s'améliorer.
Il faut également noter qu'il n'y a pas de raison théorique à ce que ces opérations génétiques améliorent les générations. Cependant, en pratique, il se trouve que l'exploration de l'espace grâce à cet algorithme est plutôt performante et qu'il y a donc convergence vers une solution efficace.
Forces et faiblesses
Pour utiliser la programmation génétique, il faut prendre en compte beaucoup de paramètres comme la taille de la population, l'ensemble des fonctions utilisées, les différentes méthodes d'initialisation, de croisement et de mutation, la profondeur initiale des arbres, ... Ainsi, même s'il n'y a pas une seule configuration optimale, il peut être difficile de trouver une configuration donnant de bons résultats, surtout qu'il n'y a pas de méthode générale, il faut obligatoirement s'adapter au problème à résoudre.
De plus, 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. À ses débuts, dans les années 1980, on la limita donc à résoudre des problèmes simples.
Cependant, le fait d'avoir une population de programmes peut permettre d'obtenir plusieurs solutions efficaces. L'algorithme peut converger vers plusieurs extrema différents et cela peut être bénéfique.
Enfin, voici quelques exemples de critères qui permettent à la programmation génétique d'être plus efficace que d'autres algorithmes d'optimisation :
- Lorsque que les relations entre les variables ne sont pas bien comprises. En effet, si le problème est bien compris, il existe surement des algorithmes plus efficace. Au contraire, si le problème n'est pas bien compris, la programmation génétique peut aider à décrouvrir les variables les plus importantes et leurs relations entre elles.
- Lorsqu'il faut trouver la forme de la solution. La programmation génétique génère des individus de tailles différentes. Ainsi, si la taille des solutions est connue, les algorithmes de recherche à taille fixe seront privilégiés.
- Lorsqu'une solution approchée est acceptée. En effet, la programmation génétique n'a aucune raison de converger vers un extremum global. Au contraire, la plupart du temps, l'algorithme converge vers un ou des extrema locaux.
Applications
À mesure que la puissance des processeurs se multiplia, la programmation génétique a commencé à donner des résultats plus puissants. Voici une liste non exhaustive de domaines où la programmation génétique est utilisée :
- calcul quantique,
- CAO électronique (placement de composants),
- résolution de jeux, tris, recherches,
- traitement d'image et de signaux,
- finance,
- biologie, bio-informatique,
- compression...
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
- Kenneth De Jong, David B.Fogel, Hans-Oaul Schwefel, (1997) A history of evolutionary computation.
En français
- Belbachir Assia, Deau Raphaël, Lenne Renaud, Snoussi Jihene : La Programmation Génétique.
