Algorithme évolutif - Evolutionary algorithm

Dans l' intelligence computationnelle (IC), un algorithme évolutionnaire ( EA ) est un sous - ensemble du calcul évolutionnaire , un algorithme d' optimisation métaheuristique générique basé sur la population . Une EA utilise des mécanismes inspirés de l'évolution biologique , tels que la reproduction , la mutation , la recombinaison et la sélection . Les solutions candidates au problème d'optimisation jouent le rôle d'individus dans une population, et la fonction de fitness détermine la qualité des solutions (voir aussi fonction de perte ). L'évolution de la population a alors lieu après l'application répétée des opérateurs ci-dessus.

Les algorithmes évolutionnaires donnent souvent de bonnes solutions approchées à tous les types de problèmes car ils ne font idéalement aucune hypothèse sur le paysage de fitness sous-jacent . Les techniques d'algorithmes évolutionnaires appliquées à la modélisation de l'évolution biologique se limitent généralement à l'exploration de processus microévolutifs et de modèles de planification basés sur des processus cellulaires. Dans la plupart des applications réelles des EA, la complexité de calcul est un facteur prohibitif. En fait, cette complexité de calcul est due à l'évaluation de la fonction de fitness. L'approximation de la forme physique est l'une des solutions pour surmonter cette difficulté. Cependant, une évaluation environnementale apparemment simple peut résoudre des problèmes souvent complexes ; par conséquent, il peut n'y avoir aucun lien direct entre la complexité de l'algorithme et la complexité du problème.

Mise en œuvre

Ce qui suit est un exemple d' algorithme génétique générique à objectif unique .

Première étape : Générer la population initiale d' individus au hasard. (Première génération)

Deuxième étape : répétez les étapes de régénération suivantes jusqu'à la fin :

Évaluer la forme physique de chaque individu de la population (limite de temps, forme physique suffisante atteinte, etc.)
Sélectionnez les individus les plus aptes à la reproduction . (Parents)
Élevez de nouveaux individus par des opérations de croisement et de mutation pour donner naissance à une progéniture .
Remplacer les individus les moins adaptés de la population par de nouveaux individus.

Les types

Des techniques similaires diffèrent par la représentation génétique et d'autres détails de mise en œuvre, et la nature du problème particulier appliqué.

Algorithme génétique - C'est le type d'EA le plus populaire. On cherche la solution d'un problème sous forme de chaînes de nombres (traditionnellement binaire, bien que les meilleures représentations soient généralement celles qui reflètent quelque chose sur le problème à résoudre), en appliquant des opérateurs tels que la recombinaison et la mutation (parfois un, parfois les deux) . Ce type d'EA est souvent utilisé dans les problèmes d' optimisation .
Programmation génétique - Ici, les solutions se présentent sous la forme de programmes informatiques, et leur aptitude est déterminée par leur capacité à résoudre un problème informatique. 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.
Programmation évolutive – Similaire à la programmation génétique, mais la structure du programme est fixe et ses paramètres numériques peuvent évoluer.
Stratégie d'évolution - Fonctionne avec des vecteurs de nombres réels comme représentations de solutions, et utilise généralement des taux de mutation auto-adaptatifs.
Évolution différentielle – Basée sur des différences vectorielles et est donc principalement adaptée aux problèmes d' optimisation numérique .
Neuroévolution - Similaire à la programmation génétique, mais les génomes représentent des réseaux de neurones artificiels en décrivant la structure et les poids de connexion. Le codage du génome peut être direct ou indirect.
Système de classificateur d'apprentissage – Ici, la solution est un ensemble de classificateurs (règles ou conditions). Un Michigan-LCS évolue au niveau des classificateurs individuels alors qu'un Pittsburgh-LCS utilise des populations d'ensembles de classificateurs. Initialement, les classificateurs n'étaient que binaires, mais incluent désormais les types réels, de réseau neuronal ou d' expression S. La forme physique est généralement déterminée avec un apprentissage par renforcement basé sur la force ou la précision ou une approche d' apprentissage supervisé .

Comparaison avec les processus biologiques

Une limitation possible de nombreux algorithmes évolutionnaires est leur absence de distinction claire entre génotype et phénotype . Dans la nature, l'ovule fécondé subit un processus complexe connu sous le nom d' embryogenèse pour devenir un phénotype mature . On pense que ce codage indirect rend la recherche génétique plus robuste (c'est-à-dire réduit la probabilité de mutations mortelles), et peut également améliorer l' évolutivité de l'organisme. De tels codages indirects (également appelés génératifs ou développementaux) permettent également à l'évolution d'exploiter la régularité de l'environnement. Des travaux récents dans le domaine de l' embryogenèse artificielle , ou des systèmes de développement artificiels, cherchent à répondre à ces préoccupations. Et la programmation de l'expression génique explore avec succès un système génotype-phénotype, où le génotype se compose de chromosomes multigéniques linéaires de longueur fixe et le phénotype se compose de plusieurs arbres d'expression ou de programmes informatiques de différentes tailles et formes.

Techniques associées

Les algorithmes Swarm incluent

L'optimisation des colonies de fourmis est basée sur les idées de fourmis par communication de phéromones pour former des chemins. Convient principalement aux problèmes d' optimisation combinatoire et de graphes .
L'algorithme runner-root (RRA) s'inspire de la fonction des coureurs et des racines des plantes dans la nature
L'algorithme de colonie d'abeilles artificielles est basé sur le comportement de butinage des abeilles mellifères. Principalement proposé pour l'optimisation numérique et étendu pour résoudre des problèmes d'optimisation combinatoire, contraint et multi-objectifs.
L'algorithme des abeilles est basé sur le comportement de recherche de nourriture des abeilles mellifères. Il a été appliqué dans de nombreuses applications telles que le routage et la planification.
La recherche du coucou s'inspire du parasitisme de la couvaison des espèces de coucous . Il utilise également des vols Lévy , et donc il convient aux problèmes d' optimisation globale .
L'optimisation des essaims de particules est basée sur les idées de comportement de troupeaux d'animaux. Convient également principalement aux problèmes d' optimisation numérique .

Autres méthodes métaheuristiques basées sur la population

Recherche de chasse – Une méthode inspirée de la chasse en groupe de certains animaux comme les loups qui organisent leur position pour entourer la proie, chacun d'eux par rapport à la position des autres et surtout celle de leur chef. Il s'agit d'une méthode d'optimisation continue adaptée comme méthode d'optimisation combinatoire.
Recherche dimensionnelle adaptative – Contrairement aux techniques métaheuristiques inspirées de la nature, un algorithme de recherche dimensionnelle adaptative n'implémente aucune métaphore comme principe sous-jacent. Il utilise plutôt une méthode simple axée sur les performances, basée sur la mise à jour du paramètre de rapport de dimensionnalité de recherche (SDR) à chaque itération.
L'algorithme Firefly s'inspire du comportement des lucioles, s'attirant mutuellement par une lumière clignotante. Ceci est particulièrement utile pour l'optimisation multimodale.
Recherche d'harmonie – Basé sur les idées du comportement des musiciens dans la recherche de meilleures harmonies. Cet algorithme est adapté à l'optimisation combinatoire ainsi qu'à l'optimisation des paramètres.
Adaptation gaussienne – Basée sur la théorie de l'information. Utilisé pour maximiser le rendement de fabrication, l' aptitude moyenne ou les informations moyennes . Voir par exemple Entropie en thermodynamique et théorie de l'information .
Algorithme mémétique – Une méthode hybride, inspirée de la notion de mème de Richard Dawkins , elle prend généralement la forme d'un algorithme basé sur la population couplé à des procédures d'apprentissage individuelles capables d'effectuer des raffinements locaux. Met l'accent sur l'exploitation des connaissances spécifiques à un problème et essaie d'orchestrer la recherche locale et mondiale de manière synergique.

Exemples

En 2020, Google a déclaré que son AutoML-Zero peut redécouvrir avec succès des algorithmes classiques tels que le concept de réseaux de neurones.

Les simulations informatiques Tierra et Avida tentent de modéliser la dynamique macroévolutive .

Galerie

Une recherche EA à deux populations sur une fonction de Rosenbrock contrainte avec un optimum global borné.
Une recherche EA à deux populations sur une fonction de Rosenbrock contrainte . L'optimum global n'est pas borné.
Estimation de l'algorithme de distribution sur la fonction de Keane
Une recherche EA à deux populations d'un optima borné de la fonction de Simionescu .

Les références

Liens externes

Un aperçu de l'histoire et des saveurs des algorithmes évolutionnaires

Bibliographie

Ashlock, D. (2006), Calcul évolutif pour la modélisation et l'optimisation , Springer, ISBN 0-387-22196-4 .
Bäck, T. (1996), Algorithmes évolutionnaires en théorie et en pratique : stratégies d'évolution, programmation évolutionnaire, algorithmes génétiques , Oxford Univ. Presse.
Bäck, T., Fogel, D., Michalewicz, Z. (1997), Handbook of Evolutionary Computation , Oxford Univ. Presse.
Banzhaf, W., Nordin, P., Keller, R., Francone, F. (1998), Programmation génétique - Une introduction , Morgan Kaufmann, San Francisco
Eiben, AE, Smith, JE (2003), Introduction à l'informatique évolutive , Springer.
Holland, JH (1992), Adaptation dans les systèmes naturels et artificiels , The University of Michigan Press, Ann Arbor
Michalewicz Z., Fogel DB (2004). Comment le résoudre : Heuristique moderne, Springer.
Benko, Attila ; Dosa, Gyorgy ; Tuza, Zsolt (2010). "Bin Packing/Covering with Delivery, résolu avec l'évolution des algorithmes". 2010 Cinquième conférence internationale de l'IEEE sur l'informatique bio-inspirée : théories et applications (BIC-TA) . p. 298-302. doi : 10.1109/BICTA.2010.5645312 . ISBN 978-1-4244-6437-1. S2CID 16875144 .
Poli, R.; Langdon, WB; McPhee, NF (2008). Un guide de terrain pour la programmation génétique . Lulu.com, disponible gratuitement sur Internet. ISBN 978-1-4092-0073-4. Archivé de l'original le 2016-05-27 . Récupéré le 05/03/2011 .
Price, K., Storn, RM, Lampinen, JA (2005). « Évolution différentielle : une approche pratique de l'optimisation globale » , Springer.
Ingo Rechenberg (1971): Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (thèse de doctorat). Réimprimé par Fromman-Holzboog (1973).
Hans-Paul Schwefel (1974): Numerische Optimierung von Computer-Modellen (thèse de doctorat). Réimprimé par Birkhäuser (1977).
Simon, D. (2013): Algorithmes d'optimisation évolutive , Wiley.
Intelligence computationnelle : une introduction méthodologique par Kruse, Borgelt, Klawonn, Moewes, Steinbrecher, Held, 2013, Springer, ISBN 978-1-4471-5012-1
Rahman, Rosshairy Abd.; Kendall, Graham; Ramli, Razamin; Jamari, Zainoddin; Ku-Mahamud, Ku Ruhana (2017). "Formulation d'aliments pour crevettes via un algorithme évolutif avec une heuristique de puissance pour la gestion des contraintes" . Complexité . 2017 : 1-12. doi : 10.1155/2017/7053710 .

Languages

In other projects