La Programmation Génétique - notions
La programmation génétique permet dans une certaine mesure de répondre au rêve de tout informaticien, à savoir créer un programme automatiquement pour résoudre un problème donné. La programmation génétique est une branche récente mise au goût du jour par John Koza à la fin des années quatre-vingts. La PG (Programmation Génétique) se classe dans la grande famille des algorithmes évolutionnaires qui s'inspire du paradigme de l'évolution darwinienne afin de faire évoluer des populations de solutions potentielles.
Dans la cadre général des techniques évolutionnaires, une population est constituée d'individus (qui correspondent plus ou moins après un processus de décodage à une solution potentielle). Par une analogie grossière avec le processus darwinien de l'évolution, cette population va évoluer afin de s'adapter à son environnement (l'environnement correspondant au problème posé).
Cette population va subir les différentes étapes d'un processus évolutif simulé :
- 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é)
- croisement des individus correspondant de manière grossière à la reproduction sexuée des individus (dans le cadre de la programmation génétique, ce processus correspond à de "subtiles" échanges de codes entre deux programmes. Oui, c'est possible !)
- mutation aléatoire des individus
La partie la plus délicate dans les techniques évolutionnaires est l'écriture d'une fonction d'adaptation. Toujours dans le cadre du mimétisme du processus darwinien, seuls les individus les mieux adaptés à leur environnement survivent. Il devient donc nécessaire d'écrire de manière informatique une telle fonction qui évaluera les individus (les programmes) afin de leur donner une note qualifiant leur degré d'adaptation. Cette fonction est généralement appelée fonction fitness ou fonction d'adaptation.
L'autre écueil, plus spécifique à la programmation génétique consiste à sélectionner les briques de base qui permettront à créer des programmes. Si mon ensemble de brique de base est trop restreint, je ne pourrai peut-être jamais obtenir une solution au problème, par si cet ensemble est trop vaste, le processus algorithmique risque de ne jamais pouvoir converger.
Historiquement, les langages utilisés pour la programmation génétique étaient les langages fonctionnels comme le LISP ou Scheme. Ces langages furent choisis car ils respectaient une importante propriété, indispensable dans le cadre de la programmation génétique, la propriété de clôture (la nécessité de cette propriété dépasse cependant cette brève présentation de la programmation génétique). Maintenant, on utilise des langages plus "classiques" comme le langage C, mais également le langage machine pour des raisons de rapidité.
Comment ça marche ?
Le principe de la programmation génétique présenté ici utilise des S-expressions LISP pour représenter des programmes répondant au problème donné.
Voici un algorithme synthétique pour la PG :
- Génération aléatoire de la population (1 individu = 1 programme)
- Évaluation du fitness de chacun des individus de la population (évaluation de l'adéquation des programmes au problème à résoudre)
- Application des opérateurs de croisement, mutation, reproduction sur la population afin de créer une nouvelle population
- Sélection des individus les mieux adaptés
- Répéter les étapes 2 et 3 un certain nombre de fois
Un exemple
Je vous propose de tenter de résoudre le problème suivant :
Retrouvez la
fonction f(x)=0,75x2-5x+3
(valeurs choisies complètement au hasard)
en connaissant 25 points de la fonction répartis dans l'intervalle [0,10]
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| f(x) | 3 | -1,25 | -4 | -5,25 | -5 | -3,25 | 0 | 4,75 | 11 | 18,75 | 28 |
La fonction que l'on cherche à approximer est représentée dans le figure suivante :
