IV.5.3.1.4 L'élitisme
Cette méthode de sélection permet de mettre
en avant les meilleurs individus de la population. Ce
sont donc les individus les plus prometteurs qui vont
participer à l'amélioration de notre population. Cette
méthode a l'avantage de permettre une convergence (plus) rapide des
solutions, mais au détriment de la diversité des individus. On
prend en effet le risque d'écarter des individus de piètre
qualité, mais qui auraient pu apporter de quoi créer de
très bonnes solutions dans les générations suivantes.
Cette méthode est extrêmement sensible à la présence
d'optimas locaux, c'est à dire à la présence de solutions
paraissant optimales tant que l'on ne s'en éloigne pas trop - le
véritable optimum pouvant alors être situé dans une toute
autre partie du domaine de recherche.
Une autre possibilité relevant aussi du domaine
de l'élitisme, pour s'assurer que les meilleurs individus feront
effectivement partie de la prochaine génération, est tout
simplement de les sauvegarder pour pouvoir les rajouter à coup sûr
dans la population suivante .
Le nombre d'individus que vous allez
sélectionner en vue d'un croisement ou d'une mutation est encore une
fois laissé à l'appréciation du programmeur. Pensez juste
qu'il n'est pas nécessaire (et pas recommandé non plus) de
modifier tous les individus d'une population.
Les méthodes de sélection permettent de
déterminer quels individus nous allons croiser. Reste maintenant
à définir comment nous allons les croiser.
IV.5.3.2 Croisement
On distingue deux types de croisements : croisement mono
point et multi points
IV.5.3.2.1 croisement mono point
Le croisement mono point permet de créer de
nouvelles chaînes en échangeant de l'information entre deux
chaînes (Figure 24). Le croisement s'effectue en deux étapes.
D'abord les nouveaux éléments produits par la reproduction sont
appariés, ensuite chaque paire de chaînes subit un croisement
comme suit : un entier k représentant une
position sur la chaîne est choisi aléatoirement entre 1 et la
longueur de chaîne moins un . Deux nouvelles chaînes sont
créées en échangeant tous les caractères compris
entre les positions k +1 et inclusivement. L'exemple
suivant (Figure 24) montre deux chaînes (A1 et A2) de longueur 5
appartenant à la population initiale. Les deux nouvelles chaînes
(A3 et A4) appartenant à la nouvelle population sont obtenues par
croisement à la position k = 4 :
88
Figure 24 exemple de croisement mono point.
IV.5.3.2.2 Croisements multi-points
Il faut découper en N morceaux (2 ou 3 peuvent
suffire) chacun des individus choisis, puis il faut prendre un gène de
chaque individu pour créer un nouvel individu.
Notez qu'il est possible de créer ainsi plusieurs
individus : si un gène d'un individu ne pas à la création
d'un individu, il peut servir à la création d'un
autre.
Donc en prenant X individus à croiser, vous
pouvez potentiellement obtenir X nouveaux individus. Mais rien ne vous
empêche d'utiliser plusieurs fois certains gènes, pour obtenir
plus de X nouveaux individus.
Il n'est pas nécessaire et surtout pas
recommandé de croiser tous les individus d'une population, car rien ne
nous dit si le résultat d'un croisement sera meilleur ou moins bon que
les individus parents.
89
|
Individus parents
|
|
Gène1
|
Gène2
|
Gène3
|
Gène4
|
|
Gène1
|
Gène2
|
Gène3
|
Gène4
|
|
Gène1
|
Gène2
|
Gène3
|
Gène4
|
|
|
Individus enfants
|
|
Gène1
|
Gène2
|
Gène3
|
Gène4
|
|
Gène1
|
Gène2
|
Gène3
|
Gène4
|
|
Gène1
|
Gène2
|
Gène3
|
Gène4
|
Figure 25 : croisement multi-point
Exemple
Dans notre exemple, nous ne pouvons pas juste prendre
des morceaux des individus parents pour créer les individus enfants. Il
faut que les nouveaux individus créés conservent la forme d'une
solution potentielle.
Ils doivent donc posséder chacune des villes une
seule fois.
La méthode de croisement que je propose pour ce
problème est la suivante : on commence à faire un croisement
"simple" entre deux individus, puis on corrige les individus
créés pour qu'ils aient la forme d'une solution.
Par exemple, si nous souhaitons croiser
{A,B,C,D,E,F,G,H,I,J} avec {D,A,F,J,C,E,G,H,B,I}, nous pouvons décider
que la première moitié du premier parent deviendra la
première moitié du premier enfant, et que la seconde
moitié du premier parent deviendra la seconde moitié du
deuxième enfant , Et inversement pour le second parent.
Nous obtiendrions ainsi les enfants {A,B,C,D,E,E,G,H,B,I}
et {D,A,F,J,C,F,G,H,I,J}.
On s'aperçoit tout de suite du problème
posé, certaines villes sont visitées 2 fois et d'autres ne le
sont pas. Je propose donc de supprimer les doublons et de les remplacer par les
villes non visitées.
Ainsi le premier enfant {A,B,C,D,E,E,G,H,B,I} serait
remplacé par {A,B,C,D,E,F,G,H,J,I} ou par {A,B,C,D,E,J,G,H,F,I} De
même le deuxième enfant passerait de {D,A,F,J,C,F,G,H,I,J}
à {D,A,F,J,C,B,G,H,I,E} ou à {D,A,F,J,C,E,G,H,I,B}
90
| 
