(mise a jour le 21.02.2007)

Bonjour,
j'ouvre ce post afin de référencer tous les types de crossOver (appelés également crossing over, hybridation, opérateurs génétiques) utiliser pour les algo génétiques. (si vous pouviez me dire quel terme vous semble le plus utilisé/approprié)
Pour ceux qui veulent savoir ce qu'est un algo génétique, je les redirige sur wiki.
J'ai moi même commencer à faire une explication sur les algo génétiques, mais ce n'est pas l'intéret de ce post (et je n'ai hélas pas encore mit ma version sur le net).
J'en ai déjà quelques un, mais j'avouerais ne pas avoir trouver grand chose sur le net.

(je vais tenter de compléter les différents cross-over avec leurs explications au fur et à mesure)

Merci d'avance pour votre aide.  

NB : les cross-over suivit d'un (OK) sont ceux que j'ai déjà créés, implémentés et testés et qui fonctionnent.

Les crossing over :
Le principe est d'utiliser (croiser) plusieurs parents (souvent 2, dans ce cas on parlera du pere et de la mere) pour créer un ou plusieurs descendants.
Il faut donc sousligner un point important :
Chaque individu (parent, enfant) possède n gènes au sein d'un même chromosome.
Ces gènes sont uniques et présents dans chaque individu.
D'un point de vue mathémtiques, pour 2 individus p1 et p2:
p1 = x1 x2 x3 ... xn
p2 = y1 y2 y3 ... yn
avec : qqsoit i,j € [1,n], il existe xi = yj.
et qqsoit i,j € [1,n], si i!=j alors xi!=xj.

->je suis preneur de toutes info,
donc n'héziter pas à poster des liens vers des explications des différents crossing over, pour le moment, j'ai juste ceux donnés par mon maître de stage, donc un seul support, c'est légé comme ressource.
Et franchement, je cherche sur le net, mais je crois que je suis pas doué pour ça.
->n'héziter pas à me dire si vous trouver mes explications claires ou au contraire incompréhensibles, car ce que vous voyez là me servira de base pour mon rapport (en tout cas sur cette partie là).

• 00 - Order based / Ordre partiel  (OK, créé par mon maitre de stage)

Explication:

Cet opérateur, proposé par Syswerda [Syswerda 1989] génère les enfants en 3 étapes :

-1- Choisir aléatoirement des locus dans le parent2 (mere). Le nombre de locus est choisi aléatoirement.
-2- Supprimer du Parent1 (pere) les valeurs sélectionnées dans le Parent2 et recopier le résultat dans l'Enfant1 (enf).
-3- Compléter les gènes vides de l'Enfant1 avec les allèles sélectionnés du Parent2 dans leur ordre d'apparition.

NB : dans notre cas, je crée uniquement 1 enfant.
Pour en créer un deuxième avec les même parents, je préfère relancer l'opération en inversant les parents (pere devient mere et mere devient pere) ceci afin d'éviter la création de ce que j'apellerais des jumeaux (cad 2 enfants en même temps).
Bonne ou mauvaise idée?

Implémentation :
pere :  1 2 3 4 5 6 7 8 9
mere : 4 1 2 8 7 6 9 3 5
enf   :  _ _ _ _ _ _ _ _ _

-1- Generer un locus
locus : 0 1 0 1 0 1 0 0 1

-2.1- recopier le pere dans enf
enf : 1 2 3 4 5 6 7 8 9

-2.2- supprimer dans enf les valeurs selectionnées (locus) dans mere
valeurs selectionnées dans mere : _ 1 _ 8 _ 6 _ _ 5
enf : _ 2 3 4 _ _ 7 _ 9

-3- completer enf avec les valeurs sélectionnées dans mere dans leur ordre d'apparition.
enf : 1 2 3 4 8 6 7 5 9

Analyse mathématiques :

-1- Si locus == 1 ... 1  
alors enfant == mere

-2- si locus == 0 ... 0
alors enfant == pere

-3- Si les allèles enlevés dans Pere sont dans le même ordre relatif que ceux de Mere,
alors pas de changement, l'enfant == pere.

-4- par extension : moins il y a de 1 dans le locus, (donc plus il y a de 0), plus il y a de chance de se retrouver dans le cas -3-

Question : es-ce possible de vérifier tout ça avec des zolis calcules? (cad proba que l'enfant reste le mm que pere ...)

• 01 - Position Based (OK)

Explication:
Proposé par Syswerda [Syswerda 1989], cet opérateur représente une variante de l'opérateur "order based".
Il génère les enfants en 4 étapes :
-1- Choisir aléatoirement des locus dans les 2 parents. Le nombre de locus étant choisi aléatoirement.
-2- Recopier les allèles des locus sélectionnés du Parent2 dans l'Enfant1 (et du Parent1 dans l'Enfant2).
-3- Retirer du Parent1 les allèles sélectionnés du Parent2 cad Parent1 - Parent2 (A), (puis retirer du Parent2 les allèles sélectionnés du Parent1 (A') ).
-4- Remplir les gènes vides de l'Enfant1 avec les allèles obtenus par (A) dans l'ordre de leur apparition (et Enfant2 avec (A') ).

NB : est-ce assez clair pour vous? ou dois-je mettre un exemple? tout en sacahnt que je l'illustredans l'implémentation?

Implémentation:
NB : idem que pour oder base, j'ai crée qu'un seul enfant (mais bon hier j'ai modifié ma fonction principal, donc maintenant ma focntion repond à la def d'un crossOver : utiliser un ou plusieurs parents pour créer 1 ou plusieurs enfants). Donc je sais aps quoi faire ...

pere :  1 2 3 4 5 6 7 8 9
mere : 4 1 2 8 7 6 9 3 5
enf   :  _ _ _ _ _ _ _ _ _

-1- Generer un locus
locus : 0 1 0 1 0 1 0 0 1

-2- recopier la mere dans enf
enf : 4 1 2 8 7 6 9 3 5

-3- /* retirer du pere les allele de la mere selectionnee  (A) */
     /* retirer de l'enfant les allele de la mere non selectionne (B) */
pour chaque locus,
si locus == 1, retirer du pere l'allele de la mere correspondant (A)
sinon le retirer dans enf (B)

locus : 0 1 0 1 0 1 0 0 1
mere : 4 1 2 8 7 6 9 3 5

pere :  _ 2 3 4 _ _ 7 _ 9 (A)
enf   : _ 1 _ 8 _ 6 _ _ 5 (B)

-3- remplir les genes vides de l'enfant avec les allele obtenu par (A) dans leur ordre d'apparition
enf : 2 1 3 8 4 6 7 9 5

Analyse mathématiques :
On se retrouve avec les même problèmes que pour l'order based mais inversement pere/mere.
(bon je ferais l'explication et l'implémentation cette aprem normalment, la je fais els test et je constates qq ptits trus)

Quelques tests :
je me retourve avec enfant == mere (donc pas géniale)

cas1 :
pere : {4,1,2,8,7,6,9,3,5}
mere : {1,2,3,4,5,6,7,8,9}
locus : { 0 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,0 }
enfant : {1,2,3,4,5,6,7,8,9}

cas2 :
pere : {1,2,3,4,5,6,7,8,9,}
mere : {4,1,2,8,7,6,9,3,5,}
locus : { 1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 , }
enfant : {4,1,2,8,7,6,9,3,5,}

pourquoi? pour les raisons citées ci-dessus (cf analyse mathématiques)

• 02 - Order cross-over (OX)

bien bien compliquer ....

• 03 - Linear Order cross-over (LOX) (OK)

Explication:
Crée par Falkenauer et Bouffouix [Falkenauer et al. 1991], cet opérateur génétique permet de conserver l'ordre absolu des allèles dans le chromosome.
-1- déterminer de façon aléatoire 2 points de coupure.
-2- recopier Parent1 et Parent2 respectivement dans Enfant1 et Enfant2.
-3- Les allèles du Parent2 sélectionnés entre les points de coupure sont supprimés de l'Enfant1 (idem avec Parent1 pour Enfant2)
-4- Pour chaque enfant, les allèles sont poussées à droite et à gauche afin d'obtenir un trou (cad tous les allèles null) entre les 2 points de coupures.
-5- Le trou de l'Enfant1 est complété avec les allèles contenus entre les points de coupure du Parent2 (et repectivement avec Enfant2 et Parent1)

Implémentation:
pere :  1 2 3 4 5 6 7 8 9
mere : 4 1 2 8 7 6 9 3 5
enf   :  _ _ _ _ _ _ _ _ _

-1- choisir 2 point de coupure aléatoires, le trou appartiendra à [pc1;pc2[
pc1 = 3
pc2 = 7
d'où :
pere :  1 2 3 | 4 5 6 | 7 8 9
mere : 4 1 2 | 8 7 6 | 9 3 5

-2- je recopie dans enf les pc1 premier gene de pere n'appartenant pas au trou de mere
enf : 1 2 3 | _ _ _ _ _ _

-3- je recopie dans l'intervalle d'enfant l'intervalle de mere
enf : 1 2 3 | 8 7 6 | _ _ _

-4- je recopie les genes de pere n'appartenant pas au trou de mere qui n'ont pas encore été ajouter
enf : 1 2 3 | 8 7 6 | 4 5 9

NB : toujours la même remarque, je ne crée qu'un seul enfant, et j'inverse ensuite pere et mere. Est-ce que c'est bien? ...

Analyse mathématiques :

-1- Si les allèles sont les mêmes chez le pere et la mere entre les 2 points de coupures,
alors l'enfant == pere.

Question : est-ce possible de calculer la probabilité que cela arrive??
car d'après moi doit pas être bien élever, mais je vois pas trop comment calculer ça.

-2- analyse de l'intervalle de coupure [pc1,pc2[,
que je déterminerais comme étant d'ordre k (k repséentant la taille de l'intervalle, avec k>0):

soit p1 = x1 x2 x3 ... xn
soit p2 = y1 y2 y3 ... yn

avec : xi € [1,n] et y € [1,n]
et
(A) qqsoit i,j , si i!=j, alors xi!=xj et yi != yj
(B) qqsoit i, il existe j tq xi=yj.

-2.1- cas où k très petit
pire cas : k==1
 p1 = x1 x2 ... | xp | ... xn-1 xn
 p2 = y1 y2 ... | yp | ... yn-1 yn

donc, d'après (A), on a yp == xi

si i € [1,p-1]
alors suppresion de xi==yp dans la partie gauche à l'intervalle de coupure
+ decalage de k sur la gauche (k==1) de la partie [xi+1,xp]
+ réinsertion de xi en p

si i == p-1
alors on aura juste une invertion de xi et xp sans decalage

de même,si i € [p+1,n]
alors suppresion de xi==yp dans la partie droite à l'intervalle de coupure
+ decalage de k sur la droite (k==1) de la partie [xp,xi-1]
+ réinsertion de xi en p

si i == p+1
alors on aura juste une invertion de xi et xp sans decalage
(probabilité que cela arrive diminue proportionnellement avec

=> Donc, dans le pire des cas k==1,ce crossover reste assez performant
malgrès une probabilité de réaliser une simple invertion très faible car diminue proportionnellement avec n augmente.
 

-2.2-a l'inverse,
cas où k très grand
pire cas k = n
 p1 = |x1 x2 ... xn-1 xn|
 p2 = |y1 y2 ... yn-1 yn|

dans ce cas, enfant == mere.

=>plus k est grand, plus l'enfant ressemblera à sa mere.

-3- je ne pense pas qu'il y ait des problèmes liés à l'ordre relatif des allèles chez le pere et la mere (contrairement à order absed et position based).

Quelques tests :

Voilà les premiers tests (une grosse série de tests est prévu pour la moitié du stage, donc grosse partie analyse pratique à venir  dans les prochaines semaines) :

• pour n=9 et k=6

pere : {1,2,3,4,5,6,7,8,9,}
mere : {4,1,2,8,7,6,9,3,5,}
coupure : [2,8[
enfant1 : {1,4,2,8,7,6,9,3,5,}

pere : {4,1,2,8,7,6,9,3,5,}
mere : {1,2,3,4,5,6,7,8,9,}
coupure : [2,8[
enfant1 : {1,2,3,4,5,6,7,8,9,}

=> confirmation des analyses.

• 04 - Cycle cross-over (CX)

• 05 - IX

• 06 - Partially Mapped CrossOver (PMX)

• 07 - croisement de fusion (MX1T)

• 08 - croisement heuristique (MX1D)

• 09 - Merging CrossOver (MOX)(OK)

Explication:
Créer par Peter G. Anderson and Daniel Ashlock.
Le principe est assez simple :

1. On fusionne aléatoirement le pere et la mere.
2. Le premier fils prendra les premières occurences de chaque gene de la fusion.
3. Le deuxième fils prendra les secondes occurences de chaque gene de la fusion.

Implémentation :
L'implémentation a été plus cocasse que ce qu'elle laissait espérer.
J'avais un bugg dans une fonction de comparaison, et la fusion aléatoire à la voler n'a pas été easy easy.

pere :  ~ 1 2 3 4 5 6 7 8 9 nbGenesTraites = 0 ;
mere : ~ 4 1 2 8 7 6 9 3 5 nbGenesTraites = 0 ;
enf1   :  _ _ _ _ _ _ _ _ _
enf2   :  _ _ _ _ _ _ _ _ _

1- je prend le parent le plus adapté au problème pour être le premier parent.

parentActuel = pere avec nbGenesTraites = 0;

2- tant que tous les gènes (pere et mere) n'ont pas été traité
2.0 - si la parent actuel a encore des gènes à traiter
2.1 - génération d'un nombre aléatoire correspondant au nombre de gène que je vais traiter (cf analayse)

decalage = 3;

2.2 -  pour chaque gene à traiter, s'il n'existe pas chez l'enfant1, ajout à enfant1
sinon, ajout à enfant2.

pere :  ~ 1 2 3 | 4 5 6 7 8 9
enf1   :  1 2 3 _ _ _ _ _ _
enf2   :  _ _ _ _ _ _ _ _ _

2.3 - ajout du nombre de genes traiter ce tour ci au nombre total de gènes traiter pour le parent courant.

pere :  1 2 3 ~ 4 5 6 7 8 9 nbGenesTraites = 3 ;

2.4 - changement de parent

parentActuel = mere avec nbGenesTraites = 0;

Fin de l'exemple :

decalage = 3
mere : ~ 4 1 2 | 8 7 6 9 3 5
enf1   :  1 2 3 4 _ _ _ _ _
enf2   :  1 2 _ _ _ _ _ _ _

decalage = 3
pere : 1 2 3 ~ 4 5 6 | 7 8 9
enf1   :  1 2 3 4 5 6 _ _ _
enf2   :  1 2 4 _ _ _ _ _ _

decalage = 4
mere : 4 1 2 ~ 8 7 6 9 | 3 5
enf1   :  1 2 3 4 5 6 8 7 9
enf2   :  1 2 4 6 _ _ _ _ _

decalage = 2
pere : 1 2 3 4 5 6 ~ 7 8 | 9
enf1   :  1 2 3 4 5 6 8 7 9
enf2   :  1 2 4 6 7 8 _ _ _

decalage = 2
mere : 4 1 2 8 7 6 9 ~ 3 5 |  
enf1   :  1 2 3 4 5 6 8 7 9
enf2   :  1 2 4 6 7 8 3 5 _

decalage = 1
pere : 1 2 3 4 5 6 7 8 ~ 9 |  
enf1   :  1 2 3 4 5 6 8 7 9
enf2   :  1 2 4 6 7 8 3 5 9

resultat :
pere : 1 2 3 4 5 6 7 8 9 ~
mere : 4 1 2 8 7 6 9 3 5 ~
enf1   :  1 2 3 4 5 6 8 7 9
enf2   :  1 2 4 6 7 8 3 5 9

Analyse mathématiques :
Le décalage :
-> implémentation :
L'étape la plus importante de ce crossover est la fusion des 2 parents, fait à la voler lors de l'implémentation pour gagner du temps et de l'espace à l'execution.
Dans mon cas, j'ai pris l'option de garder pour chaque parent son nombre de gènes traitées, et de déterminer le décalage par rapport à cette donnée.
Ce qui donne le bout de code suivant :
   
        // je limite la coupure a un intervalle précis
 int decalage = rand.nextInt((numberOfGene-nbEltTraite[parentActuel])/2+1);

Ainsi, mon décalage sera toujours compris entre 0 et la moitié du nombre de gènes qu'il reste à traiter.
Je suis obliger de faire +1 car la fonction rand.nextInt(i) tire un nombre compris entre [0,i[
or, vers la fin de l'algo, il arrive d'avoir k gèes a traiter (avec k<=2), ce qui donne k/2 = 0 et la fonction rand n'apprécit guère.

De plus, afin d'avoir toujours un decalage positif, j'incrémente le decalage de 1 :
 decalage++;

Ceci à donc pour effet au final de me faire un decalage comrpis entre [0,la moitié des gènes qu'il reste à traiter +1 ]

-> analyse :
de cette manière, je suis sur d'avoir un des premiers intervals relativement grand.
inconvénient : ceci a pour effet de copier une partie d'un des 2 parents dans le premier fils
avantage : une fois cette copie faite, la répartition des nombres qui arriveront se fera de manière plus répartie entre les 2 enfants. En effet, le premier enfant aura déjà une bonne partie des gènes, mais comme les premières sélection chez le deuxième parent sont aussi importantes, et que, s'il est différent de p1, ces gènes seront copié à la fois chez l'enfant1 et l'enfant2.
Au final, ceci a pour effet de garder les similitudes entre les parents chez les enfants.

• 10 - Croisement par recombinaison d'adjacence - edge-3 recombination -(OK)

Explication:

Il existe plusieurs types de croismeent par recombinaison d'adjacences.
Le principe général est le même pour tous : faire hériter un descendant des adjacences existant dans les 2 parents.
Celui étudié ici est le -edge-3 recombination- de K. Mathias et D. Whitley.

1- création d'un tableau d'adjacence qui à chaque gène associe le prédecesseur et le successeur des 2 parents. (dans ce cas le gène est considéré comme un noeud du tableau)
2-0- choix aléatoire d'un noeux actif initial (nai)
  -1- suppression du toutes les références à ce noeud du tableau.
  -2- ajout du noeud à enfant.
3 - choix d'un new nai dans la liste d'adjacence associée au noeud courant. Le choix se fait comme suit :
 -> si 2 gènes identiques dans la liste d'adjacence, choix de ce gène comme new nai.
 -> si aucun gène identique, choix alétoire d'un gène parmis la liste d'adjacence.
 -> si liste d'adjacence null, choix d'un new nai aléatoirement n'ayant pas encore été traité (idem 2-0).
  -> dans ce cas, l'enfilement dans enfant change.

Donc, 2 types d'enfilement possibles :
partons d'un enfant = null;
ajout de a puis b puis c puis d
enf : a b c d
changement d'enfilement,
ajout de e puis f puis g
enf : e f g a b c d
changement d'enfilement,
ajout de h puis i
enf : e f g a b c d h i
...

Implémentation :

1- createTabAdjacence();
la référence du tableau sera le parent1
avec :
parent1 (p1) : x1 x2 x3 ... xn-2 xn-1 xn
parent2 (p2) : y1 y2 y3 ... yn-2 yn-1 yn

  // peut pas mettre la belle image que j'ai faite

Pour p2, je vais stocker les gènes préd et succ de tel façon que, si j'ai des couples de gène identiques à ceux de p1 pour un même Ri donné, mes couples soit en (0,1) ou en (2,3).

NB : dans ce cas, xn sera toujours différent de yp1 mais pourra-être égale à ys1
de même, x2 sera toujours différent de ys1 mais pourra-être égale à yp1

avec : p2 : y1 ... yp1 R1 ys1 ... yp2 R2 yp2 ... yn

Arbre du couple (1,3) pour un Ri donné.
   // peut pas mettre la belle image que j'ai faite, deux fois
 
Ex de création de tableau d'adjacence:
pere : {1,2,3,4,5,6,7,8,9,}
mere : {4,1,2,8,7,6,9,3,5,}
tableau d'adjacence :
9, 1, 2, 3, 4, 5, 6, 7, 8,
4, 1, 9, 1, 4, 9, 6, 7, 6,
2, 3, 4, 5, 6, 7, 8, 9, 1,
2, 8, 5, 5, 3, 7, 8, 2, 3,

/** 2- initialisation du traitement **/
/* 2-0- choix aleatoire d'une Noeud Actif Initial (nai) */
choixAleatoireNai();
-> choix aléatoire nai dans pere : {1,2,3,4,5,6,7,8,9,} et enfant : []
 retenu : first nai = 7 and idRef 6

/* 2-1- ajout à enf */
addNaiToEnf();
-> enfant : [7]

/* 2-2- suppression du tab d'adjacence des réf au nai */
supprNaiOfTabAdj();

tableau d'adjacence :
9, 1, 2, 3, 4,  5,   6, null, 8,
4, 1, 9, 1, 4,  9,   6, null, 6,
2, 3, 4, 5, 6, null, 8,  9,   1,
2, 8, 5, 5, 3, null, 8,  2,   3,
 
On remarque que il n'y aura jamais plus de 4 références à chaque gène dans le tableau
et que une recherche colonne par colonne sera plus optimal qu'une recherche ligne par ligne
-> a prendre en comtpme pour optimalisé la suppression

/** 3- remplissage de enf **/
while(enfant.size()<pere.getNumberOfGene())
{
 chooseNaiInListeAdjacence();
 addNaiToEnf();
 supprNaiOfTabAdj();
 recupIdRef(); /* pour pouvoir ensuite se placer sur la bonne liste d'adjacence */

}

Analyse :

référence sur OX,MPX,ROX

Drapal !
 
ca ne serai pas mieux dans la section algo plutôt que java ?

bon j'ai passé quelques jours à la BU pour bien définir ce qu'est un algo génétique, une sélection et un cross-over (car trop de contradiction sur le net).

Il en ressort que une partie très importante dans les AG est la sélection.
Et contrairement aux idées reçu, la roulette est loin d'être la meilleur étant donnée qu'elle favorise grandement l'individu prépondérant de la génération et donc augmente fortement la pression de sélection (nombre de sélection espéré du meilleur individu)  qui doit rester la plus faible possible pour éviter une convergence prématurée.
Je veins donc de mettre en place la sélection par tournoi stochastique avec toutes l'analyse mathématiques permettant de démontrer une pression de sélection null qu'importe le nombre d'individu par tournoi.

Voilà, si sa interesse quelqu'un, je pourrais détailler tous ça.
Sinon, ben je vais me remettre sur les cross-over maintenant que j'ai une sélection interessante.
on allez pas laisser tous le travail de convergence à la sélection non plus, sa aurait plus aucun sens

De plus, concernant les cross-over :
il n'existe aucune règle pour créer un crossOver, donc je suis mal barrer pour tous les référencer.
J'ai trouvé des infos sur les croisements BLX-alpha volumique et BLX-alpha linéaire.
C'est, je pense, une piste à exploiter.
Mais une question se vient à moi :
les croisements BLX-alpha sont-ils des familles de croisement (et dans ce cas certains de mes cross-over peuvent être classé dedans) ou sont-ils juste 2 croisements supplémentaires?

 
Le croisement BLX-& linéaire est une extension du croisement BLX-& volumique.
Ainsi, il possède les mêmes propriétés que son prédécesseur à la différence prêt qu’il garde les éventuelles corrélations existant entre les gènes des reproducteurs concernés.
Mais ne pouvant s’appliquer à notre AG, nous feront l’impasse dessus.
En effet, ces 2 croisement, qui ne sont pas des familles de croisements, vont nous créer des nombres non-entiers, pouvant être identiques pour un même chromosome, et pouvant sortir de l’intervalle des allèles.
Donc, il n’a pas été implémenté !