Introduction aux algorithmes génétiques dans l'apprentissage automatique

introduction genetic algorithms machine learning

quel est le meilleur logiciel de base de données

Ce didacticiel sur les algorithmes génétiques explique en détail ce que sont les algorithmes génétiques et leur rôle dans l'apprentissage automatique :

Dans le Tutoriel précédent , nous avons découvert les modèles de réseaux de neurones artificiels - Perceptron multicouche, rétropropagation, polarisation radiale et cartes auto-organisées de Kohonen, y compris leur architecture.

Nous nous concentrerons sur les algorithmes génétiques qui étaient bien avant les réseaux de neurones, mais maintenant GA a été repris par NN. Bien que GA ait encore des applications dans la vie réelle, telles que des problèmes d'optimisation tels que la planification, les jeux, la robotique, la conception de matériel, les problèmes de vendeur itinérant, etc.

Les algorithmes génétiques sont des algorithmes basés sur l'idée évolutive de la sélection naturelle et de la génétique. Les GA sont des algorithmes de recherche heuristique adaptatifs, c'est-à-dire que les algorithmes suivent un modèle itératif qui change avec le temps. C'est un type d'apprentissage par renforcement où la rétroaction est nécessaire sans indiquer le bon chemin à suivre. La rétroaction peut être positive ou négative.

=> Lisez la série complète de formations sur l'apprentissage automatique

Ce que vous apprendrez:

• Pourquoi utiliser des algorithmes génétiques
  • Contexte biologique des algorithmes génétiques
• Quels sont les algorithmes génétiques
  • Corrélation d'un chromosome avec GA
  • Terminologie importante en GA
  • Un algorithme génétique simple
  • Méthode de sélection de la roulette
  • Autres méthodes de sélection
  • Crossover
  • Mutation
  • Quand arrêter l'algorithme génétique
• Avantages et inconvénients de l'algorithme génétique
• Applications des algorithmes génétiques
• Conclusion
  • lecture recommandée

Pourquoi utiliser des algorithmes génétiques

Les GA sont des algorithmes plus robustes qui peuvent être utilisés pour divers problèmes d'optimisation. Ces algorithmes ne s'écartent pas facilement en présence de bruit, contrairement aux autres algorithmes d'IA. Les GA peuvent être utilisés dans la recherche d'un grand espace ou d'un espace multimodal.

Contexte biologique des algorithmes génétiques

La génétique est dérivée du mot grec «genèse» qui signifie grandir. La génétique décide des facteurs d'hérédité, des ressemblances et des différences entre les descendants en cours d'évolution. Les algorithmes génétiques sont également dérivés de l'évolution naturelle.

Quelques terminologies dans un chromosome biologique

• Chromosomes: Toutes les informations génétiques d'une espèce sont des chromosomes stockés.
• Gènes: Les chromosomes sont divisés en plusieurs parties appelées gènes.
• Allèles: Les gènes identifient la caractéristique d'un individu. La possibilité d'une combinaison de gènes pour former une propriété est appelée allèles. Un gène peut avoir différents allèles.
• Pool de gènes: Toutes les combinaisons possibles de gènes qui sont tous des allèles dans un pool de population sont appelées pool de gènes.
• Génome: L'ensemble des gènes d'une espèce s'appelle un génome.
• Lieu: Chaque gène a une position dans un génome appelé locus.
• Génotype: Une combinaison complète de gènes chez un individu est appelée le génotype.
• Phénotype: Un ensemble de génotypes sous une forme décodée est appelé le phénotype.

Quels sont les algorithmes génétiques

Les algorithmes génétiques stimulent le processus comme dans les systèmes naturels d'évolution. Charles Darwin a déclaré la théorie de l'évolution selon laquelle, dans l'évolution naturelle, les êtres biologiques évoluent selon le principe de «survie du plus apte». La recherche GA est conçue pour encourager la théorie de la «survie du plus apte».

Les GA effectuent une recherche aléatoire pour résoudre les problèmes d'optimisation. L'AG utilise des techniques qui utilisent les informations historiques précédentes pour orienter leur recherche vers l'optimisation dans le nouvel espace de recherche.

Corrélation d'un chromosome avec GA

Le corps humain possède des chromosomes constitués de gènes. Un ensemble de tous les gènes d'une espèce spécifique est appelé le génome. Chez les êtres vivants, les génomes sont stockés dans divers chromosomes tandis que dans GA tous les gènes sont stockés dans le même chromosome.

Comparaison entre l'évolution naturelle et la terminologie des algorithmes génétiques

Terminologie importante en GA

• Population: C'est un groupe d'individus. La population comprend le nombre d'individus testés, les informations sur l'espace de recherche et les paramètres phénotypiques. Généralement, la population est initialisée de manière aléatoire.
• Personnes: Les individus sont une solution unique en population. Un individu a un ensemble de paramètres appelés gènes. Gènes combinés pour former des chromosomes.
• Gènes: Les gènes sont des éléments constitutifs des algorithmes génétiques. Un chromosome est composé de gènes. Les gènes peuvent déterminer la solution au problème. Ils sont représentés par une chaîne de bits (0 ou 1) de longueur aléatoire.
• Aptitude: L’aptitude indique la valeur du phénotype du problème. La fonction fitness indique à quel point la solution est proche de la solution optimale. La fonction de remise en forme est déterminée de nombreuses manières, telles que la somme de tous les paramètres liés au problème - distance euclidienne, etc. Il n'y a pas de règle pour évaluer la fonction de fitness.

Un algorithme génétique simple

Un GA simple a une population de chromosomes individuels. Ces chromosomes représentent des solutions possibles. Les opérateurs de reproduction sont appliqués sur ces ensembles de chromosomes pour effectuer des mutations et des recombinaisons. Il est donc important de trouver des opérateurs de reproduction appropriés car le comportement de GA en dépend.

Un algorithme génétique simple est le suivant:

#1) Commencez par la population créée au hasard.

#deux) Calculez la fonction de fitness de chaque chromosome.

# 3) Répétez les étapes jusqu'à ce que n descendants soient créés. Les descendants sont créés comme indiqué ci-dessous.

• Sélectionnez une paire de chromosomes dans la population.
• Croisez la paire avec la probabilité p_cpour former des descendants.
• Faire muter le croisement avec la probabilité p_m.

# 4) Remplacez la population d'origine par la nouvelle population et passez à l'étape 2.

Voyons les étapes suivies dans ce processus d'itération. La population initiale de chromosomes est générée. La population initiale doit contenir suffisamment de gènes pour que toute solution puisse être générée. Le premier pool de population est généré de manière aléatoire.

• Sélection: Le meilleur ensemble de gènes est sélectionné en fonction de la fonction de remise en forme. La corde avec la meilleure fonction de fitness est choisie.
• La reproduction: Les nouveaux descendants sont générés par recombinaison et mutation.
• Évaluation: Les nouveaux chromosomes générés sont évalués pour leur aptitude.
• Remplacement: Dans cette étape, l'ancienne population est remplacée par la population nouvellement générée.

Méthode de sélection de la roulette

La sélection de la roulette est la méthode de sélection largement utilisée.

Le processus de sélection est court comme indiqué ci-dessous:

Dans cette méthode, une recherche linéaire est effectuée à travers la roue de roulette. Les fentes de la roue sont pesées en fonction de la valeur de fitness individuelle. La valeur cible est fixée de manière aléatoire en fonction de la proportion de la somme de la forme physique dans la population.

La population est ensuite recherchée jusqu'à ce que la valeur cible soit atteinte. Cette méthode ne garantit pas le plus apte des individus mais a une probabilité d'être le plus apte.

Voyons les étapes de la sélection de la roulette.

La valeur attendue d'un individu = Fitness / fitness individuel de la population. Les emplacements de roue sont attribués aux individus en fonction de leur forme physique. La roue est tournée N fois où N est le nombre total d'individus dans la population. Lorsqu'une rotation est terminée, la personne sélectionnée est placée dans un pool de parents.

1. Supposons que la valeur attendue totale d'un certain nombre d'individus de la population soit S.
2. Répétez les étapes 3 à 5 n fois.
3. Sélectionnez un entier s entre 0 et S.
4. Parcourez les individus de la population, additionnez les valeurs attendues jusqu'à ce que la somme soit supérieure à s.
5. L'individu dont la valeur attendue place la somme au-dessus de la limite s est sélectionné.

Inconvénients de la sélection de la roue de roulette:

1. Si la condition physique diffère beaucoup, la circonférence de la roue de roulette sera prise au maximum par le chromosome de la fonction de forme physique la plus élevée, de sorte que les autres ont très peu de chances d'être sélectionnés.
2. C'est bruyant.
3. L'évolution dépend de la variance de la forme physique de la population.

Autres méthodes de sélection

Il existe de nombreuses autres méthodes de sélection utilisées dans le 'Sélection' étape de l'algorithme génétique.

Nous discuterons des 2 autres méthodes largement utilisées:

# 1) Sélection de rang: Dans cette méthode, chaque chromosome reçoit une valeur de fitness à partir du classement. La pire forme physique est 1 et la meilleure forme physique est N. C'est une méthode de convergence lente. Dans cette méthode, la diversité est préservée conduisant à une recherche réussie.

Les parents potentiels sont sélectionnés, puis un tournoi est organisé pour décider lequel des individus sera un parent.

# 2) Sélection du tournoi: Dans cette méthode, une stratégie de pression sélective est appliquée à la population. Le meilleur individu est celui qui a la meilleure forme physique. Cet individu est le vainqueur de la compétition de tournoi parmi les individus Nu de la population.

La population du tournoi ainsi que le vainqueur sont à nouveau ajoutés dans le pool pour générer de nouveaux descendants. La différence entre les valeurs de forme physique du gagnant et des individus dans le bassin d'accouplement fournit une pression sélective pour des résultats optimaux.

Crossover

C'est un processus qui consiste à prendre 2 individus et à en produire un enfant. Le processus de reproduction après sélection fait des clones des bonnes piqûres. L'opérateur de croisement est appliqué sur les chaînes pour produire une meilleure progéniture.

La mise en œuvre de l'opérateur de croisement est la suivante:

1. Deux individus sont choisis au hasard dans la population pour produire des descendants.
2. Un site croisé est sélectionné au hasard sur la longueur de la chaîne.
3. Les valeurs sur le site sont permutées.

Le croisement effectué peut être un croisement à un point, un croisement à deux points, un croisement multipoint, etc. Le croisement à un point a un site de croisement tandis qu'un site de croisement à deux points a 2 sites où les valeurs sont permutées.

Nous pouvons le voir dans l'exemple ci-dessous:

Crossover à point unique

Crossover à deux points

Probabilité de croisement

P_c, la probabilité de croisement est le terme qui décrit la fréquence à laquelle le croisement sera effectué. Une probabilité de 0% signifie que les nouveaux chromosomes seront une copie exacte des anciens chromosomes, tandis qu'une probabilité de 100% signifie que tous les nouveaux chromosomes sont fabriqués par croisement.

Mutation

La mutation est effectuée après Crossover. Alors que le crossover se concentre uniquement sur la solution actuelle, l'opération de mutation recherche tout l'espace de recherche. Cette méthode consiste à récupérer les informations génétiques perdues et à diffuser les informations génétiques.

Cet opérateur permet de maintenir la diversité génétique de la population. Il aide à éviter les minima locaux et empêche de générer des solutions inutiles de toute population.

La mutation est réalisée de nombreuses manières telles que l'inversion de la valeur de chaque gène avec une faible probabilité ou n'effectue une mutation que si elle améliore la qualité de la solution.

Certains des moyens de mutation sont:

• Retournement: Changement de 0 à 1 ou de 1 à 0.
• Interchanger: Deux positions aléatoires sont choisies et les valeurs sont interchangées.
• Inversion: La position aléatoire est choisie et les bits à côté sont inversés.

Voyons quelques exemples de chacun:

Retournement

Interchanger

Inversion

Probabilité de mutation

P_m, la probabilité de mutation est un terme qui détermine la fréquence à laquelle les chromosomes seront mutés. Si la probabilité de mutation est de 100%, cela signifie que tout le chromosome est changé. Si aucune mutation n'est effectuée, une nouvelle progéniture est générée directement après le croisement.

Un exemple d'algorithme génétique général Probabilité de mutation: P_m, la probabilité de mutation est un terme qui détermine la fréquence à laquelle les chromosomes seront mutés. Si la probabilité de mutation est de 100%, cela signifie que tout le chromosome est changé.

Si aucune mutation n'est effectuée, alors la nouvelle progéniture est générée directement après le croisement. La population initiale de chromosomes est donnée par A, B, C, D. La taille de la population est de 4.

La fonction fitness est considérée comme un nombre de 1 dans la chaîne.

La somme de la forme physique est de 12, ce qui implique que la fonction de forme moyenne serait ~ 12/4 = 3

Probabilité de croisement = 0,7

Probabilité de mutation = 0,001

#1) Si B et C sont sélectionnés, le croisement n'est pas effectué car la valeur de fitness de C est inférieure à la fitness moyenne.

#deux) B est muté => B: 11101110 -> B^': 01101110 pour préserver la diversité de la population

# 3) B et D sont sélectionnés, le croisement est effectué.

B: 11101110 E: 10110100 -> D: 00110100 F: 01101110

# 4) Si E est muté, alors

E: 10110100 -> E^': 10110000

Les chromosomes correspondants sont indiqués dans le tableau ci-dessous. La commande est passée au hasard.

Bien que l'individu le plus en forme avec une valeur de forme physique de 6 soit perdu, la forme physique moyenne globale de la population augmente et serait: 14/4 = 3,5

Quand arrêter l'algorithme génétique

Un algorithme génétique est arrêté lorsque certaines conditions énumérées ci-dessous sont remplies:

# 1) Meilleure convergence individuelle: Lorsque le niveau de fitness minimum tombe en dessous de la valeur de convergence, l'algorithme est arrêté. Cela conduit à une convergence plus rapide.

# 2) Pire convergence individuelle: Lorsque les individus les moins aptes de la population atteignent une valeur de fitness minimale inférieure à la convergence, l'algorithme est alors arrêté. Dans cette méthode, la norme minimale de condition physique est maintenue dans la population. Cela signifie que le meilleur individu n'est pas garanti mais que les individus ayant une valeur de forme physique minimale seront présents.

# 3) Somme de la forme physique: Dans cette méthode, si la somme des aptitudes est inférieure ou égale à la valeur de convergence, la recherche est arrêtée. Il garantit que toute la population est dans la plage de fitness.

# 4) Fitness médian: Dans cette méthode, au moins la moitié des individus de la population sera meilleure ou égale à la valeur de convergence.

Certains critères de convergence ou conditions d'arrêt peuvent être:

• Lorsqu'un nombre spécifié de générations a évolué.
• Lorsque l'heure spécifiée pour exécuter l'algorithme a été atteinte.
• Lorsque la valeur de fitness de la population ne change plus avec les itérations.

Avantages et inconvénients de l'algorithme génétique

Les avantages d'un algorithme génétique sont:

1. Il dispose d'un espace de solution plus large.
2. Il est plus facile de découvrir l'optimum global.
3. Parallélisme: Plusieurs GA peuvent fonctionner ensemble en utilisant le même processeur sans interférer les uns avec les autres. Ils fonctionnent parallèlement dans l'isolement.

Limitations de GA:

1. L'identification de la fonction de fitness est une limitation.
2. La convergence des algorithmes peut être trop rapide ou trop lente.
3. Il existe une limitation de la sélection des paramètres tels que le croisement, la probabilité de mutation, la taille de la population, etc.

Applications des algorithmes génétiques

GA est efficace pour résoudre des problèmes de grande dimension. Une GA est effectivement utilisée lorsque l'espace de recherche est très grand, qu'il n'y a pas de techniques de résolution de problèmes mathématiques disponibles et que d'autres algorithmes de recherche traditionnels ne fonctionnent pas.

Certaines applications où GA est utilisé:

• Problème d'optimisation: L'un des meilleurs exemples de problèmes d'optimisation est le problème du vendeur de voyages qui utilise GA. D'autres problèmes d'optimisation tels que la planification des travaux, l'optimisation de la qualité sonore des GA sont largement utilisés.
• Modèle du système immunitaire: Les AG sont utilisés pour modéliser divers aspects du système immunitaire pour des familles individuelles de gènes et de gènes multiples au cours de l'évolution.
• Apprentissage automatique: Les GA ont été utilisés pour résoudre des problèmes liés à la classification, à la prédiction, créer des règles d'apprentissage et de classification .

Conclusion

Les algorithmes génétiques sont basés sur la méthode de l'évolution naturelle. Ces algorithmes sont différents des autres algorithmes de classification car ils utilisent des paramètres codés (0 ou 1), il y a plusieurs nombres d'individus dans une population et ils utilisent la méthode probabiliste de convergence.

Avec le processus de croisement et de mutation, les GA convergent à des générations successives. L'exécution d'un algorithme GA ne garantit pas toujours une solution réussie. Les algorithmes génétiques sont très efficaces dans l'optimisation - problèmes de planification des travaux.

J'espère que ce tutoriel aurait enrichi vos connaissances sur le concept d'algorithmes génétiques !!

=> Visitez ici pour la série exclusive d'apprentissage automatique

lecture recommandée

• Test basé sur un modèle utilisant un algorithme génétique
• Exploration de données Vs Machine Learning Vs Intelligence Artificielle Vs Deep Learning
• Tutoriel d'apprentissage automatique: Introduction au ML et à ses applications
• Types d'apprentissage automatique: apprentissage supervisé ou non supervisé
• Un guide complet du réseau neuronal artificiel dans l'apprentissage automatique
• 11 outils logiciels d'apprentissage automatique les plus populaires en 2021
• Top 13 des meilleures entreprises de machine learning (Liste 2021 mise à jour)
• Qu'est-ce que la machine vectorielle de support (SVM) dans l'apprentissage automatique