Algorithmes génétiques - Guide rapide

L'algorithme génétique (GA) est une technique d'optimisation basée sur la recherche basée sur les principes de Genetics and Natural Selection. Il est fréquemment utilisé pour trouver des solutions optimales ou quasi optimales à des problèmes difficiles qui autrement prendraient toute une vie à résoudre. Il est fréquemment utilisé pour résoudre des problèmes d'optimisation, dans la recherche et dans l'apprentissage automatique.

Introduction à l'optimisation

L'optimisation est le processus de making something better. Dans tout processus, nous avons un ensemble d'entrées et un ensemble de sorties comme indiqué dans la figure suivante.

L'optimisation fait référence à la recherche des valeurs des entrées de manière à obtenir les «meilleures» valeurs de sortie. La définition du «meilleur» varie d'un problème à l'autre, mais en termes mathématiques, elle se réfère à la maximisation ou à la minimisation d'une ou plusieurs fonctions objectives, en faisant varier les paramètres d'entrée.

L'ensemble de toutes les solutions ou valeurs possibles que les entrées peuvent prendre constitue l'espace de recherche. Dans cet espace de recherche, se trouve un point ou un ensemble de points qui donne la solution optimale. Le but de l'optimisation est de trouver ce point ou cet ensemble de points dans l'espace de recherche.

Que sont les algorithmes génétiques?

La nature a toujours été une grande source d'inspiration pour toute l'humanité. Les algorithmes génétiques (AG) sont des algorithmes basés sur la recherche basés sur les concepts de sélection naturelle et de génétique. Les GA sont un sous-ensemble d'une branche beaucoup plus vaste du calcul connue sous le nom deEvolutionary Computation.

Les GA ont été développés par John Holland et ses étudiants et collègues de l'Université du Michigan, notamment David E. Goldberg, et ont depuis été essayés sur divers problèmes d'optimisation avec un haut degré de succès.

Dans les GA, nous avons un pool or a population of possible solutionsau problème donné. Ces solutions subissent ensuite une recombinaison et une mutation (comme dans la génétique naturelle), produisant de nouveaux enfants, et le processus se répète sur différentes générations. Chaque individu (ou solution candidate) se voit attribuer une valeur de fitness (basée sur sa valeur de fonction objective) et les individus en meilleure forme ont une plus grande chance de s'accoupler et de produire des individus plus «en forme». Ceci est conforme à la théorie darwinienne de la «survie du plus apte».

De cette façon, nous continuons à «faire évoluer» de meilleurs individus ou solutions au fil des générations, jusqu'à ce que nous atteignions un critère d'arrêt.

Les algorithmes génétiques sont de nature suffisamment aléatoire, mais ils fonctionnent bien mieux que la recherche locale aléatoire (dans laquelle nous essayons simplement diverses solutions aléatoires, en gardant une trace des meilleures à ce jour), car ils exploitent également les informations historiques.

Avantages des AG

Les AG présentent divers avantages qui les ont rendus extrêmement populaires. Ceux-ci comprennent -

  • Ne nécessite aucune information dérivée (qui peut ne pas être disponible pour de nombreux problèmes du monde réel).

  • Est plus rapide et plus efficace par rapport aux méthodes traditionnelles.

  • Possède de très bonnes capacités parallèles.

  • Optimise les fonctions continues et discrètes ainsi que les problèmes multi-objectifs.

  • Fournit une liste de «bonnes» solutions et pas seulement une solution unique.

  • Obtient toujours une réponse au problème, qui s'améliore avec le temps.

  • Utile lorsque l'espace de recherche est très grand et qu'un grand nombre de paramètres sont impliqués.

Limitations des GA

Comme toute technique, les GA souffrent également de quelques limitations. Ceux-ci comprennent -

  • Les GA ne conviennent pas à tous les problèmes, en particulier aux problèmes simples et pour lesquels des informations dérivées sont disponibles.

  • La valeur de la forme physique est calculée à plusieurs reprises, ce qui peut être coûteux en calcul pour certains problèmes.

  • Étant stochastique, il n'y a aucune garantie sur l'optimalité ou la qualité de la solution.

  • S'il n'est pas mis en œuvre correctement, l'AG peut ne pas converger vers la solution optimale.

GA - Motivation

Les algorithmes génétiques ont la capacité de fournir une solution «assez bonne» «assez rapide». Cela rend les algorithmes génétiques intéressants pour une utilisation dans la résolution de problèmes d'optimisation. Les raisons pour lesquelles les AG sont nécessaires sont les suivantes:

Résolution de problèmes difficiles

En informatique, il existe un grand nombre de problèmes, qui sont NP-Hard. Cela signifie essentiellement que même les systèmes informatiques les plus puissants prennent beaucoup de temps (voire des années!) Pour résoudre ce problème. Dans un tel scénario, les AG se révèlent être un outil efficace pour fournirusable near-optimal solutions dans un court laps de temps.

Échec des méthodes basées sur le gradient

Les méthodes traditionnelles basées sur le calcul fonctionnent en commençant à un point aléatoire et en se déplaçant dans la direction du gradient, jusqu'à ce que nous atteignions le sommet de la colline. Cette technique est efficace et fonctionne très bien pour les fonctions d'objectif à pic unique comme la fonction de coût dans la régression linéaire. Mais, dans la plupart des situations du monde réel, nous avons un problème très complexe appelé paysages, qui sont constitués de nombreux sommets et de nombreuses vallées, ce qui entraîne l'échec de ces méthodes, car elles souffrent d'une tendance inhérente à se coincer dans les optima locaux. comme indiqué dans la figure suivante.

Obtenir rapidement une bonne solution

Certains problèmes difficiles comme le problème du voyageur de commerce (TSP), ont des applications dans le monde réel comme la recherche de chemin et la conception VLSI. Imaginez maintenant que vous utilisez votre système de navigation GPS et que le calcul du chemin «optimal» de la source à la destination prend quelques minutes (voire quelques heures). Le retard dans de telles applications du monde réel n'est pas acceptable et donc une solution «assez bonne», qui est livrée «rapidement» est ce qui est nécessaire.

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énotype et génotype sont différents. Le décodage est un processus de transformation d'une solution du génotype à l'espace phénotypique, 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 avec 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

L'une des décisions les plus importantes à prendre lors de la mise en œuvre d'un algorithme génétique est de décider de la représentation que nous utiliserons pour représenter nos solutions. Il a été observé qu'une représentation incorrecte peut conduire à une mauvaise performance de l'AG.

Par conséquent, le choix d'une représentation appropriée, ayant une définition appropriée des mappages entre les espaces phénotype et génotype est essentiel pour le succès d'une AG.

Dans cette section, nous présentons certaines des représentations les plus couramment utilisées pour les algorithmes génétiques. Cependant, la représentation est très spécifique au problème et le lecteur peut trouver qu'une autre représentation ou un mélange des représentations mentionnées ici pourrait mieux convenir à son problème.

Représentation binaire

C'est l'une des représentations les plus simples et les plus utilisées dans les GA. Dans ce type de représentation, le génotype est constitué de chaînes de bits.

Pour certains problèmes lorsque l'espace de solution est constitué de variables de décision booléennes - oui ou non, la représentation binaire est naturelle. Prenons par exemple le problème du sac à dos 0/1. S'il y a n éléments, nous pouvons représenter une solution par une chaîne binaire de n éléments, où le x ème élément indique si l'élément x est choisi (1) ou non (0).

Pour d'autres problèmes, en particulier ceux traitant des nombres, nous pouvons représenter les nombres avec leur représentation binaire. Le problème avec ce type de codage est que différents bits ont une signification différente et que, par conséquent, les opérateurs de mutation et de croisement peuvent avoir des conséquences indésirables. Cela peut être résolu dans une certaine mesure en utilisantGray Coding, car un changement en un seul bit n'a pas d'effet massif sur la solution.

Représentation réelle et valorisée

Pour les problèmes où nous voulons définir les gènes en utilisant des variables continues plutôt que discrètes, la représentation réelle valorisée est la plus naturelle. La précision de ces nombres réels ou à virgule flottante est cependant limitée à l'ordinateur.

Représentation entière

Pour les gènes à valeurs discrètes, nous ne pouvons pas toujours limiter l'espace de solution au binaire «oui» ou «non». Par exemple, si nous voulons encoder les quatre distances - Nord, Sud, Est et Ouest, nous pouvons les encoder comme{0,1,2,3}. Dans de tels cas, une représentation entière est souhaitable.

Représentation par permutation

Dans de nombreux problèmes, la solution est représentée par un ordre d'éléments. Dans de tels cas, la représentation par permutation est la plus appropriée.

Un exemple classique de cette représentation est le problème du voyageur de commerce (TSP). En cela, le vendeur doit faire le tour de toutes les villes, visiter chaque ville exactement une fois et revenir à la ville de départ. La distance totale du circuit doit être minimisée. La solution à ce TSP est naturellement un ordre ou une permutation de toutes les villes et donc l'utilisation d'une représentation par permutation a du sens pour ce problème.

La population est un sous-ensemble de solutions de la génération actuelle. Il peut également être défini comme un ensemble de chromosomes. Il y a plusieurs choses à garder à l'esprit lors du traitement de la population GA -

  • La diversité de la population devrait être maintenue, sinon elle pourrait conduire à une convergence prématurée.

  • La taille de la population ne doit pas être maintenue très grande car elle peut ralentir une AG, alors qu'une population plus petite peut ne pas être suffisante pour un bon pool d'accouplement. Par conséquent, une taille optimale de la population doit être décidée par essais et erreurs.

La population est généralement définie comme un tableau à deux dimensions de - size population, size x, chromosome size.

Initialisation de la population

Il existe deux méthodes principales pour initialiser une population dans un GA. Ils sont -

  • Random Initialization - Remplissez la population initiale avec des solutions complètement aléatoires.

  • Heuristic initialization - Remplissez la population initiale en utilisant une heuristique connue pour le problème.

Il a été observé que la population entière ne doit pas être initialisée à l'aide d'une heuristique, car cela peut amener la population à avoir des solutions similaires et très peu de diversité. Il a été observé expérimentalement que les solutions aléatoires sont celles qui conduisent la population à l'optimalité. Par conséquent, avec l'initialisation heuristique, nous semons simplement la population avec quelques bonnes solutions, remplissant le reste avec des solutions aléatoires plutôt que de remplir la population entière avec des solutions heuristiques.

On a également observé que l'initialisation heuristique dans certains cas, n'affecte que la fitness initiale de la population, mais en fin de compte, c'est la diversité des solutions qui conduit à l'optimalité.

Modèles de population

Il existe deux modèles de population largement utilisés -

Régime permanent

En GA à l'état d'équilibre, nous générons une ou deux rejetons à chaque itération et ils remplacent un ou deux individus de la population. Une GA à l'état d'équilibre est également connue sous le nom deIncremental GA.

Générationnel

Dans un modèle générationnel, nous générons «n» rejetons, où n est la taille de la population, et la population entière est remplacée par la nouvelle à la fin de l'itération.

La fonction fitness simplement définie est une fonction qui prend un candidate solution to the problem as input and produces as output à quel point la solution est-elle «bonne» par rapport au problème considéré.

Le calcul de la valeur de fitness est effectué à plusieurs reprises dans un GA et doit donc être suffisamment rapide. Un calcul lent de la valeur de fitness peut nuire à une GA et la rendre exceptionnellement lente.

Dans la plupart des cas, la fonction d'aptitude et la fonction objectif sont les mêmes que l'objectif est de maximiser ou de minimiser la fonction objective donnée. Cependant, pour des problèmes plus complexes aux objectifs et contraintes multiples, unAlgorithm Designer peut choisir d'avoir une fonction de remise en forme différente.

Une fonction de remise en forme doit posséder les caractéristiques suivantes -

  • La fonction de fitness doit être suffisamment rapide pour être calculée.

  • Il doit mesurer quantitativement l'adéquation d'une solution donnée ou la manière dont les individus peuvent être produits à partir de la solution donnée.

Dans certains cas, le calcul direct de la fonction de fitness peut ne pas être possible en raison des complexités inhérentes au problème en question. Dans de tels cas, nous effectuons une approximation de la condition physique pour répondre à nos besoins.

L'image suivante montre le calcul de la condition physique pour une solution du sac à dos 0/1. Il s'agit d'une simple fonction de remise en forme qui additionne simplement les valeurs de profit des articles sélectionnés (qui ont un 1), en balayant les éléments de gauche à droite jusqu'à ce que le sac à dos soit plein.

La sélection des parents est le processus de sélection des parents qui s'accouplent et se recombinent pour créer des rejetons pour la prochaine génération. La sélection des parents est très cruciale pour le taux de convergence de l'AG, car les bons parents poussent les individus vers des solutions meilleures et plus adaptées.

Cependant, il faut veiller à éviter qu'une solution extrêmement adaptée ne prenne en charge l'ensemble de la population en quelques générations, car cela conduit à des solutions proches les unes des autres dans l'espace des solutions conduisant ainsi à une perte de diversité. Maintaining good diversitydans la population est extrêmement cruciale pour le succès d'une AG. Cette prise en charge de l'ensemble de la population par une solution extrêmement adaptée est connue sous le nom depremature convergence et est une condition indésirable dans une AG.

Sélection proportionnelle de la condition physique

La sélection proportionnelle de la condition physique est l'une des méthodes les plus populaires de sélection des parents. En cela, chaque individu peut devenir parent avec une probabilité proportionnelle à son aptitude. Par conséquent, les individus en meilleure forme ont plus de chances de s'accoupler et de propager leurs caractéristiques à la génération suivante. Par conséquent, une telle stratégie de sélection exerce une pression de sélection sur les individus les plus aptes de la population, en faisant évoluer de meilleurs individus au fil du temps.

Prenons une roue circulaire. La roue est divisée enn pies, où n est le nombre d'individus dans la population. Chaque individu reçoit une partie du cercle qui est proportionnelle à sa valeur de fitness.

Deux implémentations de la sélection proportionnelle de la condition physique sont possibles -

Sélection de la roulette

Dans une sélection de roue de roulette, la roue circulaire est divisée comme décrit précédemment. Un point fixe est choisi sur la circonférence de la roue comme illustré et la roue est tournée. La région de la roue qui vient devant le point fixe est choisie comme parent. Pour le deuxième parent, le même processus est répété.

Il est clair qu'un installateur a une plus grande tarte sur la roue et donc une plus grande chance d'atterrir devant le point fixe lors de la rotation de la roue. Par conséquent, la probabilité de choisir un individu dépend directement de son aptitude.

En ce qui concerne la mise en œuvre, nous utilisons les étapes suivantes -

  • Calculer S = la somme des finesses.

  • Génère un nombre aléatoire entre 0 et S.

  • En partant du haut de la population, continuez à ajouter les finesses à la somme partielle P, jusqu'à P <S.

  • L'individu pour lequel P dépasse S est l'individu choisi.

Échantillonnage universel stochastique (SUS)

L'échantillonnage universel stochastique est assez similaire à la sélection de la roulette, mais au lieu d'avoir un seul point fixe, nous avons plusieurs points fixes, comme indiqué dans l'image suivante. Par conséquent, tous les parents sont choisis en un seul tour de roue. En outre, une telle configuration encourage les personnes très aptes à être choisies au moins une fois.

Il est à noter que les méthodes de sélection proportionnelle à la forme physique ne fonctionnent pas dans les cas où la valeur physique peut prendre une valeur négative.

Sélection du tournoi

Dans la sélection des tournois K-Way, nous sélectionnons K individus de la population au hasard et sélectionnons les meilleurs parmi ceux-ci pour devenir parent. Le même processus est répété pour sélectionner le parent suivant. La sélection de tournois est également extrêmement populaire dans la littérature car elle peut même fonctionner avec des valeurs de fitness négatives.

Sélection de rang

La sélection de classement fonctionne également avec des valeurs de fitness négatives et est principalement utilisée lorsque les individus de la population ont des valeurs de fitness très proches (cela se produit généralement à la fin de la course). Cela conduit chaque individu à avoir une part presque égale de la tarte (comme dans le cas de la sélection proportionnelle de la forme physique) comme le montre l'image suivante et, par conséquent, chaque individu, quel que soit son ajustement les uns par rapport aux autres, a approximativement la même probabilité d'être sélectionné en tant que parent. Cela conduit à son tour à une perte de la pression de sélection envers les individus en meilleure forme, ce qui oblige l'AG à faire de mauvais choix de parents dans de telles situations.

En cela, nous supprimons le concept de valeur de fitness lors de la sélection d'un parent. Cependant, chaque individu de la population est classé en fonction de sa forme physique. La sélection des parents dépend du rang de chaque individu et non de la forme physique. Les personnes les mieux classées sont préférées aux personnes les moins bien classées.

Chromosome Valeur de remise en forme Rang
UNE 8.1 1
B 8,0 4
C 8,05 2
ré 7,95 6
E 8.02 3
F 7,99 5

Sélection aléatoire

Dans cette stratégie, nous sélectionnons au hasard les parents de la population existante. Il n'y a pas de pression de sélection envers les individus plus en forme et cette stratégie est donc généralement évitée.

Dans ce chapitre, nous discuterons de ce qu'est un opérateur Crossover avec ses autres modules, leurs utilisations et leurs avantages.

Introduction à Crossover

L'opérateur de croisement est analogue à la reproduction et au croisement biologique. Dans ce cas, plus d'un parent est sélectionné et une ou plusieurs descendants sont produits en utilisant le matériel génétique des parents. Le crossover est généralement appliqué dans un GA avec une probabilité élevée -pc .

Opérateurs de crossover

Dans cette section, nous discuterons de certains des opérateurs de croisement les plus couramment utilisés. Il est à noter que ces opérateurs de croisement sont très génériques et que le concepteur GA peut également choisir d'implémenter un opérateur de croisement spécifique au problème.

Crossover à un point

Dans ce croisement à un point, un point de croisement aléatoire est sélectionné et les queues de ses deux parents sont permutées pour obtenir de nouveaux ressorts.

Crossover multipoint

Le croisement multipoint est une généralisation du croisement à un point dans lequel des segments alternés sont permutés pour obtenir de nouveaux ressorts.

Crossover uniforme

Dans un croisement uniforme, nous ne divisons pas le chromosome en segments, nous traitons plutôt chaque gène séparément. En cela, nous lançons essentiellement une pièce pour chaque chromosome afin de décider s'il sera inclus ou non dans la progéniture. Nous pouvons également biaiser la pièce en faveur d'un parent, pour avoir plus de matériel génétique chez l'enfant de ce parent.

Recombinaison arithmétique entière

Ceci est couramment utilisé pour les représentations entières et fonctionne en prenant la moyenne pondérée des deux parents en utilisant les formules suivantes -

  • Enfant1 = α.x + (1-α) .y
  • Enfant2 = α.x + (1-α) .y

Évidemment, si α = 0,5, alors les deux enfants seront identiques, comme le montre l'image suivante.

Crossover de l'ordre de Davis (OX1)

OX1 est utilisé pour les croisements basés sur les permutations dans le but de transmettre des informations sur l'ordre relatif aux ressorts. Cela fonctionne comme suit -

  • Créez deux points de croisement aléatoires dans le parent et copiez le segment entre eux du premier parent à la première progéniture.

  • Maintenant, à partir du deuxième point de croisement dans le deuxième parent, copiez les nombres inutilisés restants du deuxième parent vers le premier enfant, en faisant le tour de la liste.

  • Répétez pour le deuxième enfant avec le rôle du parent inversé.

Il existe de nombreux autres croisements tels que le crossover partiellement mappé (PMX), le crossover basé sur l'ordre (OX2), le shuffle Crossover, le Ring Crossover, etc.

Introduction à la mutation

En termes simples, la mutation peut être définie comme une petite modification aléatoire du chromosome, pour obtenir une nouvelle solution. Il est utilisé pour maintenir et introduire la diversité dans la population génétique et est généralement appliqué avec une faible probabilité -pm. Si la probabilité est très élevée, l'AG se réduit à une recherche aléatoire.

La mutation est la partie de l'AG qui est liée à «l'exploration» de l'espace de recherche. Il a été observé que la mutation est essentielle à la convergence de l'AG alors que le croisement ne l'est pas.

Opérateurs de mutation

Dans cette section, nous décrivons certains des opérateurs de mutation les plus couramment utilisés. Comme les opérateurs de croisement, cette liste n'est pas exhaustive et le concepteur GA pourrait trouver une combinaison de ces approches ou un opérateur de mutation spécifique au problème plus utile.

Mutation de retournement de bits

Dans cette mutation de retournement de bits, nous sélectionnons un ou plusieurs bits aléatoires et les retournons. Ceci est utilisé pour les GA codés en binaire.

Réinitialisation aléatoire

La réinitialisation aléatoire est une extension du retournement de bits pour la représentation entière. En cela, une valeur aléatoire de l'ensemble des valeurs autorisées est attribuée à un gène choisi au hasard.

Changement de mutation

Dans swap mutation, nous sélectionnons deux positions sur le chromosome au hasard et échangeons les valeurs. Ceci est courant dans les codages basés sur la permutation.

Mutation de brouillage

La mutation de brouillage est également populaire avec les représentations de permutation. En cela, à partir du chromosome entier, un sous-ensemble de gènes est choisi et leurs valeurs sont brouillées ou mélangées au hasard.

Mutation d'inversion

Dans la mutation d'inversion, nous sélectionnons un sous-ensemble de gènes comme dans la mutation brouillée, mais au lieu de mélanger le sous-ensemble, nous inversons simplement la chaîne entière du sous-ensemble.

La politique de sélection des survivants détermine quelles personnes doivent être expulsées et lesquelles doivent être gardées dans la prochaine génération. Elle est cruciale car elle doit garantir que les individus les plus en forme ne soient pas expulsés de la population, tout en préservant la diversité de la population.

Certains GA emploient Elitism. En termes simples, cela signifie que le membre actuel le plus apte de la population est toujours propagé à la génération suivante. Par conséquent, en aucun cas le membre le plus apte de la population actuelle ne peut être remplacé.

La politique la plus simple consiste à expulser des membres aléatoires de la population, mais une telle approche pose souvent des problèmes de convergence, c'est pourquoi les stratégies suivantes sont largement utilisées.

Sélection basée sur l'âge

Dans la sélection basée sur l'âge, nous n'avons pas de notion de forme physique. Il est basé sur la prémisse que chaque individu est autorisé dans la population pendant une génération finie où il est autorisé à se reproduire, après cela, il est expulsé de la population, quelle que soit sa forme physique.

Par exemple, dans l'exemple suivant, l'âge est le nombre de générations pour lesquelles l'individu a fait partie de la population. Les membres les plus âgés de la population, c'est-à-dire P4 et P7, sont expulsés de la population et l'âge du reste des membres est incrémenté de un.

Sélection basée sur la condition physique

Dans cette sélection basée sur la condition physique, les enfants ont tendance à remplacer les individus les moins aptes de la population. La sélection des individus les moins aptes peut être effectuée en utilisant une variante de l'une quelconque des politiques de sélection décrites précédemment - sélection de tournoi, sélection proportionnée à la forme physique, etc.

Par exemple, dans l'image suivante, les enfants remplacent les individus les moins aptes P1 et P10 de la population. Il est à noter que puisque P1 et P9 ont la même valeur de fitness, la décision de retirer quel individu de la population est arbitraire.

La condition de fin d'un algorithme génétique est importante pour déterminer quand une analyse GA prendra fin. Il a été observé qu'au départ, l'AG progresse très rapidement avec de meilleures solutions à chaque quelques itérations, mais cela a tendance à saturer dans les étapes ultérieures où les améliorations sont très faibles. Nous voulons généralement une condition de terminaison telle que notre solution soit proche de l'optimum, à la fin de l'analyse.

Habituellement, nous conservons l'une des conditions de résiliation suivantes -

  • Lorsqu'il n'y a pas eu d'amélioration de la population pour X itérations.
  • Lorsque nous atteignons un nombre absolu de générations.
  • Lorsque la valeur de la fonction objectif a atteint une certaine valeur prédéfinie.

Par exemple, dans un algorithme génétique, nous gardons un compteur qui garde la trace des générations pour lesquelles il n'y a pas eu d'amélioration de la population. Au départ, nous mettons ce compteur à zéro. Chaque fois que nous ne générons pas de rejetons meilleurs que les individus de la population, nous incrémentons le compteur.

Cependant, si la forme physique de l'un des rejetons est meilleure, nous remettons le compteur à zéro. L'algorithme se termine lorsque le compteur atteint une valeur prédéterminée.

Comme d'autres paramètres d'un GA, la condition de terminaison est également très spécifique au problème et le concepteur GA devrait essayer diverses options pour voir ce qui convient le mieux à son problème particulier.

Jusqu'à présent dans ce tutoriel, tout ce que nous avons discuté correspond au modèle darwinien de l'évolution - sélection naturelle et variation génétique par recombinaison et mutation. Dans la nature, seules les informations contenues dans le génotype de l'individu peuvent être transmises à la génération suivante. C'est l'approche que nous avons suivie dans le tutoriel jusqu'à présent.

Cependant, d'autres modèles d'adaptation à vie - Lamarckian Model et Baldwinian Modelexistent également. Il est à noter que le modèle qui est le meilleur est ouvert au débat et les résultats obtenus par les chercheurs montrent que le choix de l'adaptation à vie est très spécifique au problème.

Souvent, nous hybridons une GA avec une recherche locale - comme dans les algorithmes mémétiques. Dans de tels cas, on peut choisir d'utiliser le modèle lamarckien ou baldwinien pour décider quoi faire des individus générés après la recherche locale.

Modèle lamarckien

Le modèle lamarckien dit essentiellement que les traits qu'un individu acquiert au cours de sa vie peuvent être transmis à sa progéniture. Il porte le nom du biologiste français Jean-Baptiste Lamarck.

Même si la biologie naturelle a complètement ignoré le lamarckisme car nous savons tous que seules les informations du génotype peuvent être transmises. Cependant, du point de vue du calcul, il a été montré que l'adoption du modèle lamarckien donne de bons résultats pour certains des problèmes.

Dans le modèle lamarckien, un opérateur de recherche locale examine le voisinage (en acquérant de nouveaux traits), et si un meilleur chromosome est trouvé, il devient la progéniture.

Modèle baldwinien

Le modèle baldwinien est une idée intermédiaire du nom de James Mark Baldwin (1896). Dans le modèle Baldwin, les chromosomes peuvent coder une tendance à apprendre des comportements bénéfiques. Cela signifie que, contrairement au modèle lamarckien, nous ne transmettons pas les traits acquis à la génération suivante, et nous n'ignorons pas non plus complètement les traits acquis comme dans le modèle darwinien.

Le modèle Baldwin se situe au milieu de ces deux extrêmes, dans lesquels la tendance d'un individu à acquérir certains traits est codée plutôt que les traits eux-mêmes.

Dans ce modèle baldwinien, un opérateur de recherche local examine le voisinage (en acquérant de nouveaux traits), et si un meilleur chromosome est trouvé, il attribue uniquement la forme améliorée au chromosome et ne modifie pas le chromosome lui-même. Le changement d'aptitude signifie la capacité des chromosomes à «acquérir le caractère», même s'il n'est pas transmis directement aux générations futures.

Les GA sont de nature très générale et leur simple application à un problème d'optimisation ne donnerait pas de bons résultats. Dans cette section, nous décrivons quelques points qui pourraient aider et aider un concepteur GA ou un réalisateur GA dans leur travail.

Introduire la connaissance du domaine spécifique au problème

Il a été observé que la connaissance du domaine plus spécifique au problème que nous incorporons dans l'AG; les meilleures valeurs objectives que nous obtenons. L'ajout d'informations spécifiques au problème peut être effectué en utilisant des opérateurs de croisement ou de mutation spécifiques au problème, des représentations personnalisées, etc.

L'image suivante montre le point de vue de Michalewicz (1990) sur l'EE -

Réduisez l'encombrement

Le surpeuplement se produit lorsqu'un chromosome parfaitement adapté se reproduit beaucoup et, en quelques générations, toute la population est remplie de solutions similaires ayant une aptitude similaire. Cela réduit la diversité qui est un élément très crucial pour assurer le succès d'une AG. Il existe de nombreuses façons de limiter la surpopulation. Certains d'entre eux sont -

  • Mutation pour introduire la diversité.

  • Passer à rank selection et tournament selection qui ont plus de pression de sélection que la sélection proportionnelle à la forme physique pour les individus ayant une forme physique similaire.

  • Fitness Sharing - Dans ce cas, la condition physique d'un individu est réduite si la population contient déjà des individus similaires.

La randomisation aide!

Il a été observé expérimentalement que les meilleures solutions sont tirées par des chromosomes randomisés car ils confèrent une diversité à la population. L'exécutant de l'AG doit veiller à conserver une quantité suffisante de randomisation et de diversité dans la population pour obtenir les meilleurs résultats.

Hybrider GA avec la recherche locale

La recherche locale consiste à vérifier les solutions au voisinage d'une solution donnée pour rechercher de meilleures valeurs objectives.

Il peut être parfois utile d'hybrider l'AG avec la recherche locale. L'image suivante montre les différents endroits dans lesquels la recherche locale peut être introduite dans une GA.

Variation des paramètres et techniques

Dans les algorithmes génétiques, il n'y a pas de «taille unique» ou de formule magique qui fonctionne pour tous les problèmes. Même une fois que l'AG initiale est prête, il faut beaucoup de temps et d'efforts pour jouer avec les paramètres tels que la taille de la population, la mutation et la probabilité de croisement, etc. pour trouver ceux qui conviennent au problème particulier.

Dans cette section, nous présentons quelques sujets avancés sur les algorithmes génétiques. Un lecteur à la recherche d'une simple introduction aux GA peut choisir de sauter cette section.

Problèmes d'optimisation contraints

Les problèmes d'optimisation sous contrainte sont les problèmes d'optimisation dans lesquels nous devons maximiser ou minimiser une valeur de fonction objective donnée soumise à certaines contraintes. Par conséquent, tous les résultats dans l'espace de solution ne sont pas réalisables, et l'espace de solution contient des régions réalisables, comme illustré dans l'image suivante.

Dans un tel scénario, les opérateurs de croisement et de mutation pourraient nous apporter des solutions irréalisables. Par conséquent, des mécanismes supplémentaires doivent être utilisés dans l'AG pour traiter des problèmes d'optimisation contraints.

Certaines des méthodes les plus courantes sont -

  • En utilisant penalty functions qui réduit l'adéquation des solutions irréalisables, de préférence de sorte que l'adéquation soit réduite proportionnellement au nombre de contraintes violées ou à la distance de la région faisable.

  • En utilisant repair functions qui prennent une solution irréalisable et la modifient pour que les contraintes violées soient satisfaites.

  • Not allowing infeasible solutions entrer dans la population du tout.

  • Utiliser un special representation or decoder functions qui garantit la faisabilité des solutions.

Contexte théorique de base

Dans cette section, nous discuterons du schéma et du théorème de la NFL ainsi que de l'hypothèse du bloc de construction.

Théorème de schéma

Les chercheurs ont essayé de comprendre les mathématiques derrière le fonctionnement des algorithmes génétiques, et le théorème de schéma de Holland est un pas dans cette direction. Au cours de l'année, diverses améliorations et suggestions ont été apportées au théorème de schéma pour le rendre plus général.

Dans cette section, nous ne nous plongerons pas dans les mathématiques du théorème de schéma, nous essayons plutôt de développer une compréhension de base de ce qu'est le théorème de schéma. La terminologie de base à connaître est la suivante -

  • UNE Schemaest un «modèle». Formellement, c'est une chaîne sur l'alphabet = {0,1, *},

    où * est indifférent et peut prendre n'importe quelle valeur.

    Par conséquent, * 10 * 1 pourrait signifier 01001, 01011, 11001 ou 11011

    Géométriquement, un schéma est un hyperplan dans l'espace de recherche de solution.

  • Order d'un schéma est le nombre de positions fixes spécifiées dans un gène.

  • Defining length est la distance entre les deux symboles fixes les plus éloignés du gène.

Le théorème de schéma stipule que ce schéma avec une aptitude supérieure à la moyenne, une longueur de définition courte et un ordre inférieur est plus susceptible de survivre au croisement et à la mutation.

Hypothèse de base

Les Building Blocks sont des schémas d'ordre bas, de faible longueur de définition avec la forme moyenne donnée ci-dessus. L'hypothèse des blocs de construction dit que ces blocs de construction servent de base au succès et à l'adaptation de l'AG dans les AG à mesure qu'il progresse en identifiant et en recombinant successivement ces «blocs de construction».

No Free Lunch (NFL) Théorème

Wolpert et Macready ont publié en 1997 un article intitulé «Aucun théorème de déjeuner gratuit pour l'optimisation». Il déclare essentiellement que si nous faisons la moyenne sur l'espace de tous les problèmes possibles, alors tous les algorithmes de boîte noire non revisitant présenteront les mêmes performances.

Cela signifie que plus nous comprenons un problème, notre GA devient plus spécifique au problème et donne de meilleures performances, mais il compense cela en fonctionnant mal pour d'autres problèmes.

Apprentissage automatique basé sur GA

Les algorithmes génétiques trouvent également une application dans l'apprentissage automatique. Classifier systems sont une forme de genetics-based machine learning(GBML) fréquemment utilisé dans le domaine de l'apprentissage automatique. Les méthodes GBML sont une approche de niche de l'apprentissage automatique.

Il existe deux catégories de systèmes GBML -

  • The Pittsburg Approach - Dans cette approche, un chromosome a codé une solution, et ainsi la forme physique est attribuée aux solutions.

  • The Michigan Approach - une solution est généralement représentée par de nombreux chromosomes et la forme physique est donc attribuée à des solutions partielles.

Il faut garder à l'esprit que les problèmes standard tels que le croisement, la mutation, le lamarckien ou le darwinien, etc. sont également présents dans les systèmes GBML.

Les algorithmes génétiques sont principalement utilisés dans les problèmes d'optimisation de divers types, mais ils sont également fréquemment utilisés dans d'autres domaines d'application.

Dans cette section, nous énumérons certains des domaines dans lesquels les algorithmes génétiques sont fréquemment utilisés. Ce sont -

  • Optimization- Les algorithmes génétiques sont les plus couramment utilisés dans les problèmes d'optimisation dans lesquels nous devons maximiser ou minimiser une valeur de fonction objective donnée sous un ensemble donné de contraintes. L'approche pour résoudre les problèmes d'optimisation a été mise en évidence tout au long du didacticiel.

  • Economics - Les GA sont également utilisés pour caractériser divers modèles économiques comme le modèle de la toile d'araignée, la résolution d'équilibre de la théorie des jeux, la tarification des actifs, etc.

  • Neural Networks - Les GA sont également utilisés pour entraîner les réseaux de neurones, en particulier les réseaux de neurones récurrents.

  • Parallelization - Les AG ont également de très bonnes capacités parallèles, se révèlent être des moyens très efficaces pour résoudre certains problèmes, et constituent également un bon domaine de recherche.

  • Image Processing - Les GA sont utilisés pour diverses tâches de traitement d'image numérique (DIP) ainsi que pour la correspondance dense de pixels.

  • Vehicle routing problems - Avec plusieurs fenêtres horaires souples, plusieurs dépôts et une flotte hétérogène.

  • Scheduling applications - Les GA sont également utilisés pour résoudre divers problèmes d'ordonnancement, en particulier le problème de dépôt de temps.

  • Machine Learning - comme déjà discuté, l'apprentissage automatique basé sur la génétique (GBML) est un domaine de niche dans l'apprentissage automatique.

  • Robot Trajectory Generation - Les GA ont été utilisés pour planifier le chemin emprunté par un bras de robot en se déplaçant d'un point à un autre.

  • Parametric Design of Aircraft - Les GA ont été utilisés pour concevoir des avions en faisant varier les paramètres et en développant de meilleures solutions.

  • DNA Analysis - Les GA ont été utilisés pour déterminer la structure de l'ADN en utilisant des données spectrométriques sur l'échantillon.

  • Multimodal Optimization - Les GA sont évidemment de très bonnes approches d'optimisation multimodale dans lesquelles il faut trouver de multiples solutions optimales.

  • Traveling salesman problem and its applications - Les GA ont été utilisés pour résoudre le TSP, qui est un problème combinatoire bien connu utilisant de nouvelles stratégies de croisement et de compactage.

Les livres suivants peuvent être consultés pour améliorer davantage les connaissances du lecteur sur les algorithmes génétiques et le calcul évolutif en général -

  • Algorithmes génétiques dans la recherche, l'optimisation et l'apprentissage automatique par David E. Goldberg.

  • Algorithmes génétiques + structures de données = programmes évolutifs par Zbigniew Michalewicz.

  • Algorithmes génétiques pratiques par Randy L. Haupt et Sue Ellen Haupt.

  • Optimisation multi-objectifs à l'aide d'algorithmes évolutifs par Kalyanmoy Deb.