B.2. Opérateur de croisement
Un opérateur de croisement (crossover) consiste
à créer de nouveaux individus -des enfants- en échangeant
des caractères -des gènes- entre les deux parents. La zone de
croisement est généralement choisie aléatoirement dans les
chromosomes. Toutefois l'opérateur
4.5. LES ALGORITHMES GÉNÉTIQUES
de croisement n'est pas systématiquement
appliqué à chaque paire de parents, mais avec une
probabilité de croisement pc (classiquement =
0.9, nous suivrons ici aussi le schéma classique où deux
enfants (notés E1 et E2) sont créés par
le croisement. [13]
76
FIGURE 4.4 - Croisement en un
point
B.3. Opérateur de mutation
Pour des raisons de diversification, il est bon de temps en
temps de modifier très légèrement un enfant
créé. C'est le rôle de l'opérateur de mutation qui
est appliqué à un enfant avec une petite probabilité
pm (classiquement= 0.01). [13]
FIGURE 4.5 - La mutation
C. Critère d'arrêt
Les critères les plus utilisés sont les suivants
:
· Arrêt de l'algorithme après un certain
nombre de générations, fixé au départ; c'est ce que
l'on est tenté de faire lorsque l'on doit trouver une solution dans un
temps limité.
· L'algorithme peut être arrêté
lorsque la population n'évolue plus ou plus suffisamment rapidement,
c.-à-d. les meilleurs individus ne s'améliorent plus depuis un
certain nombre de générations. [13]
77
4.5. LES ALGORITHMES GÉNÉTIQUES
Paramètres internes de l'algorithme
génétique
Les algorithmes génétiques possèdent des
paramètres internes qui doivent être choisis avec les
considérations suivantes :
· Taille de la population N : Elle doit
être judicieusement choisie en fonction de la taille du
problème.
· Probabilité de croisement :
Plus le taux de croisement est élevé, plus il y aura de nouvelles
structures qui apparaissent dans la population.
· Probabilité de mutation: la
probabilité de mutation est généralement inférieur
à 0.01, mais il n'est pas rare de voir dans d'autres applications un
taux plus important, par exemple dans les problèmes d'ordonnancement.
4.6. SCHÉMA DES MÉTHODES APPROCHÉES
| 
