Crossover (algorithme génétique)

Dans les algorithmes génétiques et le calcul évolutionnaire , le croisement , également appelé recombinaison , est un opérateur génétique utilisé pour combiner les informations génétiques de deux parents afin de générer une nouvelle progéniture. Il s'agit d'une façon de générer de manière stochastique de nouvelles solutions à partir d'une population existante, et est analogue au croisement qui se produit lors de la reproduction sexuée en biologie . Des solutions peuvent également être générées en clonant une solution existante, ce qui est analogue à la reproduction asexuée . Les solutions nouvellement générées peuvent être mutées avant d'être ajoutées à la population.

Différents algorithmes de calcul évolutionnaire peuvent utiliser différentes structures de données pour stocker les informations génétiques, et chaque représentation génétique peut être recombinée avec différents opérateurs de croisement. Les structures de données typiques qui peuvent être recombinées avec croisement sont les tableaux de bits , les vecteurs de nombres réels ou les arbres .

La liste des opérateurs présentée ci-dessous n'est en aucun cas exhaustive et sert principalement d'illustration exemplaire de ce type d'opérateur génétique dyadique . D'autres opérateurs et davantage de détails peuvent être trouvés dans la littérature.

Crossover pour tableaux binaires

Les algorithmes génétiques traditionnels stockent les informations génétiques dans un chromosome représenté par un tableau de bits . Les méthodes de croisement pour les tableaux de bits sont populaires et constituent un exemple illustratif de recombinaison génétique .

Croisement à un point

Un point sur les chromosomes des deux parents est choisi au hasard et désigné comme « point de croisement ». Les bits à droite de ce point sont échangés entre les deux chromosomes parents. Il en résulte deux descendants, chacun porteur d'informations génétiques des deux parents.

Croisement à deux points et à point k

Dans le cas d'un croisement à deux points, deux points de croisement sont choisis au hasard parmi les chromosomes parents. Les bits entre les deux points sont échangés entre les organismes parents.

Le croisement à deux points équivaut à effectuer deux croisements à un seul point avec des points de croisement différents. Cette stratégie peut être généralisée au croisement à k points pour tout entier positif k, en choisissant k points de croisement.

Croisement uniforme

En cas de croisement uniforme, chaque bit est généralement choisi chez l'un des deux parents avec une probabilité égale. D'autres ratios de mélange sont parfois utilisés, ce qui donne naissance à une progéniture qui hérite de plus d'informations génétiques d'un parent que de l'autre. Dans un croisement uniforme, nous ne divisons pas le chromosome en segments, mais nous traitons chaque gène séparément. Dans ce cas, nous lançons une pièce pour chaque chromosome afin de décider s'il sera ou non inclus dans la progéniture.

Crossover pour génomes à valeurs entières ou réelles

Pour les opérateurs de croisement présentés ci-dessus et pour la plupart des autres opérateurs de croisement pour les chaînes de bits, il est vrai qu'ils peuvent également être appliqués en conséquence aux génomes à valeur entière ou réelle dont les gènes sont chacun constitués d'un nombre entier ou réel. Au lieu de bits individuels, des nombres entiers ou réels sont alors simplement copiés dans le génome enfant. La progéniture se trouve sur les coins restants de l'hypercorps formé par les deux parents et , comme illustré dans l'image ci-jointe pour le cas tridimensionnel. ${\displaystyle P_{1}=(1.5,6,8) <semantics> <mrow> <mstyle> <msub> <mi>P</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mo>(</mo> <mn>1,5</mn> <mo>,</mo> <mn>6</mn> <mo>,</mo> <mn>8</mn> <mo>)</mo> </mstyle> </mrow> <annotation>{ displaystyle P_ {1} = (1.5,6,8)}</annotation> </semantics> </math><img src=$ ${\displaystyle P_{2}=(7,2,1) <semantics> <mrow> <mstyle> <msub> <mi>P</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>=</mo> <mo>(</mo> <mn>7</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mn>1</mn> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle P_{2}=(7,2,1)}</annotation> </semantics> </math><img src=$

Recombinaison discrète

Si les règles du croisement uniforme pour les chaînes de bits sont appliquées lors de la génération de la progéniture, cela est également appelé recombinaison discrète .

Recombinaison intermédiaire

Dans cet opérateur de recombinaison, les valeurs alléliques du génome enfant sont générées en mélangeant les allèles des deux génomes parents et : ${\displaystyle a_{i <semantics> <mrow> <mstyle> <msub> <mi>un</mi> <mrow> <mi>je</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle a_{i}}</annotation> </semantics> </math><img src=$ ${\displaystyle a_{i,P_{1 <semantics> <mrow> <mstyle> <msub> <mi>un</mi> <mrow> <mi>je</mi> <mo>,</mo> <msub> <mi>P</mi> <mrow> <mn>1</mn> </mrow> </msub> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle a_{i,P_{1}}}</annotation> </semantics> </math><img src=$ ${\displaystyle a_{i,P_{2 <semantics> <mrow> <mstyle> <msub> <mi>un</mi> <mrow> <mi>je</mi> <mo>,</mo> <msub> <mi>P</mi> <mrow> <mn>2</mn> </mrow> </msub> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle a_{i,P_{2}}}</annotation> </semantics> </math><img src=$

{\displaystyle \alpha _{i}=\alpha _{i,P_{1}}\cdot \beta _{i}+\alpha _{i,P_{2}}\cdot \left(1-\beta _{i} ight)\quad {\mathsf {with}}\quad \beta _{i}\in \left[-d,1+d ight] <semantics> <mrow> <mstyle> <msub> <mi>α</mi> <mrow> <mi>je</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>α</mi> <mrow> <mi>je</mi> <mo>,</mo> <msub> <mi>P</mi> <mrow> <mn>1</mn> </mrow> </msub> </mrow> </msub> <mo>⋅</mo> <msub> <mi>β</mi> <mrow> <mi>je</mi> </mrow> </msub> <mo>+</mo> <msub> <mi>α</mi> <mrow> <mi>je</mi> <mo>,</mo> <msub> <mi>P</mi> <mrow> <mn>2</mn> </mrow> </msub> </mrow> </msub> <mo>⋅</mo> <mrow> <mo>(</mo> <mrow> <mn>1</mn> <mo>−</mo> <msub> <mi>β</mi> <mrow> <mi>je</mi> </mrow> </msub> </mrow> <mo>)</mo> </mrow> <mspace></mspace> <mrow> <mrow> <mi>m</mi> <mi>je</mi> <mi>t</mi> <mi>h</mi> </mrow> </mrow> <mspace></mspace> <msub> <mi>β</mi> <mrow> <mi>je</mi> </mrow> </msub> <mo>∈</mo> <mrow> <mo>[</mo> <mrow> <mo>−</mo> <mi>d</mi> <mo>,</mo> <mn>1</mn> <mo>+</mo> <mi>d</mi> </mrow> <mo>]</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle \alpha _{i}=\alpha _{i,P_{1}}\cdot \beta _{i}+\alpha _{i,P_{2}}\cdot \gauche(1-\beta _{i}\droite)\quad {\mathsf {avec}}\quad \beta _{i}\in \gauche[-d,1+d\droite]}</annotation> </semantics> </math></span><img src=

{\displaystyle i <semantics> <mrow> <mstyle> <mi>je</mi> </mstyle> </mrow> <annotation>{\displaystyle i}</annotation> </semantics> </math></span><img src=

Le choix de l'intervalle fait qu'en plus de l'intérieur de l'hypercorps couvert par les valeurs d'allèles des gènes parents, un certain environnement pour la plage de valeurs de la progéniture est également en question. Une valeur de est recommandée pour contrecarrer la tendance à réduire les valeurs d'allèles qui existe autrement à . ${\displaystyle [-d,1+d] <semantics> <mrow> <mstyle> <mo>[</mo> <mo>−</mo> <mi>d</mi> <mo>,</mo> <mn>1</mn> <mo>+</mo> <mi>d</mi> <mo>]</mo> </mstyle> </mrow> <annotation>{\displaystyle [-d,1+d]}</annotation> </semantics> </math><img src=$ ${\displaystyle 0.25 <semantics> <mrow> <mstyle> <mn>0,25</mn> </mstyle> </mrow> <annotation>{\displaystyle 0.25}</annotation> </semantics> </math><img src=$ ${\displaystyle d <semantics> <mrow> <mstyle> <mi>d</mi> </mstyle> </mrow> <annotation>{\displaystyle d}</annotation> </semantics> </math><img src=$ ${\displaystyle d=0 <semantics> <mrow> <mstyle> <mi>d</mi> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation>{\displaystyle d=0}</annotation> </semantics> </math><img src=$

La figure ci-contre montre, pour le cas bidimensionnel, la gamme des nouveaux allèles possibles des deux parents exemplaires et en recombinaison intermédiaire. Les descendants de la recombinaison discrète et sont également représentés. La recombinaison intermédiaire satisfait le calcul arithmétique des valeurs d'allèles du génome enfant requis par la théorie de l'alphabet virtuel. La recombinaison discrète et intermédiaire sont utilisées comme norme dans la stratégie d'évolution . ${\displaystyle P_{1}=(3,6) <semantics> <mrow> <mstyle> <msub> <mi>P</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mo>(</mo> <mn>3</mn> <mo>,</mo> <mn>6</mn> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle P_{1}=(3,6)}</annotation> </semantics> </math><img src=$ ${\displaystyle P_{2}=(9,2) <semantics> <mrow> <mstyle> <msub> <mi>P</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>=</mo> <mo>(</mo> <mn>9</mn> <mo>,</mo> <mn>2</mn> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle P_{2}=(9,2)}</annotation> </semantics> </math><img src=$ ${\displaystyle C_{1 <semantics> <mrow> <mstyle> <msub> <mi>C</mi> <mrow> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle C_{1}}</annotation> </semantics> </math><img src=$ ${\displaystyle C_{2 <semantics> <mrow> <mstyle> <msub> <mi>C</mi> <mrow> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle C_{2}}</annotation> </semantics> </math><img src=$

Crossover pour permutations

Pour les tâches combinatoires , on utilise généralement des permutations conçues spécifiquement pour les génomes qui sont eux-mêmes des permutations d'un ensemble . L'ensemble sous-jacent est généralement un sous-ensemble de ou . Si un croisement à 1 ou n points ou uniforme pour les génomes entiers est utilisé pour de tels génomes, un génome enfant peut contenir certaines valeurs deux fois et d'autres peuvent être manquantes. Cela peut être corrigé par une réparation génétique , par exemple en remplaçant les gènes redondants en fidélité positionnelle par ceux manquants de l'autre génome enfant. ${\displaystyle \mathbb {N} <semantics> <mrow> <mstyle> <mrow> <mi>N</mi> </mrow> </mstyle> </mrow> <annotation>{\displaystyle \mathbb {N} }</annotation> </semantics> </math><img src=$ ${\displaystyle \mathbb {N} _{0 <semantics> <mrow> <mstyle> <msub> <mrow> <mi>N</mi> </mrow> <mrow> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{ displaystyle mathbb {N} _ {0}}</annotation> </semantics> </math><img src=$

Afin d'éviter la génération de descendants invalides, des opérateurs de croisement spéciaux pour les permutations ont été développés qui remplissent les exigences de base de tels opérateurs pour les permutations, à savoir que tous les éléments de la permutation initiale sont également présents dans la nouvelle et que seul l'ordre est modifié. On peut distinguer les tâches combinatoires, où toutes les séquences sont admissibles, et celles où il existe des contraintes sous la forme de séquences partielles inadmissibles. Un représentant bien connu du premier type de tâche est le problème du voyageur de commerce (TSP), où l'objectif est de visiter un ensemble de villes exactement une fois lors du tour le plus court. Un exemple de type de tâche contraint est la planification de plusieurs flux de travail . Les flux de travail impliquent des contraintes de séquence sur certaines des étapes de travail individuelles. Par exemple, un filetage ne peut pas être coupé tant que le trou correspondant n'a pas été percé dans une pièce. De tels problèmes sont également appelés permutations basées sur l'ordre .

Dans ce qui suit, deux opérateurs de croisement sont présentés à titre d'exemple, le croisement partiellement mappé (PMX) motivé par le TSP et le croisement d'ordre (OX1) conçu pour les permutations basées sur l'ordre. Une deuxième progéniture peut être produite dans chaque cas en échangeant les chromosomes parents.

Crossover partiellement cartographié (PMX)

L'opérateur PMX a été conçu comme un opérateur de recombinaison pour les problèmes de type TSP. L'explication de la procédure est illustrée par un exemple :

Croisement d'ordre (OX1)

Le croisement d'ordre remonte à Davis dans sa forme originale et est présenté ici dans une version légèrement généralisée avec plus de deux points de croisement. Il transfère des informations sur l'ordre relatif du deuxième parent à la progéniture. Tout d'abord, le nombre et la position des points de croisement sont déterminés de manière aléatoire. Les séquences génétiques résultantes sont ensuite traitées comme décrit ci-dessous :

Entre autres choses, le croisement d'ordres est bien adapté à la planification de plusieurs flux de travail, lorsqu'il est utilisé en conjonction avec le croisement à 1 et n points.

Autres opérateurs de croisement pour les permutations

Au fil du temps, un grand nombre d'opérateurs de croisement pour les permutations ont été proposés, la liste suivante n'est donc qu'une petite sélection. Pour plus d'informations, le lecteur est invité à se référer à la littérature.

croisement de cycles (CX)
croisement basé sur les ordres (OX2)
croisement basé sur la position (POS)
recombinaison de bord
recombinaison de vote (VR)
croisement à positions alternées (AP)
croisement maximal conservateur (MPX)
croisement de fusion (MX)
opérateur de croisement constructif séquentiel (SCX)

L'approche habituelle pour résoudre les problèmes de type TSP par des algorithmes génétiques ou, plus généralement, évolutionnaires, présentés plus haut, consiste soit à réparer les descendants illégaux, soit à ajuster les opérateurs de manière appropriée afin qu'une descendance illégale n'apparaisse pas en premier lieu. Alternativement, Riazi suggère l'utilisation d'une représentation chromosomique double, qui évite la descendance illégale.