La Programmation Génétique
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 les 11 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 :
Continue
