PROGRAMMATION GÉNÉTIQUE
Principe
Algorithmes génétiques et programmation génétique
Les algorithmes génétiques sont une méthode d´optimisation
de type évolutionniste consistant à coder des solutions
potentielles d´un problème en chaînes de longueur fixe. Une
population de telles chaînes est évaluée par une fonction
d´adaptation mesurant la plus ou moins grande capacité de ces
solutions à résoudre le problème. À chaque génération des individus
sont sélectionnés aléatoirement avec une probabilité proportionnelle
à leur valeur d´adaptation, cette opération de reproduction
favorise les individus les mieux adaptés. De nouvelles chaînes sont
créées par croisement de paires d´individus sélectionnés ce qui
a pour effet d´enrichir leur patrimoine génétique. Des mutations
aléatoires introduisent des erreurs autorisant de nouvelles
potentialités.
Cette méthode s´est montrée étonamment efficace dans la recherche
de l´extremum global de certains problèmes d´optimisation, en particulier
ceux qui sont hautement non linéaires ou ceux qui présentent des
interactions couplées compliquées de paramètres.
Cependant la complexité d´une solution optimale à un problème
donné n´est pas connue à l´avance. En ne fixant pas à priori la longueur
des chaînes, cette complexité peut évoluer au cours de la reproduction.
Plus précisément, la programmation génétique opère sur
des chaînes de longueurs variables représentant des programmes
plutôt qu´un codage par caractères. La population initiale est un
ensemble de programmes censés résoudre le problème posé, et la
fonction d´adaptation mesure la plus ou moins grande capacité de
ces programmes à trouver de bonnes solutions.
Le langage LISP a la particularité de représenter,
aussi bien le code que les structures de données, sous formes d´arbres.
La programmation génétique consiste à faire évoluer des populations
de tels arbres, elle est donc facilement implémentable en LISP. Cependant
rien n´empêche d´utiliser un autre langage (C ou C++ par exemple).
S_expressions et arbres
Les objets de base manipulés par le LISP sont les atomes
et les listes. Les atomes peuvent être soit des symboles,
soit des nombres, une liste est une suite ordonnée d´objets
encadrés par des parenthèses, par exemple:
(ceci est une liste)
Une forme est une liste particulière
dont le premier terme est le nom d´une fonction et
les termes suivants sont les paramètres d´appel de cette fonction.
Par exemple:
(+ 3 5) retourne la valeur de la fonction PLUS appliquée aux
deux nombres 3 et 5, c´est à dire 8.
Un programme LISP n´est rien d´autre qu´une forme.
Une forme, ou S-expression se représente par un arbre,
exemples:
Figure 5-1: S-expressions et arbres associés.
Dans un tel arbre on distingue deux types de noeuds:
1) Les feuilles, ou noeuds terminaux qui sont
soit des constantes, soit des variables, soit encore des fonctions
sans arguments.
2) Les autres noeuds sont toujours des fonctions ayant au moins
un argument.
Populations de programmes
Population initiale
Une population initiale de programmes est générée aléatoirement
sous la forme d´arbres construits de la façon suivante:
On suppose donnés:
1) Un ensemble de fonctions {fi(arg1,arg2,...,argni)}0 <= i <= n
2) Un ensemble d´éléments terminaux {t1,t2,...,tm)}0 <= i <= m
On définit une construction récursive de l´arbre à partir de
la racine en choisissant d´abord aléatoirement une fonction, si
celle-ci
prend n arguments, il y aura n branches partant de la racine.
Pour chaque branche recommencer récursivement l´opération.
La construction cesse dès qu´est tirée une feuille, ou
dès que la profondeur de récursion atteint une limite donnée,
auquel cas le choix est restreint à une feuille.
Exemple:
L´ensemble des fonctions est: {+(arg1,arg2),*(arg1,arg2)}
L´ensemble des éléments terminaux est {3,x,y}
Le premier tirage aléatoire d´une fonction donne ´+´ pour la racine,
ayant deux arguments.
Le choix pour la première branche est la constante 3 qui, n´ayant
pas d´argument, termine le développement de cette branche.
Le choix pour la deuxième branche est la fonction ´*´ ayant
deux arguments.
Le choix pour la première branche est la variable x qui, n´ayant
pas d´argument, termine le développement de cette branche.
Le choix pour la deuxième branche est la variable y qui, n´ayant
pas d´argument, termine le développement de cette branche.
Figure 5-2: Construction d´un arbre aléatoire.
C´est la méthode de croissance [KOZA 1994].
Dans la méthode dite complète tous les noeuds d´ordre maximum
sont terminaux, tous les autres étant des fonctions.
Une autre méthode intermédiaire consiste à générer le même
nombre d´arbres de profondeurs comprises entre 2 et un maximum n, et,
pour chaque profondeur, la moitié des arbres sont créés par la méthode
de croissance et l´autre moitié par la méthode complète: Cette
méthode assure la plus grande variété possible de formes et de tailles
des arbres et améliore la convergence de l´algorithme.
Koza propose aussi d´utiliser, outre les constantes et les
variables, un troisième type d´éléments terminaux: Les constantes
aléatoires éphémères dont la valeur est tirée aléatoirement.
Mesure d´adaptation
La fonction d´adaptation, appliquée à un individu de la population,
retourne une valeurs appelée adaptation brute fb de cet individu,
le problème consiste à minimiser cette fonction.
L´adaptation standardisée fs est une mesure d´adaptation telle
que plus d´individus bien adaptés ont une plus petite adaptation
standardisée que les individus moins bien adaptés. Un individu parfaitement
optimal doit avoir une adaptation normalisée nulle. L´adaptation brute
est parfois égale à l´adaptation standardisée, mais il peut être
nécessaire de définir une transformation de l´adaptation brute
en adaptation standardisée afin de satisfaire la définition ci-dessus.
L´adaptation ajustée fa est définie par rapport à
l´adaptation standardisée:
fa = 1 / (1 + fs)
L´adaptation normalisée fn est définie par:
Reproduction
Des individus sont
sélectionnés avec une probabilité proportionnelle
à leur adaptation normalisée.
Dans l´adaptation proportionnelle le meilleur remplace le pire
(sélectionné par l´inverse de la fonction d´adaptation).
Dans la sélection compétitive les programmes sont
tirés aléatoirement par paquets (par exemple par groupes de 5),
dans chaque paquet le meilleur remplace le pire.
Les individus
sélectionnés sont ensuite appariés puis
croisés, permutés, encapsulés, contractés et
éventuellement mutés.
Croisement
Un noeud est tiré aléatoirement sur chacun des arbres d´une paire
sélectionnée, puis les sous arbres ayant ce noeud pour racine
sont échangés. Exemple:
Figure 5-3: Programmes sélectionnés
Figure 5-4: Programmes croisés
Permutation
Un noeud de fonction est tiré aléatoirement et l´ordre des
arguments de la fonction sont permutés aléatoirement. Par exemple
si f(a1,a2,a3) est un tel noeud, il peut devenir:
f(a1,a2,a3) ou f(a1,a3,a2) ou f(a2,a1,a3) ou f(a2,a3,a1)
ou f(a3,a1,a2) ou f(a3,a2,a1).
Encapsulation
Un noeud est tiré aléatoirement et le sous arbre ayant ce noeud
pour racine est remplacé par une fonction sans argument. Lorsque
celle-ci est appelée, le sous arbre est évalué. Le but de
l´encapsulation est de conserver des sous arbres utiles lors de
l´opération de croisement.
Contraction
Un noeud est tiré aléatoirement et prend la place de
son père. Cet opérateur a pour but de réduire la taille
des arbres qui peut augmenter considérablement lors de
l´évolution de la population.
Mutation
Un noeud est tiré aléatoirement sur un arbre, le sous arbre
ayant ce noeud pour racine est remplacé par un sous arbre
généré aléatoirement. Exemple:
Figure 5-5: Mutation d´un programme