Sélection
La sélection est l'étape de la génétique algorithmique dans laquelle les génomes individuels sont choisis à partir d’une population d'élevage plus tard (en utilisant l’opérateur de croisement).
Une procédure de sélection générique peut être mise en œuvre comme suit:
- La fonction de fitness est évaluée pour chaque individu, fournissant des valeurs de fitness qui sont ensuite normalisées. La normalisation consiste à diviser la valeur de la forme physique de chaque individu par la somme de toutes les valeurs de la forme physique, de sorte que la somme de toutes les valeurs résultantes de la forme physique soit égale à 1.
- La population est triée par valeur de remise en forme décroissante.
- Les valeurs de fitness normalisées accumulées sont calculées: la valeur de fitness accumulée d'un individu est la somme de sa propre valeur de fitness et des valeurs de fitness de tous les individus précédents; la condition physique accumulée du dernier individu doit être égale à 1, sinon quelque chose s'est mal passé lors de l’étape de normalisation.
- Un nombre aléatoire R compris entre 0 et 1 est choisi
- L'individu sélectionné est le dernier dont la valeur normalisée accumulée est supérieure ou égale à R.
Pour un grand nombre d'individus, l'algorithme ci-dessus peut s'avérer très démodé par calcul. Une alternative plus simple et plus rapide utilise ce que l'on appelle l'acceptation stochastique.
Si cette procédure est répétée jusqu'à ce qu'il y ait suffisamment d'individus sélectionnés, cette méthode de sélection est appelée sélection proportionnelle à la forme ou sélection à la roulette. Si, au lieu d'un seul pointeur tourné plusieurs fois, il existe plusieurs pointeurs équidistants sur une roue qui tourne une fois, on parle alors d’échantillonnage stochastique universel. La sélection répétée du tournoi est la sélection du meilleur individu d'un sous-ensemble choisi au hasard. La sélection de la troncature constitue la moitié, le tiers ou une autre proportion optimale des individus.
D'autres algorithmes de sélection ms ne prennent pas en compte tous les individus mais uniquement ceux dont la valeur de fitness est supérieure à une constante donnée (arbitraire). D'autres algorithmes effectuent une sélection dans un pool restreint où seul un certain pourcentage d’individus est autorisé, en fonction de la valeur de la condition physique.
Conserver les meilleurs individus de la génération sans changement de la prochaine génération est appelé élitisme ou sélection élitiste. C'est une variante réussie (légère) du processus général de construction d'une nouvelle population
