Présentation de l'algorithme génétique

Les techniques d'optimisation sont les techniques utilisées pour découvrir la meilleure solution parmi toutes les solutions possibles disponibles sous les contraintes présentes. Ainsi, l'algorithme génétique est l'un de ces algorithmes d'optimisation qui est construit sur la base du processus évolutif naturel de notre nature. L'idée de la sélection naturelle et de l'héritage génétique est utilisée ici. Il utilise la recherche aléatoire guidée, contrairement à d'autres algorithmes, c'est-à-dire trouver la solution optimale en commençant par une fonction de coût initial aléatoire et en ne cherchant ensuite que dans l'espace le moins coûteux (dans la direction guidée). Convient lorsque vous travaillez avec des ensembles de données énormes et complexes.

Qu'est-ce qu'un algorithme génétique?

L'algorithme génétique est basé sur la structure génétique et le comportement du chromosome de la population. Les éléments suivants sont à la base des algorithmes génétiques.

  • Chaque chromosome indique une solution possible. Ainsi, la population est une collection de chromosomes.
  • Chaque individu de la population est caractérisé par une fonction de fitness. Une meilleure forme physique est la meilleure solution.
  • Parmi les individus disponibles dans la population, les meilleurs individus sont utilisés pour la reproduction des descendants de la prochaine génération.
  • La progéniture produite aura des caractéristiques des deux parents et est le résultat d'une mutation. Une mutation est un petit changement dans la structure du gène.

Phases de l'algorithme génétique

Voici les différentes phases de l'algorithme génétique:

1. Initialisation de la population (codage)

  • Chaque gène représente un paramètre (variables) dans la solution. Cette collection de paramètres qui forme la solution est le chromosome. La population est une collection de chromosomes.
  • L'ordre des gènes sur les questions chromosomiques.
  • La plupart du temps, les chromosomes sont représentés en binaire sous forme de 0 et de 1, mais il existe également d'autres codages possibles.

2. Fonction fitness

  • Parmi les chromosomes disponibles, nous devons sélectionner les meilleurs pour la reproduction des descendants, de sorte que chaque chromosome reçoit une valeur de fitness.
  • Le score de fitness permet de sélectionner les individus qui seront utilisés pour la reproduction.

3. Sélection

  • L'objectif principal de cette phase est de trouver la région où les chances d'obtenir la meilleure solution sont les plus importantes.
  • L'inspiration vient de la survie des plus aptes.
  • Ce devrait être un équilibre entre l'exploration et l'exploitation de l'espace de recherche.
  • GA essaie de déplacer le génotype vers une meilleure condition physique dans l'espace de recherche.
  • Un biais de sélection de fitness trop fort peut conduire à des solutions sous-optimales.
  • Une sélection de biais de fitness trop faible entraîne une recherche non focalisée.
  • Ainsi, la sélection proportionnelle Fitness est utilisée, également connue sous le nom de sélection de roulette, est un opérateur génétique utilisé dans les algorithmes génétiques pour sélectionner des solutions potentiellement utiles pour la recombinaison.

4. Reproduction

La génération de descendants se produit de 2 manières:

  • Crossover
  • Mutation

À travers

Le croisement est l'étape la plus vitale de l'algorithme génétique. Pendant le croisement, un point aléatoire est sélectionné lors de l'accouplement d'une paire de parents pour générer des descendants.

Il existe 3 principaux types de croisement.

  • Point de croisement à point unique: 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.
  • Crossover à deux points : deux points de crossover sont choisis au hasard parmi les chromosomes parents. Les bits entre les deux points sont échangés entre les organismes parents.
  • Crossover uniforme: Dans un crossover uniforme, généralement, chaque bit est choisi parmi l'un ou l'autre parent avec une probabilité égale.

La nouvelle progéniture est ajoutée à la population.

b) Mutation

Dans quelques nouveaux descendants formés, certains de leurs gènes peuvent être soumis à une mutation avec une faible probabilité aléatoire. Cela indique que certains des bits du chromosome binaire peuvent être inversés. Il arrive que la mutation prenne soin de la diversité de la population et arrête la convergence prématurée.

5. Convergence (quand s'arrêter)

Peu de règles suivies qui indiquent quand s'arrêter sont les suivantes:

  • Lorsqu'il n'y a pas d'amélioration de la qualité de la solution après avoir terminé un certain nombre de générations définies à l'avance.
  • Quand une gamme dure et rapide de générations et de temps est atteinte.
  • Jusqu'à ce qu'une solution acceptable soit obtenue.

Application de l'algorithme génétique

Dans cette section, nous discuterons de certains des domaines dans lesquels l'algorithme génétique est fréquemment appliqué.

1. Déplacement et acheminement des envois

Le problème du voyageur de commerce est l'une des principales applications de l'algorithme génétique. Par exemple, lorsqu'un planificateur de voyage est invité à planifier un voyage, il prendrait l'aide d'un algorithme génétique qui aide non seulement à réduire le coût global du voyage, mais aussi à réduire le temps.GE est également utilisé pour planifier la livraison de produits d'un endroit à l'autre de la manière la plus efficace.

2. Robotique

L'algorithme génétique est largement utilisé dans le domaine de la robotique. Les robots diffèrent les uns des autres par le but pour lequel ils sont conçus. Par exemple, peu sont conçus pour une tâche de cuisine, peu sont conçus pour des tâches d'enseignement, etc.

  • Sélection d'entités importantes dans l'ensemble de données donné.
  • Dans la méthode traditionnelle, les entités importantes de l'ensemble de données sont sélectionnées à l'aide de la méthode suivante. c'est-à-dire que vous regardez l'importance de ce modèle, puis définissez une valeur de seuil pour les entités, et si l'entité a une valeur d'importance supérieure à un seuil, elle est considérée.
  • Mais ici, nous utilisons une méthode appelée un problème de sac à dos.
  • Nous recommencerons avec la population d'un chromosome, où chaque chromosome sera une chaîne binaire. 1 dénotera «l'inclusion» de la caractéristique dans le modèle et 0 dénotera «l'exclusion» de la caractéristique dans le modèle.
  • La fonction fitness ici sera notre métrique de précision de la compétition. Plus notre ensemble de chromosomes est précis dans la prévision de la valeur, plus il sera en forme.
  • Il existe de nombreuses autres applications des algorithmes génétiques comme l'analyse de l'ADN, les applications de planification, la conception technique.

Conclusion

Dans le scénario actuel, GE est utilisé dans de grandes entreprises de fabrication comme les avions, etc. afin d'optimiser l'utilisation du temps et des ressources. D'autres scientifiques travaillent à trouver de nouvelles façons de combiner des algorithmes génétiques avec d'autres techniques d'optimisation.

Articles recommandés

Ceci est un guide sur Qu'est-ce que l'algorithme génétique? Ici, nous discutons de l'introduction, des phases et des applications de l'algorithme génétique. Vous pouvez également consulter nos autres articles suggérés -

  1. Algorithmes de routage
  2. Types d'algorithmes
  3. Algorithmes de réseau neuronal
  4. Algorithmes d'exploration de données
  5. guide des exemples d'algorithmes C ++

Catégorie:

Big Data