3.2 Programmation génétique
Le terme programmation génétique peut avoir deux
différentes significations. En premier, il peut être
utilisé pour regrouper tous les algorithmes évolutionnaires dont
la population est sous forme d'une structure de données arborescente.
Dans le deuxième cas, il est utilisé pour désigner tous
les algorithmes évolutionnaires qui font évoluer des programmes,
c'est-à-dire des algorithmes évolutionnaires dont la population
est constituée de programmes informatiques.
La programmation génétique a été,
à la base, conçue pour faire évoluer, de façon
automatique, des programmes informatiques. En programmation
génétique, certaines données en entrée et leurs
résultats correspondants en sortie sont déjà connus.
L'objectif est de trouver le meilleur algorithme, au sens de la performance,
qui, étant donné un ensemble de situations de départ,
fourni les résultats appropriés.
Compte tenu de l'apport de l'arborescence de la population
qu'elle manipule, l'utilisation de la programmation génétique
s'est vite propagée vers d'autres domaines tels que l'optimisation,
l'Ingegneri électrique, le data mining, la médecine, la
robotique, etc.
3.2.1 Population
La programmation génétique fait évoluer
une population constituée d'un ensemble d'arbres. La
génération de la population initiale est une étape
décisive et compliquée. L'espace de recherche étant
infini, il est très difficile de répartir plus ou moins
équitablement la population initiale sur l'espace de recherche de telle
sorte que cet espace soit au maximum parcouru. Pour générer cette
population initiale, la première chose à faire est de limiter la
profondeur de l'arbre, limitant ainsi l'espace de recherche et assurant une
convergence de l'algorithme.
Nous devrions donc disposer d'un ensemble initial d'arbre dont
la profondeur ne dépasse pas une certaine valeur maximal d. il existe
trois façon pour créer cette population. La méthode
full crée des arbres dont la profondeur a exactement la valeur
d.
la méthode grow, elle aussi, crée des
arbres dont la longueur ne dépasse pas d, mais qui peut être
inférieur. Un choix aléatoire décide si un noeud qui vient
d'être ajouter à l'arbre sera considéré comme une
feuille ou pas. La méthode ramped half-and-half, quant à
elle, est une méthode mixte. Pour chaque arbre à créer, un
nombre r est aléatoirement choisi entre 2 et d. En suite, l'arbre sera
créé soit avec la méthode full, soit avec la
méthode half avec r comme profondeur maximale. Cette méthode est
plus préférée comme elle produit des arbres de profondeurs
différentes et assure ainsi une plus grande diversité.
FIGURE 3.2 - Exemples de création par la méthode
Full
FIGURE 3.3 - Exemples de création par la méthode
Grow
| 
