Equipe ORCHIDS

ALGORITHMES GENETIQUES
Illustration de l'opérateur de croisement de permutation 2X
EXPLICATIONS

C'est un opérateur génétique de croisement en deux points.
Nous prenons ici des permutations de 10 entiers, qui représentent l'ordre de 10 objets (secteurs, tâches...) numérotés 1, 2, 3, ... , 10.
Le premier parent (que l'on peut appeler le père) correspond, par exemple, à l'ordre 1, 4, 10, 9, 8, 5, 6, 3, 2, 7.
Le deuxième parent (que l'on peut appeler la mère) correspond, par exemple, à l'ordre 1, 2, 10, 8, 9, 6, 5, 4, 3, 7.

DESCRIPTION DU CROISEMENT 2X SUR L'EXEMPLE.

1) L'opérateur de croisement 2X choisit de manière aléatoire deux points de croisement,
par exemple entre le 3 ème et le 4 ème gène et entre le 6 ème et le 7 ème gène. L'opérateur de croisement 2X peut créer en fait quatre enfants (dont on peut garder les deux meilleurs si on n'en souhaite que deux).

2) Pour les enfants 1 et 2, on recopie le milieu du parent 1 (4 gènes) au milieu du fils 1 et le milieu du parent 2 (4 gènes) au milieu du fils 2.

FILS 1 - - - 9 8 5 - - - -

(rappel : parent 1 = 1, 4, 10, 9, 8, 5, 6, 3, 2, 7)

FILS 2 - - - 8 9 6 - - - -

(rappel : parent 2 = 1, 2, 10, 8, 9, 6, 5, 4, 3, 7)

L'opérateur de croisement 2X complète le fils 1, en conservant au début les gènes qui étaient au début du père et en les plaçant dans l'ordre de la mère et en conservant à la fin les gènes qui étaient à la fin du père et en les plaçant dans l'ordre de la mère.

De manière analogue, l'opérateur de croisement 2X complète le fils 2, en conservant au début les gènes qui étaient au début de la mère et en les plaçant dans l'ordre du père et en conservant à la fin les gènes qui étaient à la fin de la mère et en les plaçant dans l'ordre du père.

FILS 1 1 10 4 9 8 5 2 6 3 7

(rappel : parent 2 = 1, 2, 10, 8, 9, 6, 5, 4, 3, 7)

FILS 2 1 10 2 8 9 6 4 5 3 7

(rappel : parent 1 = 1, 4, 10, 9, 8, 5, 6, 3, 2, 7)

3) Pour les enfants 3 et 4, par rapport à enfant 1 et enfant 2, on échange la position des parties copiées d'un parent et des parties réordonnées selon l'autre parent.

La nouvelle recopie donne :

FILS 3 1 4 10 - - - 6 3 2 7

(rappel : parent 1 = 1, 4, 10, 9, 8, 5, 6, 3, 2, 7)

FILS 4 1 2 10 - - - 5 4 3 7

(rappel : parent 2 = 1, 2, 10, 8, 9, 6, 5, 4, 3, 7

Le réordonnancement des parties centrales donne :

FILS 3 1 4 10 8 9 5 6 3 2 7

(rappel : parent 2 = 1, 2, 10, 8, 9, 6, 5, 4, 3, 7)

FILS 4 1 2 10 9 8 6 5 4 3 7

(rappel : parent 1 = 1, 4, 10, 9, 8, 5, 6, 3, 2, 7)