Algorithmes génétiques - Fondamentaux

Cette section présente la terminologie de base requise pour comprendre les GA. En outre, une structure générique des AG est présentée dans les deuxpseudo-code and graphical forms. Il est conseillé au lecteur de bien comprendre tous les concepts présentés dans cette section et de les garder à l'esprit lors de la lecture d'autres sections de ce didacticiel.

Terminologie de base

Avant d'entamer une discussion sur les algorithmes génétiques, il est essentiel de se familiariser avec la terminologie de base qui sera utilisée tout au long de ce tutoriel.

  • Population- C'est un sous-ensemble de toutes les solutions possibles (codées) au problème donné. La population pour une AG est analogue à la population des êtres humains sauf qu'au lieu des êtres humains, nous avons des Solutions Candidates représentant des êtres humains.

  • Chromosomes - Un chromosome est l'une de ces solutions au problème donné.

  • Gene - Un gène est une position d'élément d'un chromosome.

  • Allele - C'est la valeur qu'un gène prend pour un chromosome particulier.

  • Genotype- Le génotype est la population dans l'espace de calcul. Dans l'espace de calcul, les solutions sont représentées d'une manière qui peut être facilement comprise et manipulée à l'aide d'un système informatique.

  • Phenotype - Le phénotype est la population dans l'espace réel des solutions du monde réel dans lequel les solutions sont représentées d'une manière qu'elles sont représentées dans des situations du monde réel.

  • Decoding and Encoding - Pour des problèmes simples, le phenotype and genotypeles espaces sont les mêmes. Cependant, dans la plupart des cas, les espaces phénotypiques et génotypiques sont différents. Le décodage est un processus de transformation d'une solution du génotype à l'espace phénotype, tandis que l'encodage est un processus de transformation du phénotype à l'espace génotypique. Le décodage doit être rapide car il est effectué à plusieurs reprises dans un GA pendant le calcul de la valeur de fitness.

    Par exemple, considérons le problème du sac à dos 0/1. L'espace Phénotype est constitué de solutions qui contiennent uniquement les numéros d'articles des articles à prélever.

    Cependant, dans l'espace génotypique, il peut être représenté comme une chaîne binaire de longueur n (où n est le nombre d'éléments). UNE0 at position x représente que xthl'élément est sélectionné tandis qu'un 1 représente l'inverse. C'est un cas où les espaces génotype et phénotype sont différents.

  • Fitness Function- Une fonction de fitness simplement définie est une fonction qui prend la solution comme entrée et produit l'adéquation de la solution comme sortie. Dans certains cas, la fonction de fitness et la fonction objective peuvent être identiques, tandis que dans d'autres, elles peuvent être différentes en fonction du problème.

  • Genetic Operators- Ceux-ci modifient la composition génétique de la progéniture. Ceux-ci incluent le croisement, la mutation, la sélection, etc.

Structure basique

La structure de base d'un GA est la suivante -

Nous commençons par une population initiale (qui peut être générée au hasard ou ensemencée par d'autres heuristiques), sélectionnons les parents de cette population pour l'accouplement. Appliquez des opérateurs de croisement et de mutation sur les parents pour générer de nouveaux rejetons. Et enfin, ces rejetons remplacent les individus existants dans la population et le processus se répète. De cette manière, les algorithmes génétiques essaient en fait d'imiter dans une certaine mesure l'évolution humaine.

Chacune des étapes suivantes est traitée dans un chapitre distinct plus loin dans ce didacticiel.

Un pseudo-code généralisé pour un GA est expliqué dans le programme suivant -

GA()
   initialize population
   find fitness of population
   
   while (termination criteria is reached) do
      parent selection
      crossover with probability pc
      mutation with probability pm
      decode and fitness calculation
      survivor selection
      find best
   return best