IV.5.3.3 Mutation
La mutation est exécutée seulement sur une
seule chaîne. Elle représente la modification
aléatoire
et occasionnelle de faible probabilité de la
valeur d'un caractère de la chaîne, pour un codage binaire cela
revient à changer un 1 en 0 et vice versa (Figure 26). Cet
opérateur introduit de la diversité dans le processus de
recherche des solutions et peut aider l'AG à ne pas stagner dans un
optimum local.
Figure 26 Représentation d'une mutation de bits
dans une chaîne
Une autre solution que le croisement pour créer
de nouveaux individus est de modifier ceux déjà existants. Une
fois de plus, le hasard va nous être d'une grande utilité. Il peut
s'avérer efficace de modifier aléatoirement quelques individus de
notre population en modifiant un gène ou un autre. Rien ne nous dit que
l'individu muté sera meilleur ou moins bon, mais il apportera des
possibilités supplémentaires qui pourraient bien être
utiles pour la création de bonnes solutions. De même que pour les
croisements, il n'est pas recommandé de faire muter tous les individus.
Il est possible de faire muter un individu de la manière qu'il vous
plaira. Une seule contrainte : l'individu muté doit être de la
forme d'une solution potentielle.
Généralement, on ne modifie qu'un
gène pour passer d'une solution à une autre solution de forme
similaire mais qui peut avoir une évaluation totalement
différente.
Problème de l'informaticien en
vacances
La méthode de mutation que je vous propose
consiste en une permutation de deux villes. Nous sommes certains que les
individus mutés auront toujours la forme d'une solution potentielle car
nous ne changeons que l'ordre des villes.
Par exemple, {A,B,C,D,E,F,G,H,I,J} pourra être
muté en {A,B,H,D,E,F,G,C,I,J}
91
IV.5.4 L'insertion des nouveaux individus dans la
population
Une fois que nous avons créé de nouveaux
individus que ce soit par croisement ou par mutation,
il nous faut sélectionner ceux qui vont
continuer à participer à l'amélioration de notre
population. Une fois encore, libre au programmeur de choisir ceux qu'il
souhaite conserver. Il est possible de refaire une étape
d'évaluation des individus nouvellement créés. De
même qu'il est possible de conserver tous les nouveaux individus en plus
de notre population.
Il n'est toutefois pas recommandé de ne
conserver que les nouveaux individus et d'oublier la population de travail. En
effet, rien ne nous dit que les nouveaux individus sont meilleurs que les
individus de départ.
Une méthode relativement efficace consiste
à insérer les nouveaux individus dans la population, à
trier cette population selon l'évaluation de ses membres, et à ne
conserver que les N meilleurs individus.
| 
