Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Date de publication : 10 juin 2006 Date de dernière validation : 09 mai 2019 Po

Date de publication : 10 juin 2006 Date de dernière validation : 09 mai 2019 Pour toute question : Service Relation clientèle Techniques de l’Ingénieur Immeuble Pleyad 1 39, boulevard Ornano 93288 Saint-Denis Cedex Par mail : infos.clients@teching.com Par téléphone : 00 33 (0)1 53 35 20 20 Réf. : S7218 V1 Algorithmes génétiques et algorithmes évolutionnaires Cet article est issu de : Technologies de l'information | Technologies logicielles Architectures des systèmes par Évelyne LUTTON Résumé Les algorithmes évolutionnaires se basent sur l’observation des phénomènes biologiques mis en œuvre par des populations d’organismes vivants en vue de s’adapter à leur environnement. Ces mécanismes de sélection et d’héritage génétique représentent une version artificielle de la théorie de l'évolution selon Darwin. Cette discipline couvre ainsi un ensemble de techniques, nommées « algorithmes génétiques », « programmation génétique », « stratégies d’évolution », « programmation évolutionnaire ». Le domaine des algorithmes évolutionnaires est en pleine expansion tant au niveau théorique qu’au niveau applicatif. Document téléchargé le : 11/12/2019 Pour le compte : 7200055112 - universite paris 7 diderot // 81.194.22.198 © Techniques de l'Ingénieur | tous droits réservés Toute reproduction sans autorisation du Centre français d’exploitation du droit de copie est strictement interdite. © Techniques de l’Ingénieur S 7 218 − 1 Algorithmes génétiques et algorithmes évolutionnaires par Évelyne LUTTON INRIA – Rocquencourt – Projet FRACTALES es principes de base des algorithmes évolutionnaires (en court AE), dont les plus connus sont les algorithmes génétiques, s’inspirent de l’observa- tion de phénomènes biologiques, plus précisément de la capacité de popula- tions d’organismes vivants à s’adapter à leur environnement à l’aide de mécanismes de sélection et d’héritage génétique. En d’autres termes, ces algo- rithmes évolutionnaires représentent une version artiﬁcielle, informatique, de la théorie de l’évolution selon Darwin. 1. Algorithmes génétiques, algorithmes évolutionnaires et darwinisme artiﬁciel .......................................................................... S 7 218 - 2 1.1 Bref historique du domaine........................................................................ — 2 1.1.1 Darwinisme, évolutionnisme............................................................. — 2 1.1.2 Version artiﬁcielle du darwinisme..................................................... — 3 1.2 Notions et vocabulaire de base.................................................................. — 3 2. Programmer et utiliser un algorithme évolutionnaire................... — 3 2.1 Structure et ingrédients .............................................................................. — 3 2.2 Représentation du problème et les opérateurs génétiques..................... — 5 2.2.1 Représentation discrète ..................................................................... — 5 2.2.2 Représentation continue .................................................................... — 6 2.2.3 Programmation génétique et représentation fonctionnelle............ — 6 2.3 Sélection et pression sélective ................................................................... — 7 2.4 Exploitation/exploration : un dosage délicat............................................. — 7 3. Aperçu théorique : pourquoi et comment ça marche ? ................ — 8 3.1 Approche intuitive : schémas, théorème des schémas ............................ — 8 3.2 Analyse markovienne.................................................................................. — 9 3.3 Analyse fractale, irrégularité des fonctions de ﬁtness ............................. — 9 4. Extensions du modèle............................................................................. — 10 4.1 Copier la biologie des populations : exemple du nichage par partage des ressources......................................................................... — 10 4.2 Approche parisienne, co-évolution et approches à base d’agents.......... — 11 4.2.1 Systèmes de classeurs....................................................................... — 11 4.2.2 Vie artiﬁcielle....................................................................................... — 12 4.2.3 Approche parisienne .......................................................................... — 12 4.3 Multi-objectif................................................................................................ — 12 4.4 Approches interactives................................................................................ — 13 5. Exemples d’applications ........................................................................ — 13 5.1 Vision stéréo pour la robotique par algorithme évolutionnaire : l’algorithme des mouches........................................................................... — 14 5.2 Dans le domaine artistique, exemple du logiciel ArtiE-Fract ................... — 14 6. Conclusion ................................................................................................. — 14 Références bibliographiques ......................................................................... — 16 L Parution : juin 2006 - Dernière validation : mai 2019 - Ce document a ete delivre pour le compte de 7200055112 - universite paris 7 diderot // 81.194.22.198 Ce document a ete delivre pour le compte de 7200055112 - universite paris 7 diderot // 81.194.22.198 Ce document a ete delivre pour le compte de 7200055112 - universite paris 7 diderot // 81.194.22.198 tiwekacontentpdf_s7218 v1 ALGORITHMES GÉNÉTIQUES ET ALGORITHMES ÉVOLUTIONNAIRES ______________________________________________________________________________ Toute reproduction sans autorisation du Centre français d’exploitation du droit de copie est strictement interdite. S 7 218 − 2 © Techniques de l’Ingénieur Depuis une quarantaine d’années, de nombreuses méthodes de résolution de problèmes, d’optimisation stochastique, ont été développées à partir de ces principes simpliﬁés à l’extrême pour les besoins informatiques. C’est ce que l’on commence actuellement à nommer de façon générale le « darwinisme artiﬁciel ». Le terme « algorithmes évolutionnaires » couvre ainsi un ensemble de techniques, nommées « algorithmes génétiques », « programmation génétique », « stratégies d’évolution », « programmation évolutionnaire », suivant la façon dont les principes darwiniens sont traduits dans le modèle artiﬁciel. 1. Algorithmes génétiques, algorithmes évolutionnaires et darwinisme artiﬁciel La caractéristique principale de ces algorithmes est qu’ils mani- pulent des populations – qui représentent par exemple des points d’un espace de recherche – et les font évoluer via des opérations stochastiques. Ces opérations sont usuellement organisées en générations et copient de façon très simpliﬁée la génétique natu- relle. Elles sont de deux types : — la sélection, fondée sur la performance d’un individu, ou plus précisément sur une mesure de la qualité de cet individu vis-à-vis du problème que l’on cherche à résoudre ; — les opérateurs génétiques, le plus souvent nommés croi- sement et mutation, pour faire un parallèle avec la génétique, et qui produisent de nouveaux individus, pour la génération suivante. La réussite d’un tel algorithme est fondée sur l’hypothèse que l’action des opérateurs génétiques sur des individus sélectionnés produit statistiquement des individus de plus en plus proches de la solution recherchée. En d’autres termes, le processus stochastique sous-jacent ainsi produit doit être correctement calibré et paramétré pour que les populations successives convergent vers ce que l’on souhaite, c’est-à-dire le plus souvent l’optimum global de la fonction de performance. Une grande part des recherches théoriques sur les algorithmes évolutionnaires est consacrée à cet épineux problème de convergence, et à celui de savoir ce qui rend la tâche aisée ou difﬁcile pour un algorithme évolutionnaire (notion d’AE-difﬁculté). Comme nous le verrons plus loin, un certain nombre de réponses théoriques rassurantes existent (oui, cela converge, si l’on respecte un certain nombre d’hypothèses), mais d’autres questions cruciales d’un point de vue pratique (vitesses de convergence, notamment) restent ouvertes. On peut dire que pour l’instant un certain nombre de résultats de convergence ont été établis, qui justiﬁent l’efﬁcacité des algorithmes évolutionnaires en tant qu’heuristiques de recher- che aléatoire, confortant ainsi une connaissance empirique datant maintenant d’une quarantaine d’années. Du point de vue de l’optimisation, l’intérêt des algorithmes évolutionnaires est que ce sont des méthodes stochastiques d’ordre 0, c’est-à-dire que seule la connaissance des valeurs de la fonction à optimiser aux points d’échantillonnages est nécessaire (pas de dérivées), ce qui en fait des méthodes d’optimisation utilisables pour des fonctions très irrégulières, mal conditionnées ou complexes à calculer. En revanche, un algorithme évolutionnaire a un coût cal- culatoire qui peut devenir important. Ces deux caractéristiques en font des méthodes adaptées aux cas où les méthodes standards plus rapides du point de vue du calcul (par exemple des méthodes de gradient requérant l’existence et le calcul de dérivées) ne sont plus applicables, du fait qu’elles se trouvent trop rapidement piégées dans des optima locaux : espace de recherche trop vaste, fonctions trop irrégulières, jeu de variables mixtes, par exemple. Nous verrons plus loin que d’autres problèmes (comme les problèmes dynami- ques ou les problèmes interactifs) peuvent être traités à l’aide d’une approche évolutionnaire et qu’il est aussi souvent avantageux d’hybrider approche traditionnelle et approche évolutionnaire. Malgré l’apparente simplicité d’un processus évolutionnaire (ce qui a conduit de nombreux programmeurs à écrire très vite « leur » algorithme génétique, parfois bien décevant), fabriquer un algorithme évolutionnaire efﬁcace est une tâche difﬁcile, car les pro- cessus évolutionnaires sont très sensibles aux choix algorithmiques et paramétriques, aux représentations du problème notamment. Le design des ingrédients de base d’un algorithme évolutionnaire efﬁcace n’est pas une tâche simple et l’expérience prouve que les grandes réussites sont fondées sur une très bonne connaissance du problème à traiter, sur beaucoup de créativité, et sur une bonne compréhension des mécanismes évolutionnaires. Il est tout bonnement hasardeux de considérer ces techniques en « boîte noire », comme un « optimiseur universel ». Cela dit, les « success-stories » sont nombreuses, et les tech- niques évolutionnaires ne sont pas très loin de faire partie de notre quotidien, il sufﬁt par exemple d’aller visiter le site du réseau euro- péen EvoNet (http://evonet.dcs.napier.ac.uk/) pour s’en convaincre... En effet, le champ d’application des algorithmes évolutionnaires est très large : il va des applications réelles complexes comme le contrôle du ﬂux de pipelines de gaz, le design de proﬁls d’ailes, le routage aérien ou la planiﬁcation de trajectoires de robots, à des problèmes plus théoriques et combinatoires, en théorie des jeux, en modélisation économique, en ﬁnance, en commande de pro- cessus et en apprentissage (voir par exemple [2] [20] [30] [34] [45] [73] [86]). 1.1 Bref historique du domaine 1.1.1 Darwinisme, évolutionnisme C’est par l’observation patiente et systématique des lignées d’espèces, et grâce à un voyage effectué de 1831 à 1836 sur le « Beagle » à destination des côtes sud-américaines, des mers du Sud, du Paciﬁque, de l’Australie, de la Nouvelle-Zélande, que Charles Darwin a construit sa théorie de l’évolution des espèces. Les espèces endémiques des îles Galapagos notamment attirèrent son attention, lui uploads/Litterature/ algorithmes-genetiques-pdf.pdf