B. Itération d'un algorithme
génétique
Sur base de la population courante, diverses opérateurs
vont être appliqués successivement à des sous-ensembles
d'individus, appelés des parents, pour générer de nouveau
individus appelés enfants.
B.1. Opérateur de sélection
Il s'agit des pairs d'individus qui sont
sélectionnées au sein de la population courante, une telle paire
sera noté P1 et P2. Il convient donc de définir
un mécanisme de sélection de paires de parents. Cet
opérateur de sélection est généralement
aléatoire mais doit néanmoins d'autant plus favoriser la
sélection d'un individu que sa fonction fitness est meilleure. [13]
Plusieurs méthodes existent et sont, généralement,
basées sur la théorie de Darwin. Nous présenterons les
deux plus connues:
· La roulette (roulette Wheel sélection)
: [13] Cette méthode exploite la métaphore d'une
roulette de casino. La roue est divisée en autant de secteurs que
d'individus dans la population. La taille de ces secteurs est proportionnelle
à l'adaptation de chaque individu (une probabilité pi).
Un nombre aléatoire r E [0,1] désigne alors
l'individu i* sélectionné par la formule :
? ? ???
????
0 < r < Pi*
i=1 pi, si i* = 1.
Pi*-1
i=1 pi < r < Pi*
i=1pi, si non.
75
4.5. LES ALGORITHMES GÉNÉTIQUES
FIGURE 4.2 - Sélection par roulette
· Sélection par tournoi(tournatment
selection) : [13] Plusieurs individus (classiquement deux) sont
d'abord choisis totalement aléatoirement dans la population. Ils se
confrontent alors sur base de leur valeur fitness et le meilleur est
sélectionné.
FIGURE 4.3 - Sélection par tournoi (entre deux
individus)
| 
