2.3 Principales familles
2.3.1 Algorithmes génétiques
Les algorithmes génétiques sont les plus
populaires des algorithmes évolutionnaires. Ils impliquent
l'évolution d'une population de vecteurs de dimension fixe
composés de caractères, généralement des bits.
L'idée des algorithmes génétiques est vaguement
inspirée des chaînes d'ADN, qui composent tout organisme vivant.
Les AG sont utilisés dans le but de découvrir une solution,
généralement numérique, résolvant un
problème donné, et ce sans avoir de connaissance à priori
sur l'espace de recherche. Seul un critère de qualité est
nécessaire pour discriminer différentes solutions. Dans la
plupart des cas, ce critère, l'adéquation, est une mesure
objective qui permet de quantifier la capacité de l'individu à
résoudre le problème donné. Le processus de recherche
s'effectue en appliquant itérativement à une population de
solutions potentielles des opérations de variation
génétique (généralement le croisement et la
mutation), et des opérations de sélection naturelle
biaisées vers les individus les plus forts. En utilisant ce processus,
la population de solutions potentielles évolue dans le temps
jusqu'à ce
qu'un certain critère d'arrêt soit atteint. Dans
un contexte d'optimisation de fonctions à paramètres
réels, une variante importante des AG consiste à
représenter les individus directement par des vecteurs de nombres
réels.
FIGURE 2.1 - Cycle de base d'un algorithme
évolutionnaire
2.3.2 Programmation génétique
La programmation génétique est un paradigme
permettant la programmation automatique d'ordinateurs par des heuristiques
basées sur les mêmes principes dévolution que les
algorithmes génétiques : des opérations de variation
génétique et des opérations de sélection naturelle.
La différence entre la programmation génétique et les
algorithmes génétique réside essentiellement dans la
représentation des individus. En effet, la programmation
génétique consiste à faire évoluer des individus
dont la structure est similaire à des programmes informatiques. La
programmation génétique représente les individus sous
forme d'arbres, c'est-à-dire des graphes orientés et sans cycle,
dans lesquels chaque noeud est associé à une opération
élémentaire relative au domaine du problème. Plusieurs
autres représentations comme des programmes linéaires et des
graphes cycliques, ont été utilisées depuis. La
programmation génétique est particulièrement
adaptée à l'évolution de structures complexes de
dimensions variables.
| 
