Algorithmes génétiques - Crossover

Dans ce chapitre, nous discuterons de ce qu'est un opérateur Crossover avec ses autres modules, leurs utilisations et leurs avantages.

Introduction à Crossover

L'opérateur de croisement est analogue à la reproduction et au croisement biologique. Dans ce cas, plus d'un parent est sélectionné et une ou plusieurs descendants sont produits en utilisant le matériel génétique des parents. Le crossover est généralement appliqué dans un GA avec une probabilité élevée -pc .

Opérateurs de crossover

Dans cette section, nous discuterons de certains des opérateurs de croisement les plus couramment utilisés. Il est à noter que ces opérateurs de croisement sont très génériques et que le concepteur GA peut également choisir d'implémenter un opérateur de croisement spécifique au problème.

Crossover à un point

Dans ce croisement à un point, un point de croisement aléatoire est sélectionné et les queues de ses deux parents sont permutées pour obtenir de nouveaux ressorts.

Crossover multipoint

Le croisement multipoint est une généralisation du croisement à un point dans lequel des segments alternés sont permutés pour obtenir de nouveaux ressorts.

Crossover uniforme

Dans un croisement uniforme, nous ne divisons pas le chromosome en segments, nous traitons plutôt chaque gène séparément. En cela, nous lançons essentiellement une pièce pour chaque chromosome afin de décider s'il sera inclus ou non dans la progéniture. Nous pouvons également biaiser la pièce en faveur d'un parent, pour avoir plus de matériel génétique chez l'enfant de ce parent.

Recombinaison arithmétique entière

Ceci est couramment utilisé pour les représentations entières et fonctionne en prenant la moyenne pondérée des deux parents en utilisant les formules suivantes -

  • Enfant1 = α.x + (1-α) .y
  • Enfant2 = α.x + (1-α) .y

Évidemment, si α = 0,5, alors les deux enfants seront identiques comme le montre l'image suivante.

Crossover de l'ordre de Davis (OX1)

OX1 est utilisé pour les croisements basés sur les permutations dans le but de transmettre des informations sur l'ordre relatif aux ressorts. Cela fonctionne comme suit -

  • Créez deux points de croisement aléatoires dans le parent et copiez le segment entre eux du premier parent à la première progéniture.

  • Maintenant, à partir du deuxième point de croisement dans le deuxième parent, copiez les nombres inutilisés restants du deuxième parent vers le premier enfant, en faisant le tour de la liste.

  • Répétez pour le deuxième enfant avec le rôle du parent inversé.

Il existe de nombreux autres croisements tels que le crossover partiellement mappé (PMX), le crossover basé sur l'ordre (OX2), le shuffle Crossover, le Ring Crossover, etc.