3.2.2 Evaluation et sélection
Comme tout algorithme évolutionnaire, lorsqu'une
solution est générée, sa qualité d'adaptation est
évaluée. La façon de ce faire est très
dépendante du problème à traiter par l'algorithme. Ainsi,
pour un problème de classification, plus le nombre d'exemple bien
classés par le programme généré est
élevé, plus sa qualité sera grande. Pour un
problème de regression, un écart entre les valeurs
générées par le programme et les valeurs exemples est
calculé; et plus cet écart est élevé, mois la
qualité du programme sera bonne. Ainsi ces valeurs sont incomparables
entre elle.
Il existe trois représentations possibles de la valeur
d'évaluation pour remédier au problème
d'incompatibilité. La Représentation standardisées
considère que la meilleure
valeur possible est 0 et que toutes les valeurs sont
positives. La représentation normalisée est similaire à la
représentation précédente, mais les valeurs sont ici
comprises entre 0 et 1. En fin, la représentation ajustée est
similaire à la représentation normalisée, où le
meilleur score possible est 1.
La programmation génétique utilise souvent la
sélection par tournoi. Avec cette méthode, un ensemble
d'individus est sélectionné au hasard pour participer à un
tournoi de la meilleure aptitude. Normalement, la sélection passe sans
remplacement, c'est-àdire que tous les individus du tournoi doivent
être différents. En programmation génétique, deux
tournois se déroulent en parallèle pour produire les deux parents
d'un croisement. Avant que les vainqueurs subissent la variation, une copie de
chacun d'eux est conservée pour remplacer le plus mauvais perdant du
tournoi. L'avantage des tournois est qu'ils peuvent être lancés
indépendamment les uns des autres, et n'exigent pas d'informations
globales sur la population.
3.2.3 Reproduction
Mutation
Les individus peuvent subir de petites variations durant le
processus de reproduction de l'algorithme évolutionnaire. Une telle
mutation est habituellement définie comme la sélection
aléatoire d'un noeud, la suppression de ce noeud ainsi que ses
descendants, et finalement leur remplacement par un autre noeud. De cette
idée, trois opérateurs peuvent être dérivés :
le remplacement aléatoire de certains noeuds, l'insertion de nouveaux
noeuds et la suppression de certains noeuds.
Recombinaison
L'opérateur de recombinaison par défaut est
l'échange de sous-arbres. Un sousarbre est aléatoirement
sélectionné de chacun des deux parents, il est en suite
enlevé et transféré à l'autre partenaire. Si des
restrictions sont imposées sur la profondeur maxi-male de l'arbre, les
opérateurs de recombinaison doivent les respecter et ne pas les
dépasser. La recombinaison part de l'idée que les
caractéristiques des bons individus vont se propager dans la population,
et en s'intégrant dans de d'autres bons individus, ils
amélioreront leurs qualité. Cependant, la recombinaison peut
avoir des effets désastreux quant à leurs aptitudes.
Permutation
La permutation est un opérateur de reproduction unaire. Un
noeud est sélectionné au hasard et déplacé de
façon aléatoire dans l'arbre (généralement en
gardant le même
FIGURE 3.4 - Différentes possibilités de
Mutation
FIGURE 3.5 - Recombinaison par échange de sous-arbres
FIGURE 3.6 - Permutation
parent), pour produire l'arbre fils. Le but principal est de
réarranger les noeuds des bons individus pour les rendre moins fragiles
à d'autres opérateurs tels que la recombinaison.
Encapsulation
L'idée de l'encapsulation est de rechercher des
sous-arbres potentiellement utiles et de les agréger en un seul noeud.
Cela permettra d'assurer leur regroupement et d'empêcher d'autres
opérateurs de reproduction de les séparer. L'encapsulation permet
en outre de faire propager le sous-arbre potentiel de façon
entière dans le reste de la population.
FIGURE 3.7 - Encapsulation
Emballage
L'emballage consiste à sélectionner au
début un noeud it de façon aléatoire dont au moins un fils
est libre, et de créer par la suite un autre noeud iii, en dehors de
l'arbre. On déplace maintenant le noeud it (et éventuellement
tous ses descendants) dans cet espace vide. En fin, on insert le noeud iii dans
la position qu'occupait le noeud it précédemment. Le but de cette
méthode est d'autoriser des modifications des noeuds qui ont une grande
probabilité d'être utiles.
FIGURE 3.8 - Permutation
Lifting
Le lifting est l'opérateur inverse de l'emballage. Il
consiste à faire monter un noeud dans l'arbre. On commence par la
sélection arbitraire d'un noeud de l'arbre. Ce noeud
va remplacer son parent qui sera supprimé avec tous ses
fils.
FIGURE 3.9 - Permutation
Sélection des noeuds
Dans la plupart des opérations de reproduction, aussi
bien dans la mutation que dans la recombinaison, certains noeuds dans l'arbre
doivent être choisis. Une bonne façon pour ce faire est
d'attribuer une probabilité de sélection équivalente
à tous les noeuds comme est le cas de la méthode de
sélection uniforme. Par conséquent, le poids de chaque noeud sera
défini comme le nombre des sous-arbres dont il est la racine (le nombre
de ses descendants). De cette façon, la probabilité qu'un noeud
soit choisi est l'inverse de son poids.
| 
