Un algorithme génétique est un algorithme de recherche heuristique adaptatif inspiré de la théorie de l'évolution de la nature de Darwin. .' Il est utilisé pour résoudre des problèmes d’optimisation dans l’apprentissage automatique. C’est l’un des algorithmes importants car il aide à résoudre des problèmes complexes qui prendraient beaucoup de temps à résoudre.

Les algorithmes génétiques sont largement utilisés dans différentes applications du monde réel, par exemple Conception de circuits électroniques, décryptage, traitement d'images et créativité artificielle.

Dans ce sujet, nous expliquerons en détail l'algorithme génétique, y compris les terminologies de base utilisées dans l'algorithme génétique, son fonctionnement, les avantages et les limites de l'algorithme génétique, etc.

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

Avant de comprendre l'algorithme génétique, comprenons d'abord les terminologies de base pour mieux comprendre cet algorithme :

Population:La population est le sous-ensemble de toutes les solutions possibles ou probables qui peuvent résoudre un problème donné.Chromosomes :Un chromosome est l'une des solutions dans la population pour un problème donné, et la collection de gènes génère un chromosome.Gène:Un chromosome est divisé en un gène différent ou constitue un élément du chromosome.Allèles :L'allèle est la valeur fournie au gène dans un chromosome particulier.Fonction de remise en forme:La fonction condition physique est utilisée pour déterminer le niveau de condition physique d’un individu dans la population. Cela signifie la capacité d’un individu à rivaliser avec d’autres individus. À chaque itération, les individus sont évalués en fonction de leur fonction de condition physique.Opérateurs génétiques :Dans un algorithme génétique, le meilleur individu s'accouple pour régénérer sa progéniture mieux que ses parents. Ici, les opérateurs génétiques jouent un rôle dans la modification de la composition génétique de la génération suivante.Sélection

Après avoir calculé l'aptitude de chaque élément de la population, un processus de sélection est utilisé pour déterminer laquelle des individualités de la population pourra se reproduire et produire la graine qui formera la génération à venir.

Types de styles de sélection disponibles

Sélection de roulette Sélection d'événements Sélection fondée sur le rang

Nous pouvons donc désormais définir un algorithme génétique comme un algorithme de recherche heuristique pour résoudre des problèmes d’optimisation. Il s’agit d’un sous-ensemble d’algorithmes évolutifs utilisés en informatique. Un algorithme génétique utilise les concepts de génétique et de sélection naturelle pour résoudre des problèmes d'optimisation.

Comment fonctionne l’algorithme génétique ?

L'algorithme génétique travaille sur le cycle générationnel évolutif pour générer des solutions de haute qualité. Ces algorithmes utilisent différentes opérations qui améliorent ou remplacent la population pour donner une solution d'ajustement améliorée.

Il s'agit essentiellement de cinq phases pour résoudre les problèmes d'optimisation complexes, qui sont indiqués ci-dessous :

Initialisation Devoir de remise en forme Sélection la reproduction Résiliation

1. Initialisation

Le processus d’un algorithme génétique commence par générer un ensemble d’individus, appelé population. Ici, chaque individu est la solution au problème posé. Un individu contient ou est caractérisé par un ensemble de paramètres appelés gènes. Les gènes sont combinés en une chaîne et génèrent des chromosomes, ce qui constitue la solution au problème. L’une des techniques d’initialisation les plus populaires consiste à utiliser des chaînes binaires aléatoires.

2. Devoir de remise en forme

La fonction fitness est-elle utilisée pour déterminer la forme physique d'un individu ? Cela signifie la capacité d’un individu à rivaliser avec d’autres individus. À chaque itération, les individus sont évalués en fonction de leur fonction de condition physique. La fonction fitness fournit un score de condition physique à chaque individu. Ce score détermine en outre la probabilité d'être sélectionné pour la reproduction. Plus le score de condition physique est élevé, plus il y a de chances d'être sélectionné pour la reproduction.

3. Sélection

La phase de sélection implique la sélection d'individus pour la reproduction de la progéniture. Tous les individus sélectionnés sont ensuite disposés par paire de deux pour augmenter la reproduction. Ces individus transmettent ensuite leurs gènes à la génération suivante.

Il existe trois types de méthodes de sélection disponibles, à savoir :

• Sélection de roulette
• Sélection du tournoi
• Sélection basée sur le classement

4. Reproduction

Après le processus de sélection, la création d’un enfant a lieu lors de l’étape de reproduction. Dans cette étape, l'algorithme génétique utilise deux opérateurs de variation appliqués à la population parente. Les deux opérateurs impliqués dans la phase de reproduction sont donnés ci-dessous :

Croisement :Le croisement joue un rôle très important dans la phase de reproduction de l’algorithme génétique. Dans ce processus, un point de croisement est sélectionné au hasard au sein des gènes. Ensuite, l'opérateur de croisement échange les informations génétiques de deux parents de la génération actuelle pour produire un nouvel individu représentant la progéniture.

Les gènes des parents sont échangés entre eux jusqu'à ce que le point de croisement soit atteint. Ces descendants nouvellement générés s'ajoutent à la population. Ce processus est également appelé ou crossover. Types de styles de croisement disponibles :
• Crossover à un point
• Croisement à deux points
• Crossover de livrée
• Crossover d’algorithmes héritables
Mutation
L'opérateur de mutation insère des gènes aléatoires dans la progéniture (nouvel enfant) pour maintenir la diversité de la population. Cela peut être fait en retournant certains bits des chromosomes.
La mutation aide à résoudre le problème de la convergence prématurée et améliore la diversification. L'image ci-dessous montre le processus de mutation :
Types de styles de mutation disponibles,
Mutation du bit inversé Mutation gaussienne Mutation d'échange/échange

5. Résiliation

Après la phase de reproduction, un critère d'arrêt est appliqué comme base de terminaison. L’algorithme se termine une fois que la solution de fitness seuil est atteinte. Il identifiera la solution finale comme la meilleure solution parmi la population.

Flux de travail général d'un algorithme génétique simple

Avantages de l'algorithme génétique

• Les capacités parallèles des algorithmes génétiques sont les meilleures.
• Il aide à optimiser divers problèmes tels que les fonctions discrètes, les problèmes multi-objectifs et les fonctions continues.
• Il fournit une solution à un problème qui s’améliore avec le temps.
• Un algorithme génétique n'a pas besoin d'informations dérivées.

Limites des algorithmes génétiques

• Les algorithmes génétiques ne sont pas des algorithmes efficaces pour résoudre des problèmes simples.
• Cela ne garantit pas la qualité de la solution finale à un problème.
• Le calcul répétitif des valeurs de condition physique peut générer certains défis informatiques.

Différence entre les algorithmes génétiques et les algorithmes traditionnels

• Un espace de recherche est l’ensemble de toutes les solutions possibles au problème. Dans l’algorithme traditionnel, un seul ensemble de solutions est conservé, alors que dans un algorithme génétique, plusieurs ensembles de solutions dans l’espace de recherche peuvent être utilisés.
• Les algorithmes traditionnels ont besoin de plus d’informations pour effectuer une recherche, alors que les algorithmes génétiques n’ont besoin que d’une seule fonction objective pour calculer l’aptitude d’un individu.
• Les algorithmes traditionnels ne peuvent pas fonctionner en parallèle, alors que les algorithmes génétiques peuvent fonctionner en parallèle (le calcul de l'aptitude des individualités est indépendant).
• Une grande différence dans les algorithmes génétiques est qu'au lieu d'opérer directement sur les résultats du chercheur, les algorithmes héritables opèrent sur leurs représentations (ou rendus), souvent appelées chromosomes.
• L’une des grandes différences entre l’algorithme traditionnel et l’algorithme génétique est qu’il n’opère pas directement sur les solutions candidates.
• Les algorithmes traditionnels ne peuvent générer qu'un seul résultat à la fin, tandis que les algorithmes génétiques peuvent générer plusieurs résultats optimaux provenant de différentes générations.
• L'algorithme traditionnel n'est pas plus susceptible de générer des résultats optimaux, alors que les algorithmes génétiques ne garantissent pas de générer des résultats globaux optimaux, mais il existe également une grande possibilité d'obtenir le résultat optimal pour un problème car ils utilisent des opérateurs génétiques tels que Crossover et Mutation.
• Les algorithmes traditionnels sont de nature déterministe, tandis que les algorithmes génétiques sont de nature probabiliste et stochastique.