Worldlex Wiki Un algorithme génétique ( AG ) est une métaheuristique inspirée du processus de sélection naturelle et appartenant à la vaste classe des algorithmes évolutionnaires (AE) en informatique et en recherche opérationnelle . 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 grâce à des opérateurs bio-inspirés tels que la sélection , le croisement et la mutation . Parmi les applications des AG, on peut citer l'optimisation des arbres de décision pour de meilleures performances, la résolution de grilles de sudoku , l'optimisation des hyperparamètres et l'inférence causale .
population de solutions candidates (appelées individus, créatures, organismes 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 son génotype ) qui peuvent être mutées et modifié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 débute généralement à partir d'une population d'individus générés aléatoirement et se déroule de manière itérative , la population de chaque itération étant appelée génération . À chaque génération, la valeur d'adaptation de chaque individu est évaluée ; cette valeur correspond généralement à la valeur de la fonction objectif du problème d'optimisation à résoudre. Les individus les plus adaptés sont sélectionnés de manière stochastique au sein de la population actuelle, et leur génome est modifié ( recombinaison et éventuellement mutation aléatoire) pour former une nouvelle génération. Cette nouvelle génération de solutions candidates est ensuite utilisée lors de l'itération suivante de l' algorithme . Généralement, l'algorithme s'arrête lorsqu'un nombre maximal de générations a été atteint ou lorsqu'un niveau d'adaptation satisfaisant a été atteint pour la population.
Un algorithme génétique typique nécessite :
- une représentation génétique du domaine de solution,
- une fonction d'évaluation pour déterminer le domaine de la solution.
Chaque solution candidate est généralement représentée par un tableau de bits (également appelé ensemble de bits ou chaîne de bits ). Des tableaux d'autres types et structures peuvent être utilisés de manière similaire. La principale propriété qui rend ces représentations génétiques pratiques est que leurs éléments s'alignent facilement grâce à leur taille fixe, ce qui simplifie les opérations de croisement . Des représentations de longueur variable peuvent également être utilisées, mais la mise en œuvre du croisement est alors plus complexe. Les représentations arborescentes sont explorées en programmation génétique et les représentations graphiques en programmation évolutionnaire ; une combinaison de chromosomes linéaires et d'arbres est explorée en programmation d'expression génique .
Une fois la représentation génétique et la fonction d'adaptation définies, un algorithme génétique procède à l'initialisation d'une population de solutions, puis à son amélioration par l'application répétée 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 elle comprend généralement des centaines, voire des milliers, de solutions possibles. Souvent, la population initiale est générée aléatoirement, couvrant ainsi l'ensemble des solutions possibles (l' espace de recherche ). Il arrive que les solutions soient « ensemencées » dans des zones où les solutions optimales sont susceptibles d'être trouvées, ou que la distribution de la probabilité d'échantillonnage soit ajustée pour se concentrer sur les zones d'intérêt majeur.
Sélection
La fonction d'évaluation est définie sur la représentation génétique et mesure la qualité de la solution représentée. Cette fonction dépend toujours du problème. Par exemple, dans le problème du sac à dos, l'objectif est de maximiser la valeur totale des objets pouvant être placés dans un sac à dos de capacité fixe. Une solution peut être représentée par un tableau de bits, où chaque bit représente un objet différent et sa valeur (0 ou 1) indique si l'objet est présent ou non dans le sac. Toutes les représentations ne sont pas valides, car la taille des objets peut dépasser la capacité du sac. L' évaluation de la solution correspond à la somme des valeurs de tous les objets présents dans le sac si la représentation est valide, et à 0 sinon.
Dans certains problèmes, il est difficile, voire impossible, de définir l'expression de la fonction d'adaptation ; dans ces cas, une simulation peut être utilisée pour déterminer la valeur de la fonction d'adaptation d'un phénotype (par exemple , la dynamique des fluides numérique est utilisée pour déterminer la résistance à l'air d'un véhicule dont la forme est codée comme phénotype), ou même des algorithmes génétiques interactifs sont utilisés.
opérateurs génétiques
Pour chaque nouvelle solution à produire, une paire de solutions « parentales » est sélectionnée parmi celles précédemment choisies. La production d'une solution « enfant » par croisement et mutation permet de créer une nouvelle solution qui partage généralement de nombreuses caractéristiques de ses « parents ». De nouveaux parents sont sélectionnés pour chaque enfant, et le processus se poursuit jusqu'à l'obtention d'une population de solutions de taille appropriée. Bien que les méthodes de reproduction basées sur l'utilisation de deux parents soient davantage inspirées par la biologie, certaines recherches suggèrent que plus de deux « parents » produisent des chromosomes de meilleure qualité.
Ces processus aboutissent à une population chromosomique de génération suivante différente de celle de la génération initiale. Généralement, la valeur sélective moyenne de la population augmente grâce à cette procédure, car seuls les meilleurs organismes de la première génération sont sélectionnés pour la reproduction, ainsi qu'une faible proportion d'organismes moins performants. Ces derniers garantissent la diversité génétique au sein du patrimoine génétique parental et, par conséquent, celle de la génération suivante.
Les avis divergent quant à l'importance relative du croisement et de la mutation. Fogel (2006) cite de nombreuses références qui appuient l'importance de la recherche basée sur la mutation.
Il est judicieux d'ajuster des paramètres tels que la probabilité de mutation , la probabilité de croisement et la taille de la population afin de trouver des valeurs appropriées pour la classe de complexité du problème étudié. Un taux de mutation trop faible peut entraîner une dérive génétique (qui est non ergodique par nature). 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 d'utiliser une sélection élitiste . Une taille de population adéquate garantit une diversité génétique suffisante pour le problème considéré, mais peut engendrer un gaspillage de ressources de calcul si elle est supérieure aux besoins.
Heuristiques
Outre les opérateurs principaux mentionnés ci-dessus, d'autres heuristiques peuvent être utilisées pour accélérer ou renforcer le calcul. L' heuristique de spéciation pénalise les croisements entre solutions candidates trop similaires ; cela favorise la diversité de la population et contribue à prévenir une convergence prématurée vers une solution sous-optimale.
Terminaison
Ce processus de génération se répète jusqu'à ce qu'une condition d'arrêt soit atteinte. Les conditions d'arrêt courantes sont :
- On trouve une solution qui satisfait aux critères minimaux
- Un nombre fixe de générations atteint
- Budget alloué (temps de calcul/argent) atteint
- La solution la mieux classée atteint ou a atteint un plateau, de sorte que les itérations successives ne produisent plus de meilleurs résultats.
- Inspection manuelle
- Combinaisons des éléments ci-dessus
L'hypothèse des éléments constitutifs
Les algorithmes génétiques sont simples à implémenter, mais leur fonctionnement est difficile à comprendre. En particulier, il est difficile de comprendre pourquoi ces algorithmes parviennent si souvent à générer des solutions performantes lorsqu'ils sont appliqués à des problèmes concrets. L'hypothèse des blocs constitutifs (BBH) repose sur les principes suivants :
- Description d'une heuristique qui effectue une adaptation en identifiant et en recombinant des « éléments constitutifs », c'est-à-dire des schémas de faible ordre et de faible longueur de définition avec une aptitude supérieure à la moyenne.
- L'hypothèse selon laquelle un algorithme génétique réalise l'adaptation en implémentant implicitement et efficacement cette heuristique.
Goldberg décrit l'heuristique comme suit :
- « Des schémas courts, de faible ordre et très performants sont échantillonnés, recombinés (croisés) et rééchantillonnés pour former des chaînes potentiellement plus performantes. En travaillant avec ces schémas particuliers (les éléments constitutifs), nous avons en quelque sorte réduit la complexité de notre problème : au lieu de construire des chaînes performantes en essayant toutes les combinaisons possibles, nous construisons des chaînes de plus en plus performantes à partir des meilleures solutions partielles des échantillonnages précédents. »
- « Parce que les schémas très adaptés, de faible longueur et de faible ordre, jouent un rôle si important dans le fonctionnement des algorithmes génétiques, nous leur avons déjà donné un nom spécial : les blocs de construction. De même qu’un enfant crée de magnifiques forteresses en assemblant de simples blocs de bois, un algorithme génétique recherche des performances quasi optimales par la juxtaposition de schémas courts, de faible ordre et de haute performance, ou blocs de construction. »
Malgré l'absence de consensus quant à la validité de l'hypothèse des blocs de construction, celle-ci a été constamment évaluée et utilisée comme référence au fil des années. De nombreux algorithmes d'estimation de distributions , par exemple, ont été proposés afin de fournir un environnement où cette hypothèse serait vérifiée. Bien que de bons résultats aient été obtenus pour certaines classes de problèmes , le scepticisme persiste quant à la généralité et/ou la praticabilité de l'hypothèse des blocs de construction pour expliquer l'efficacité des algorithmes génétiques. De fait, de nombreux travaux s'attachent à comprendre ses limites du point de vue des algorithmes d'estimation de distributions.
Limites
Lorsqu'on utilise des représentations binaires d'entiers, on recourt souvent au codage de Gray . Ainsi, de petites modifications de l'entier peuvent être facilement apportées par mutation ou recombinaison. Il a été démontré que cela contribue à prévenir la convergence prématurée aux points de convergence dits « murs de Hamming » , où un trop grand nombre de mutations (ou de recombinaisons) simultanées doivent se produire pour que le chromosome atteigne une meilleure solution.
D'autres approches consistent à utiliser des tableaux de nombres réels plutôt que des chaînes binaires 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. Cependant, les chercheurs ont été initialement surpris d'obtenir de bons résultats avec des chromosomes à valeurs réelles. Ceci s'explique par le fait que l'ensemble des valeurs réelles d'une population finie de chromosomes forme un alphabet virtuel (lorsque la sélection et la recombinaison sont dominantes) avec une cardinalité bien inférieure à celle attendue d'une représentation à virgule flottante.
L'extension du domaine d'application des algorithmes génétiques peut être obtenue par un encodage plus complexe des ensembles de solutions, en concaténant plusieurs types de gènes à encodage hétérogène au sein d'un même chromosome . Cette approche permet de résoudre des problèmes d'optimisation nécessitant des domaines de définition très différents pour les paramètres. Par exemple, dans le cadre du réglage de contrôleurs en cascade, la structure du contrôleur de la boucle interne peut correspondre à un régulateur classique à trois paramètres, tandis que la boucle externe peut implémenter un contrôleur linguistique (tel qu'un système flou) dont la description est fondamentalement différente. Ce type d'encodage requiert un mécanisme de croisement spécialisé qui recombine le chromosome par sections ; il constitue un outil précieux pour la modélisation et la simulation de systèmes adaptatifs complexes, notamment les processus d'évolution.
Un autre élargissement important de l'espace de solutions accessible aux algorithmes génétiques (AG) a été motivé par la nécessité de concevoir des représentations adaptées à différents niveaux de connaissance des états de la solution. Les représentations de longueur variable s'inspirent de l'observation selon laquelle, dans la nature, l'évolution tend à progresser des organismes les plus simples vers les plus complexes, ce qui suggère une justification sous-jacente à l'adoption de structures flexibles. Une seconde motivation, plus pragmatique, tient au fait que la plupart des problèmes d'ingénierie et des problèmes à base de connaissances du monde réel ne se conforment pas naturellement à des structures de connaissances rigides.
Ces premières innovations en matière de représentations de longueur variable ont jeté les bases essentielles du développement de la programmation génétique , qui a étendu le paradigme classique des algorithmes génétiques. Ces représentations ont nécessité des améliorations des opérateurs génétiques simplistes utilisés pour les chromosomes de longueur fixe, permettant ainsi l'émergence de modèles d'algorithmes génétiques plus sophistiqués et adaptatifs.
Élitisme
Une variante pratique du processus général de construction d'une nouvelle population consiste à conserver, sans modification, le ou les meilleurs organismes de la génération actuelle pour la suivante. Cette stratégie, appelée sélection élitiste , garantit que la qualité de la solution obtenue par l'algorithme génétique 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 déclinent en deux catégories. Les algorithmes génétiques parallèles à gros grains supposent une population sur chaque nœud de calcul et la migration des individus entre les nœuds. Les algorithmes génétiques parallèles à grains fins supposent un individu sur chaque nœud de processeur, qui interagit avec ses 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 d'évaluation.
algorithmes génétiques adaptatifs
Les algorithmes génétiques à paramètres adaptatifs (algorithmes génétiques adaptatifs, AGA) constituent une autre variante importante et prometteuse des algorithmes génétiques. Les probabilités de croisement (pc) et de mutation (pm) déterminent fortement la précision de la solution et la vitesse de convergence des algorithmes génétiques. La convergence des algorithmes génétiques a été analysée analytiquement par des chercheurs.
Au lieu d'utiliser des valeurs fixes pour pc et pm , les algorithmes génétiques adaptatifs (AGA) exploitent les informations de la population à chaque génération et ajustent de manière adaptative pc et pm afin de maintenir la diversité de la population et d'assurer la convergence. Dans un AGA (algorithme génétique adaptatif) , l'ajustement de pc et pm dépend des valeurs d'adaptation des solutions. Il existe d'autres exemples de variantes d'AGA : la méthode de zoom successif est un exemple précoce d'amélioration de la convergence . Dans un CAGA (algorithme génétique adaptatif basé sur le clustering) , grâce à l'analyse de clustering permettant de déterminer les états d'optimisation de la population, l'ajustement de pc et pm dépend de ces états. Des approches récentes utilisent des variables plus abstraites pour déterminer pc et pm . On peut citer, par exemple, les principes de dominance et de codominance et le LIGA (algorithme génétique interpolatif nivelé), qui combine un algorithme génétique flexible avec une recherche A* modifiée pour gérer l'anisotropie de l'espace de recherche
Combiner un algorithme génétique (AG) avec d'autres méthodes d'optimisation peut s'avérer très efficace. Un AG excelle généralement dans la recherche de bonnes solutions globales, mais est peu performant pour trouver les dernières mutations permettant d'atteindre l'optimum absolu. D'autres techniques (comme l' algorithme de recherche locale ) sont très efficaces pour trouver l'optimum absolu dans une région limitée. Alterner AG et recherche locale permet d'améliorer l'efficacité de l'AG tout en palliant le manque de robustesse de l'algorithme de recherche locale.opérateur d'inversion a la possibilité de placer les étapes de manière consécutive ou dans tout autre ordre approprié favorisant la survie ou l'efficacité.
Une variante, où c'est la population dans son ensemble qui évolue plutôt que ses membres individuels, est connue sous le nom de recombinaison du pool génétique.
Plusieurs variantes ont été développées pour tenter d'améliorer les performances des algorithmes génétiques (AG) sur des problèmes présentant un degré élevé d'épistasie de la fonction d'adaptation, c'est-à-dire lorsque la fonction d'adaptation d'une solution est constituée de sous-ensembles interagissant de ses variables. Ces algorithmes visent à apprendre (avant d'exploiter) ces interactions phénotypiques bénéfiques. De ce fait, ils s'inscrivent dans l'hypothèse des blocs constitutifs en réduisant de manière adaptative la recombinaison perturbatrice. Parmi les exemples notables de cette approche, on peut citer mGA , GEMGA et LLGA
Domaines problématiques
Les problèmes d'ordonnancement et de planification semblent particulièrement bien adaptés à la résolution par algorithmes génétiques , et de nombreux logiciels d'ordonnancement sont basés sur ces algorithmes . Les algorithmes génétiques ont également été appliqués à l'ingénierie . Ils sont fréquemment utilisés pour résoudre les problèmes d'optimisation globale .
De manière générale, les algorithmes génétiques peuvent s'avérer utiles dans les domaines problématiques présentant un paysage d'adaptation complexe , car le mélange (c'est-à-dire la combinaison de mutation et de croisement ) vise à éloigner la population des optima locaux dans lesquels un algorithme de recherche locale classique pourrait se retrouver bloqué. Il est important de noter que les opérateurs de croisement couramment utilisés ne peuvent modifier une population uniforme. La mutation seule peut garantir l'ergodicité du processus global de l'algorithme génétique (représenté par une chaîne de Markov ).
Exemples de problèmes résolus par des algorithmes génétiques : miroirs conçus pour canaliser la lumière du soleil vers un collecteur solaire, antennes conçues pour capter des signaux radio dans l'espace, méthodes de marche pour les figures informatiques, conception optimale de corps aérodynamiques dans des champs d'écoulement complexes
Dans son manuel de conception d'algorithmes , Skiena déconseille l'utilisation des algorithmes génétiques pour quelque tâche que ce soit :
Il est assez artificiel de modéliser des applications en termes d'opérateurs génétiques comme la mutation et le croisement sur des chaînes binaires. La pseudobiologie ajoute un niveau de complexité supplémentaire entre vous et votre problème. De plus, les algorithmes génétiques sont extrêmement longs à exécuter sur des problèmes non triviaux. [...] L'analogie avec l'évolution — où des progrès significatifs nécessitent des millions d'années — peut s'avérer tout à fait pertinente.
[...]
I have never encountered any problem where genetic algorithms seemed to me the right way to attack it. Further, I have never seen any computational results reported using genetic algorithms that have favorably impressed me. Stick to simulated annealing for your heuristic search voodoo needs.
—Steven Skiena
History
In 1950, Alan Turing proposed a "learning machine" which would parallel the principles of evolution. Computer simulation of evolution started as early as in 1954 with the work of Nils Aall Barricelli, who was using the computer at the Institute for Advanced Study in Princeton, New Jersey. His 1954 publication was not widely noticed. Starting in 1957, the Australian quantitative geneticist Alex Fraser published a series of papers on simulation of artificial selection of organisms with multiple loci controlling a measurable trait. From these beginnings, computer simulation of evolution by biologists became more common in the early 1960s, and the methods were described in books by Fraser and Burnell (1970) and Crosby (1973). Fraser's simulations included all of the essential elements of modern genetic algorithms. In addition, Hans-Joachim Bremermann published a series of papers in the 1960s that also adopted a population of solution to optimization problems, undergoing recombination, mutation, and selection. Bremermann's research also included the elements of modern genetic algorithms. Other noteworthy early pioneers include Richard Friedberg, George Friedman, and Michael Conrad. Many early papers are reprinted by Fogel (1998).
Bien que Barricelli ait simulé, dans un travail publié en 1963, l'évolution de l'aptitude à 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. L' équipe de Rechenberg a réussi à résoudre des problèmes d'ingénierie complexes grâce à des stratégies évolutionnaires . Une autre approche fut la technique de programmation évolutionnaire de Lawrence J. Fogel , proposée pour générer l'intelligence artificielle. La programmation évolutionnaire utilisait initialement des automates à états finis pour prédire les environnements, et recourait à la variation et à la sélection pour optimiser les logiques prédictives. Les algorithmes génétiques, en particulier, ont gagné en popularité grâce aux travaux de John Holland au début des années 1970, et notamment à son ouvrage *Adaptation in Natural and Artificial Systems * (1975). Ses travaux s'appuyaient sur des études d' automates cellulaires menées par Holland et ses étudiants à l' Université du Michigan . Holland a introduit un cadre formalisé pour prédire la qualité de la génération suivante, connu sous le nom de théorème de schéma de Holland . La recherche sur les algorithmes génétiques est restée largement théorique jusqu'au milieu des années 1980, date à laquelle 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 commercialisé le premier produit au monde basé sur un algorithme génétique, une suite logicielle pour ordinateurs centraux conçue pour les processus industriels. En 1989, Axcelis, Inc. a lancé Evolver , le premier algorithme génétique commercial au monde pour ordinateurs de bureau. John Markoff, journaliste spécialisé en technologie au New York Times, a écrit un article sur Evolver en 1990 Evolver a été vendu à Palisade en 1997, traduit en plusieurs langues et en est actuellement à sa sixième version. Depuis les années 1990, MATLAB intègre trois algorithmes heuristiques d'optimisation sans dérivée (recuit simulé, optimisation par essaims de particules et algorithme génétique) et deux algorithmes de recherche directe (recherche simplex et recherche de motifs).
Techniques connexes
Domaines connexes
Algorithmes évolutionnaires
- Les stratégies d'évolution (SE, voir Rechenberg, 1994) font évoluer les individus par mutation et recombinaison intermédiaire ou discrète. Les algorithmes SE sont conçus spécifiquement 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 par adaptation de la matrice de covariance ( CMA-SE ).
- La programmation évolutionnaire (PE) met en œuvre des populations de solutions reposant principalement sur la mutation et la sélection, et utilisant des représentations arbitraires. Elle recourt à l'auto-adaptation pour ajuster les paramètres et peut inclure d'autres opérations de variation, comme la combinaison d'informations provenant de plusieurs parents.
- L'algorithme d'estimation de distribution (EDA) remplace les opérateurs de reproduction traditionnels par des opérateurs guidés par un modèle. Ces modèles sont appris à partir 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 par croisement guidé.
- La programmation génétique (PG) est une technique apparentée, popularisée par John Koza , qui optimise les programmes informatiques plutôt que les paramètres de fonctions. La programmation génétique utilise souvent des structures de données internes arborescentes pour représenter les programmes informatiques à adapter, contrairement aux structures de listes typiques des algorithmes génétiques. Il existe de nombreuses variantes de la programmation génétique, notamment la programmation génétique cartésienne , la programmation par expression génique , l'évolution grammaticale , la programmation génétique linéaire et la programmation multi-expression .
- le bin packing , l'équilibrage de lignes, le clustering selon une mesure de distance, le regroupement par piles égales, etc., pour lesquels les AG classiques ont montré des performances médiocres. Équivalenter les gènes aux groupes implique l'utilisation de chromosomes de longueur variable et d'opérateurs génétiques spécifiques qui manipulent des groupes entiers d'éléments. Pour le bin packing en particulier, un AGR hybride, combiné au 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 font appel à l'évaluation humaine. Ils sont généralement appliqués à des domaines où il est difficile de concevoir une fonction d'évaluation informatique, par exemple pour faire évoluer des images, de la musique, des créations artistiques et des formes afin de répondre aux préférences esthétiques des utilisateurs.
intelligence collective
- L'optimisation par colonie de fourmis ( ACO ) utilise de nombreuses fourmis (ou agents) équipées d'un modèle de phéromones pour parcourir l'espace des solutions et trouver des zones localement productives.
- Bien que considérée comme un algorithme d'estimation de distribution , l'optimisation par essaims de particules (PSO) est une méthode de calcul pour l'optimisation multiparamètre qui utilise également une approche populationnelle. 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 meilleure position connue et par la meilleure position connue globale de l'essaim. À l'instar des algorithmes génétiques, la méthode PSO repose sur le partage d'informations entre les membres de la population. Dans certains problèmes, la PSO est souvent plus efficace en termes de calcul que les algorithmes génétiques, notamment pour les problèmes sans contraintes avec des variables continues
Autres algorithmes de calcul évolutionnaire
Le calcul évolutionnaire est un sous-domaine des méthodes métaheuristiques .
- L'algorithme mémétique (AM), souvent appelé algorithme génétique hybride , est une méthode basée sur une population où les solutions font l'objet de phases d'amélioration locale. Le concept d'algorithme mémétique s'inspire des mèmes qui, contrairement aux gènes, sont capables de s'adapter. Dans certains domaines, il s'avère plus efficace que les algorithmes évolutionnaires classiques.
- l'écologie évolutive et, plus particulièrement, de l'adaptation bactériologique. L'écologie évolutive étudie les organismes vivants dans leur environnement, afin de comprendre comment ils s'adaptent. Son principe fondamental est que, dans un environnement hétérogène, aucun individu ne s'adapte parfaitement à l'ensemble de celui-ci. Il est donc nécessaire de raisonner à l'échelle de la population. On pense également que les AB pourraient être appliqués avec succès à des problèmes complexes de positionnement (antennes de téléphones portables, urbanisme, etc.) ou d'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 de connaissance appelée espace de croyance.
- Évolution différentielle (DE) inspirée par la migration des superorganismes.
- L'adaptation gaussienne (ou adaptation normale, abrégée NA pour éviter toute confusion avec GA) vise à maximiser le rendement de production des systèmes de traitement du signal. Elle peut également être utilisée pour l'optimisation paramétrique classique. Elle repose sur un théorème valable pour toutes les régions d'acceptabilité et toutes les distributions gaussiennes. L'efficacité de la NA repose sur la théorie de l'information et un théorème d'efficacité. Elle est définie comme l'information divisée par le travail nécessaire pour l'obtenir . La NA maximisant la fitness moyenne plutôt que la fitness individuelle, le paysage de fitness est lissé, ce qui peut faire disparaître les creux entre les pics. Elle tend donc à éviter les pics locaux. La NA excelle également dans la franchissement des crêtes abruptes grâce à l'adaptation de la matrice des moments, car elle maximise le désordre ( information moyenne ) de la gaussienne tout en maintenant la fitness moyenne constante.
Autres méthodes métaheuristiques
Les méthodes métaheuristiques relèvent globalement des méthodes d'optimisation stochastique .
- Le recuit simulé (RS) est une technique d'optimisation globale apparentée qui explore l'espace de recherche en testant des mutations aléatoires sur une solution individuelle. Une mutation améliorant la performance est toujours acceptée. Une mutation la dégradant est acceptée de manière probabiliste, en fonction de la différence de performance et d'un paramètre de température décroissant. Dans le contexte du RS, on parle de rechercher l'énergie minimale plutôt que la performance maximale. Le RS peut également être intégré à un algorithme génétique standard en commençant par un taux de mutation relativement élevé et en le diminuant progressivement selon une séquence prédéfinie.
- La recherche tabou (RT) est similaire au recuit simulé, car les deux explorent l'espace des solutions en testant des mutations d'une solution individuelle. Alors que le recuit simulé ne génère qu'une seule solution mutée, la recherche tabou en génère plusieurs et se dirige vers celle dont l'énergie est la plus basse. Afin d'éviter les boucles et d'encourager une exploration plus poussée de l'espace des solutions, une liste taboue de solutions partielles ou complètes est maintenue. Il est interdit de se déplacer vers une solution contenant des éléments de cette liste, qui est mise à jour au fur et à mesure de l'exploration de l'espace des solutions.
- L'optimisation extrémale (OE), contrairement aux algorithmes génétiques (AG) qui travaillent avec une population de solutions candidates, fait évoluer une solution unique en apportant des modifications locales à ses composants les moins performants. Ceci requiert le choix d'une représentation appropriée permettant d'attribuer à chaque composant de la solution une mesure de qualité (« fitness »). Le principe fondamental de cet algorithme est l' amélioration émergente par la suppression sélective des composants de faible qualité et leur remplacement par un composant sélectionné aléatoirement. Ceci est en contradiction avec un AG qui sélectionne les bonnes solutions dans le but d'en créer de meilleures.
Autres méthodes d'optimisation stochastique
- La méthode d'entropie croisée (CE) génère des solutions candidates à partir d'une distribution de probabilité paramétrée. Les paramètres sont mis à jour par minimisation de l'entropie croisée, afin de générer de meilleurs échantillons à l'itération suivante.
- L'optimisation par recherche réactive (RSO) préconise l'intégration de techniques d'apprentissage automatique sub-symboliques aux heuristiques de recherche pour la résolution de problèmes d'optimisation complexes. Le terme « réactif » suggère une capacité de réponse rapide aux événements survenant pendant la recherche, grâce à une boucle de rétroaction interne permettant l'auto-ajustement des paramètres critiques. Parmi les méthodologies d'intérêt pour la recherche réactive figurent l'apprentissage automatique et les statistiques, notamment l'apprentissage par renforcement , l'apprentissage actif ou par requêtes , les réseaux de neurones et les métaheuristiques .