Plan du site Aide Abonnement Nous Contacter


Actualité
Editorial
Interviews
Démocratie
Visites virtuelles
Art. Imaginaire
Du côté des labos
Le feuilleton
Manifestations
Biblionet
CD Rom
Echanges
Liens Utiles

 

Accueil > Interviews
Automates Intelligents s'enrichit du logiciel Alexandria.
Double-cliquez sur chaque mot de cette page et s'afficheront alors définitions, synonymes et expressions constituées de ce mot. Une fenêtre déroulante permet aussi d'accéder à la définition du mot dans une autre langue.
 
Archives
Franck Brancheri
Jean-Pierre Goux
Jean-Claude Lapraz
Jean-Pascal Capp
Henri Boulouet

25 Avril 2002
propos recueillis par Jean-Paul Baquiast, le 01/04/2002

Discussion avec Marc Shoenauer

Les algorithmes évolutionnaires

Cet interview est le second d'une série que l'AFIA (Association Française pour l'Intelligence Artificielle) souhaite consacrer à un certain nombre de chercheurs choisis dans la communauté IA française. Ils seront publiés sur le nouveau portail de l'AFIA http://www.afia-france.org, ainsi que dans notre revue en ligne Automates-intelligents. L'objectif est de mieux faire connaître les travaux des équipes et des laboratoires, recherches trop souvent réservées aux seuls spécialistes.

A notre avis, la communication en direction des autres disciplines, du milieu économique et plus généralement du grand public constitue désormais un enjeu majeur. Les chercheurs français sont bons, souvent très bons, mais ils pensent trop souvent que le fait d'être connus de tous va de soi, ce qui n'est évidemment pas le cas, particulièrement hors leur domaine...

Aujourd'hui, l'insertion dans des réseaux de gestion des connaissances et des compétences est indispensable à la survie scientifique et économique. Outre des démarches bien précises à l'égard de ces réseaux, ceci suppose la publication d'articles ou d'ouvrages visant la vulgarisation, la participation à des émissions, à des enquêtes et interviews organisés par les médias, l'inscription dans des cercles de connaissance partagée... : une démarche indispensable qui demande du temps, nécessite parfois quelque apprentissage...

Jean-Paul Baquiast et Christophe Jacquemin

Marc ShoenauerMarc Shoenauer est Directeur de recherches à l'INRIA (projet Fractales). Il est également Professeur chargé de cours à temps partiel à l'Ecole Polytechnique
Ses activités de recherches en ont fait un spécialiste des algorithmes évolutionnaires. Nous les avons plusieurs fois évoquées dans cette revue (Voir notes en bas de page notamment).

Site web : http://www.cmap.polytechnique.fr/~marc/
Contact : Marc.Schoenauer@inria.fr


Automates Intelligents (AI) : Marc Schoenauer, bonjour. Pouvez-vous vous présenter à nos lecteurs ?
Marc Shoenauer (MS) : J'ai fait mes études à l'Ecole Normale Supérieure, en mathématiques appliquées. Puis j'ai passé un certain temps au CNRS, en section mathématiques appliquées, où je suis entré en 1980. Je m'y suis intéressé à l'optimisation. Je suis venu à l'intelligence artificielle indirectement, par goût et aussi du fait de l'avènement des systèmes-experts.

AI : On ne parle plus guère de systèmes-experts aujourd'hui...
MS : En effet, le mouvement s'est assez vite amorti. Il est apparu que, notamment dans les domaines que je connaissais, les mathématiques appliquées, les systèmes-experts étaient très limités par une chose essentielle : comment acquérir les fameuses connaissances ?

AI : Un système-expert en mathématiques appliquées, c'est quoi ?
MS : On a le choix, pour résoudre un problème d'optimisation, entre plusieurs méthodes, et à l'intérieur de celles-ci, entre de nombreux cheminements. Un système-expert reprend toutes les expériences qu'il a pu rassembler, et fournit une aide à l'optimisation et au diagnostic.

AI : Le besoin demeure cependant...
MS : Oui, mais encore une fois, il faut pouvoir récupérer la connaissance. Il n'y a pas toujours d'experts et, quand il y en a, ils ne savent pas toujours formaliser leurs connaissances, du moins quand ils doivent utiliser le formalisme un peu préhistorique des systèmes-experts de l'époque. Je suis donc passé à l'acquisition de connaissance par l'apprentissage automatique et j'y ai rencontré les algorithmes génétiques. Je m'y suis investi à partir de 1989.

AI : Les algorithmes génétiques avaient été initialisés aux Etats-Unis ?
MS : Oui, par John Holland et son équipe du Michigan. C'était la seule forme connue d'algorithmes évolutionnaires à l'époque.

AI : Pour vous, ces méthodes était intéressantes en matière d'optimisation…
MS : Elles ont de multiples avantages et aussi de multiples inconvénients par rapport aux méthodes d'optimisation numérique classiques. Elles permettent surtout d'attaquer les problèmes que l'on ne sait pas résoudre autrement. Mais j'ai rapidement élargi mon horizon aux algorithmes évolutionnaires... Je tiens à préciser que le mot "évolutionnaire" est un néologisme basé sur le mot anglais "evolutionary" - et également un calembour facile sur le mot "révolutionnaire".

AI : Quelle différences faites-vous entre les algorithmes génétiques et les algorithmes évolutionnaires ?
MS : Les premiers sont un cas particulier des seconds. Ceux-ci constituent un ensemble d'algorithmes dont le principe est d'imiter grossièrement l'évolution des populations selon Darwin. Les algorithmes génétiques représentent les solutions à chercher sous forme de chaînes de bits, à la manière des chromosomes. Les algorithmes évolutionnaires font évoluer des objets de toutes sortes, en s'affranchissant de la représentation binaire.

Mon passé de mathématicien appliqué était choqué à l'idée de coder des paramètres réels sous forme binaire, car a priori le réel et le continu sont des espaces de nature très différentes du point de vue des problèmes d'optimisation.

Petit à petit, je suis revenu aux questions de mathématiques appliquées en utilisant ces méthodes issues de l'intelligence artificielle, mais que l'on peut voir aussi d'un point de vue probabiliste comme des algorithmes stochastiques au même titre que le recueil simulé (Les algorithmes stochastiques sont basés sur des tirage de nombres aléatoires).

J'ai ainsi pu réintégrer mon domaine d'applications, c'est-à-dire les problèmes d'optimisation numérique. Ma position au centre de mathématiques appliquée de l'Ecole Polytechnique était privilégiée, puisque j'y travaillais au sein d'équipes de numériciens. Quand ils rencontraient un problème d'optimisation qu'ils n'arrivaient pas à résoudre, je savais que le problème était intéressant et qu'il n'y avait pas de méthode numérique triviale pour le résoudre.

Depuis 1990 je travaille essentiellement à la résolution de problèmes d'optimisation, surtout numériques mais pas exclusivement, à l'aide d'algorithmes évolutionnaires, ce qui oblige souvent à des développements algorithmiques en cas de difficulté. Je travaille donc en parallèle sur les applications et sur les algorithmes eux-mêmes.

AI : Quelle est votre situation actuelle ?
MS : Depuis septembre 2001, date à laquelle j'ai quitté le CNRS (et de ce fait l'Ecole Polytechnique - où je demeure pourtant en tant qu'enseignant de mathématiques appliquées) je suis directeur de recherches à l'Inria, où je vais mener le même type de recherche. Au CNRS, ma carrière était plus heurtée. J'étais dans la section Mathématiques, qui tend à considérer que ce genre de travaux ne relève pas de ses compétences. En 1997, j'ai passé une habilitation Spécialité informatique, mais du coup la section mathématiques ne m'a plus reconnu comme un des siens.

AI : C'est la France, je suppose…
MS : A l'Inria, je vais continuer à travailler sur les applications mais aussi sur les algorithmes eux-mêmes, au niveau théorique ou heuristique : méthodes de prise en compte des contraintes, co-évolution, optimisation multi-critères, etc.

AI : Peut-être pourriez vous maintenant nous dire comment vous voyez le développement de votre domaine, les algorithmes évolutionnaires. Pouvez-vous d'abord nous rappeler la logique du recours à ceux-ci ? Comment procédez-vous ?
MS : Nous cherchons des solutions à des problèmes non triviaux , nous les générons aléatoirement et ensuite, nous les modifions de manière aléatoire et aveugle, c'est-à-dire indépendamment du problème. Il faut ensuite sélectionner les solutions les meilleures. En itérant ce processus, on arrive à des solutions très bonnes, voire optimales, mais on n'en a aucune garantie dans la mesure où tout repose sur des tirages aléatoires.

AI : Dans les conférences JET, vous montrez qu'il apparaît par ce moyen de nombreuses solutions à de nombreux problèmes(1).
MS : Absolument. Il s'agit de problèmes d'optimisation combinatoire de type "tournée du facteur" avec beaucoup de contraintes et de variables. J'ai travaillé par exemple à l'optimisation des créneaux de décollage et des routes dans l'espace aérien français, à partir des plans de vol déposés par les avions, tout ceci pour minimiser le travail des contrôleurs aériens. Il y a plus de 6000 vols sur lesquels on peut jouer. Le modèle sert à voir quelles sont les modifications les meilleures sur l'ensemble des vols (par exemple avancer un décollage de 5 minutes, demander à un vol particulier de passer par une autre route, ...) du point de vue de la charge de travail des contrôleurs.

AI : Ceci veut dire qu'un client qui dispose d'une solution doit vous l'apporter, par exemple sous la forme d'un modèle paramétré...
MS : C'est une possibilité, bien sûr. Cependant, je suis persuadé que dans de nombreux problèmes, des progès peuvent être faits en n'hésitant pas à rejeter le modèle que l'on m'apporte, et en remontant en amont vers le problème pour le traiter différemment. Ceci dans la mesure où, comme il arrive souvent, la personne qui a écrit le modèle avait en tête des méthodes d'optimisation classiques qui ne peuvent travailler que sur un nombre  fixe de variables réelles. Sachant au contraire que les algorithmes évolutionnaires sont capables de travailler sur des espaces beaucoup plus baroques, on peut modéliser différemment, d'une façon intraitable par les algorithmes classiques. C'est cette déconstruction-reconstruction qui participe à ce qu'on pourrait appeler ma valeur ajoutée.

AI : Cela suppose que vous vous plongiez dans les univers professionnels et les formalisations variées des divers métiers avec lesquels vous travaillez...
MS : Oui. C'est un de mes credo : on ne peut pas faire de bonne optimisation en boîte noire. Le problème et la méthode doivent échanger des informations en permanence.

AI : Y a-t- il seulement optimisation ou au contraire possibilité de découvertes. Dans la mesure où vous remontez vers des problèmes en amont, le déval des algorithmes évolutionnaires ne peut-il faire apparaître d'autres "réalités" ?
MS : C'est ce que l'on commence à appeler la créativité artificielle. Est-ce le cas ou non, je ne sais pas. Ce qui est sûr, c'est que les algorithmes évolutionnaires peuvent suggérer des solutions entièrement nouvelles, parce qu'ils ont une représentation différente du problème et donc un point de vue différent. Il y a des choses extraordinaires qui ont pu être redécouvertes de cette façon. Je vous renvoie au livre de Peter Bentley : Evolutionnary Créative Design(2). Il s'agit d'un recueil d'articles montrant les solutions créatives permises par les algorithmes évolutionnaires. Ma propre philosophie serait de dire que c'est d'abord le programmeur qui est créatif puisqu'il a choisi le bon modèle et les bons algorithmes.

AI : Comme les théories scientifiques s'expriment par des modèles mathématiques, ne pourrait-on reprendre ces modèles par l'intermédiaire d'algorithmes évolutionnaires, et faire apparaître des hypothèses interdites aux premières formulations de la théorie : variables cachées ou lois diverses ?
MS : Je serai très prudent. Les algorithmes évolutionnaires sont tirés par la sélection naturelle. Pour qu'il y ait sélection, il faut qu'il y ait d'abord un programmeur disposant d'une idée de ce qu'il recherche. C'est lui qui définit des espaces de variation, pour pouvoir dire qu'une théorie est meilleure qu'une autre.

AI : Oui, mais on pourrait tester en vrai diverses théories, pour retenir la meilleure. L'essentiel est d'avoir des hypothèses neuves pour construire des expériences elles-mêmes neuves. On a dit que la science moderne manquait d'hypothèses, vu l'excessive spécialisation...
MS : Vous avez raison. La méthode peut être utilisée comme " souffleur " d'hypothèses. Mais il ne faut pas oublier, j'insiste, le fait qu'il faille un programmeur pour lancer la recherche. On n'en est pas arrivé à pouvoir lancer n'importe quoi. La recherche se fait dans un espace bien particulier. Si on n'est pas au bon endroit, dans le bon espace, on ne trouvera rien.

AI : Cela veut dire que la formation des jeunes programmeurs et chercheurs devrait intégrer ces nouvelles perspectives...
MS : La machine de la formation universitaire est lourde, et doit en ce moment intégrer beaucoup de choses. Cependant les idées évolutionnaires commencent à percoler. Elles plaisent beaucoup aux étudiants…je dirais aussi qu'elles plaisent dans la mesure où il y dans la méthode un manque de rigueur qui rend l'abord plus facile (il n'y a pas de résultats théoriques globaux, pas de démonstrations générales). L'esprit cartésien français classique se rebiffe, mais par contre beaucoup d'étudiants s'y épanouissent. Cela les change de ce qu'ils connaissaient avant. Qui plus est, la méthode marche. Que demander de plus ?

AI : Quelles sont les contraintes en matière de formation et de recherche?
MS : Ces méthodes demandent beaucoup de ressources CPU (processeurs) puisqu'on va faire les calculs de la fonction à optimiser des centaines de milliers de fois. Mais on retrouve les autres exigences qui sont celles de la formation dans le domaine scientifique.

AI : Peut-on envisager de travailler en réseau sur des milliers de micros, sur le modèle du Grid(3) ?
MS : Ce sont effectivement des algorithmes qui se parallélisent très bien. Sur le modèle du Grid, je ne sais pas. Mais sur des réseaux locaux, ou même des réseaux plus larges, c'est envisageable. Je participe au projet européen DREAM Distributed Resources Evolutionnaary Algoriths Machines, dans le but de créer un logiciel qui permettra de lancer facilement tous azimuts des calculs évolutionnaires(4).

Je distinguerai cependant la mise en commun de ressources et celle d'idées. Pour ce qui concerne les idées, les algorithmes évolutionnaires ne se prêtent pas plus que d'autres méthodes à faire vivre des communautés.

AI : Comment voyez vous l'avenir du domaine ?
MS : Nous aurons d'abord de plus en plus de méthodes d'optimisation qui seront intégrées à celles que l'on trouve partout, dans le commerce ou dans le public.

Mais en ce qui concerne l'apport des algorithmes évolutionnaires à la créativité proprement dite, comme le fonctionnement en boite noire est impossible, le mouvement sera plus lent. Il faudra une large information des chercheurs. Je dis information et non formation. Je suis optimiste en pensant que les algorithmes évolutionnaire peuvent apporter plus qu'une simple méthode d'optimisation, mais tout le monde n'en est pas convaincu. On retrouve là le problème de l'ouverture d'esprit des gens. Il faut être informé plutôt que formé. Ceux qui sont informés se forment ensuite facilement. Il faudra donc s'assurer que les gens seront informés, et qu'ils perdront les scléroses imposées par leurs cadres de travail habituel.

AI : Le web jouera-t-il d'après-vous un rôle pour diffuser cette information?
MS : Je n'en suis pas certain. Trop d'information tue l'information. Par contre, faire savoir que les algorithmes évolutionnaires offrent de nouvelles méthodes d'optimisation participera beaucoup à leur diffusion.

AI : Ce sera donc là peut-être une retombée de cette interview… Mais revenons sur les perspectives d'avenir. Vous avez dit que les algorithmes évolutionnaires font évoluer des objets, par exemple la représentation d'une table. Où sera la créativité ?
MS : La créativité humaine sera là : comment représenter une table ? Ce qui sortira sera fonction de ce qui aura été mis dans le système.

AI : Au fond, ce que vous dites est qu'il n'y a pas de limite à la possibilité de représenter des entités qui entreront en compétition darwinienne dans ces systèmes...
MS : Je suis davantage d'accord avec cette formulation qu'avec celle consistant à dire que les algorithmes évolutionnaires n'ont pas de limites dans leurs possibilités de découverte. Imagination, intuition et rigueur s'imposent chez le programmeur.

AI : Vous rejoignez les travaux des roboticiens concernant les robots évolutionnaires, animats et autres...
MS : Absolument. Mais ceux-ci ne sont déjà pas très éloignés des méthodes d'optimisation. On peut faire évoluer par optimisation les comportements, mais aussi la morphologie des robots, comme ce que font les gens de Brandeis(5). On retrouve là un peu le rêve de Frankenstein.

AI : Est-ce que toutes ces perspectives ont atteint l'ensemble des communautés de l'intelligence artificielle que vous connaissez bien ?
MS : On y est ni plus ni moins sectaire qu'ailleurs. Beaucoup apprécient, beaucoup pensent pouvoir s'en passer.

AI : Personne ne considère encore les algorithmes évolutionnaires comme aussi indispensables que, mettons, l'informatique…
MS : Absolument pas. Qu'il y en ait un jour partout, oui. Mais de là à se poser la question d'évaluer l'opportunité des algorithmes évolutionnaires, en connaissance de cause, pour résoudre un problème…peu de gens y pensent.

AI : Il y a encore beaucoup de terrain à conquérir...
MS : Oui, mais il faut rester très pragmatique, et ne pas se présenter comme apportant la solution universelle. - ce que les spécialistes savent impossible. De plus, c'est toujours difficile de prêcher hors de sa paroisse. Les gens ont leurs méthodes et vous regardent avec méfiance.

AI : Comment se situe la France par rapport au reste du monde ?
MS : Pas très bien. Le berceau sont les Etats-Unis. En Angleterre, beaucoup de gens utilisent les algorithmes. En Allemagne, on a développé beaucoup d'algorithmes sous forme d'optimisation stochastique sans aucune référence à l'intelligence artificielle, pour se rendre compte ensuite que c'était la même chose. En France, comme je vous l'ai dit , l'esprit cartésien n'est pas très préparé. En contrepartie nous avons une école mathématique de première grandeur. On ne peut peut-être pas être bon partout. Il y aurait sans doute quelques structures à modifier pour permettre cette pluridisciplinarité dont on parle beaucoup en France mais qui n'existe pas encore.

AI : Vous mentionnez les mathématiques. Or beaucoup de chercheurs qui se sont exprimés dans notre revue regrettent que les mathématiques et l'informatique ne permettent pas aujourd'hui de comprendre ce qu'est la vie et la modéliser sur des automates. Rodney Brooks vient de dire la même chose. Pensez vous que vos méthodes puissent répondre à ce besoin ?
MS : Les algorithmes évolutionnaires ne vont pas répondre à la question de ce qu'est la vie. Mais ils permettent des simulations. Ma culture personnelle ne me permet pas d'en dire plus.

AI : Que pensez-vous du rôle de l'Europe dans votre domaine ?
MS : Il y a en Europe un nombre suffisant de projets qui sont à risques, c'est-à-dire qui autorisent une part d'échec, parce qu'ils sont assez innovants pour accepter l'insuccès partiel ou total. C'est une bonne chose. Je n'ai pas entendu parler de la même chose au niveau français. Aux Etats-Unis, des instances mettent 10% de leurs budgets pour des projets jugés par les pairs trop à risques et qui vont être repêchés au titre de ce risque.

AI : Quelles conclusion proposeriez vous à notre entretien ?
MS : On peut insister à nouveau sur ce que nous disions. Il faut échanger les expériences. C'est l'objet des JET, qui sont nées de l'identification de ce besoin d'échange. C'était au départ une action CNRS, mais depuis deux ans, l'action est auto-financée. Il y a beaucoup de gens éparpillés qui ont besoin d'être rassemblés et d'échanger leur expérience. Les journées JET comme les conférences françaises "Évolution artificielle" marchent très bien, avec 50 chercheurs au moins à chaque fois. Les JET sont francophones.

Il n'y a malheureusement pas d'industriels à les fréquenter. Evonet(6),  le site d'excellence européen ne les attire pas non plus beaucoup. Ce pourrait être une autre de nos conclusions : regretter l'absence des industriels.


Notes
(1)Conférences JET : http://www.afia.polytechnique.fr/node.php?lang=fr&node=285 Remonter d'où l'on vient
(2)Peter Bentley : Evolutionnary Créative Design http://www.cs.ucl.ac.uk/staff/P.Bentley/PetersPapers.html Remonter d'où l'on vient
(3)Grid. Gridforum http://www.gridforum.org/ Remonter d'où l'on vient
(4)DREAM : http://www.dcs.napier.ac.uk/~benp/dream/dream.htm Remonter d'où l'on vient
(5)Brandeis University : http://www.brandeis.edu/ ; voir aussi notre article (août 2000) : GOLEM, ou comment créer des robots évolutifs qui se fabriquent eux-mêmes Remonter d'où l'on vient

(6) Evonet http://www.evonet.polytechnique.fr/
Remonter d'où l'on vient

Rappel
Voir aussi nos articles
Interview de Pierre Collet
CEMAP


© Automates Intelligents 2002

 





 

 

 

Qui sommes nous ? Partenaires Abonnement Nous Contacter

© Association Automates Intelligents