Algorithme génétique - Genetic algorithm

L' antenne du vaisseau spatial NASA ST5 de 2006 . Cette forme compliquée a été trouvée par un programme de conception informatique évolutif pour créer le meilleur diagramme de rayonnement. Il est connu comme une antenne évoluée .

En informatique et en recherche opérationnelle , un algorithme génétique ( AG ) est une métaheuristique inspirée du processus de sélection naturelle qui appartient à la classe plus large des algorithmes évolutionnaires (EA). Les algorithmes génétiques sont couramment utilisés pour générer des solutions de haute qualité aux problèmes d' optimisation et de recherche en s'appuyant sur des opérateurs biologiquement inspirés tels que la mutation , le croisement et la sélection .

Méthodologie

Problèmes d'optimisation

Dans un algorithme génétique, une population de solutions candidates (appelées individus, créatures ou phénotypes ) à un problème d'optimisation évolue vers de meilleures solutions. Chaque solution candidate possède un ensemble de propriétés (ses chromosomes ou génotype ) qui peuvent être mutées et altérées ; traditionnellement, les solutions sont représentées en binaire sous forme de chaînes de 0 et de 1, mais d'autres encodages sont également possibles.

L'évolution commence généralement à partir d'une population d'individus générés aléatoirement et est un processus itératif , la population à chaque itération étant appelée une génération . À chaque génération, l' aptitude de chaque individu de la population est évaluée ; la fitness est généralement la valeur de la fonction objectif dans le problème d'optimisation en cours de résolution. Les individus les plus en forme sont sélectionnés de manière stochastique dans la population actuelle, et le génome de chaque individu est modifié ( recombiné et éventuellement muté de manière aléatoire) pour former une nouvelle génération. La nouvelle génération de solutions candidates est ensuite utilisée dans l'itération suivante de l' algorithme . Généralement, l'algorithme se termine lorsqu'un nombre maximal de générations a été produit ou qu'un niveau de fitness satisfaisant a été atteint pour la population.

Un algorithme génétique typique nécessite :

  1. une représentation génétique du domaine de solution,
  2. une fonction de fitness pour évaluer le domaine de solution.

Une représentation standard de chaque solution candidate est un tableau de bits (également appelé ensemble de bits ou chaîne de bits ). Des réseaux d'autres types et structures peuvent être utilisés essentiellement de la même manière. La principale propriété qui rend ces représentations génétiques pratiques est que leurs parties sont facilement alignées en raison de leur taille fixe, ce qui facilite les opérations de croisement simples . Des représentations de longueur variable peuvent également être utilisées, mais la mise en œuvre croisée est plus complexe dans ce cas. Les représentations arborescentes sont explorées en programmation génétique et les représentations sous forme de graphes sont explorées en programmation évolutive ; un mélange de chromosomes linéaires et d'arbres est exploré dans la programmation de l'expression génique .

Une fois la représentation génétique et la fonction de fitness définies, une AG procède à l'initialisation d'une population de solutions puis à son amélioration par application répétitive des opérateurs de mutation, de croisement, d'inversion et de sélection.

Initialisation

La taille de la population dépend de la nature du problème, mais contient généralement plusieurs centaines ou milliers de solutions possibles. Souvent, la population initiale est générée aléatoirement, permettant toute la gamme des solutions possibles (l' espace de recherche ). Parfois, les solutions peuvent être "ensemencées" dans des domaines où des solutions optimales sont susceptibles d'être trouvées.

Sélection

Au cours de chaque génération successive, une partie de la population existante est sélectionnée pour élever une nouvelle génération. Les solutions individuelles sont sélectionnées par le biais d'un processus basé sur la condition physique , où des solutions plus adaptées (telles que mesurées par une fonction de condition physique ) sont généralement plus susceptibles d'être sélectionnées. Certaines méthodes de sélection évaluent l'adéquation de chaque solution et sélectionnent préférentiellement les meilleures solutions. D'autres méthodes n'évaluent qu'un échantillon aléatoire de la population, car le premier processus peut prendre beaucoup de temps.

La fonction de fitness est définie sur la représentation génétique et mesure la qualité de la solution représentée. La fonction fitness dépend toujours du problème. Par exemple, dans le problème du sac à dos, on veut maximiser la valeur totale des objets qui peuvent être placés dans un sac à dos d'une certaine capacité fixe. Une représentation d'une solution peut être un tableau de bits, où chaque bit représente un objet différent, et la valeur du bit (0 ou 1) représente si l'objet est ou non dans le sac à dos. Toutes ces représentations ne sont pas valables, car la taille des objets peut dépasser la capacité du sac à dos. L' adéquation de la solution est la somme des valeurs de tous les objets dans le sac à dos si la représentation est valide, ou 0 sinon.

Dans certains problèmes, il est difficile voire impossible de définir l'expression de fitness ; dans ces cas, une simulation peut être utilisée pour déterminer la valeur de la fonction de fitness d'un phénotype (par exemple, la dynamique des fluides computationnelle est utilisée pour déterminer la résistance à l'air d'un véhicule dont la forme est codée en tant que phénotype), ou même des algorithmes génétiques interactifs sont utilisés.

Opérateurs génétiques

L'étape suivante consiste à générer une population de solutions de deuxième génération à partir de celles sélectionnées grâce à une combinaison d' opérateurs génétiques : croisement (également appelé recombinaison) et mutation .

Pour chaque nouvelle solution à produire, un couple de solutions "parentes" est sélectionné pour l'élevage dans le pool sélectionné précédemment. En produisant une solution « enfant » en utilisant les méthodes de croisement et de mutation ci-dessus, une nouvelle solution est créée qui partage généralement de nombreuses caractéristiques de ses « parents ». De nouveaux parents sont sélectionnés pour chaque nouvel enfant, et le processus se poursuit jusqu'à ce qu'une nouvelle population de solutions de taille appropriée soit générée. Bien que les méthodes de reproduction basées sur l'utilisation de deux parents soient plus « inspirées de la biologie », certaines recherches suggèrent que plus de deux « parents » génèrent des chromosomes de meilleure qualité.

Ces processus aboutissent finalement à la prochaine génération de population de chromosomes qui est différente de la génération initiale. En général, l'aptitude moyenne aura augmenté par cette procédure pour la population, puisque seuls les meilleurs organismes de la première génération sont sélectionnés pour la reproduction, ainsi qu'une petite proportion de solutions moins adaptées. Ces solutions moins adaptées assurent la diversité génétique au sein du pool génétique des parents et assurent donc la diversité génétique de la génération suivante d'enfants.

Les avis sont partagés sur l'importance du croisement par rapport à la mutation. Il existe de nombreuses références dans Fogel (2006) qui soutiennent l'importance de la recherche basée sur les mutations.

Bien que le croisement et la mutation soient connus comme les principaux opérateurs génétiques, il est possible d'utiliser d'autres opérateurs tels que le regroupement, la colonisation-extinction ou la migration dans les algorithmes génétiques.

Il vaut la peine de régler des paramètres tels que la probabilité de mutation, la probabilité de croisement et la taille de la population pour trouver des paramètres raisonnables pour la classe de problèmes sur laquelle on travaille. Un très faible taux de mutation peut entraîner une dérive génétique (qui est de nature non ergodique ). Un taux de recombinaison trop élevé peut conduire à une convergence prématurée de l'algorithme génétique. Un taux de mutation trop élevé peut entraîner la perte de bonnes solutions, à moins qu'une sélection élitiste ne soit utilisée. Une taille de population adéquate garantit une diversité génétique suffisante pour le problème à résoudre, mais peut entraîner un gaspillage de ressources informatiques si elle est définie sur une valeur supérieure à celle requise.

Heuristique

En plus des principaux opérateurs ci-dessus, d'autres heuristiques peuvent être utilisées pour rendre le calcul plus rapide ou plus robuste. L' heuristique de spéciation pénalise le croisement entre des solutions candidates trop proches ; cela encourage la diversité de la population et aide à éviter une convergence prématurée vers une solution moins optimale.

Résiliation

Ce processus générationnel est répété jusqu'à ce qu'une condition de terminaison soit atteinte. Les conditions de terminaison courantes sont :

  • Une solution est trouvée qui satisfait les critères minimaux
  • Nombre fixe de générations atteint
  • Budget alloué (temps de calcul/argent) atteint
  • La forme physique de la solution la mieux classée atteint ou a atteint un plateau tel que les itérations successives ne produisent plus de meilleurs résultats
  • Contrôle manuel
  • Combinaisons de ce qui précède

L'hypothèse du bloc de construction

Les algorithmes génétiques sont simples à mettre en œuvre, mais leur comportement est difficile à comprendre. En particulier, il est difficile de comprendre pourquoi ces algorithmes parviennent fréquemment à générer des solutions de haute adéquation lorsqu'ils sont appliqués à des problèmes pratiques. L'hypothèse du bloc de construction (BBH) consiste en :

  1. Une description d'une heuristique qui effectue l'adaptation en identifiant et en recombinant des « blocs de construction », c'est-à-dire des schémas d' ordre faible, de faible longueur de définition avec une aptitude au-dessus de la moyenne.
  2. Une hypothèse selon laquelle un algorithme génétique effectue une adaptation en implémentant implicitement et efficacement cette heuristique.

Goldberg décrit l'heuristique comme suit :

"Les schémas courts, d'ordre inférieur et hautement ajustés sont échantillonnés, recombinés [croisés] et rééchantillonnés pour former des chaînes de fitness potentiellement plus élevées. D'une certaine manière, en travaillant avec ces schémas particuliers [les blocs de construction], nous avons réduit la complexité de notre problème ; au lieu de construire des chaînes de haute performance en essayant toutes les combinaisons imaginables, nous construisons des chaînes de mieux en mieux à partir des meilleures solutions partielles des échantillonnages passés.
« Parce que les schémas hautement ajustés de faible longueur de définition et d'ordre faible jouent un rôle si important dans l'action des algorithmes génétiques, nous leur avons déjà donné un nom spécial : blocs de construction. Tout comme un enfant crée de magnifiques forteresses grâce à l'agencement de simples blocs de bois, de même qu'un algorithme génétique recherche des performances presque optimales grâce à la juxtaposition de schémas ou de blocs de construction courts, d'ordre inférieur et de haute performance. »

Malgré l'absence de consensus concernant la validité de l'hypothèse de base, elle a été systématiquement évaluée et utilisée comme référence au fil des ans. De nombreux algorithmes d'estimation d'algorithmes de distribution , par exemple, ont été proposés pour tenter de fournir un environnement dans lequel l'hypothèse tiendrait. Bien que de bons résultats aient été rapportés pour certaines classes de problèmes, le scepticisme concernant la généralité et/ou l'aspect pratique de l'hypothèse des blocs de construction comme explication de l'efficacité des AG demeure. En effet, il existe une quantité raisonnable de travaux qui tentent de comprendre ses limites du point de vue de l'estimation des algorithmes de distribution.

Limites

Il existe des limites à l'utilisation d'un algorithme génétique par rapport aux algorithmes d'optimisation alternatifs :

  • L' évaluation répétée de la fonction de fitness pour des problèmes complexes est souvent le segment le plus prohibitif et le plus limitatif des algorithmes évolutifs artificiels. Trouver la solution optimale à des problèmes multimodaux complexes de grande dimension nécessite souvent des évaluations de fonction de fitness très coûteuses . Dans les problèmes du monde réel tels que les problèmes d'optimisation structurelle, une seule évaluation de fonction peut nécessiter plusieurs heures à plusieurs jours de simulation complète. Les méthodes d'optimisation typiques ne peuvent pas traiter de tels types de problèmes. Dans ce cas, il peut être nécessaire de renoncer à une évaluation exacte et d'utiliser une adéquation approximative qui est efficace en termes de calcul. Il est évident que la fusion de modèles approximatifs peut être l'une des approches les plus prometteuses pour utiliser de manière convaincante l'AG pour résoudre des problèmes complexes de la vie réelle.
  • Les algorithmes génétiques ne s'adaptent pas bien à la complexité. C'est-à-dire que lorsque le nombre d'éléments exposés à la mutation est important, il y a souvent une augmentation exponentielle de la taille de l'espace de recherche. Cela rend extrêmement difficile l'utilisation de la technique sur des problèmes tels que la conception d'un moteur, d'une maison ou d'un avion. Afin de rendre de tels problèmes traitables à la recherche évolutionniste, ils doivent être décomposés en la représentation la plus simple possible. Par conséquent, nous voyons généralement des algorithmes évolutifs codant des conceptions pour les pales de ventilateur au lieu de moteurs, des formes de construction au lieu de plans de construction détaillés et des profils aérodynamiques au lieu de conceptions d'avions entiers. Le deuxième problème de complexité est la question de savoir comment protéger les pièces qui ont évolué pour représenter de bonnes solutions contre d'autres mutations destructrices, en particulier lorsque leur évaluation de l'aptitude nécessite qu'elles se combinent bien avec d'autres pièces.
  • La "meilleure" solution n'est que par rapport à d'autres solutions. En conséquence, le critère d'arrêt n'est pas clair dans tous les problèmes.
  • Dans de nombreux problèmes, les AG ont tendance à converger vers des optima locaux ou même des points arbitraires plutôt que vers l' optimum global du problème. Cela signifie qu'il ne « sait pas » sacrifier la forme physique à court terme pour obtenir une forme physique à long terme. La probabilité que cela se produise dépend de la forme du paysage de fitness : certains problèmes peuvent permettre une ascension facile vers un optimum global, d'autres peuvent permettre à la fonction de trouver plus facilement les optima locaux. Ce problème peut être atténué en utilisant une fonction de fitness différente, en augmentant le taux de mutation ou en utilisant des techniques de sélection qui maintiennent une population diversifiée de solutions, bien que le théorème No Free Lunch prouve qu'il n'y a pas de solution générale à ce problème. Une technique courante pour maintenir la diversité consiste à imposer une « pénalité de niche », dans laquelle, tout groupe d'individus suffisamment similaires (rayon de niche) se voit ajouter une pénalité, ce qui réduira la représentation de ce groupe dans les générations suivantes, permettant à d'autres (moins similaires ) individus à maintenir dans la population. Cette astuce, cependant, peut ne pas être efficace, selon le paysage du problème. Une autre technique possible serait de simplement remplacer une partie de la population par des individus générés aléatoirement, lorsque la plupart de la population est trop similaire les uns aux autres. La diversité est importante dans les algorithmes génétiques (et la programmation génétique ) car le croisement sur une population homogène ne donne pas de nouvelles solutions. Dans les stratégies d'évolution et la programmation évolutive , la diversité n'est pas essentielle en raison d'une plus grande dépendance à la mutation.
  • Il est difficile de travailler sur des ensembles de données dynamiques, car les génomes commencent à converger tôt vers des solutions qui peuvent ne plus être valables pour des données ultérieures. Plusieurs méthodes ont été proposées pour y remédier en augmentant d'une manière ou d'une autre la diversité génétique et en empêchant une convergence précoce, soit en augmentant la probabilité de mutation lorsque la qualité de la solution diminue (appelée hypermutation déclenchée ), soit en introduisant occasionnellement des éléments entièrement nouveaux et générés aléatoirement dans le pool génétique. (appelés immigrants aléatoires ). Encore une fois, les stratégies d'évolution et la programmation évolutive peuvent être mises en œuvre avec une soi-disant "stratégie de virgule" dans laquelle les parents ne sont pas maintenus et les nouveaux parents sont sélectionnés uniquement à partir de la progéniture. Cela peut être plus efficace sur les problèmes dynamiques.
  • Les AG ne peuvent pas résoudre efficacement les problèmes dans lesquels la seule mesure de fitness est une seule mesure juste/mauvais (comme les problèmes de décision ), car il n'y a aucun moyen de converger vers la solution (pas de colline à gravir). Dans ces cas, une recherche aléatoire peut trouver une solution aussi rapidement qu'un GA. Cependant, si la situation permet à l'essai succès/échec d'être répété en donnant (éventuellement) des résultats différents, alors le rapport des succès aux échecs fournit une mesure de fitness appropriée.
  • Pour des problèmes d'optimisation spécifiques et des instances de problème, d'autres algorithmes d'optimisation peuvent être plus efficaces que les algorithmes génétiques en termes de vitesse de convergence. Algorithmes alternatifs et complémentaires comprennent des stratégies d'évolution , la programmation évolutive , recuit simulé , adaptation gaussienne , l' escalade d' une colline , et l' intelligence en essaim (par exemple: ant optimisation des colonies , l' optimisation des essaim de particules ) et les méthodes basées sur integer programmation linéaire . La pertinence des algorithmes génétiques dépend de la quantité de connaissance du problème ; les problèmes bien connus ont souvent des approches meilleures et plus spécialisées.

Variantes

Représentation chromosomique

L'algorithme le plus simple représente chaque chromosome sous la forme d'une chaîne de bits . En règle générale, les paramètres numériques peuvent être représentés par des entiers , bien qu'il soit possible d'utiliser des représentations à virgule flottante . La représentation en virgule flottante est naturelle aux stratégies d' évolution et à la programmation évolutionniste . La notion d'algorithmes génétiques à valeur réelle a été proposée mais est vraiment un terme impropre car elle ne représente pas vraiment la théorie des blocs de construction qui a été proposée par John Henry Holland dans les années 1970. Cette théorie n'est cependant pas sans fondement, basée sur des résultats théoriques et expérimentaux (voir ci-dessous). L'algorithme de base effectue un croisement et une mutation au niveau du bit. D'autres variantes traitent le chromosome comme une liste de nombres qui sont des index dans une table d'instructions, des nœuds dans une liste chaînée , des hachages , des objets ou toute autre structure de données imaginable . Le croisement et la mutation sont effectués de manière à respecter les limites des éléments de données. Pour la plupart des types de données, des opérateurs de variation spécifiques peuvent être conçus. Différents types de données chromosomiques semblent fonctionner mieux ou moins bien pour différents domaines de problèmes spécifiques.

Lorsque des représentations de chaînes de bits d'entiers sont utilisées, le codage Gray est souvent utilisé. De cette façon, de petits changements dans l'entier peuvent être facilement affectés par des mutations ou des croisements. Cela s'est avéré aider à prévenir la convergence prématurée au niveau des parois dites de Hamming , dans lesquelles trop de mutations simultanées (ou d'événements de croisement) doivent se produire afin de changer le chromosome pour une meilleure solution.

D'autres approches impliquent l'utilisation de tableaux de nombres réels au lieu de chaînes de bits pour représenter les chromosomes. Les résultats de la théorie des schémas suggèrent qu'en général plus l'alphabet est petit, meilleures sont les performances, mais il était initialement surprenant pour les chercheurs que de bons résultats aient été obtenus en utilisant des chromosomes à valeur réelle. Cela a été expliqué comme l'ensemble des valeurs réelles dans une population finie de chromosomes comme formant un alphabet virtuel (lorsque la sélection et la recombinaison sont dominantes) avec une cardinalité beaucoup plus faible que celle attendue d'une représentation à virgule flottante.

Une expansion du domaine de problème accessible de l'algorithme génétique peut être obtenue grâce à un codage plus complexe des pools de solutions en concaténant plusieurs types de gènes codés de manière hétérogène dans un chromosome. Cette approche particulière permet de résoudre des problèmes d'optimisation qui nécessitent des domaines de définition très disparates pour les paramètres du problème. Par exemple, dans les problèmes de réglage de contrôleur en cascade, la structure du contrôleur de boucle interne peut appartenir à un régulateur conventionnel de trois paramètres, tandis que la boucle externe pourrait mettre en œuvre un contrôleur linguistique (tel qu'un système flou) qui a une description intrinsèquement différente. Cette forme particulière de codage nécessite un mécanisme de croisement spécialisé qui recombine le chromosome par section, et c'est un outil utile pour la modélisation et la simulation de systèmes adaptatifs complexes, en particulier les processus d'évolution.

Élitisme

Une variante pratique du processus général de construction d'une nouvelle population consiste à permettre au(x) meilleur(s) organisme(s) de la génération actuelle de passer à la suivante, sans modification. Cette stratégie est connue sous le nom de sélection élitiste et garantit que la qualité de la solution obtenue par l'AG ne diminuera pas d'une génération à l'autre.

Implémentations parallèles

Les implémentations parallèles d'algorithmes génétiques se présentent sous deux formes. Les algorithmes génétiques parallèles à grain grossier supposent une population sur chacun des nœuds informatiques et une migration des individus entre les nœuds. Les algorithmes génétiques parallèles à grain fin supposent un individu sur chaque nœud de processeur qui agit avec les individus voisins pour la sélection et la reproduction. D'autres variantes, comme les algorithmes génétiques pour les problèmes d' optimisation en ligne , introduisent une dépendance temporelle ou du bruit dans la fonction de fitness.

GA adaptatifs

Les algorithmes génétiques avec des paramètres adaptatifs (algorithmes génétiques adaptatifs, AGA) sont une autre variante importante et prometteuse des algorithmes génétiques. Les probabilités de croisement (pc) et de mutation (pm) déterminent grandement le degré de précision de la solution et la vitesse de convergence que les algorithmes génétiques peuvent obtenir. Au lieu d'utiliser des valeurs fixes de pc et pm , les AGA utilisent les informations de population à chaque génération et ajustent de manière adaptative pc et pm afin de maintenir la diversité de la population ainsi que la capacité de convergence. En AGA (algorithme génétique adaptatif), l'ajustement de pc et pm dépend des valeurs de fitness des solutions. Dans CAGA (algorithme génétique adaptatif basé sur le clustering), grâce à l'utilisation de l'analyse de clustering pour juger les états d'optimisation de la population, l'ajustement de pc et pm dépend de ces états d'optimisation. Il peut être très efficace de combiner GA avec d'autres méthodes d'optimisation. L'AG a tendance à être assez bonne pour trouver des solutions globales généralement bonnes, mais assez inefficace pour trouver les dernières mutations pour trouver l'optimum absolu. D'autres techniques (telles que l' escalade simple ) sont assez efficaces pour trouver l'optimum absolu dans une région limitée. L'alternance de GA et d'escalade peut améliorer l'efficacité de l'AG tout en palliant le manque de robustesse de l'escalade.

Cela signifie que les règles de variation génétique peuvent avoir un sens différent dans le cas naturel. Par exemple, à condition que les étapes soient stockées dans un ordre consécutif, le croisement peut additionner un certain nombre d'étapes de l'ADN maternel en ajoutant un certain nombre d'étapes de l'ADN paternel et ainsi de suite. C'est comme ajouter des vecteurs qui peuvent plus probablement suivre une crête dans le paysage phénotypique. Ainsi, l'efficacité du procédé peut être augmentée de plusieurs ordres de grandeur. De plus, l' opérateur d'inversion a la possibilité de placer des étapes dans un ordre consécutif ou tout autre ordre approprié en faveur de la survie ou de l'efficacité.

Une variation, où la population dans son ensemble évolue plutôt que ses membres individuels, est connue sous le nom de recombinaison du pool génétique.

Un certain nombre de variantes ont été développées pour tenter d'améliorer les performances des AG sur des problèmes avec un degré élevé d'épistasie de fitness, c'est-à-dire où la fitness d'une solution consiste en l'interaction de sous-ensembles de ses variables. De tels algorithmes visent à apprendre (avant d'exploiter) ces interactions phénotypiques bénéfiques. En tant que tels, ils sont alignés sur l'hypothèse du bloc de construction en réduisant de manière adaptative la recombinaison perturbatrice. Parmi les exemples marquants de cette approche, citons le mGA, le GEMGA et le LLGA.

Domaines problématiques

Les problèmes qui semblent être particulièrement appropriés pour une solution par des algorithmes génétiques comprennent les problèmes d' horaire et d'ordonnancement, et de nombreux progiciels d'ordonnancement sont basés sur les AG. Les AG ont également été appliquées à l' ingénierie . Les algorithmes génétiques sont souvent appliqués comme approche pour résoudre des problèmes d' optimisation globale .

En règle générale, les algorithmes génétiques peuvent être utiles dans les domaines problématiques qui ont un paysage de fitness complexe , car le mélange, c'est-à-dire la mutation en combinaison avec le croisement , est conçu pour éloigner la population des optima locaux selon lesquels un algorithme d' escalade traditionnel pourrait rester bloqué. in. Observez que les opérateurs de croisement couramment utilisés ne peuvent pas modifier une population uniforme. La mutation à elle seule peut fournir l'ergodicité du processus global de l'algorithme génétique (considéré comme une chaîne de Markov ).

Des exemples de problèmes résolus par des algorithmes génétiques incluent : des miroirs conçus pour canaliser la lumière du soleil vers un capteur solaire, des antennes conçues pour capter des signaux radio dans l'espace, des méthodes de marche pour les figures informatiques, une conception optimale de corps aérodynamiques dans des champs d'écoulement complexes

Dans son Algorithm Design Manual , Skiena déconseille les algorithmes génétiques pour n'importe quelle tâche :

[I]l n'est pas du tout naturel de modéliser des applications en termes d'opérateurs génétiques comme la mutation et le croisement sur des chaînes de bits. La pseudobiologie ajoute un autre niveau de complexité entre vous et votre problème. Deuxièmement, les algorithmes génétiques prennent beaucoup de temps sur des problèmes non triviaux. [...] [L]'analogie avec l'évolution - où des progrès significatifs nécessitent [sic] des millions d'années - peut être tout à fait appropriée.

[...]

Je n'ai jamais rencontré de problème où les algorithmes génétiques m'ont semblé la bonne façon de l'attaquer. De plus, je n'ai jamais vu de résultats informatiques rapportés à l'aide d'algorithmes génétiques qui m'ont favorablement impressionné. Tenez-vous en au recuit simulé pour vos besoins vaudous de recherche heuristique.

-  Steven Skiena

Histoire

En 1950, Alan Turing a proposé une "machine à apprendre" qui serait parallèle aux principes de l'évolution. La simulation informatique de l'évolution a commencé dès 1954 avec les travaux de Nils Aall Barricelli , qui utilisait l'ordinateur à l' Institute for Advanced Study de Princeton, New Jersey . Sa publication de 1954 n'a pas été largement remarquée. À partir de 1957, le généticien quantitatif australien Alex Fraser a publié une série d'articles sur la simulation de la sélection artificielle d'organismes à loci multiples contrôlant un caractère mesurable. À partir de ces débuts, la simulation informatique de l'évolution par les biologistes est devenue plus courante au début des années 1960, et les méthodes ont été décrites dans les livres de Fraser et Burnell (1970) et Crosby (1973). Les simulations de Fraser comprenaient tous les éléments essentiels des algorithmes génétiques modernes. De plus, Hans-Joachim Bremermann a publié une série d'articles dans les années 1960 qui ont également adopté une population de solutions aux problèmes d'optimisation, subissant une recombinaison, une mutation et une sélection. Les recherches de Bremermann comprenaient également les éléments des algorithmes génétiques modernes. Parmi les autres premiers pionniers remarquables, citons Richard Friedberg, George Friedman et Michael Conrad. De nombreux articles anciens sont réimprimés par Fogel (1998).

Bien que Barricelli, dans un travail qu'il rapporte en 1963, ait simulé l'évolution de la capacité à jouer à un jeu simple, l' évolution artificielle n'est devenue une méthode d'optimisation largement reconnue qu'à la suite des travaux d' Ingo Rechenberg et de Hans-Paul Schwefel dans les années 1960 et au début des Années 1970 - Le groupe de Rechenberg était capable de résoudre des problèmes d'ingénierie complexes grâce à des stratégies d'évolution . Une autre approche était la technique de programmation évolutive de Lawrence J. Fogel , qui a été proposée pour générer de l'intelligence artificielle. La programmation évolutionnaire utilisait à l'origine des machines à états finis pour prédire les environnements, et utilisait la variation et la sélection pour optimiser les logiques prédictives. Les algorithmes génétiques en particulier sont devenus populaires grâce aux travaux de John Holland au début des années 1970, et en particulier son livre Adaptation in Natural and Artificial Systems (1975). Son travail est né d'études sur les automates cellulaires , menées par Holland et ses étudiants de l' Université du Michigan . Holland a introduit un cadre formalisé pour prédire la qualité de la prochaine génération, connu sous le nom de théorème de schéma de Holland . La recherche sur les AG est restée largement théorique jusqu'au milieu des années 1980, lorsque la première conférence internationale sur les algorithmes génétiques s'est tenue à Pittsburgh, en Pennsylvanie .

Produits commerciaux

À la fin des années 1980, General Electric a commencé à vendre le premier produit d'algorithme génétique au monde, une boîte à outils basée sur l'ordinateur central conçue pour les processus industriels. En 1989, Axcelis, Inc. a lancé Evolver , le premier produit GA commercial au monde pour les ordinateurs de bureau. L' écrivain technologique du New York Times John Markoff a écrit sur Evolver en 1990, et il est resté le seul algorithme génétique commercial interactif jusqu'en 1995. Evolver a été vendu à Palisade en 1997, traduit en plusieurs langues, et est actuellement dans sa 6e version. Depuis les années 1990, MATLAB a intégré trois algorithmes heuristiques d' optimisation sans dérivée (recuit simulé, optimisation d'essaim de particules, algorithme génétique) et deux algorithmes de recherche directe (recherche simplex, recherche de motifs).

Techniques associées

Champs parents

Les algorithmes génétiques sont un sous-domaine :

Domaines connexes

Algorithmes évolutifs

Les algorithmes évolutionnaires sont un sous-domaine de l' informatique évolutionnaire .

  • Les stratégies d'évolution (ES, voir Rechenberg, 1994) font évoluer les individus par mutation et recombinaison intermédiaire ou discrète. Les algorithmes ES sont spécialement conçus pour résoudre des problèmes dans le domaine des valeurs réelles. Ils utilisent l'auto-adaptation pour ajuster les paramètres de contrôle de la recherche. La dé-randomisation de l'auto-adaptation a conduit à la stratégie d'évolution de l'adaptation de la matrice de covariance ( CMA-ES ).
  • La programmation évolutive (EP) implique des populations de solutions avec principalement des mutations et des sélections et des représentations arbitraires. Ils utilisent l'auto-adaptation pour ajuster les paramètres et peuvent inclure d'autres opérations de variation telles que la combinaison d'informations provenant de plusieurs parents.
  • L'algorithme d'estimation de la distribution (EDA) remplace les opérateurs de reproduction traditionnels par des opérateurs guidés par un modèle. Ces modèles sont appris de la population en utilisant des techniques d'apprentissage automatique et représentés sous forme de modèles graphiques probabilistes, à partir desquels de nouvelles solutions peuvent être échantillonnées ou générées à partir d'un croisement guidé.
  • La programmation génétique (GP) est une technique connexe popularisée par John Koza dans laquelle les programmes informatiques, plutôt que les paramètres de fonction, sont optimisés. La programmation génétique utilise souvent à base d' arbres interne des structures de données pour représenter les programmes informatiques pour l' adaptation au lieu de la liste des structures typiques des algorithmes génétiques. Il existe de nombreuses variantes de la programmation génétique, y compris la programmation génétique cartésien , la programmation de l' expression génique , Grammatical Evolution , programmation génétique linéaire , programmation multi expression , etc.
  • L'algorithme génétique de regroupement (AGG) est une évolution de l'AG où l'accent est déplacé des éléments individuels, comme dans les AG classiques, aux groupes ou sous-ensembles d'éléments. L'idée derrière cette évolution GA proposée par Emanuel Falkenauer est que la résolution de certains problèmes complexes, alias problèmes de clustering ou de partitionnement où un ensemble d'éléments doit être divisé en groupes disjoints d'éléments de manière optimale, serait mieux réalisé en faisant des caractéristiques des groupes d'éléments équivalents aux gènes. Ces types de problèmes incluent l' emballage des bacs , l'équilibrage des lignes, le regroupement par rapport à une mesure de distance, des piles égales, etc., sur lesquels les GA classiques se sont avérés peu performants. Rendre les gènes équivalents à des groupes implique des chromosomes en général de longueur variable et des opérateurs génétiques spéciaux qui manipulent des groupes entiers d'éléments. Pour le conditionnement en bacs en particulier, un GGA hybride avec le critère de dominance de Martello et Toth, est sans doute la meilleure technique à ce jour.
  • Les algorithmes évolutionnaires interactifs sont des algorithmes évolutionnaires qui utilisent l'évaluation humaine. Ils sont généralement appliqués à des domaines où il est difficile de concevoir une fonction d'aptitude informatique, par exemple, faire évoluer les images, la musique, les conceptions artistiques et les formes pour s'adapter aux préférences esthétiques des utilisateurs.

L'intelligence en essaim

L'intelligence en essaim est un sous-domaine de l' informatique évolutive .

  • L'optimisation des colonies de fourmis ( ACO ) utilise de nombreuses fourmis (ou agents) équipées d'un modèle de phéromone pour parcourir l'espace de solution et trouver des zones localement productives.
  • Bien que considérée comme un algorithme d'estimation de la distribution , l'optimisation par essaim de particules (PSO) est une méthode de calcul pour l'optimisation multi-paramètres qui utilise également une approche basée sur la population. Une population (essaim) de solutions candidates (particules) se déplace dans l'espace de recherche, et le mouvement des particules est influencé à la fois par leur propre position la mieux connue et la position globale la mieux connue de l'essaim. Comme les algorithmes génétiques, la méthode PSO dépend du partage d'informations entre les membres de la population. Dans certains problèmes, le PSO est souvent plus efficace en termes de calcul que les AG, en particulier dans les problèmes sans contraintes avec des variables continues.

Algorithmes évolutifs combinés à l'intelligence Swarm

Autres algorithmes de calcul évolutifs

Le calcul évolutif est un sous-domaine des méthodes métaheuristiques .

  • L'algorithme mémétique (AM), souvent appelé algorithme génétique hybride entre autres, est une méthode basée sur la population dans laquelle les solutions sont également soumises à des phases d'amélioration locales. L'idée des algorithmes mémétique vient des mèmes , qui contrairement aux gènes, peuvent s'adapter. Dans certains domaines problématiques, ils se sont avérés plus efficaces que les algorithmes évolutionnaires traditionnels.
  • Algorithmes bactériologiques (AB) inspirés de l' écologie évolutive et, plus particulièrement, de l'adaptation bactériologique. L'écologie évolutive est l'étude des organismes vivants dans le contexte de leur environnement, dans le but de découvrir comment ils s'adaptent. Son concept de base est que dans un environnement hétérogène, il n'y a pas un seul individu qui corresponde à l'ensemble de l'environnement. Il faut donc raisonner au niveau de la population. On pense également que les BA pourraient être appliqués avec succès à des problèmes de positionnement complexes (antennes pour téléphones portables, urbanisme, etc.) ou à l'exploration de données.
  • L'algorithme culturel (AC) se compose de la composante population presque identique à celle de l'algorithme génétique et, en plus, d'une composante connaissance appelée espace de croyance.
  • Evolution différentielle (DS) inspirée de la migration des superorganismes.
  • L'adaptation gaussienne ( adaptation normale ou naturelle, en abrégé NA pour éviter toute confusion avec GA) est destinée à maximiser le rendement de fabrication des systèmes de traitement du signal. Il peut également être utilisé pour l'optimisation paramétrique ordinaire. Elle repose sur un certain théorème valable pour toutes les régions d'acceptabilité et toutes les distributions gaussiennes. L'efficacité de NA repose sur la théorie de l'information et un certain théorème d'efficacité. Son efficacité est définie comme l'information divisée par le travail nécessaire pour obtenir l'information. Parce que NA maximise la fitness moyenne plutôt que la fitness de l'individu, le paysage est lissé de telle sorte que les vallées entre les pics peuvent disparaître. Par conséquent, il a une certaine "ambition" d'éviter les pics locaux dans le paysage du fitness. NA est également bon pour gravir des crêtes abruptes en adaptant la matrice des moments, car NA peut maximiser le désordre ( information moyenne ) de la gaussienne en maintenant simultanément la valeur adaptative moyenne constante.

Autres méthodes métaheuristiques

Les méthodes métaheuristiques relèvent largement des méthodes d'optimisation stochastique .

  • Le recuit simulé (SA) est une technique d'optimisation globale connexe qui traverse l'espace de recherche en testant des mutations aléatoires sur une solution individuelle. Une mutation qui augmente la forme physique est toujours acceptée. Une mutation qui diminue la fitness est acceptée de manière probabiliste sur la base de la différence de fitness et d'un paramètre de température décroissant. Dans le langage SA, on parle de rechercher l'énergie la plus faible au lieu de la forme physique maximale. SA peut également être utilisé dans un algorithme GA standard en commençant par un taux de mutation relativement élevé et en le diminuant au fil du temps selon un calendrier donné.
  • La recherche tabou (TS) est similaire au recuit simulé en ce sens que les deux traversent l'espace des solutions en testant les mutations d'une solution individuelle. Alors que le recuit simulé ne génère qu'une seule solution mutée, la recherche tabou génère de nombreuses solutions mutées et se déplace vers la solution avec la plus faible énergie de celles générées. Afin d'éviter les cycles et d'encourager un plus grand mouvement dans l'espace de solution, une liste taboue de solutions partielles ou complètes est maintenue. Il est interdit de passer à une solution qui contient des éléments de la liste tabou, qui est mise à jour au fur et à mesure que la solution traverse l'espace des solutions.
  • Optimisation extrême (EO) Contrairement aux GA, qui fonctionnent avec une population de solutions candidates, l'EO fait évoluer une solution unique et apporte des modifications locales aux pires composants. Cela nécessite qu'une représentation appropriée soit sélectionnée qui permette aux composants de solution individuels d'être assignés à une mesure de qualité ("fitness"). Le principe directeur derrière cet algorithme est celui de l' amélioration émergente en supprimant sélectivement les composants de faible qualité et en les remplaçant par un composant sélectionné au hasard. Ceci est décidément en contradiction avec une AG qui sélectionne de bonnes solutions dans le but de faire de meilleures solutions.

Autres méthodes d'optimisation stochastique

  • La méthode d'entropie croisée (CE) génère des solutions candidates via une distribution de probabilité paramétrée. Les paramètres sont mis à jour via la minimisation de l'entropie croisée, afin de générer de meilleurs échantillons à l'itération suivante.
  • L'optimisation de la recherche réactive (RSO) préconise l'intégration de techniques d'apprentissage automatique sous-symboliques dans les heuristiques de recherche pour résoudre des problèmes d'optimisation complexes. Le mot réactif fait allusion à une réponse immédiate aux événements pendant la recherche via une boucle de rétroaction en ligne interne pour l'auto-réglage des paramètres critiques. Méthodologies d'intérêt pour la recherche réactive comprennent l' apprentissage des machines et des statistiques, en particulier l' apprentissage par renforcement , apprentissage actif ou d'une requête , les réseaux de neurones , et métaheuristiques .

Voir également

Les références

Bibliographie

Liens externes

Ressources

Tutoriels