Quelques principes généraux
Les S-expressions
Dans le cas de la programmation génétique, les programmes seront représentées sous la forme de S-expression en langage LISP. Les S-expressions sont un moyen commode de représenter des programmes.
Les S-expressions LISP sont des expressions préfixées qui peuvent être mises sous la forme d'arbres. Chaque arbre est constitué de terminaux et de fonctions. Par exemple, l'expression mathématique 2x+3 se représente par l'arbre suivant :
Cet arbre est constitué de :
- terminaux : la variable x, les constantes numériques 2 et 3
- fonctions : les fonctions d'arité 2 + et *
Cette représentation arborescente permet de représenter tout type de programme informatique même si elle nécessite un minimum d'habitude. Par exemple, le programme Java suivant :
if (roblet.obstacleDevant()) robot.recule(); else robot.avance();peut tout à fait se présenter sous la forme arborescente suivante :
A quelle expression arithmétique correspond l'arbre ci-dessous ?
La première étape algorithmique du processus de programmation génétique consiste à générer une population d'individus ( un individu = un arbre = un programme). Une population est généralement constituée de plusieurs milliers de programmes qui co-existent.
L'étape suivante consistera à évaluer la performance de chacun des programmes générés aléatoirement afin de leur donner une valeur de fitness.
Chaque arbre généré est susceptible d'être croisé avec d'autres arbres afin de générer d'autres possibilités.
La supposition très importante de la programmation
génétique
est la suivante : des S-expressions
de petite
taille
et de fitness élevé vont se recombiner afin de
donner des
S-expressions plus complexes et de fitness encore plus
élevé.