Divers codages des problèmes et opérateurs génétiques associés aux codages
Choix des allèles ou du codage
Historiquement, les allèles prennent la valeur 0 ou 1, c'est-à-dire que l'on utilise un codage binaire.
Si on utilise des valeurs qui ont une signification pour le problème considéré, par exemple des lettres ou des chiffres, on parle alors de codage symbolique.
Mais le codage peut être plus complexe, par exemple, des matrices ayant une structure particulière, des ordres ou permutations, des ensembles de listes ou des arborescences.
Définition : Codage direct et indirect
Dans le cas d'un codage direct : le chromosome contient la description complète d'une solution.
Dans le cas d'un codage indirect : le chromosome contient des "paramètres" qui permettront de construire une solution en utilisant un générateur.
Dans le cas du codage indirect, les gènes fournissent le génotype.
L'application du générateur fournit un phénotype.
Remarque :
Dans le cas du codage direct, comme le chromosome contient la description d'une solution, il y a correspondance biunivoque entre l'ensemble des solutions et l'ensemble des chromosomes.
Dans le cas d'un codage indirect, cette correspondance biunivoque n'est en général plus vérifiée, car le générateur peut donner la même solution à partir de deux chromosomes différents et en outre, on n'est pas certain que toutes les solutions pourront être obtenues à partir du générateur appliqué à toutes les valeurs possibles pour les codages.
Les opérateurs sur le codage binaire
Le codage binaire est le premier qui a été proposé.
Les opérateurs de croisement et de mutation sur le codage binaire sont les plus simples et les plus anciens.
Exemple de croisement binaire
Un point de croisement est choisi, par exemple de manière aléatoire.
Il est matérialisé sur l'exemple par une barre verticale rose.
Les gènes du père qui se trouvent avant le point de croisement (coloriés en rose) sont placés au début du fils.
Les gènes de la mère qui se trouvent avant le point de croisement (coloriés en vert) sont placés au début de la fille.
Les gènes du père qui se trouvent après le point de croisement (coloriés en violet) sont placés à la fin de la fille.
Les gènes de la mère qui se trouvent après le point de croisement (coloriés en gris) sont placés à la fin du fils.
Le résultat du croisement dépend du point de croisement
Dans cette animation, on conserve toujours le même chromosome comme père et le même chromosome comme mère.
Lorsque l'on clique sur le bouton "Appliquer le croisement binaire", on change la position du point de croisement.
On obtient ainsi le résultat du croisement binaire selon le point de croisement choisi (qui doit laisser une position au moins à gauche et une position au moins à droite).
Illustration générale du croisement binaire
Dans cette animation, on peut générer de manière aléatoire (éventuellement répétée) le chromosome père et le chromosome mère.
On peut également appliquer à la version courante du chromosome père et du chromosome mère le croisement binaire.
Le point de croisement change d'une position à chaque appel de l'opérateur de croisement.
Exemple de mutation binaire
Un gène est choisi de manière aléatoire.
Si sa valeur est à 1, il prend la valeur 0 et si sa valeur est à 0, il prend la valeur 1.
Les opérateurs sur le codage symbolique
La seule différence est que les cases contiennent des valeurs quelconques de type chaînes.
La liste des chaînes possibles peut être restreinte à un sous-ensemble de valeurs fournies a priori lorsque l'on code les solutions du problème.
Une même chaîne peut apparaître plusieurs fois dans le même chromosome.
Exemple d'un croisement sur codage symbolique quelconque
Un point de croisement est choisi, par exemple de manière aléatoire.
Il est matérialisé sur l'exemple par une barre verticale rose.
Les gènes du parent 1 qui se trouvent avant le point de croisement (coloriés en rose) sont placés au début de l'enfant 1.
Les gènes du parent 2 qui se trouvent avant le point de croisement (coloriés en vert) sont placés au début de l'enfant 2.
Les gènes du parent 1 qui se trouvent après le point de croisement (coloriés en violet) sont placés à la fin de l'enfant 2.
Les gènes du parent 2 qui se trouvent après le point de croisement (coloriés en gris) sont placés à la fin de l'enfant 1.
Exemple d'une mutation sur codage symbolique quelconque
Un gène est choisi de manière aléatoire.
Il prend une autre valeur symbolique autorisée, par exemple, de manière aléatoire.
Les opérateurs sur les codages de type ordre ou permutation
Dans le codage de permutation, si le chromosome contient n gènes, l'ensemble des gènes contient une et une seule fois toutes les valeurs entières de 1 à n.
Il y a énormément de problèmes concrets qui peuvent être codés par des permutations.
Par exemple,
le problème du voyageur de commerce où le voyageur de commerce doit passer une fois et une seule par toutes les villes qu'il doit visiter,
tous les problèmes d'ordonnancement à une machine où toutes les pièces doivent passer une seule fois sur la machine,
les problèmes d'ordonnancement à deux machines où toutes les pièces passent dans le même ordre sur les deux machines,
les problèmes d'ordonnancement de projets de type disjonctifs où il faut décider dans quel ordre les opérations passent sur une ressource qui existe en un seul exemplaire,
etc.
Grandes diversités des opérateurs génétiques pour les codages de permutation
En raison de leur intérêt concert, de très nombreux opérateurs génétiques ont été proposés pour les codages de permutation.
Nous n'en donnons que quelques uns comme exemple.
Face à un problème concret à résoudre de manière efficace,
on peut soit tester plusieurs opérateurs génétiques et choisir celui qui en moyenne donne les meilleurs résultats sur un échantillon significatif de données numériques correspondant au problème à résoudre,
soit utiliser une technique élaborée d'apprentissage qui utilise toute une panoplie d'opérateurs génétiques et cherche à utiliser avec une plus forte probabilité ceux qui donnent de meilleurs résultats.
Attention :
Les opérateurs génétiques pour les codages symboliques quelconques ne conviennent pas pour les codages de permutation, car ils autorisent de répéter plusieurs fois la même valeur pour les allèles à l'intérieur du chromosome.
Exemple de croisement de permutation : le croisement 1X
Un point de croisement est choisi, par exemple de manière aléatoire.
Il est matérialisé sur l'exemple par une barre verticale rose.
Les gènes du père qui se trouvent avant le point de croisement (coloriés en rose) sont placés au début du fils 1.
Les gènes de la mère qui se trouvent avant le point de croisement (coloriés en vert) sont placés au début du fils 2.
Les gènes du père qui se trouvent après le point de croisement (coloriés en violet) sont placés à la fin du fils 3.
Les gènes de la mère qui se trouvent après le point de croisement (coloriés en gris) sont placés à la fin du fils 4.
Le fils 1 est complété à la fin par les gènes manquant en les triant dans l'ordre de la mère.
Le fils 2 est complété à la fin par les gènes manquant en les triant dans l'ordre du père.
Le fils 3 est complété au début par les gènes manquant en les triant dans l'ordre de la mère.
Le fils 4 est complété au début par les gènes manquant en les triant dans l'ordre du père.
(les parties triées dans l'ordre de l'autre chromosome sont coloriées en jaune)
Remarque :
Plusieurs enfants peuvent être identiques, dans ce cas, on ne conserve qu'un seul des enfants identiques.
Des enfants peuvent être identiques au père ou à la mère.
Le résultat dépend du point de croisement
Dans cette animation, on conserve toujours le même chromosome comme père et le même chromosome comme mère.
Lorsque l'on clique sur le bouton "Appliquer le croisement 1X", on change la position du point de croisement.
On obtient ainsi le résultat du croisement 1X selon le point de croisement choisi (qui doit laisser deux positions au moins à gauche et deux positions au moins à droite).
Illustration générale du croisement 1X
Dans cette animation, on peut générer de manière aléatoire (éventuellement répétée) le chromosome père et le chromosome mère.
On peut également appliquer à la version courante du chromosome père et du chromosome mère le croisement 1X.
Le point de croisement change d'une position à chaque appel de l'opérateur de croisement.
Autre exemple de croisement d'ordres : le croisement LOX
1) l'opérateur de croisement LOX 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.
2) l'opérateur de croisement LOX recopie le milieu du parent 1 (3 gènes) au milieu du fils 1 (colorié en rose)
et le milieu du parent 2 (3 gènes) au milieu du fils 2 (colorié en vert).
3) l'opérateur de croisement LOX complète le fils 1 avec les gènes manquant en les plaçant depuis le début dans les cases non remplies dans l'ordre de la mère et le fils 2 avec les gènes manquant en les plaçant depuis le début dans les cases non remplies dans l'ordre du père.
Illustration générale du croisement LOX
Dans cette animation, on peut générer de manière aléatoire (éventuellement répétée) le chromosome père et le chromosome mère.
On peut également appliquer à la version courante du chromosome père et du chromosome mère le croisement LOX.
Les points de croisement changent à chaque appel de l'opérateur de croisement.
Premier exemple de mutation sur le codage de permutation
Une position p est choisie de manière aléatoire entre 1 et n-1.
La valeur du gène situé à la position p est échangée avec la valeur du gène situé à la position p+1.
Deuxième exemple de mutation sur le codage de permutation
Deux positions p et p' sont choisies de manière aléatoire entre 1 et n.
La valeur du gène situé à la postion p est échangée avec la valeur du gène situé à la position p'.
Troisième exemple de mutation sur le codage de permutation
Deux positions p et p' sont choisie de manière aléatoire entre 1 et n.
Les valeurs des gènes entre les position p+1 et p' sont recopiées dans position p à p'-1.
La valeur du gène précédemment en position p est déplacé en position p' qui est devenue libre.
Quatrième exemple de mutation sur le codage de permutation
Deux positions p et p' sont choisies de manière aléatoire.
Les valeurs des gènes des positions p à p' sont copiées dans les positions p' à p.
La partie de la permutation entre les deux positions est donc inversée.
