Algorithmes génétiques - Sélection des parents

La sélection des parents est le processus de sélection des parents qui s'accouplent et se recombinent pour créer des rejetons pour la prochaine génération. La sélection des parents est très cruciale pour le taux de convergence de l'AG, car les bons parents poussent les individus vers des solutions meilleures et plus adaptées.

Cependant, il faut veiller à éviter qu'une solution extrêmement adaptée ne prenne en charge l'ensemble de la population en quelques générations, car cela conduit à des solutions proches les unes des autres dans l'espace des solutions conduisant ainsi à une perte de diversité. Maintaining good diversitydans la population est extrêmement cruciale pour le succès d'une AG. Cette prise en charge de l'ensemble de la population par une solution extrêmement adaptée est connue sous le nom depremature convergence et est une condition indésirable dans une AG.

Sélection proportionnelle de la condition physique

La sélection proportionnelle de la condition physique est l'une des méthodes les plus populaires de sélection des parents. En cela, chaque individu peut devenir parent avec une probabilité proportionnelle à son aptitude. Par conséquent, les individus en meilleure forme ont plus de chances de s'accoupler et de propager leurs caractéristiques à la génération suivante. Par conséquent, une telle stratégie de sélection exerce une pression de sélection sur les individus les plus aptes de la population, en faisant évoluer de meilleurs individus au fil du temps.

Prenons une roue circulaire. La roue est divisée enn pies, où n est le nombre d'individus dans la population. Chaque individu reçoit une partie du cercle qui est proportionnelle à sa valeur de fitness.

Deux implémentations de la sélection proportionnelle de la condition physique sont possibles -

Sélection de la roulette

Dans une sélection de roue de roulette, la roue circulaire est divisée comme décrit précédemment. Un point fixe est choisi sur la circonférence de la roue comme illustré et la roue est tournée. La région de la roue qui vient devant le point fixe est choisie comme parent. Pour le deuxième parent, le même processus est répété.

Il est clair qu'un installateur a une plus grande tarte sur la roue et donc une plus grande chance d'atterrir devant le point fixe lors de la rotation de la roue. Par conséquent, la probabilité de choisir un individu dépend directement de son aptitude.

En ce qui concerne la mise en œuvre, nous utilisons les étapes suivantes -

  • Calculer S = la somme des finesses.

  • Génère un nombre aléatoire entre 0 et S.

  • En partant du haut de la population, continuez à ajouter les finesses à la somme partielle P, jusqu'à P <S.

  • L'individu pour lequel P dépasse S est l'individu choisi.

Échantillonnage universel stochastique (SUS)

L'échantillonnage universel stochastique est assez similaire à la sélection de la roulette, mais au lieu d'avoir un seul point fixe, nous avons plusieurs points fixes, comme indiqué dans l'image suivante. Par conséquent, tous les parents sont choisis en un seul tour de roue. En outre, une telle configuration encourage les personnes très aptes à être choisies au moins une fois.

Il est à noter que les méthodes de sélection proportionnelle à la forme physique ne fonctionnent pas dans les cas où la valeur physique peut prendre une valeur négative.

Sélection du tournoi

Dans la sélection des tournois K-Way, nous sélectionnons K individus de la population au hasard et sélectionnons les meilleurs parmi ceux-ci pour devenir parent. Le même processus est répété pour sélectionner le parent suivant. La sélection de tournois est également extrêmement populaire dans la littérature car elle peut même fonctionner avec des valeurs de fitness négatives.

Sélection de rang

La sélection de classement fonctionne également avec des valeurs de fitness négatives et est principalement utilisée lorsque les individus de la population ont des valeurs de fitness très proches (cela se produit généralement à la fin de la course). Cela conduit chaque individu à avoir une part presque égale de la tarte (comme dans le cas de la sélection proportionnelle de la forme physique) comme le montre l'image suivante et, par conséquent, chaque individu, quel que soit son ajustement les uns par rapport aux autres, a approximativement la même probabilité d'être sélectionné en tant que parent. Cela conduit à son tour à une perte de la pression de sélection envers les individus en meilleure forme, ce qui oblige l'AG à faire de mauvais choix de parents dans de telles situations.

En cela, nous supprimons le concept de valeur de fitness lors de la sélection d'un parent. Cependant, chaque individu de la population est classé en fonction de sa forme physique. La sélection des parents dépend du rang de chaque individu et non de la forme physique. Les personnes les mieux classées sont préférées aux personnes les moins bien classées.

Chromosome Valeur de remise en forme Rang
UNE 8.1 1
B 8,0 4
C 8,05 2
7,95 6
E 8.02 3
F 7,99 5

Sélection aléatoire

Dans cette stratégie, nous sélectionnons au hasard les parents de la population existante. Il n'y a pas de pression de sélection envers les individus plus en forme et cette stratégie est donc généralement évitée.