L'évolution artificielle : un outil d'optimisation stochastique

29/08/2017
Auteurs : Evelyne Lutton
Publication REE REE 2006-7
OAI : oai:www.see.asso.fr:1301:2006-7:19692
DOI :

Résumé

L'évolution artificielle : un outil d'optimisation stochastique

Métriques

18
4
2.57 Mo
 application/pdf
bitcache://2ab86e00aa9dd71f7413ec98040a9781074128f1

Licence

Creative Commons Aucune (Tous droits réservés)
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/1301:2006-7/19692</identifier><creators><creator><creatorName>Evelyne Lutton</creatorName></creator></creators><titles>
            <title>L'évolution artificielle : un outil d'optimisation stochastique</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2017</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Tue 29 Aug 2017</date>
	    <date dateType="Updated">Tue 29 Aug 2017</date>
            <date dateType="Submitted">Fri 10 Aug 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">2ab86e00aa9dd71f7413ec98040a9781074128f1</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>33463</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Dossier DU TRAITEMENT NUMÉRIQUE À LA GESTION DES CONNAISSANCES DEE N 0 UVELLES VO 1 ES D'l NVESTI GATI 0 N ? (1 le partie) L'évolution artificielle : un outil d'optimisation stochastique Evelyne LUTTON INRIA, Equipe COMPLEX Mots clés Darwinismeartificiel Algorithmesgénétiques, Programmationgénétique, Stratégiesd'évolution, Algorithmesévolutionnaires Les informaticiens s'inspirent des principes d'évolution naturelle pour attaquer des problèmes complexes qui résistent aux méthodes d'optimisation classiques. 1. L'informatique Darwinienne La transposition informatique de la très célèbre théo- rie de Darwin, consiste à imiter grossièrement au sein d'un programme la capacité d'une population d'organis- mes vivants à s'adapter à son environnement à l'aide de mécanismes de sélection et d'héritage génétique. Depuis une quarantaine d'années de nombreuses méthodes d'op- timisation stochastique sont fondées sur ce principe. Le Darwinisme artificiel ou les algorithmes évoluttonnai- res correspondent à un ensemble de techniques appelées par exemple algorithmes génétiques, programmation génétique, stratégies d'évolution ou programmation évo- lutionnaire. L'ingrédient commun de ces techniques est la manipula- tion de populations (représentant par exemple des points d'un espace de recherche) qui évoluent sous l'action d'opérateurs aléatoires. L'évolution est usuellement orga- nisée en générations et copie de façon très simplifiée la génétique naturelle. Les moteurs de cette évolution sont d'une part la sélection, liée à la performance d'un indi- vidu, à une mesure de sa qualité vis à vis du problème que l'on cherche à résoudre, et d'autre part les opérateiirs génétiques, usuellement nommés croisement et mutation, qui génèrent les individus d'une nouvelle génération.c L'efficacité d'un algorithme évolutionnaire dépend du paramétrage du processus stochastique précédent : les populations successives doivent converger vers ce que l'on souhaite, c'est-à-dire le plus souvent l'optimum glo- bal de la fonction de performance. Une grande part des recherches théoriques sur les algorithmes évolutionnaires est consacrée à ce délicat problème de convergence, et à celui de savoir ce qui rend la tâche aisée ou difficile pour un algorithme évolutionnaire. Des réponses théoriques existent : ces algorithmes convergent [50, 2, 25, 13, 381. Mais d'autres questions cruciales d'un point de vue prati- que (vitesses de convergence, notamment) restent ouver- tes. On peut cependant dire que l'intérêt des algorithmes évolutionnaires en tant qu'heuristiques de recherche sto- chastique est raisonnablement fondé d'un point de vue théorique, confortant ainsi des constatations expérimenta- les vieilles d'une quarantaine d'années. Par ailleurs, les algorithmes évolutionnaires sont des méthodes d'optimisation stochastique d'ordre 0, en effet aucune propriété de continuité ni de dérivabilité n'est nécessaire au bon déroulement de la méthode, seule la connaissance des valeurs de la fonction à optimiser aux points d'échantillonnages est requise (parfois même une approximation suffit). Ces méthodes sont donc particuliè- rement adaptées aux fonctions très irrégulières, mal conditionnées ou complexes à calculer. En revanche un algorithme évolutionnaire a un coût de calcul qui peut ESSENTtEL SYNOPStS Les principesde lathéorie de l'évolution selon Darwin servent de baseaux algorithmesd'évolution artificielle, dont les plus connus sont lesalgorithmes génétiques.Nousexpliquonsce quesont ces méthodes d'optimisation stochastique, et pourquoi leur réglage est délicat.Leurflexibilité est un atout, car ils permettent de mani- pulerdes variablesou des structuresde naturesdifférentes,ce qui s'est avérétrès puissantdans nombre d'applications réelles. Evolutionary algorithms, among with the famous genetic algo- rithms, are based on the principlesof Darwiniantheory of evolu- tion. These stochastic optimisation methods have been proved very efficient in various applications.If the tuning of the se algo- rithm is sometimes quite delicate,their versatilityis a majoradvan- tage as they are able to handle variablesor structures of different natures. REE N 8 Septembre2006 Dossier DU TRAITEMENT NUMÉRIQUE À LA GESTION DES CONNAISSANCES DE NOUVELLES VOIES D'INVESTIGATION ? (le'e partie devenir important. Cela fonde la recommandation usuelle de leur emploi dans le cas où les méthodes standards plus rapides sur le plan du calcul (par exemple des méthodes de descente de gradient) 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. D'autres problèmes (comme les problèmes dynamiques ou les problèmes interactifs) peuvent être traités à l'aide d'une approche évo ! utionnaire. Il est aussi souvent avan- tageux d'hybrider approche traditionnelle et approche évolutionnaire. Malgré l'attrayante simplicité d'un processus évolution- naire, fabriquer un algorithme évolutionnaire efficace est une tâche difficile, car les processus évolutionnaires sont très sensibles aux choix algorithmiques et paramétriques. L'élaboration d'un algorithme évolutionnaire efficace repose sur une très bonne connaissance du problème à traiter, sur beaucoup de créativité, et sur une bonne com- préhension de la mécanique évolutionnaire. L'emploi en « boîte noire » est fortement déconseillé. Cela dit, de nombreuses « succes-stories » industriel- les existent,'et les applications sont très variées : applica- tions réelles complexes comme le contrôle du flux de pipelines de gaz, le design de profils d'ailes, le routage aérien ou la planification de trajectoires de robots, ou pro- blèmes plus théoriques en combinatoire, en théorie des jeux, en modélisation, économique, en finance, en com- mande de processus ou en apprentissage [20, 39, 1, 48, 28, 16, 11]. 2. Concepts de base Les algorithmes évolutionnaires ont empruntés (et considérablement simplifiés !) des principes de génétique naturelle. Ainsi l'on parle d'individus qui représentent des solutions ou des points d'un espace de recherche aussi appelé environnement. C'est sur cet environnement que l'on recherche le maximum d'une fonction dite,fonction d'évaluation oufilness. Usuellement, les individus sont représentés sous forme de codes (réels, binaires, de taille fixe ou variable, simples ou composés), ce sont des chromosomes, des génomes, ou des génotypes, les solutions correspondantes (les vecteurs de l'espace de recherche) étant des phénotypes. L'algorithme évolutionnaire fait évoluer sa population de façon à adapter les individus à l'environnement, ce qui se traduit par une maximisation de la fonction d'évaluation sur les individus de la population. Ce qui est présenté ci-après est un canevas de base, un algorithme évolutionnaire « canonique ». Les applica- ,'%Il clr lu sulutinn (1 t.'1 1-noe- ,,, 1.1 1 1 Séleclicm- Sélecti ") l clit Il il, t 2 Figzrre J. Oraai7igi-ciiiitiie de l'algoritiiiiie éiohitionnaiié.iinl ? le. tions réelles sont évidemment plus complexes, le pro- blème essentiel étant d'adapter, de créer même, les opéra- teurs répondant aux spécificités du problème. 2.1. La boucle évolutionnaire Le premier élément est une boucle générationnelle de populations d'individus correspondant chacun à une solution au problème considéré (voir figure 1 et [12, 16, 3 6, 5 1]). L'initialisation est usuellement aléatoire (d'autres straté- gies sont envisageables notamment dans un espace de recherche complexe ou de grande dimension). C'est là que l'on peut injecter la ou les solutions initiales que l'on a pu obtenir par ailleurs (par exemple à l'aide d'autres techniques de résolution). Si l'initialisation a théorique- ment peu d'importance (on converge en limite toujours vers l'optimum global), on constate expérimentalement que cette étape influence énormément la variance des résultats ainsi que la rapidité de convergence. Il est ainsi souvent très avantageux d'injecter le maximum de connaissances a priori sur le problème par le biais de l'initialisation. La sélection a pour rôle de décider quels individus de la population courante seront autorisés à se reproduire. La sélection est fondée sur la qualité des individus, estimée à l'aide de la fonction de « fitness », aussi appelée « fonc- tion d'évaluation » ou « Performance ». Le paramètre principal de cette étape de sélection est ce que l'on appelle la pression sélective qui correspond glo- balement au quotient de la probabilité de sélection du meilleur individu sur la probabilité de sélection de l'indi- vidu moyen de la population courante. L'influence de la pression sélective sur la diversité génétique est énorme, et le bon déroulement de l'algorithme en dépend. Un excès de pression sélective amène un appauvrissement généti- que des populations (perte de diversité génétique) et une Voir [16] pages126à 129,pourdesapplicationsdéveloppéesjusqu'à 1989,et le sitedu réseauEuropeenEvoNet(http ://evonet.dcs.napier.ac.uk/) pourunpaneld'applicationsrécentes. REE NO 8 Septembre2006 L'évolution artificielle : un outi d'optimisation stochastique concentration trop rapide de la population autour de ses meilleurs individus (risque de convergence prématurée par blocage dans un optimum local). La plus simple des méthodes de sélection, la sélection proportionnelle, se fait par tirage aléatoire biaisé où la probabilité de sélection d'un individu est directement proportionnelle à sa valeur de fitness : Taillepop P (i) lfitness (i)/ (Ifitness (k » k - 1 Cette méthode ne permet pas de contrôler la pression sélective. Les méthodes de sélection les plus efficaces permet- tent un contrôle de la pression sélective, les plus usuelles sont : a Le scaling qui ré étalonne linéairement la fonction de fitness pour que le nouveau maximum de la fitness soit C fois sa moyenne sur la population courante. C représente une mesure de la pression sélective (voir [16]). En règle générale, C est fixé entre 1,2 et 2. . La sélection par le rang consiste à affecter une probabi- lité de sélection proportionnelle au rang de chaque indi- vidu dans la population classée par ordre de fitness décroissant. . La sélection par tournoi consiste à tirer aléatoirement T individus dans la population (indépendamment de leurs valeurs de fitness), et à choisir le meilleur d'entre eux. La pression sélective est directement reliée à la taille du tournoi : plus T est grand, plus elle est importante. La reproduction génère des descendants. Dans le schéma canonique de l'algorithme génétique (AG) « à la Goldberg » [16], 2 parents donnent 2 enfants, ainsi on sélectionne un nombre de parents égal au nombre d'en- fants désirés, mais évidemment bien d'autres schémas moins conventionnels peuvent être programmés (2 parents pour 1 enfant, n parents pour p enfant, etc.). Les deux opérations principales sont le croisement, qui combine les gènes de 2 parents, et la mutation qui consiste en une légère perturbation du génome. Ces opé- rations sont appliquées aléatoirement, à l'aide de deux paramètres, la probabilité de croisement Pc, et la probabi- lité mutation p. Intuitivement, la sélection et le croisement permettent une concentration de la population autour des « bons » individus (exploitation des informations). Au contraire, la mutation a pour effet de contrarier l'attraction exercée par les meilleurs individus de façon à laisser la population explorer d'autres zones de l'espace de recherche. L'évaluation consiste à calculer (ou estimer) la qualité des individus nouvellement créés. C'est là, et uniquement là, qu'intervient la fonction à optimiser. Aucune hypo- thèse n'est faite sur la fonction elle-même, excepté le fait qu'elle doit servir de base au processus de sélection (elle doit pouvoir permettre de définir une probabilité ou au minimum un ordre sur les solutions). Le remplacement gère la composition de la génération n + 1. Un mécanisme d'élitisme est souvent recommandé pour ne pas perdre la mémoire des bons individus visités : les stratégies usuelles consistent à transmettre directement un pourcentage des meilleurs individus de la population courante dans la population suivante (pourcentage de renouvellement ou « Génération gap » [26]). Les straté- gie d'évolution (u, À) et (t + le) [4, 21, 22] génèrent À descendants à partir d'une population de t individus. La stratégie «, » gère l'élitisme par le biais de la différence l - le (on garde les t - le meilleurs individus de la popu- lation courante et on complète par les descendants), tan- dis que la stratégie « + » est plus adaptative à partir d'un ensemble intermédiaire de taille t + ; constitué des t individus de la population courante et des le descendants, on sélectionne les À meilleurs individus de la génération suivante. Dans le cas d'implantations parallèles il est parfois utile de s'affranchir de la notion de génération. Le schéma sta- tionnaire injecte directement chaque nouvel individu dans la population courante via une opération de rempla- cement, dite « sélection inverse » (déterministe ou aléa- toire), pour remplacer les plus mauvais individus de la population courante par des nouveaux venus. L'arrêt du processus au bon moment est essentiel du point de vue pratique, mais si l'on a peu ou pas d'infor- mations sur la valeur-cible de l'optimum recherché, il est délicat de savoir quand arrêter l'évolution. Une stratégie couramment employée consiste à stopper l'algorithme dès qu'un nombre maximal d'itérations est atteint, ou qu'une stagnation est identifiée. Il est aussi possible de tester la dispersion de la population. Il est évident qu'une bonne gestion de l'arrêt de l'évolution contribue de façon importante à l'efficacité de la méthode, et intervient au même titre que le réglage des principaux paramètres de l'algorithme (taille de population, probabilités de croise- ment et de mutation, pression sélective, proportion de remplacement). Intuitivement, on peut voir un AE comme un algorithme de « tâtonnement aléatoire » où la composante aléatoire doit être dosée intelligemment, en fonction de ce que l'on peut savoir a priori sur le problème à résoudre : trop d'ex- ploration aléatoire fait perdre du temps, trop peu risque de le bloquer dans un optimum local. 2.2. Représentations et opérateurs Les opérateurs génétiques dépendent directement du choix de la représentation, c'est un des aspects qui diffé- rencie les algorithmes génétiques des stratégies d'évolu- tion, de la programmation génétique, ou de l'évolution grammaticale. Nous verrons rapidement ci-dessous les REE NO 8 Septembre2006 Dossier DU TRAITEMENT NUMÉRIQUE À LA GESTION DES CONNAISSANCES DE NOUVELLES VOIES D'INVESTIGATION ? (l'ce partie) Parents Descendants ..., 1 p,>i,,t Parents Descendants L,' Parents Descendants (...... t Figzrre 2. Croiseiiients binaires. représentations, les opérateurs, les stratégies de sélection et de remplacement les plus classiques, mais on pourra trouver dans la littérature bien d'autres déclinaisons de ces composantes dans des espaces de recherche non stan- dard, en fonction des différentes applications (espaces de listes, de graphes,...). 2.2. 1. Représentation discrète Les algorithmes génétiques sont initialement fondés sur l'emploi d'une représentation binaire des solutions, assez rapidement étendue ensuite à une représentation discrète. Chaque individu de la population est représenté par une chaîne de longueur fixe, dont les éléments (gènes ou allèles) sont choisis dans un alphabet fini. Cette représentation sied évidemment bien à des problèmes combinatoires discrets mais des problèmes continus peuvent aussi être abordés grâce à un échantillonnage de l'espace de recherche. Dans ce cas la précision d'échantillonnage (longueur du chromo- some) est un paramètre important de la méthode [49]. Les opérateurs de croisement les plus classiques, utilisés dans les applications d'optimisation sont décrits dans la figure 2. Le croisement à un site consiste à choisir aléatoi- rement un point sur le chromosome, et à échanger les chaînes de code autour de ce point. Le croisement à deux sites effectue également le même échange de portions de codes, mais autour de deux points de croisements. Enfin, le croisement uniforme en est une généralisation multi- site : chaque gène d'un descendant est choisi aléatoire- ment parmi les gènes des parents ayant la même position dans le chromosome (un second descendant est construit en prenant les choix complémentaires). D'autres croise- ments spécialisés existent, comme dans le cas du pro- blème du voyageur de commerce ou des problèmes d'or- donnancement, qui tiennent compte de la structure parti- culière du codage employé. La mutation binaire classique décide avec une proba- Parent -Li loolitiôôi 1111'1- () ()] 1 DescendantDescendant LI-I) L ") il il toi-J i Io Figure 3. Mutation binaire. bilité p. si chaque bit du chromosome doit subir une inversion ou non (figure 3). La probabilité de mutation pm est habituellement très faible et constante tout au long de l'évolution de l'AG, m ais on implante aussi des sché- mas où la probabilité de mutations décroît au fur et à mesure des générations'. 2.2.2. Représentation continue La représentation continue, ou représentation réelle, est historiquement liée aux approches de type stratégies d'évolution. Dans cette approche, la recherche s'effectue dans Rn ou une partie de celui-ci. Les opérateurs généti- ques associés à cette représentation sont soit des exten- sions continues des opérateurs discrets, soit directement des opérateurs continus. Les croisements discrets consistent à mélanger les gènes réels d'un chromosome, sans toucher à leur contenu, on peut ainsi adapter directement les opérateurs de croise- ment binaires précédents, par exemple les croisements à un point, plusieurs points ou les croisements uniformes. L'avantage de la représentation continue est certainement mieux exploitée avec des opérateurs spécialisés, dits croi- sements continus qui mélangent plus intimement les com- posantes des vecteurs parents pour fabriquer de nouveaux individus. Ainsi le croisement barycentrique, encore appelé croisement intermédiaire ou arithmétique, produit un descendant x'à partir d'un couple de vecteurs (x, y) de Rn grâce au tirage aléatoire d'une constante a, choisie uniformément dans [0, 1] (ou [-E, 1 + E] pour le croise- ment BLX-E), tel que : vi (E il... In, X'i - axj + üc) Yi La constante a peut être tirée une fois pour toute pour l'ensemble des coordonnées de ', ou tirée indépendam- ment pour chacune de ses coordonnées. La généralisation à un croisement à plus de 2 parents, voire même à l'ensemble de la population (croisement « global ») est assez directe [40]. Beaucoup d'opérateurs de mutation ont été proposés et expérimentés pour la représentation réelle. Le plus classi- que est la mutation Gaussienne, qui consiste à ajouter un bruit Gaussien aux composantes du vecteur-individu 22 Mêmes'il existeactuellementdesalgorithmesgénétiquesàcodageréel,lecodagediscretestlacaractéristiquehistoriqueducourant"algorithmegénétique." 3 Il aétéeneffetprouvéqu'un tel schémaconvergeversl'optimumglobaldel'espacederecherchesi la probabilitédemutationdécroîtàchaquegéné- rationselonuneloi logarithmique[13]. REE NO 8 Septembre2006 L'évolution artificielle : un outi d'optimisation stochastique : ; :4.'04- 1 v !-------------------------------------------------------------------- Figure 4. Exeiiiple d'une représentation arborescente de la fonction ( (cos(x) + 2 * y) * (1 + x ». r concerné, ce qui implique l'ajustement d'un paramètre supplémentaire, cr, la déviation standard de ce bruit : 'Vi E il... 1 n, x'i = xi + N (O,ci) L'ajustement de a est relativement complexe (trop petit, il ralentit l'évolution, trop grand, il perturbe la convergence de l'algorithme évolutionnaire). De nom- breuses stratégies ont été proposées, consistant à rendre ce paramètre variable au cours de l'évolution, soit en fonction du temps, de la valeur de fitness, dépendant des axes de l'espace de recherche (mutations non isotropes), ou encore auto-adaptatif (c'est-à-dire considéré comme un paramètre supplémentaire, optimisé directement par l'algorithme). Des études ont aussi été conduites sur l'emploi de bruits non Gaussiens. Une excellente revue des divers opérateurs génétiques se trouve dans [6]. 2.2.3. Représentation par arbre La programmation génétique (PG) correspond à une représentation de structures de longueurs variables sous forme d'arbres. La PG a été imaginée à l'origine pour manipuler des programmes codés en LISP [28], dans le but créer des programmes qui puissent résoudre des pro- blèmes pour lesquels ils n'ont pas été explicitement pro- grammés. La richesse de la représentation arborescente de taille variable est l'une des clés du succès de cette technique, en effet beaucoup de problèmes d'optimisa- tion, de commande ou de contrôle peuvent se formuler comme un problème d'induction de programme. Un algorithme de PG explore un espace de program- mes récursivement composés à partir d'éléments d'en- sembles de fonctions, de variables et de tenninaisons (données, constantes)'. Les individus de la population sont des programmes qui, lorsqu'ils sont exécutés, pro- duisent les solutions au problème posé. Les croisements sont le plus souvent des échanges de sous arbres. Les mutations sont plus complexes, on en distingue plusieurs suivant leur action sur la structure du génome (suppression ou ajout de noeud, modification de la fonction d'un noeud, mutation des constantes (valeurs continues), mutation des variables discrètes). Les applications de la programmation génétique sont très nombreuses, par exemple en contrôle optimal, en pla- nification de trajectoires et d'actions en robotique, ou pour la régression symbolique (recherche d'une formule mathématique qui modélise au mieux un ensemble fini de données). 3. Un peu plus que de l'optimisation Faire évoluer une population sur un espace de recher- che selon les principes décrits précédemment permet non seulement de localiser l'optimum global d'une fonction complexe (cela est même prouvé théoriquement, voir par exemple [50, 2, 25, 13, 38]) mais aussi de glaner d'autres informations sur la fonction et son espace de recherche. Par exemple, si la fonction à optimiser est multimodale, des modifications relativement légères de la boucle évo- lutionnaire permettent de faire converger la population en sous-populations localisées sur les « niches écologiques » correspondant aux différents optima. Ces méthodes consistent à contrôler la diversité des populations ou à implanter une notion de partage des ressources entre indi- vidus voisins [16, 17] pour favoriser l'émergence d'espè- ces distinctes. Elles nécessitent la définition d'une mesure de distance entre chromosomes. Il est aussi parfois possible de formuler un problème comme une tâche d'apprentissage collectif, la solution recherchée étant construite à partir de l'ensemble d'une population évoluée et non plus à partir du seul meilleur individu de la population finale. Les techniques les plus connues de cette tendance sont les systèmes de classeur [8], l'approche Parisienne [10], les techniques de coévo- lution (proie/prédateurs), et les techniques à base de colo- nies d'insectes sociaux, et parmi ces dernières les algo- rithmes à colonies de fourmis (ou ACO, ant colony opti- misation) [14, 15]. L'approche Parisienne a notamment permis des appli- cations en « text-retrieval » [29, 30], des applications artistiques [9] et des applications temps-réel (vision sté- réo par algorithme des mouches [33]), ce qui est tout à fait notable pour des algorithmes ayant une réputation d'extrême gourmandise en temps de calcul ! Par ailleurs, dans certaines applications, l'identification précise des quantités à optimiser est parfois difficile, par- ticulièrement dans des cas où il existe plusieurs critères 4 Un problèmecourammentrencontrédanscedomaineestceluidu« bloat »,c'est-à-diredela saturationdel'espacemémoireliéeàunecroissancedéme- suréedestaillesd'arbresaucoursdel'évolutionsi l'on neprendpaslaprécautiondelimiter lataille desgénomesparunmoyenouunautre[3 1, 43]. REE N 8 Septembre2006 Dossier DU TRAITEMENT NUMÉRIQUE À LA GESTION DES CONNAISSANCES DE NOUVELLES VOIES D'INVESTIGATION ? (lele partie) 1 de jugement, éventuellement contradictoires (maximiser la résistance d'une pièce mécanique, tout en minimisant son poids et son coût de fabrication, par exemple). Ces optimisations sont d'autant plus complexes à traiter que l'on ne sait pas forcément estimer les poids relatifs des divers critères et contraintes enjeu. On parle alors d'optimi- sation multicritère, sans donner de priorités aux différents critères. La solution à un problème d'optimisation multicri- tère est alors un ensemble de solutions, formant ce que l'on nomme lefront de Pareto, C'est-à-dire un ensemble de com- promis optimaux. L'idée d'utiliser des AE pour trouver le front de Pareto d'un problème multicritère vient alors assez naturellement, au prix d'une légère modification du schéma évolutionnaire classique. La procédure de sélection doit notamment être adaptée de façon à pousser la population vers le front de Pareto, tout en maintenant une bonne diver- sité pour assurer son échantillonnage. Là encore, la maîtrise de la diversité de la population est cruciale. Une étude com- parative des méthodes évolutionnaires pour l'optimisation multicritère se trouve dans [51]. Enfin, si ce que l'on souhaite optimiser n'est pas mesurable à l'aide d'une fonction mathématique (par exemple la sim- ple notion de " satisfaction "), il s'agit alors de faire interve- nir un utilisateur humain dans la boucle évolutionnaire. On parle alors d'algorithmes évolutionnaires interactifs. Les premiers travaux sur dans ce domaine [42, 41, 46, 3] concernaient la création artistique et la synthèse d'images numériques. De nombreuses études touchent maintenant bien d'autres domaines d'application, où les quantités à optimiser sont liées à des jugements subjectifs (visuels ou auditifs). Des travaux tout à fait caractéristiques sur le sujet sont par exemple [45] pour l'adaptation de prothèse auditi- ves, [27] pour le développement de lois de contrôle de bras de robot qui correspondent à des mouvements souples, pro- ches de l'humain et psychologiquement bien perçus par l'utilisateur, ou [37] pour le design de pages HTML. On pourra trouver une revue de ce vaste sujet dans [44]. 4. Conclusion La physique et l'ingénierie ont été source de nom- breux problèmes réels complexes pour le Darwinisme artificiel, par exemple pour l'optimisation de structures mécaniques [47, 32, 19], de profils d'ailes d'avion, de tuyères de réacteurs, ou de processus chimiques indus- triels. Des domaines comme l'économie et la finance (simulation d'économies artificielles, optimisation de portefeuilles bancaires), le traitement d'images et de signaux (détection de formes caractéristiques, vision sté- réo [33], ou débruitage d'images [35] par exemple), la biologie et la médecine (séquencement du génome, ana- lyse du repliement de protéines, analyse de données et imagerie médicale) ont aussi largement puisé dans le panel des méthodes évolutionnaires. Il faut toutefois prendre garde à ne pas utiliser les concepts d'évolution artificielle pour produire des algorithmes ridi- culement coûteux en temps de calcul. D'un point de vue expérimental, il ne faut donc jamais hésiter à comparer et à hybrider un AE avec des techniques classiques du domaine d'application visé. Comparer sa méthode évolu- tionnaire à une recherche aléatoire brute, de façon à éva- luer le niveau d'intelligence et le coût de calcul induit par l'évolution, peut être riche d'enseignements [34]. L'expérience prouve aussi que si les composantes (autre- ment dit la représentation et la topologie de recherche induite par les opérateurs génétiques associés) ainsi que les paramètres de l'évolution sont soigneusement réglés, il possible d'obtenir des algorithmes extrêmement effica- ces et rapides [7]. Faciliter le réglage des paramètres est un des enjeux des recherches actuelles sur les algorithmes évolutionnaires : les travaux théoriques récents, essentiellement en ce qui concerne l'étude de la convergence de ces algorithmes, ont permis de poser des bases Solides. On commence à comprendre plus finement quand et pourquoi un AE est efficace. Le design d'algorithmes auto-adaptatifs répond aussi à ce besoin de recettes de réglage des paramètres : laisser l'évolution prendre en charge elle-même cette tâche est certainement une excellente solution, explorée par de nombreux chercheurs du courant " stratégies d'évolution : si l'on prend bien garde de ne pas alourdir trop l'algo- rithme. Comme toujours, ce choix est soumis à un com- promis : les capacités adaptatives sont coûteuses, il faut les exploiter à bon escient. L'idée d'exploiter le Darwinisme artificiel dans un cadre élargi, en ne se limitant plus à des tâches l'optimisation " simples, " est enfin un courant qui prend actuellement beaucoup d'ampleur, tout comme les travaux sur l'évolu- tion interactive. Le dynamisme de ce domaine de recher- che se concrétise par le nombre de croissant conférences internationales et de workshops consacrés exclusivement à ce thème, ainsi que par le nombre de publications de livres, de revues et de logiciels. Références [1] J. ALBERT,F FERRI,J. DOMINGO et M. VINCENS.An Ap- proachto Natural SceneSegmentationby Means of Genetic Algoritms with FuzzyData. ln PatternRecognitionand Image Analysis, pages 97-113, 1992. Selected papers of the 4th Spanish Symposium (Sept 90), Perezde la Blanca Ed. [2] L.ALTENBERG.Evolutionary Computation ModelsFromPopu- lation Genetics. part 2: An historical toolbox. In Congresson Evolutionary Computation, 2000, Tutoria. [3] P J. ANGELINE.Evolving fractal movies./n Genetic Program- ming 1996: Proceedings of the First Annual Conference, John R KOZA, David E. GOLDBERG,David B FOGEL et Rick L RIOLO (Eds), pages 503-511,1996. [41 T BAECK et H. P SCHWEFEL.An Overview of Evolution- nary Algorithms for Parameter Optimisation. Technical REE No 8 Septembre2006 L'évolution artificielle : un outi d'optimisation stochastique report, University of Dortmund, 1992. [5] VV. BANZHAF, Handbook of Evolutionary Computation, chapter Interactive Evolution Oxford University Press, 1997. [61 S. BEN HAMIDA. Algorithmes évolutionnaires. prise en compte des contraintes et applications réelles. PhD thesis, Université Pris-Sud XI, spécialité informatique, 2001. 29 Mars 2001. [7] A. BOUMAZA et J. LOUCHET. Dynamic Files Using Real- time Evolution in Robotics. In EVO-IASP 2001 Workshop, Artificial Evolution in Image Analysis and Signal Processing, 2001 [8] L. BULL et T C. FOGARTY. Co-Evolving Communicating Classifier Systems for Tracking. pages 522-527, Innsbruck, Austria, 13-16April 1993, Springer-Veriag,VVien, [91 J. CHAPUIS et E. LUTTON. Artie-Fract Interactive Evolution of Fractals. In 4th International Conference on Generative Art, Milano, Italy, December 12-14 2001 [IOJ P COLLET, E. LUTTON, F RAYNAL et M. SCHOENAUER. Polar Ifs + Parisian Genetic Programming Efficient IFS Inverse Problem Solving. Genetic Programming and Evolvable Machines Journal, 1(4) : 339-361, 2000. October. 1111 Y. DAVIDOR. Genetic Algorithms and Robotics. A Heuristic Strategy for Optimization. World Scientific Series in Robotics and Automated Systems - vol 1. VVord Scientic, Teaneck, NJ, 1991. [12] L. DAVIS. Genetic Algorithms and Simulated Annealing. Plttman, London, 1987 [131 T E. DAVIS et J. C. PRINCIPE. A Simulated Annealing Like Convergence Theory for the Simple Genetic Algorithm. In Proceedings of the Fourth International Conference on Genetic Algorithm, pages 174-182, 1991 13-16 July. [14] M. DORIGO et G. DI CARO. The Ant Colony Optimization Meta-Heuristic. New Ideas in Optimization, pages 11-32, 1999. D. Corne, M. Dorigo and F Glover, editors, McGraw-Hill. [15] M. DORIGO, G. DI CARO et L. M. GAMBARDELLA. Ant Algo- rithms for Discrete Optimization. Artificial Life, 5 (2) : 137-172, 1999. [16] D. E. GOLDBERG. Gene tic AIgorithms in Search, OptimlZation, and Machine Learning. Addison-Wesley Publishing Com- pany, inc., Reading, MA, January 1989. [17] D. E. GOLDBERG et J. RICHARDSON. Genetic Algorithms with Sharing for Multimodal Function Optimization. ln J. J. Grefenstette, editor, Genetic Algorithms and their Applications, pages 41-49, Hillsdale, New Jersey, 1987 Lawrence Erlbaum Associates. [181 D. E. GOLDBERG et R. E. SMITH. Nonstationary Function Optimization Using Genetic Algorithms with Dominance and Diploidy. In J. J. Grefenstette, editor, Proceedings of the Second International Conference on Genetic Algorithms and their Applications, pages 59-68, Hillsdale, New Jersey, 1987 Lawrence Erlbaum Associates. [19] H. HAMDA, F JOUVE, E. LUTTON, M. SCHOENAUER et M. SEBAG. Compact Unstructured Representations in Evolutionary Topological Optimum Design. Applied Intelligence, 16, 2002. [201 A. HILL et C. J. TAYLOR. Model-Based Image Interpretation using Genetic Atgorithms./mage and Vision Computmg, 10 (5) 295-301, June 1992. [21] F HOFFMEISTER et T BÀCK. Genetic Algorithms and Evolution Strategies : Similarities and Differences. In H. P Schwefel and R. Mânner, editors, Parallel Problem Solving from Nature - Proceedings of Ist Workshop, PPSN 1, volume 496 of Lecture Notes ln Computer Sc/ence. pages 455-469, Dortmund, Germany, 1-3 Oct 1991. Springer- Verlag, Berlin, Germany. [22] F. HOFFMEISTER et T BAECK. Genetic Algorithms and Evo- lution Strategies : Similarities and Differences. Technical Report SYS-1/92, University of Dortmund, February 1992. [231 J. H. HOLLAND. Outline for a Logical Theory of Adaptative systems. Journal of the association for the Computing Machinery, (3) 297-314, 1962. [24] J. H. HOLLAND. Adaptation in Natural and Artificial System. Ann Arbor, University of Michigan Press, 1975. [25] J. HORN. Finite Markov Chain Analysis of Genetic Algorithms with Niching. Illi - GAL Report 93002, University of Ilinois at Urbana Champaign, Department of General Engineering, 117 Transportation Building, 104 South Mathews Avenue, Urbana, IL 61801-2996, February 1993. J261 K. A. DE JONG. Analysis of the Behavior of a Class of Genetic Adaptive Systems. PhD thesis, University of Michigan, 1975. 5140B. [27] S. KAMOHARA, H. TAKAGI et T TAKEDA. Control Rule Acquisition for an Arm Wrestling Robot. ln IEEE Int Conf. on System, Man and Cybernetics (SMC'97), volume 5, Orlando, FL, USA, 1997 [281 J. R. KOZA. Genetic Programming. MIT Press, 1992. [29] Y U\NDR ! N-SCHWE) TZER, P COLLET et E. LUTTON, Inter- active gp for Data Retrieval in Medical Databases. In EUROGP'03. LNCS, Springer Verlag, 2003. [301 Y LANDRIN-SCHWEITZER, P COLLET, E. LUTTON, et T PROST. Introducing Lateral Thinking in Search Engines with Interactiveevolutionary Algorithms. In Annual ACM Symposium on Applied Computing (SAC 2003), Special Track on " Computer Applications in Health Care " (COMPA- HEC 2003), 2003. March 9 to 12, Melbourne, Florida, U.SA [31] W. B. LANGDON et W. BANZHAF. Genetic Programming Bloat without Semantics. ln M. Schoenauer, K. Deb, G. Rudolf, X. Yao, E. Lutton, Merelo. J.J. and H.-P Schwefel, editors, Parallel Problem Solving from Nature - PPSN VI 6th International Conference, Paris, France, September 16-20 2000. SpringerVerlag. LNCS 1917 [32] R. LERICHE et R.T HAFTKA. Optimization of Laminate Stacking Sequence for Buckling load Maximization by Genetic Algorithm. AIAA Journal, 31 (5 951-969, May 1993. [33] J. LOUCHET, M. GUYON, M.-J. LESOT et A. BOUMAZA. Dynamic Flies A New Pattern Recognition Tool Applied to Stereo Sequence Processlng. Pattern Recognition Letters, 2002. N'. 23 pp. 335-345, Elsevier Science BV [34] E. LUTTON, P COLLET, et J. LOUCHET. Easea Compari- sons on Test Functions Galib versus eo. In EAOI Conference on Artificial Evolution, Le Creusot, octobre 2001. [35] J. LÉVY VÉHEL et E. LUTTON. Evolutionary Signal Enhan- cement Based on Hblder Regularity Analysis. ln EVO-IASP 2001 Workshop, Artificial Evolution in Image Analysis and Signal Processing, 2001. REE No 8 Septembre2006 Dossier DU TRAITEMENT NUMÉRIQUE À LA GESTION DES CONNAISSANCES DE NOUVELLES VOIES D'INVESTIGATION ? ll'e partie) 1361 Z. MICHALEVVICZ. Genetic Algorithms + Data Structures = Evolution Programs. Artificial Intelligence. Springer Verlag, NevvYork, 1992. (37] N. Monmarche, G. Nocent, G. Venturini, and P Santini, Artificial Evolution, European Conference, AE 99, Dunkerque, France, November 1999, Selected papers, volume Lecture Notes in Computer Science 1829, Chapter On Generating HTML Style Sheets with an Interactive Genetic Algorithm Based on Gene Frequencies SpringerVerlag, 1999. [381 A.E. NIX et MD VOSE. Modeling Genetic Algorithms with Markov Chains. Annals of Mathematics and Artificial Intelligence, 5 (l) : 79-88, April 1992. [391 G. ROTH et M. D. LEVINE. Geometric Primitive Extraction Using a Genetic Algorithm. In IEEE Computer Society Conference on CV and PR, pages 640-644, 1992. 1401 H-P SCHWEFEL. Numerical Optimization of Computer Models. JohnWiley & sons, New-York, 1981, 1995 2nd edition. [41] K. SIMS. Interactive Evolution of Dynamical Systems. ln First European Conference on Artificial Life, pages 171- 178, 1991. Paris, December. [42] K. SIMS Artificial evolution for Computer Graphics. Computer Graphics, 25 (4) : 319-328, July 1991. [431 T SOULE, J. A. FOSTER et J. DICKINSON. Code Growth in Genetic Programming n John R. Koza, David E. Goldberg, David B Fogel, Rick L. Riolo, editors, Genetic Programming 1996. Proceedings of the First Annual Conference, pages 215-223, Stanford University, CA, USA, 28-31 1996. MIT Press. [441 H. TAKAGI. Interactive Evolutionary Computation System Optimisation Based on Human Subjective Evaluation. In IEEE Int. Conf. on Intelligent Engineering Systems (INES'98), Vienna, Austria, Sept. 17-19 1998. [45] H. TAKAGI et M. OHSAKI. lec-Based Hearing Aids Fitting. In IEEE Int Cont on System, Man and Cybernetics (SMC'99), volume 3, Tokyo, Japan, Oct 12-15 1999. [46] S. J. P TODD et W LATHAM. Evolutionary Art and Compu- ters. Academic Press, 1992. [471 P TROMPETTE, J. L. MARCELIN et C. SCHMELDING. Opti- mal Damping of Viscoelastic Constrained Beams or Plates by Use of a Genetic Algotithm. In IUTAM, 1993, Zakopane Pologne [48] S. TRUVÉ. Using a Genetic Algorithm to solve Constraint Satisfation Problems Generated by an Image Interpreter. In Theory and Applications of Ima_qe Analysis 7th Scandinavian Conference on Image Analysis, pages 378-386, August 1991. Aalborg (DK). [49] J. LÉVYVÉHEL et E. LUTTON. Optimization of Fractal Func- tions Using Genetic Algorithms. In Fractal 93, 1993. London. [501 M. VOSE. Modelng simple genetic agorithms. In FOGA-92, Foundations of Genetic Algorithms, Vail, Colorado, 24-29 July 1992. Emai vose@cs.utk.edu. [51] E. ZITZLER, K. DEB, et L. THIELE. Comparison of Multiob- jective Evolutionary Algorithms : Empirica Evolutionary Computation, 8 (2) : 173-195, 2000. results. L'auteur Evelyne Lutton est chercheur à l'INRIA Rocquencourt depuis 1990. Elle est actuellement responsable scientifique de l'équipe COMPLEX. Ses activités de recherche concernent l'analyse de l'ir- régularité des phénomènes et de l'émergence de celle-ci à diver- ses échelles. Elle étudie en particulier les liens entre i'évo ! ution arti- ficielle et les fractales, tant au niveau théorique qu'applicatif. Evelyne Lutton est membre du comité de pilotage de l'association " Evolution Artificielle " depuis sa création en 1993. REE N 8 Septembre2006