Automates Intelligents : labos

Le Centre de Mathématiques Appliquées (CMAP) de l'École Polytechnique et les algorithmes évolutionnaires

Qu'attend-on pour utiliser systématiquement les algorithmes évolutionnaires?

Le CMAP http://www.cmap.polytechnique.fr/

Le Centre de Mathématiques Appliquées de l'Ecole Polytechnique (CMAP) a été créé en 1974. Il a été dès l'origine orienté vers la recherche en Analyse Numérique et en Calcul Scientifique mais en liaison étroite avec les applications à la Mécanique (mécanique des fluides, mécanique des solides, propagation des ondes) puis à la Physique (électromagnétisme, plasmas, semi-conducteurs). En 1976 a été mis en place un noyau de probabilistes également orienté vers les applications.

L'arrivée de plusieurs professeurs à plein temps a favorisé un développement rapide du CMAP tant en chercheurs qu'en thèmes de recherche (notamment en probabilités et en théorie du signal). Parallèlement, la cohabilitation de l'École Polytechnique à plusieurs DEA de Mathématiques Appliquées de la région parisienne a permis d'attirer vers la recherche un nombre important d'élèves de l'X à leur sortie de l'École.

Les effectifs du CMAP (chercheurs, doctorants, ITA) se montent à 75 personnes environ. L'École Polytechnique ne comptant que peu de personnels enseignants ou chercheurs permanents, cette situation se reflète au CMAP qui ne compte que 3 professeurs et 1 DR pleins temps payés par l'X. De plus, peu d'enseignants à mi-temps du département de Mathématiques Appliquées y effectuent leur recherche. C'est le CNRS qui fournit la plus grande partie des chercheurs permanents (2 DR, 11 CR) et qui apparaît ainsi comme un partenaire essentiel de la politique scientifique du CMAP. Par ailleurs, le CMAP compte 7 professeurs et 5 maîtres de conférences des universités qui y effectuent tout ou partie (le plus souvent) de leur recherche. Il accueille 32 doctorants bénéficiant de bourses de thèse ou industrielles ou appartenant à un corps de l'État (Mines, Ponts, Armement recherche, Aviation civile). Enfin 4 ingénieurs de recherche (dont 1 à mi-temps) assurent l'assistance informatique, l'encadrement des doctorants au niveau logiciel, le développement des logiciels et la gestion des contrats.

En moyenne le CMAP forme une équipe jeune marquée par un renouvellement rapide : les jeunes docteurs partent majoritairement dans l'industrie tandis que les chercheurs, leur habilitation soutenue, quittent normalement le CMAP pour prendre un poste de professeur des universités en province. Ceci se traduit par une pénurie en chercheurs permanents "senior" de niveau DR. Pour mener à bien une politique scientifique ambitieuse, le CMAP se doit donc de "séduire" en permanence des chercheurs confirmés du CNRS ou des professeurs des universités pour qu'ils y effectuent tout ou partie de leur recherche.

A côté de thèmes classiquement étudiés au CMAP pour lesquels ses chercheurs ont acquis une expertise reconnue, on a cherché à favoriser des thèmes de recherche initialisés récemment - voire très récemment - au CMAP et qui se révèlent particulièrement importants tant d'un point de vue ``fondamental" que celui des applications potentielles.

Ont ainsi été distingués dix grands thèmes de recherche :

Méthodes intégrales et propagation d'onde (responsable : J.C. Nédélec)
Ecoulements diphasiques et combustion (resp. V. Giovangigli)
Modélisation probabiliste et milieux aléatoires (resp. P. Cattiaux )
Théorie du signal (resp. S. Mallat)
Modélisation et simulation en transport de particules chargées (resp. P.A. Raviart)
Optimisation de forme et matériaux (resp. E. Bonnetier et F. Jouve)
Algorithmes génétiques (resp. M. Schoenauer)
Équations aux dérivées partielles et contrôle (resp. J.P. Puel)
Génie logiciel et visualisation scientifique (resp. J.F. Colonna)
Mathématiques financière (resp N. El Karoui)
(extraits source CMAP)

Le Thème de recherche Algorithmes génétiques - algorithmes évolutionnaires http://www.cmap.polytechnique.fr/Activite/temp8.html

Marc Shoenauer

Les algorithmes génétiques, ou plus généralement les algorithmes évolutionnaires, sont au centre des activités de cette équipe. Ces algorithmes utilisent une métaphore - grossière - de l'évolution darwinienne des espèces (les individus les plus adaptés survivent) pour rechercher des optima de la fonction d'adaptation considérée à l'aide de transformations aléatoires : ce sont des méthodes d'optimisation stochastiques.

En tant qu'algorithmes d'optimisation, ce sont de méthodes pouvant travailler sans hypothèses fortes de régularité. En particulier, l'espace de recherche peut être quelconque (espace de paramètres continus, discrets, espaces fonctionnels, graphes, ...), et ce sont des méthodes d'ordre 0 (ne nécessitant que la connaissance des valeurs de la fonction à optimiser). Le prix à payer est un temps-calcul important. Par contre, ces algorithmes permettent d'attaquer - avec succès - des problèmes jusqu'alors non résolus.

Les domaines suivis au CMAP sont les suivants:

- Optimum Design. L'optimisation topologique des formes est un domaine où les algorithmes évolutionnaires ont été la source d'un grand pas en avant, permettant de résoudre des problèmes sur lesquels les méthodes traditionnelles n'ont pas de prises. Ainsi, des résultats originaux en optimisation topologique de formes ont été obtenus dans le cadre de la thèse de C. Kane sur l'optimisation de structures en élasticité non-linéaire, ou pour des cas de chargements de multiples.

- Identification et problèmes inverses. Les problèmes inverses sont un domaine de prédilection des méthodes évolutionnaires : en effet, il suffit de maîtriser le problème direct (i.e., de disposer d'un modèle numérique robuste et précis) pour pouvoir aborder le problème inverse. Ainsi, lorsqu'un modèle de processus (physique, chimique, mécanique), utilise une loi interne pour sa résolution numérique (e.g., loi d'état, loi de comportement, commande), l'identification de cette loi est un problème inverse : on recherche la loi donnant des résultats simulés en accord avec l'expérience, ou le résultat cherché.

- Autres problèmes d'optimisation.

- Optimisations ... des techniques évolutionnaires. L'utilisation d'outils sur des problèmes nouveaux entraîne souvent des améliorations techniques des outils en question. C'est ainsi qu'une méthode de prise en compte successive des contraintes a été imaginée, calquée sur la méthode des approximations successives bien connue des numériciens. Une méthode de contrôle des algorithmes génétiques utilisant les techniques d'apprentissage inductif, a été mise au point. (extraits source CMAP)

On trouvera sur la page personnelle de Marc Schoenauer http://www.cmap.polytechnique.fr/~marc/ de nombreuses autres informations sur les Algorithmes Evolutionnaires.

EA'01

Marc Schoenauer, conjointement avec Pierre Collet – Ecole Polytechnique, Evelyne Lutton – INRIA Rocquencourt, Cyril Fonlupt – Université de Calais, Jin-Kao HAO – Université d’Angers, organisent par ailleurs la 5e conférence internationale sur l'Evolution Artificielle http://www.cmap.polytechnique.fr/~ea01/

Annonce de la 5ème conférence internationale sur l'Evolution Artificielle

Voir aussi : http://www.automatesintelligents.com/manif/2001/mar/evolartif.html

"Les algorithmes évolutionnaires (AE) sont des méthodes d'optimisation stochastiques inspirées -- grossièrement -- de l'évolution naturelle des populations. Méthodes globales d'ordre 0, leur robustesse et leur souplesse leur permettent d'attaquer la résolution numérique de problèmes difficiles à résoudre autrement. Mais c'est leur capacité à travailler sur des espaces de recherche non standards qui leur offre les perspectives les plus originales".

Il ne faudrait pas croire que les AE sont réservés à des applications intéressant les mathématiques, la physique des matériaux et structures, ou plus généralement les sciences de l'ingénieur. Elles trouvent déjà, et trouveront de plus en plus, de nombreux utilisateurs dans tous les domaines manipulant des populations nombreuses d'objets, en mouvements fréquents, non modélisables par les algorithmes linéaires et les systèmes informatiques classiques: gestion de stocks et d'expéditions, gestions financières, gestions internes d'entreprises et d'administrations relèvent, ou relèveront bientôt de cette approche.

Lors de la 6ème Journée Evolutionnaire Trimestrielle (30 mars 2001 - Université de Paris 5 - http://www-lil.univ-littoral.fr/~fonlupt/JET6/ ) (voir aussi http://www.automatesintelligents.com/manif/2001/mar/jet.html) ont été présentées plusieurs applications de ce dernier type. Malheureusement, en France, la démarche reste encore principalement du domaine de la recherche. Les chercheurs formés à ces techniques, notamment au sein du Centre de Mathématiques Appliquées de l'école polytechnique trouvent difficilement des débouchés dans le secteur privé, et moins encore dans le secteur public, sauf à entrer dans des sociétés étrangères ayant déjà bien compris les enjeux économiques et de société impliqués. On citera à cet égard l'exemple de Biosgroup Inc, http://www.biosgroup.com/ qui travaille sur le marché européen par l'intermédiaire de sa filiale Eurobios http://www.eurobios.com/.

Le slogan de Biosgroup est "Rendre simple la complexité - complexité made simple". Ce pourrait être aussi le slogan des AE en général, appliqués à tous les problèmes de gestion affrontant la complexité et les changements rapides des acteurs et des données. Les AE peuvent être considérés comme les successeurs de l'informatique lourde, qui pendant 30 à 40 ans s'est employée, non d'ailleurs sans succès, à la manipulation des grandes masses et des grands systèmes. Mais, même avec les progrès récents de la programmation, amenant à découper dans les applications des "objets" plus réduits et mieux mobilisables, cette informatique achoppe dorénavant sur le coût de la prise en compte de nouveaux acteurs, de nouveaux délais de réponse, d'une exigence pour un service moins hiérarchisé et plus près de l'utilisateur ou du client final. Le choc avec Internet est frontal, et peu d'entreprises ou d'administrations, notamment en France, ont réussi à fusionner deux approches radicalement différentes.

L'informatique traditionnelle reste encore campée sur la défensive, expliquant que certaines exigences de l'utilisateurs, certaines réécritures de programme, pour tenir de nécessaires réformes de structures ou de procédures, sont impossibles, pour des raisons de coûts et de délais. Les décideurs, confrontés à des devis inacceptables, en concluent que ces réformes sont à différer - ce qui est la meilleure façon de se condamner à terme. Dans le même temps cependant, ils sont amenés à supporter les dépenses provoquées par le crash de plus en plus menaçant de leurs systèmes informatiques (on citera l'arrêt complet du dédouanement survenu en février dernier dans l'administration en charge).

Cette ignorance des décideurs tient en grande partie au fait que la culture gestionnaire française, notamment dans les administrations et les collectivités locales, ignore encore tout des AE. Les rares informaticiens de ces administrations connaissant un peu la question n'en parlent pas, faute qu'existent des stimulants aux efforts de productivité des individus. Bref, nous sommes en train de passer à côté d'une modernisation qui pourrait être aussi importante que celle de l'Internet, et dont il conviendrait que les Pouvoirs Publics fassent une priorité, au même titre que la conversion à ce dernier.

Nous ne développerons pas ici les secrets d'utilisation des AE. Il s'agit de matières encore difficiles, supposant une grande aptitude à manipuler les systèmes et leur complexité, ainsi que des outils mathématiques peu attirants pour le profane. De plus, il n'existe pas encore de normes d'usage ni de langages de programmation consacrées par le marché. Les développeurs sont un peu laissés à eux-mêmes, sauf à s'en remettre entièrement à des sociétés de service extérieures, ce qui n'est jamais souhaitable. On peut cependant retenir sans grands risques d'erreur quatre principes de base:

Tout ceci mériterait évidemment d'être testé par de grands donneurs d'ordre, travaillant avec nos universitaires les plus compétents. Des expériences-pilotes s'imposent, précédées elles-mêmes d'un minimum de formation des décideurs à la veille technologique Le problème est que, lorsque des ingénieurs évoquent de telles perspectives avec ces derniers, ils se font répondre que tout est déjà très difficile, et que le moment n'est ni à l'innovation, ni à de nouveaux investissements.