Mécanisme de fonctionnement de l'algorithme génétique
Mécanisme de fonctionnement de l'algorithme génétique
M. Abd Al-Sattar Ismail Wadaa
L'algorithme génétique est une méthode parmi les méthodes d'optimisation et de recherche. Cette méthode peut être classée comme l'une des méthodes algorithmes évolutifs qui s'appuient sur l'imitation du fonctionnement de la nature d'un point de vue darwinien. L'algorithme génétique : est une technique de recherche utilisée pour trouver des solutions précises ou approximatives qui réalisent l'optimalité, les algorithmes génétiques sont classés comme des recherches globales inférentielles et sont également une catégorie particulière d'algorithmes évolutifs connus sous le nom de calcul évolutif qui utilisent des technologies inspirées de la biologie évolutive telles que l'hérédité, les mutations, la sélection et le croisement. Les algorithmes génétiques sont considérés comme des techniques importantes dans la recherche de la meilleure option parmi un ensemble de solutions disponibles pour un design particulier, et reposent sur le principe darwinien dans la sélection où ce traitement génétique transmet les caractéristiques optimales à travers des processus de reproduction successifs, et renforce ces traits, et ces traits ont la plus grande capacité à entrer dans le processus de reproduction, produisant une descendance optimale et avec la répétition du cycle génétique, la qualité de la descendance s'améliore progressivement.
Méthodologie
1- Les algorithmes génétiques sont exécutés en tant que simulation informatique où les chromosomes sont utilisés comme individus dans les processus qu'ils effectuent pour trouver les meilleures solutions, en général, les solutions sont représentées par un système binaire de 0 et 1, et d'autres symboles peuvent également être utilisés.
2- Le processus d'évolution commence généralement par le choix aléatoire des chromosomes et cela se produit dans les générations suivantes, à chaque génération, la fonction d'optimalité est calculée pour chaque chromosome individuellement et les meilleurs chromosomes sont sélectionnés en fonction de la meilleure fonction d'optimalité, puis un croisement (fusion) est effectué et également une mutation, cet algorithme s'arrête lorsque nous atteignons le plus grand nombre de générations produites ou atteignons la meilleure réalisation à travers la fonction d'optimalité, si l'arrêt est dû au plus grand nombre de générations, la solution optimale n'est pas réalisée.
3-Les algorithmes génétiques se trouvent dans les applications bioinformatique et en informatique, ingénierie, économie, chimie, industries manufacturières, mathématiques, physique et d'autres domaines.
Étapes de l'algorithme génétique
Premièrement - Initialisation : Au début, de nombreuses solutions individuelles sont générées aléatoirement sous forme initiale de chromosomes. La taille des chromosomes dépend de la nature du problème, mais il y a généralement plusieurs centaines ou milliers de solutions possibles. Traditionnellement, les chromosomes sont générés aléatoirement, de sorte à couvrir un ensemble complet de solutions possibles dans l'espace de recherche et parfois, cette solution peut être "classée" en atteignant la solution optimale.
Deuxièmement - Sélection : Au cours de chaque génération successive, un certain pourcentage des chromosomes actuels est sélectionné pour produire une nouvelle génération. Ces chromosomes sont sélectionnés en fonction de la fonction d'optimalité, où le pourcentage de sélection est basé sur la supériorité de la fonction d'optimalité, et il existe une autre méthode consistant à choisir un groupe aléatoire de chromosomes, mais ce processus peut prendre beaucoup de temps.
Troisièmement - Reproduction : C'est un processus de génération d'une deuxième génération de chromosomes qui ont été sélectionnés par le processus de sélection, puis un processus de croisement et de mutation est effectué pour produire des descendants.
Processus de croisement :- À partir des parents qui ont été choisis par le processus de sélection, chaque paire de parents est croisée pour produire deux nouveaux enfants et ce processus se poursuit jusqu'à ce qu'un nouvel ensemble de chromosomes soit trouvé en plus de l'ensemble des parents.
Il existe de nombreuses techniques utilisées dans le processus de croisement :
1- Croisement à un point : ce processus produit finalement la prochaine génération de la population de chromosomes qui diffèrent de la première génération, toutes les données sont organisées en fonction de ce point où un échange de données se produit à condition qu'il n'y ait pas de répétition.
2- Croisement à deux points : ce processus produit finalement la prochaine génération de la population de chromosomes qui diffèrent de la première génération, toutes les données sont organisées en fonction de ces deux points où un échange de données se produit à condition qu'il n'y ait pas de répétition.
3- Coupure et connexion : ce processus coupe les données d'une zone différente de celle du deuxième chromosome, ce qui entraîne une différence dans la longueur du chromosome.
Mutation : - C'est un changement soudain dans les descendants résultant du processus de croisement, de sorte qu'il y ait un changement dans la forme du chromosome par le biais d'un changement d'un des composants du chromosome, un changement (bit) qui n'est pas le résultat des parents.
Le processus de reproduction conduit finalement à la production de nouveaux chromosomes sur lesquels la fonction d'optimalité est appliquée pour produire de nouveaux descendants.
Quatrièmement - Terminaison : Le processus de génération d'une nouvelle génération se poursuit jusqu'à ce qu'une des raisons de terminaison se produise, qui sont :
1- Atteindre la meilleure solution.
2- Atteindre le nombre de générations requis.
3- Atteindre une valeur spécifique comme le calcul (temps/argent)
4- Atteindre et ne pas pouvoir en sortir.
5- Deviner.
6- En utilisant un ensemble des raisons précédentes.
Cinquièmement : le code trompeur de l'algorithme.
1- Choisir un ensemble de données chromosomes.
2- Calculer la fonction d'optimalité pour chaque chromosome.
3- Répéter
4- Choisir les meilleurs parents pour le processus de production des descendants.
5- Générer une nouvelle génération en utilisant le croisement et la mutation.
6- Évaluer le nouvel enfant en fonction de la fonction d'optimalité.
7- Apporter des modifications aux chromosomes originaux en fonction des valeurs des descendants.