logo admiroutes Les automates intelligents
robotique, vie artificielle, réalité virtuelle


information, réflexion, discussion
logo automate © Anne Bedel
Jean-Paul Baquiast Jean-Paul.Baquiast@wanadoo.fr
Christophe Jacquemin christophe.jacquemin@admiroutes.asso.fr

Revue n° 10
Retour au sommaire

Interview
Pierre Collet, spécialiste des algorithmes évolutionnaires

Propos recueillis par Christophe Jacquemin
17/04/2001
   

Pierrre Collet

Spécialiste des algorithmes évolutionnaires, Pierre Collet est chercheur dans l'équipe "Evolution artificielle et apprentissage" au Centre de mathématiques appliquées de l'école Polytechnique (http://www.cmap.polytechnique.fr). Docteur en informatique, il est l'auteur d'une trentaine d'articles et de publications.
 
Contact :
Pierre.Collet@Polytechnique.fr
http://www.cmap.polytechnique.fr/~collet/

 
C.J : Pierre Collet, on parle de plus en plus "d'évolution artificielle". Mais que recouvre exactement ce terme ?
Pierre Collet : L'évolution artificielle regroupe plusieurs domaines dont le plus connu, je devrais dire le plus médiatisé, est celui des algorithmes génétiques. En quelques mots, il s'agit d'une méthode de résolution ou d'optimisation de problèmes complexes en employant métaphoriquement les concepts, principes ou mécanismes sous-tendant l'évolution naturelle, et plus spécifiquement le principe de sélection Darwinienne.
Les solutions à un problème donné peuvent souvent être représentées comme une série de paramètres qu'il faut optimiser.

C.J : Pouvez-vous nous expliquer cela à partir d'un exemple ?
P.C. : Prenons par exemple l'optimisation d'un profil d'aile d'avion : la solution au problème, à savoir l'obtention de la  meilleure portance à basse vitesse et de la meilleure finesse à grande vitesse, sera représentée par une série de coordonnées (x,y) de points décrivant un profil d'aile d'avion.
L'idée des algorithmes évolutionnaires est de faire évoluer une population d'ailes d'avion en ne gardant que les meilleurs éléments de génération en génération. Ainsi, dans notre exemple, la liste de coordonnées des points représentant le profil peut être métaphoriquement assimilée à l'ensemble des gènes d'un individu qui est une aile d'avion. Chaque point de l'aile pourra être considéré comme un gène.

C.J : Comment crée-t-on cette évolution ? Comment fait-on évoluer ces gènes ?
P.C. :
la recette est assez simple, et tourne autour de huit points fondamentaux :
1) au départ de l'algorithme, créez par exemple une population de vingt ailes d'avion en choisissant des valeurs aléatoires pour leurs gènes. Le résultat sera vingt profils différents probablement difformes et ayant de très mauvaises performances,
2) évaluez ensuite tous les individus, ce qui, dit en d'autres termes, revient à déterminer la performance des profils qu'ils représentent,
3) ensuite - et c'est là que le principe Darwinien intervient-, sélectionnez parmi ces individus un certain nombre de "géniteurs" (les profils ayant donné les meilleurs résultats lors de l'évaluation, par exemple). Métaphoriquement, seuls les plus adaptés se reproduisent,
4) Créez de nouveaux individus (enfants) en reproduisant les individus sélectionnés (parents) entre eux en imitant la nature, c'est à dire en recombinant leurs gènes (croisement) et/ou en les mutant pour obtenir une nouvelle population de profils d'aile d'avion constituée de la population initiale plus les "enfants" qui viennent d'être créés,
5) évaluez les enfants,
6) supprimez alors de cette population (parents + enfants) certains individus pour revenir à la taille de la population initiale (les moins performants, par exemple),
7) un critère d'arrêt de l'algorithme a-t-il été satisfait (a-t-on atteint un nombre prédéterminé de générations/un enfant satisfaisant les conditions requises a-t-il été engendré) ? Auquel cas l'algorithme s'arrête et donne comme résultat le meilleur individu,
8) retournez à la phase 3, et recommencez .

C.J : Ainsi, on peut considérer que c'est un principe comparable à celui de la sélection naturelle Darwinienne qui a optimisé le profil d'aile d'avion...
P.C :
Exactement... J'ai choisi cet exemple là car je le crois simple à comprendre et représentatif des problèmes complexes : on ne sait pas calculer l'inverse des épouvantables équations de Navier-Stokes (qui permettent d'évaluer un profil). Du coup, on est obligé d'agir à tâtons en faisant varier les paramètres au petit bonheur, en évaluant chaque nouvel essai. Alors, dans ces cas, les algorithmes évolutionnaires permettent de trouver rapidement de bonnes solutions.
Notez d'ailleurs qu'il existe d'autres manières de prendre la nature pour référence afin de résoudre certains problèmes, par exemple en observant l'émergence de comportements collectifs chez les insectes sociaux. Plusieurs équipes s'intéressent ainsi à l'optimisation par essaim ou par colonies de fourmis. On reproduit sur ordinateur les comportements individuels de ces insectes sociaux pour trouver, notamment, le plus court chemin entre deux points, comme le font les fourmilières qui arrivent à optimiser la trajectoire de colonnes de fourmis entre des points de nourriture et la fourmilière, en laissant sur le terrain des informations stigmergiques (les très médiatisées phéromones). Ces algorithmes sont utilisés dans les réseaux pour trouver un ordinateur distant par exemple. Enfin, il faut aussi citer les "animats", capables d'effectuer des tâches, de suivre des pistes et la vie artificielle, dont votre revue a d'ailleurs récemment parlé... (ndr : cf http://www.admiroutes.asso.fr/larevue/2000/ameyer.htm)

C.J : Dans quels cas utilise-t-on les algorithmes évolutionnaires plutôt que d'autres méthodes pour résoudre un problème ? Y-a-t-il des inconvénients à leur utilisation ?
P.C :
Les algorithmes évolutionnaires ont pour principal avantage d'explorer très largement l'ensemble des solutions possibles, appelé espace de recherche. Ainsi, ils se font moins facilement piéger par des optima locaux que les algorithmes d'optimisation classiques comme "la descente de gradient "ou même le "recuit simulé" ont du mal à contourner. Cela dit, ils ne deviennent réellement compétitifs que là où toutes les autres méthodes échouent. Ce sont un peu les algorithmes de la dernière chance, pour trouver de très bonnes solutions à des problèmes dont on a montré mathématiquement qu'il n'existait aucune autre méthode pour les résoudre que d'explorer combinatoirement toutes les possibilités - problèmes dits NP-complets ou NP-difficiles. Les algorithmes d'optimisation classiques sont face à une explosion combinatoire de solutions possibles dont ils se sortent très mal, là où les algorithmes évolutionnaires, grâce à leur large exploration non systématique de l'espace de recherche, trouvent plus rapidement de meilleures solutions.
Leur autre avantage est de pouvoir résoudre des problèmes difficiles à exprimer mathématiquement, ce qui est habituellement le cas des problèmes inverses dont on a décrit un exemple avec l'optimisation des ailes d'avion. En effet, les algorithmes classiques optimisent les paramètres de problèmes mis préalablement en équations mathématiques. Dans le cas des algorithmes évolutionnaires, ceci n'est pas nécessaire. L'évaluation des individus créés peut se faire par comparaison avec un résultat recherché, ou, cas extrême, en demandant son avis à l'utilisateur sur la qualité de la solution trouvée.

C.J :  Par exemple...
P.C :
Les constructeurs automobiles cherchent à maximiser l'agrément de conduite des véhicules qu'ils produisent. On pourrait donc croire que le but recherché serait de minimiser le bruit à l'intérieur de l'habitacle, ce que pourrait faire un algorithme standard en cherchant à minimiser le bruit du moteur, les vibrations transmises par la carrosserie, les roues... Mais ce n'est pas le cas ! Les études montrent que l'utilisateur ne recherche pas le silence mais un bruit "agréable" où doit être présent le son du moteur, avec aussi une pincée de bruit de roulement - suggérant que le moteur, bien qu'audible, est silencieux - mais sans basses fréquences prédominantes... impossible à mettre en équation. Les algorithmes évolutionnaires trouvent leur application dans de tels cas où l'utilisateur fait office de fonction d'évaluation.

C.J :  Les domaines d'applications semblent donc extrêmement vastes...
P.C : Oui. D'ailleurs on pourrait en faire une liste à la Prévert... Les algorithmes évolutionnaires permettent de résoudre non seulement des problèmes purement théoriques en combinatoire, en économie, en apprentissage, dans la théorie des jeux, mais aussi des problèmes liés à des applications réelles complexes. Ainsi, ils sont par exemple utilisés pour analyser des sondages de sous-sol et détecter des champs pétrolifères, pour fabriquer des emplois du temps, pour prévoir les cours de la bourse (nombreuses applications financières), pour contrôler les pipe-lines de gaz (aux Etats-Unis), dans la conception des automobiles, en logistique (meilleure solution actuelle au problème du voyageur de commerce, avec une approche couplant algorithmes évolutionnaires et recherche opérationnelle), pour optimiser les ailes d'avion, les empennages de missiles supersoniques, les aubes de turbines, les hélices, les tuyères de propulseurs, les manoeuvres des avions de combat, les allocations de routes aériennes, les allocations dynamiques de fréquences en téléphonie mobile (meilleur résultat actuel), le positionnement d'antennes, le routage dans les réseaux, l'analyse d'images médicales, la trajectoire de robots, la recherche de gènes responsables de maladies génétiques, l'approximation de formes 2D par des fractales (pour compression fractale d'image), ...

C.J :  Ils sont donc beaucoup utilisés, chez les chercheurs ou dans le monde industriel ?
P.C. : Non et c'est assez malheureux. Les algorithmes évolutionnaires restent peu connus, notamment des industriels, qui ne sollicitent donc pas les chercheurs pour résoudre leurs problèmes. Du coup, la demande étant faible, ce secteur se développe peut-être un peu lentement.

C.J : Pourtant, ces outils ne datent pas d'hier...
P.C. : En effet. les algorithmes évolutionnaires sont apparus dans les années 60, issus de plusieurs travaux indépendants : John Holland a modélisé des systèmes adaptatifs avec ce qui allait devenir les "algorithmes génétiques", et qui a débouché sur la publication du livre fondateur "Adaptation in Natural and Artificial Systems", Ann Arbor, Univ. of Michigan Press, 1975. En parallèle, I. Rechenberg et H.-P. Schwefel, étudiants ingénieurs à l'Université de Berlin, ont inventé les "stratégies d'évolution" pour l'optimisation de tuyères, et ont publié respectivement "Evolutionstrategie: Optimierung Technisher Systeme nach Prinzipien des Biologischen Evolution", Fromman-Hozlboog Verlag, en 1973,  et "Numerical Optimization of Computer Models", John Wiley \& Sons en 1981.
L. J. Fogel, pour sa part,  a travaillé sur ce qu'il a appelé la "programmation évolutionnaire" pour la prédiction de séries temporelles, et a publié avec A. J. Owens and M. J. Walsh le livre "Artificial Intelligence through Simulated Evolution", John Wiley & Sons 1966.
Plus récemment, John Koza a popularisé ce qui est considéré aujourd'hui comme la quatrième roue du carosse évolutionnaire : la programmation génétique, en publiant "Genetic Programming : On the Programming of Computers by Means of Natural Evolution", MIT Press 1992.

C.J : Il semble donc y avoir une contradiction : comment expliquez-vous que les algorithmes évolutionnaires, apparus il y a quelque 40 ans, soient encore si peu connus et développés ?
P.C. : Parce qu'après l'engouement suscité lors de leur apparition dans les années 60, ils ont connu un déclin marqué, probablement dû aux faibles puissances des machines de l'époque par rapport à des algorithmes par essence gourmands en temps de calcul. Le renouveau de ces algorithmes est donc récent et date du début des années 90, ce qui signifie que les travaux sur le sujet sont encore peu nombreux.

C.J : Y-a-t-il un profil type du chercheur en algorithmes évolutionnaires. Quel a été votre parcours ?
P.C. : Oh, mon parcours est assez atypique... Passionné d'informatique depuis l'âge de 14 ans - âge auquel j'ai travaillé et économisé pour m'offrir mon premier ordinateur, un DAI pour ceux qui se souviennent -, j'ai donc choisi la voie des études d'informatique, contrairement à certains amis de l'époque qui ont préféré se faire embaucher rapidement dans le privé. Suivent donc des études universitaires m'ayant amené à un DEA de Systèmes Informatiques suivi par un début de thèse à l'INRIA sur les algorithmes de ramasse-miettes qui se termine mal, suite à la dérive du sujet vers les noyaux de systèmes distribués à objet. Vient alors une incursion dans le privé de quelques années comme directeur adjoint d'une ... compagnie aérienne de premier niveau !

C.J : Et...
P.C. : Et l'on revient toujours à ses premières amours, c'est-à-dire, la recherche, dans mon cas.
Suite à une discussion avec un ami chirurgien ORL me décrivant les dangers de son art, ses sueurs froides lors d'interventions délicates et l'appareillage dont il aurait besoin, nous décidons de créer ensemble le projet de recherche Magellan de chirurgie assistée par ordinateur. Ce projet, financé par l'Institut Electricité Santé, en collaboration avec l'Hôpital Avicenne et comptant jusqu'à dix chercheurs et ingénieurs aboutira, quatre années plus tard à un prototype opérationnel permettant au chirurgien de superposer en temps réel et en 3D ses instruments sur les images scanner du patient prises avant l'intervention.
Après plusieurs opérations, réussies, réalisées à l'aide du prototype Magellan - objet de mon doctorat d'informatique -, l'impossibilité, que j'estime d'ailleurs classique en France, de trouver les crédits ou les industriels pour passer du prototype opérationnel au produit fini, ainsi que l'apparition concomitante d'une copie conforme du prototype (réalisé par une grosse société Américaine et présenté au 94ème Congrès de Chirurgie ORL à Paris malgré l'antériorité de notre brevet international) ont signé l'arrêt de mort du projet.
Suit alors une période un peu difficile mais où grâce à mes contacts dans la recherche, j'ai rencontré Evelyne Lutton, chargée de recherches à l'INRIA, qui s'occupe du projet Fractales. C'est elle qui m'a initié aux algorithmes évolutionnaires et aux fractales.
Après une collaboration fructueuse de plusieurs années, le projet de recherche européen DREAM - comportant six équipes européennes dont le Centre de Mathématiques Appliquées de l'école Polytechnique (http://www.dcs.napier.ac.uk/~benp/dream/dream.htm) a démarré, découlant sur mon embauche comme chercheur dans l'Equipe Evolution Artificielle et Apprentissage dirigée par Marc Schoenauer, que vous avez fort bien décrite d'ailleurs sur votre site (ndr : cf:http://www.admiroutes.asso.fr/larevue/2001/9/algoevol.htm)

C.J : Sur quoi travaillez-vous aujourd'hui ?
P.C. : Après un travail sur les algorithmes évolutionnaires eux-mêmes, ayant abouti à l'approche Parisienne (dénommée ainsi en clin d'oeil à l'approche "Pittsburgh" et l'approche "Michigan," des systèmes de classeurs), et à son application aux problème inverse des Systèmes de Fonctions Itérées (IFS en anglais) montrant que dans les problèmes de cette classe, cette approche permettait de gagner plusieurs ordres de grandeur en temps de calcul (1), j'ai intégré l'Action de Recherche Coopérative EVOLAB(2), coordonnée par Evelyne Lutton, regroupant cinq équipes de recherche françaises et dont le but était de simplifier l'accès aux algorithmes évolutionnaires.
Comme vous avez pu le pressentir dans cette description, l'implémentation d'un algorithme évolutionnaire tient du croisement entre une montre suisse - par la précision requise dans le choix des paramètres et la finesse de l'implémentation des bons opérateurs et des bonnes stratégies - et une usine à gaz (par la gestion d'une population d'individus potentiellement capables de se reproduire, ...), ce qui décourage beaucoup de non initiés.
En effet, les utilisateurs potentiels des algorithmes évolutionnaires ne sont pas les informaticiens, mais les autres scientifiques - les physiciens, les mathématiciens, ... - dont le langage de programmation naturel est souvent le FORTRAN. Malheureusement, les seules simplifications proposées à l'utilisateur pour écrire son propre algorithme prennent la forme de librairies C++ ou, depuis peu, JAVA, écrites par des informaticiens, et utilisant donc à fond les concepts objets nécessitant l'écriture de classes utilisant des templates, avec leur sillage de constructeurs, constructeurs de copie, destructeurs, et autres horreurs qui sont totalement étrangères aux non informaticiens. Un physicien, même très expérimenté en FORTRAN (ou dans un langage procédural de type PASCAL ou même C ne pourra donc utiliser ces librairies que sous peine de devoir perdre un temps précieux à découvrir les bugs vicieux découlant des subtilités des langages à objets. L'ARC EVOLAB avait donc pour but de permettre la programmation d'algorithme évolutionnaires par l'intermédiaire d'une interface graphique simple d'emploi.
Etant le seul informaticien de formation dans les cinq équipes formant l'ARC, ce qui montre bien qui sont les vrais utilisateurs des algorithmes évolutionnaires, la responsabilité de l'élaboration de cette plate-forme logicielle m'est échue.

En établissant les spécifications, je me suis rapidement rendu compte qu'il fallait non seulement que l'utilisateur puisse décrire un algorithme évolutionnaire avec une interface graphique (c'est à dire sans véritablement programmer), mais aussi qu'il puisse sauvegarder son travail (un algorithme évolutionnaire) en fin de session et le récupérer ultérieurement.
En quelques mots, il fallait un langage de spécification d'algorithmes évolutionnaires et son compilateur, permettant de traduire le fichier de sauvegarde source en un objet : l'algorithme évolutionnaire à proprement parler.
Le logiciel d'EVOLAB devait à l'origine faire fonctionner EO(3), la librairie évolutionnaire créée au sein du réseau européen EVONET. Comme elle n'était alors qu'un prototype et qu'il ne semblait pas judicieux de travailler sur une base encore instable, j'ai proposé de créer un langage général de spécification d'algorithmes évolutionnaires indépendant de toute librairie existante, plutôt que de dépenser de l'énergie sur une représentation spécifique à EO.

C.J : Langage de spécification qui n'existait pas...
P.C. :  En effet, et ceci forçait les utilisateurs à tout reprogrammer dans des langages génériques de troisième génération d'assez bas niveau comme C, C++ ou FORTRAN, totalement inadaptés à cette tâche, et ceci alors que pratiquement toutes autres branches de l'informatique possédaient le leur, y compris certaines applications comme les tableurs !  En attendant les premières versions stables d'EO, j'ai choisi d'utiliser GALib(4), qui est une librairie américaine C++ parmi les plus utilisées, bien qu'étant de conception ancienne. Ainsi, le langage EASEA(5) (pour EAsy Specification of Evolutionary Algorithms) et son compilateur ont vu le jour, permettant de transformer un code source EASEA purement procédural ne contenant que le minimum nécessaire à la description d'un algorithme évolutionnaire quelconque en un programme complet prêt à compiler, utilisant la librairie choisie par l'utilisateur. Ce dernier est ainsi déchargé de la lourde tâche de l'écriture de l'algorithme pour lui permettre de se concentrer sur le problème qu'il tente de résoudre.
Depuis janvier 2001, la version 0,6 (EASEA Millenium Edition) permet de transformer un code source EASEA en un programme utilisant au choix GALib ou la toute nouvelle librairie européenne EO (dont le CMAP participe activement au développement).

C.J : Quels sont les avantages ?
P.C. :  Ce langage résout par la même occasion deux autres problèmes importants.
D'une part, comme il n'existait jusqu'à présent aucun langage dédié aux algorithmes évolutionnaires, chaque laboratoire implémentait son algorithme de manière indépendante, rendant très difficiles les comparaisons de performances entre équipes différentes. Avec un langage de spécification indépendant de toute librairie ou de toute machine comme EASEA, il devient possible de comparer deux algorithmes, car si deux équipes ont installé le langage, il leur devient possible d'échanger leur code source pour comparaison, chaque équipe pouvant tester les améliorations proposées localement, en les faisant tourner avec leur machines et la librairie dont ils ont l'habitude.

D'autre part,  l'enseignement pratique des algorithmes évolutionnaires s'est toujours avéré délicat, du fait de la difficulté d'implémentation de ces algorithmes. En effet, il est malaisé de demander à des étudiants de résoudre un problème avec un algorithme évolutionnaire dans un mini-projet d'une durée d'un mois, car c'est à peine le temps nécessaire pour assimiler une librairie existante ou pour récrire un algorithme de toute pièce. La résolution du problème passe alors au second plan. Dans ce cas, EASEA permet aux étudiants de se consacrer pleinement à la résolution du problème proposé, en effaçant toute difficulté d'implémentation. EASEA est ainsi utilisé pour l'enseignement à l'ENSTA, à l'Ecole Polytechnique, à l'Ecole Centrale, au Laboratoire d'Informatique de l'Université du Littoral - où un prototype d'interface graphique pour EASEA a été réalisé - et l'année prochaine à l'Université de Bourgogne.

A l'étranger, deux universités anglaises et une université australienne m'ont fait part de leur désir de l'utiliser prochainement.
Pour donner un exemple de l'efficacité d'EASEA comme langage d'enseignement, nous avons proposé à deux étudiants de deuxième année de l'ENSTA qui avaient réalisé un très bon mini-projet sur les animats de l'étendre à une idée nouvelle : faire évoluer un animat (une fourmi) dans le but de détecter les contours d'une image en niveaux de gris. Après un encadrement précis effectué par Evelyne Lutton, Jean Louchet (ENSTA) et moi, les étudiants ont produit en un mois supplémentaire (deux au total) un programme EASEA suffisamment intéressant pour motiver l'écriture d'un article(6) qui ... a été accepté en présentation à la conférence internationale EUROGP(7) (à Côme en Italie du 18 au 20 avril 2001). L'école a payé leur droit d'inscription et leur voyage avec enthousiasme.

C.J : Quel enseignement tirer de cet exemple ?
P.C. :  On peut en tirer que la simplification de l'écriture de ces algorithmes est un réel besoin. En effet, quels que soient les talents de programmation de Christian Zerbi et Enzo Bolis, les auteurs de l'article, et les talents d'encadrement de leurs enseignants, faire réaliser (avec EASEA) en deux mois à deux étudiants ne connaissant rien aux algorithmes évolutionnaires un travail accepté dans une conférence internationale reconnue, montre bien que le problème de la difficulté d'implémentation n'est pas mineur et qu'un langage comme EASEA n'est pas sans intérêt.

C.J : Participez-vous à des projets européens ?
P.C. : Oui, je participe au projet européen DREAM que j'ai un peu évoqué plus haut, et dont le Centre de Mathématiques Appliquées de l'école Polytechnique (CMAP) est un "noeud," pour utiliser la terminologie de la Communauté Européenne. La Distributed Evolutionary Algorithm Machine (qui n'existe pour l'instant qu'à l'état de prototype) a pour but - relativement à la mode- d'utiliser la puissance de calcul de milliers d'ordinateurs connectés via Internet pour faire tourner des algorithmes évolutionnaires répartis, un peu à la façon du projet SETI(8) (Search for Extra-Terrestrial Intelligence) ou sur les nombres premiers de Mersenne(9).
De nouveaux concepts doivent être élaborés pour résoudre les nouveaux problèmes posés. Par exemple, les ordinateurs contenant des sous-populations doivent pouvoir être déconnectés (éteints) pendant un certain temps puis être reconnectés à la DREAM pour continuer l'évolution artificielle.

Mon rôle dans ce projet européen regroupant les universités Napier (Ecosse), South Bank (Angleterre), de Leiden (Pays-Bas), de Dortmund (Allemagne), de Grenade (Espagne) et l'école Polytechnique a été - conjointement avec Dortmund - de concevoir l'interface et le comportement social des "infohabitants" dans leurs "îlots" (qui peuvent être placés sur des machines différentes) ainsi, bien sûr que du langage de programmation des applications. A cette occasion, la version 0,7 d'EASEA (sur laquelle je travaille actuellement) permettra donc de compiler un même fichier de spécification pour créer un fichier source GALib (C++), EO (C++) ou DREAM (JAVA) car la DREAM est réalisée en JAVA, pour des raisons de portabilité, montrant ainsi que le pari de faire d'EASEA un langage universel de spécification d'algorithmes évolutionnaires a été tenu.

C.J : Combien de chercheurs compte votre laboratoire ?
P.C. :
 Le CMAP est un laboratoire assez atypique au sens où il regroupe environ 80 chercheurs - contre une dizaine, étudiants compris,  pour un laboratoire habituel - regroupés dans des équipes traitant de domaines différents.

C.J : Combien la "communauté algorithmes évolutionnaires" regroupe-t-elle de chercheurs en France ?
P.C. :
Ceci est une question absolue, qui nécessite donc une mise en perspective de la discipline par rapport aux autres pour que la réponse soit significative.
Vous connaissez certainement l'adage populaire qui dit qu'un savant, à force d'approfondir un sujet de plus en plus spécialisé, est une personne qui finit par connaître tout... sur rien. Et bien il en va de même pour la communauté scientifique travaillant sur un sujet précis. Plus le sujet est pointu, moins il y a de monde travaillant dessus. Comme vous l'avez vu précédemment, j'ai côtoyé plusieurs disciplines avant d'aboutir dans la communauté évolutionnaire. Je m'en servirai donc comme étalon pour l'évaluer.
Il y a probablement des dizaines de milliers de chercheurs de par le monde travaillant dans les système d'exploitation, et en informatique médicale. Dès que l'on affine le sujet (dans les systèmes, prenons les systèmes répartis à objets spécialité noyaux /en informatique médicale, dans la chirurgie assistée par ordinateur, prenons la spécialité ORL) le club est déjà beaucoup plus restreint. Suite à la lecture d'une vingtaine d'articles sur le sujet et après quelques conférences internationales, on finit par connaître le microcosme dans lequel gravitent les principaux acteurs du domaine et mettre un nom sur leur visage.

Rappelons, qu'en ce qui concerne les algorithmes évolutionnaires, il s'agit d'une discipline encore très jeune, comme je vous l'ai expliqué précédemment. Je comparerais donc cette discipline à une spécialité d'une spécialité d'une autre grande discipline. Les grandes conférences internationales, voire mondiales, CEC (http://cec2001.kaist.ac.kr/) ou GECCO (http://www-illigal.ge.uiuc.edu:8080/GECCO-2001/) réunissent ces derniers temps environ 600 participants, si cela peut donner une échelle.
De plus, et cela montre la difficulté de votre question sur le nombre de "chercheurs" de la communauté évolutionnaire, il faut dire que la communauté scientifique d'une spécialité se décompose généralement en deux ou même trois catégories.
Tout d'abord, il y a les piliers, de notoriété internationale, qui, au prorata de la recherche mondiale se comptent en France sur les doigts d'une main.
Viennent ensuite les chercheurs permanents et enseignants chercheurs "ordinaires," qui sont beaucoup moins visibles (peu d'articles marquants, car sinon, ils seraient dans la première catégorie) et donc plus difficilement dénombrables. Ils se comptent généralement par dizaines.
La troisième catégorie est celle des étudiants.
Dans la première équipe de recherche dont je faisais partie (en systèmes distribués), il y avait 11 thésards pour un directeur de recherches et un chercheur, ce qui était certainement exagéré, cependant, les étudiants se comptent certainement par centaines.

Ainsi, pour répondre à votre question, et en ce qui concerne la communauté évolutionnaire Française, je pense qu'il faut distinguer les chercheurs dont le sujet de recherche est l'évolution artificielle et les chercheurs qui utilisent ces algorithmes pour leurs recherches, dont le sujet principal est ailleurs. Ainsi, je dirais que nous avons probablement trois ou quatre pointures internationales en cette matière, une vingtaine de chercheurs permanents, vingt thésards dont le sujet de recherche est centré sur les algorithmes évolutionnaires, et un nombre indéterminé, en progression constante, de thésard du 2ème type...

C.J : Soit une centaine de personnes ?
P.C. : C'est difficile à dire : comme je vous le dis, les chiffres sont biaisés par le fait que les algorithmes évolutionnaires intéressent de nombreuses disciplines, notamment les maths appliquées. Il y a donc aussi un certain nombre de chercheurs - et leurs étudiants- utilisant les algorithmes évolutionnaires mais qui ne sont pas considérés comme faisant partie de la "communauté" évolutionnaire.

C.J : Estimez-vous que cette communauté soit suffisante ?
P.C. : Cette communauté reste donc relativement petite, tout en étant, à mon avis, au dessus de la masse critique lui permettant de survivre en tant que discipline à part entière. Il manque cependant des chercheur confirmés, capables à leur tour d'encadrer des étudiants. Mais comme les étudiants scientifiques de valeur sont de moins en moins nombreux...
La désaffection des jeunes pour les sciences est en effet très préoccupante et l'exposé des raisons probables nécessiterait un autre article à part entière.
En tout cas, le petit nombre de personnes concernées par les algorithmes évolutionnaires permet l'organisation périodique informelle de "Journées Evolutionnaires Trimestrielles" (ou JETs) http://www.eeaax.polytechnique.fr/eeaax.html. Elles ont été créées par le CMAP (Marc Schoenauer) en 1998 sur un budget alloué dans le cadre du programme "Modélisation et simulation numérique - Algorithmique aléatoire" de la section 01 (Mathematiques et Physique de Base) du CNRS. Malheureusement, voici maintenant plusieurs JETs que le budget est épuisé. Les journées continuent cependant bénévolement sans subventions, et toujours sans droits d'inscription. Elles ne sont plus trimestrielles mais réunissent la communauté évolutionnaire française (ndr : la dernière de ces journée s'est tenue le 30 mars dernier - cf votre compte rendu http://www.admiroutes.asso.fr/larevue/2001/9/algoevol.htm#ae)

C.J : Quelle est la valeur de cette communauté par rapport à celle des autres pays ?  
P.C. : La communauté française est active et connue sur le plan international. Les travaux de Jin-Kao Hao, Dorne et Galinier sur les allocations dynamiques de fréquence pour les téléphones mobiles ont fourni les meilleurs résultats actuels, Daniel Delahaye est invité dans des conférences internationales pour décrire son travail sur les allocations de routes aériennes...
Concernant la visibilité de la France d'un point de vue international, Evelyne Lutton, Marc Schoenauer Jean Louchet et moi-même avons récemment publié un article dans GPEM introduisant l'idée nouvelle de représenter la solution à un problème par un ensemble d'individus, que nous avons appelé l'approche Parisienne (dont je vous ai déjà parlée tout à l'heure), mais il est impossible de citer ici l'ensemble des travaux des chercheurs français ayant apporté une pierre à l'édifice.

C.J : Quels liens entretenez-vous avec les collègues d'autres pays ?  
P.C. : L'activité de la communauté évolutionnaire française transparaît aussi par les manifestations internationales organisées. En septembre 2000, Marc Schoenauer(10) (école Polytechnique) et Evelyne Lutton (11) (INRIA) étaient les organisateurs de la conférence internationale PPSN VI (12) à Paris, et leur cv prestigieux trahit leurs activités internationales.
En octobre 2001, j'ai l'honneur d'organiser, avec Evelyne Lutton, Marc Schoenauer, Cyril Fontlupt et Jin-Kao Hao la cinquième conférence sur l'Evolution Artificielle(13), dont Evelyne Lutton et Marc Schoenauer (encore eux !) font partie des membres fondateurs. Je voudrais d'ailleurs en profiter  pour rappeler que la date limite de soumissions d'articles est le 11 mai prochain).
Il est aussi intéressant de noter que cette conférence internationale, la seule en Europe sur le sujet entre juillet 2001 et février 2001, a pour originalité de solliciter autant de subventions que possible pour limiter les droits d'inscription en dessous de 1 000 F (contre trois à quatre mille francs pour les autres manifestations internationales). La gestion très saine d'EA'99, organisée à Dunkerque par Cyril Fonlupt et Philippe Preux, avait permis de financer le voyage de certains doctorants ou leur hébergement.

C.J : Depuis la création de ces algorithmes, quelles ont été les sophistications apportées. Où en est aujourd'hui la recherche dans le domaine ? Que reste-t-il à perfectionner ?
P.C. : Les sophistications sont multiples, et trahissent à mon avis la jeunesse du domaine. En effet, et probablement aussi du fait du très vaste domaine d'application des algorithmes évolutionnaires, de nombreux travaux présentent "encore" des applications réalisées à l'aide des algorithmes évolutionnaires.
La transposition aux langages de programmation donnerait la caricature suivante : "En utilisant ADA, nous avons réalisé un programme de gestion d'un robot. Nous n'avons utilisé que 10% de procédures à effet de bord, car nous avons remarqué que ... Comme nous n'obtenions pas de bons résultats, nous avons récrit les fonctions d'allocation dynamique de mémoire pour tenir compte de la localité temporelle des données..."
Comme cette transposition le montre, on ne sait toujours pas de façon claire et définitive quel algorithme utiliser dans quel cas, quels sont les paramètres à adopter pour résoudre au mieux le problème posé. Le résultat dépend encore beaucoup trop à mon goût du flair de l'expérimentateur.

De très nombreuses sophistications sont introduites pour se rendre compte par la suite que les améliorations constatées ne sont pas dues aux dites sophistications, mais à l'influence d'un paramètre mis en évidence par l'expérience conduite. En fait, sauf dans de rares cas simplissimes où il a été possible d'explorer scientifiquement le comportement d'un algorithme évolutionnaire, et d'expliquer les effets constatés, l'impression que j'ai est que nous sommes toujours face à un domaine relativement inconnu, où les avancées proviennent de recherches apparentées à celles Pierre et Marie Curie découvrant les propriétés du radium. D'innombrables mesures rigoureuses et scientifiques sont effectuées pour souvent aboutir à des résultats inattendus, montrant d'autres voies, sans pour autant répondre de façon claire à la question initiale.

Cela dit, de nombreux progrès ont été faits, et de grandes tendances se dégagent. On peut de plus en plus souvent prédire, suivant le problème à résoudre, s'il est approprié ou non de choisir tel ou tel opérateur de sélection, de remplacement, ...

Il faut aussi dire à la décharge des expérimentateurs que les algorithmes évolutionnaires sont difficiles à cerner car ils marchent souvent trop bien.
En effet, le principe de sélection naturelle est très puissant, et arrive à gommer les différences et même les bugs d'implémentation ! Il arrive très souvent qu'on découvre après coup qu'un programme qui donne des résultats satisfaisants comporte des erreurs grossières. La sélection naturelle arrive presque toujours à trouver le résultat demandé, contournant si nécessaire les bugs mis en travers de sa route, au seul prix d'une performance moins élevée.
Avec une telle robustesse, allez déterminer l'influence d'une sophistication parmi l'influence potentielle des nombreux paramètres de l'algorithmes et de plusieurs bugs résiduels non détectés, car ça marche malgré tout !
En conclusion, je pense - en temps qu'informaticien - que les sophistications actuelles sont trop nombreuses pour être utiles. A mon idée, pour être performant, un algorithme générique doit être sain et exempt de verrues. Que l'on rajoute des sophistications par la suite pour mieux coller à un problème précis relève d'une autre démarche : celle de l'optimisation du programme d'optimisation. Mais elle doit venir en dernier.
Je crois donc que le perfectionnement des algorithmes évolutionnaires prendra la forme d'une épuration et d'une simplification laissant moins de place à l'improvisation.

C.J : Quels rapports les spécialistes des algorithmes évolutionnaires entretiennent-ils avec les chercheurs issus d'autres disciplines (physiciens, chimistes, neurobiologistes, sociologues, linguistes, etc.). Ceux-ci viennent-ils vous soumettrent des problèmes paritculiers ?
P.C. :
En fait, il arrive souvent que des chercheurs d'autres disciplines utilisent eux-mêmes les algorithmes évolutionnaires pour résoudre leurs problèmes. On peut alors les considérer comme utilisateurs des algorithmes évolutionnaires, par comparaison aux concepteurs, qui ont pour but d'améliorer ou de trouver de nouveaux algorithmes. Les présentations faites par les "utilisateurs" montrent qu'ils sont assez souvent "autodidactes," ce qui est très dangereux pour les algorithmes évolutionnaires, tout comme - c'est un paradoxe- peut l'être le langage EASEA en permettant à des "non initiés" de faire des essais.
En effet, comme je l'ai dit plus haut, l'expérience de l'utilisateur est encore trop souvent déterminante pour régler finement les nombreux paramètres des algorithmes, sans quoi, leurs performances peuvent être assez mauvaises.
A titre d'exemple, nous avons reçu lors des JET 5 la présentation d'un chercheur "utilisateur" qui se plaignait du manque de convergence de son algorithme alors qu'au détour d'un transparent, nous avons vu qu'il utilisait une probabilité de mutation de 0,4, ce qui est énorme. En effet, cela signifie que pour son problème, l'évolution artificielle était fortement ralentie par les nombreuses mutations qui avaient lieu alors que normalement elles doivent être assez rares (0,04 aurait été amplement suffisant).
Ainsi, et c'est vrai dans tous les domaines mais particulièrement dans les algorithmes évolutionnaires, il est possible que de nombreux utilisateurs soient déçus par les performances des algorithmes évolutionnaires pour la simple raison qu'ils ont essayé par eux-même, sans consulter de spécialistes sur le sujet.
C'est un danger pour les algorithmes évolutionnaires, car les informaticiens qui les créent n'en sont pas les utilisateurs, et les utilisateurs ne viennent que trop rarement consulter les spécialistes car c'est un domaine où l'on obtient tout de suite des résultats - grâce à la robustesse inhérente aux algorithmes évolutionnaires - , ce qui encourage à continuer seul sur sa lancée.

C.J : Mais vous, proposez-vous vos services à des utilisateurs potentiels ?
P.C. :
En fait, il y a un problème plus profond. La personne qui travaille sur les algorithmes évolutionnaires n'est pas celle qui a un problème à résoudre, et inversement. Les chercheurs sur les algorithmes évolutionnaires, n'ont pas besoin d'aller chercher des utilisateurs, car des cas-tests représentatifs des problèmes potentiels existent - eux-même trouvés par d'autres chercheurs, car il est difficile de trouver un cas-test intéressant. Ils sont donc autonomes dans leur travail, et la communication avec les utilisateurs peut être rare.
C'est donc aux utilisateurs de ne pas se contenter de quelques essais mais de se documenter sérieusement sur ces algorithmes pour les utiliser au mieux.

C.J : En résumé, êtes-vous assez connus ?
P.C. : Ce n'est pas la même question. J'ai montré plus haut que les utilisateurs des algorithmes évolutionnaires font souvent des erreurs d'utilisation, car ils ne sont pas les concepteurs des algorithmes et ne les connaissent donc pas intimement. En revanche, s'ils utilisent ces algorithmes, c'est qu'ils en connaissent l'existence.
Quant à ceux qui n'en ont jamais entendu parler, ils ne les essaieront pas, ce qui n'est peut-être pas un mal, car cela évitera de les décevoir. En effet, les algorithmes évolutionnaires ne gagnent pas à être connus ... si c'est pour les aborder trop rapidement, car il est très facile d'être déçu par leur performance s'ils sont mal utilisés. L'idéal, qui serait de demander à un expert sur les algorithmes évolutionnaires de résoudre un problème d'optimisation, n'est pas une solution non plus, tant les domaines des utilisateurs sont étrangers aux informaticiens. La double compétence mathématiques appliquées ET informatique est donc absolument nécessaire pour faire du travail intéressant, et c'est cette contrainte qu'EASEA essaye de lever en partie en minimisant l'importance des connaissances informatiques nécessaires pour obtenir de bons résultats.
Maintenant, pour répondre à votre question, je pense qu'effectivement, les algorithmes évolutionnaires sont encore bien méconnus de nombreux utilisateurs potentiels.

C.J : Quels exemples avez-vous de collaborations réussies, dans lesquelles il y a eu enrichissement mutuel ?
P.C. : Si vous voulez un exemple, je pense immédiatement à l'Institut Français du Pétrole (IFP), où Bertrand Braunschweig maintient depuis de nombreuses années un département utilisant les algorithmes évolutionnaires pour les besoins de l'Institut. Les problèmes à résoudre sont réels, et les personnes qui utilisent les algorithmes évolutionnaires sont maintenant suffisamment compétentes pour les utiliser à bon escient et pour proposer régulièrement des améliorations aux algorithmes, mais là aussi, ce n'est pas le seul cas. Yann Landrin-Schweitzer fait actuellement une thèse à l'INRIA en convention CIFRE avec NOVARTIS Pharma avec des  algorithmes évolutionnaires interactifs et peut-être avec l'approche Parisienne. La société Cartier, pour sa part, a utilisé des images fractales produites par algorithmes évolutionnaires pour le design de ses bijoux (INRIA Fractales)...

C.J : Pensez-vous que ces échanges soient aujourd'hui optimaux ? Sinon, que serait, d'après-vous, l'idéal ?
P.C : Les échanges sont loin d'être optimaux. L'idéal serait bien sûr que de nombreux scientifiques connaissent l'existence des algorithmes évolutionnaires, et qu'ils fassent appel à des spécialistes pour les utiliser, ou qu'ils prennent la peine de se former suffisamment longtemps s'ils veulent les implémenter eux-même.
Le problème est que les personnes dont c'est la spécialité de résoudre des problèmes par algorithmes évolutionnaires sont très peu nombreuses, peut-être du fait de la double compétence nécessaire. L'expérience de tels spécialistes serait précieuse pour montrer les directions à explorer.

C.J : A propos de directions à explorer, on parle beaucoup à l'heure actuelle de modernisation de l'Etat, de modernisation des administrations publiques. Pensez-vous que les algorithmes évolutionnaires pourraient être utiles en cette matière ?
P.C : Pouvez-vous être plus explicite...

C.J : Par exemple, pour la gestion de projets, ne serait-ce déjà que pour trouver un calendrier idéal de réunions - ainsi que le lieu idéal de ces réunions - pour des personnes très occupées et très souvent en déplacement...
De façon moins anecdotique, pourrait-on, grâce à ces outils, tendre vers les meilleures solutions - en tous cas les moins mauvaises - pour la prise de décision face à des problèmes complexes. Les algorithmes évolutionnaires seraient-ils capables de trouver une réponse à des questions telles que : Comment répartir au mieux les tâches pour optimiser le fonctionnement d'une administration ? Quelle serait la meilleure des décentralisations ? Quel serait le meilleur budget de la recherche, en tous cas la meilleure des répartitions de ce budget en fonction d'objectifs à atteindre...

P.C : Une des applications potentielles dans l'administration est traitée par de nombreuses équipes de recherche, dans la satisfaction de contraintes dont un bon exemple est la fabrication automatique d'emplois du temps. Ben Paechter, de l'Université Napier à  Edimbourg, travaille sur le sujet et met sur le net un programme d'évaluation (http://www.tatties.org).
On peut également citer le travail de Yann Landrin-Schweitzer pour Novartis Pharma, sur le "text mining", qui consiste à retrouver de l'information dans des bases de données de textes pouvant être diverses, distribuées, de structures différentes, et qui peuvent être appelées au travers de thesauri différents.

Les algorithmes évolutionnaires élaborés dans ces domaines sont donc particulièrement bien adaptés à la gestion de projets, à la conception de calendriers de réunion, à l'aide dans la prise de décisions, dans la détermination de la meilleure décentralisation, de la meilleure répartition d'un budget en fonction des objectifs a atteindre.
Mais il faudrait bien entendu un développement spécifique pour chacune de ces applications...

Couverture du livrre : l'ordinateur génétique Pour en savoir plus sur les algorithmes évolutionnaires
les lecteurs intéressés pourront consulter avec avantage "L'ordinateur génétique", de Jean-Louis Dessalles aux Editions Hermès, 1996, livre remarquablement clair et concis, dont nous proposerons une chronique dans un prochain numéro.

C. Jacquemin


(1) P. Collet, E. Lutton, F. Raynal, M. Schoenauer, "Polar IFS + Parisian Genetic Programming = Efficient IFS Inverse Problem Solving," Genetic Programming and Evolvable Machines Journal, vol 1 Number 4, pp 339-361 Remonter d'où l'on vient
(2)
Voir
http://www-syntim.inria.fr/fractales/ACTION-INCITATIVE/EVO-Lab.html Remonter d'où l'on vient
(3) Voir http://www.eeaax.polytechnique.fr/EO/EO.html Remonter d'où l'on vient
(4) Voir http://lancet.mit.edu/ga/ Remonter d'où l'on vient

(5) Voir http://www-rocq.inria.fr/EASEA/ Remonter d'où l'on vient
(6) E. Bolis, C. Zerbi, P. Collet, J. Louchet, E. Lutton, "A GP Artificial Ant for Image Processing: Preliminary Experiments with EASEA," EUROGP 2001 Remonter d'où l'on vient
(7) Voir http://evonet.dcs.napier.ac.uk/eurogp2001
Remonter d'où l'on vient
(8) Voir http://www.setileague.org/ Remonter d'où l'on vient
(9) Voir http://www.mersenne.org/prime.htm  Remonter d'où l'on vient
(10) Voir http://www.cmap.polytechnique.fr/~marc/bio_short.html Remonter d'où l'on vient
(11) Voir  http://www-rocq.inria.fr/fractales/Staff/Lutton/Lutton.html  Remonter d'où l'on vient
(12) Voir http://www-syntim.inria.fr/fractales/PPSN2000/  Remonter d'où l'on vient
(13) Voir http://www.cmap.polytechnique.fr/ea01 Remonter d'où l'on vient

Retour au sommaire