Groupe  META

Groupe de travail de la
ROADEF , GDR ALP, et du GDR MACS.

Métaheuristiques : Théorie et Applications


Animé par E-G. Talbi & P. Siarry

Pour s'abonner à la liste META

 

 
 Journées organisées :

1. Journée META-BERMUDES "Métaheuristiques & Ordonnancement",
   le 7 février 2003, à Lille

 

2. Organisation de 2 sessions du Congrès ROADEF'03,
   les 26-28 février 2003, à Avignon

 

3. Réunion META- Section Automatique du Club EEA, sur le thème "Automatique et Optimisation",

le 20 mars 2003 , à Créteil

4. Journée ACI GRID2 GDR ARP - META "Optimisation combinatoire et data mining sur Grille
   le 21 Mars 2003 à Lille
   
   
5. Séminaire sur l'optimisation par essaim particulaire (OEP), Paris, au " Carré des Sciences ", le jeudi 2 octobre 2003.
   
   
6. Réunion META, en commun avec le groupe JET, qui s'intéresse aux algorithmes évolutionnaires : Paris, 12 Mars 2004
   
   
7. Réunion META, en commun avec le groupe SCDD,  (Systèmes complexes et décision distribuée): Créteil 1 Avril 2004

8. Organisation de deux sessions du Congrès FRANCORO’2004. Environ 20 présents par session : 18-21/08/04, à Fribourg (Suisse) : .

9. Organisation d’une session du Congrès MOSIM’2004. 15 présents :  01-03/09/04, à Nantes :

10. Dans le cadre du Congrès du GdR MACS, pôle STP, organisation de deux sessions de recherche. 15 présents par session : 21-22/10/04, Aix-en-Provence.

11. Organisation de 2 sessions du Congrès ROADEF'05,
    Février 2005, à Tours
12. Organisation d’une session du Congrès IMACS’2005 : 11-15/07/05, à Paris 
    
13. Organisation d'une journées commune META-PM2O sur les métaheuristiques pour l'optimisation multi-objectif, 20 Mai 2005, Lille
    
14. Par l’intermédiaire du GT META, la ROADEF sponsorise l’organisation du Congrès EA’2005 : 26-28/10/05, à Lille

Cadre des métaheuristiques :

Les ingénieurs se heurtent quotidiennement à des problèmes technologiques de complexité grandissante, qui surgissent dans des domaines très divers, comme dans les transports, les télécommunications, la génomique, la mécanique, le traitement d’images, et l’électronique. Nous nous intéressons à un groupe de méthodes, dénommées métaheuristiques, comprenant notamment la méthode du recuit simulé, les algorithmes évolutionnaires, la méthode de recherche tabou, les algorithmes de colonies de fourmis, la programmation par contraintes... apparues, à partir des années 1980, avec une ambition commune : résoudre au mieux les problèmes dits d'optimisation difficile. Les métaheuristiques se prêtent, en outre, à des extensions diverses, qui ont été proposées pour faire face à des particularités de l’optimisation. Pour illustrer la vitalité du domaine, on peut citer quelques unes de ces extensions : modèles parallèles, optimisation multiobjectif, adaptation aux problèmes à variables continues, optimisation multimodale, méthodes hybrides, nouvelles métaheuristiques.

Cette présentation ne doit pas éluder la principale difficulté à laquelle est confronté l’utilisateur, en présence d’un problème d’optimisation concret : celui du choix d’une méthode " efficace ", capable de produire une solution " optimale " - ou de qualité acceptable – au prix d’un temps de calcul " raisonnable ". Face à ce souci pragmatique, la théorie n’est pas encore d’un grand secours, car les théorèmes de convergence sont souvent inexistants, ou applicables sous des hypothèses très restrictives. En outre, le réglage " optimal " des divers paramètres d’une métaheuristique, qui peut être préconisé par la théorie, est souvent inapplicable en pratique, car il induit un coût de calcul prohibitif. En conséquence, le choix d’une " bonne " méthode, et le réglage des paramètres de celle-ci, font généralement appel au savoir-faire et à l’ " expérience " de l’utilisateur, plutôt qu’à l’application fidèle de règles bien établies.

Les efforts de recherche en cours visent à remédier à cette situation, périlleuse à terme pour la crédibilité des métaheuristiques : compte tenu du foisonnement du domaine, il est devenu indispensable d’éclairer l’utilisateur dans le choix d’une métaheuristique ou d’une méthode hybride, et dans l’ajustement de ses paramètres. Nous mentionnons en particulier trois enjeux importants de ces travaux. Le premier est l’exploitation systématique d’hybridations et de coopérations entre méthodes (émergence des systèmes multi-agents, mise au point d’une taxinomie des méthodes hybrides, …). Le second concerne les possibilités d’analyse systématique des métaheuristiques du point de vue de la convergence, la complexité, la robustesse et les garanties de qualité ; une voie prometteuse est l’analyse des " paysages d’énergie " (rugosité, caractère fractal, …). Le troisième enjeu porte sur les tentatives d’unification du domaine, par exemple sous la dénomination de " programmation à mémoire adaptative ".

Cohérence du groupe META avec d’autres structures existantes :

Le groupe META, créé dans le cadre de la ROADEF, est clairement partie prenante dans les projets de participation de la communauté de Recherche Opérationnelle aux GdRs existants. Il faut toutefois signaler que la nature très pluridisciplinaire du sujet crée un lien avec d’autres structures existantes. En particulier, une partie des enseignants-chercheurs concernés ne relèvent pas de la section 27 du CNU. Par exemple, l’adaptation des métaheuristiques en vue de la résolution des problèmes à variables continues ouvre un vaste champ d’application dans le domaine de l’ " identification ", qui intéresse en premier lieu les automaticiens (section 61 du CNU). A cet égard, l’appartenance des initiateurs du groupe META à deux sections différentes du CNU (les sections 27 et 61) nous apparaît comme une source potentielle d’élargissement de la communauté de chercheurs concernée par le groupe META. Nous avons en outre identifié plusieurs industriels intéressés par le groupe META. Par ailleurs, le groupe EU/ME est favorable à l’établissement de liens forts avec le groupe META. L’organisation de manifestations communes avec le groupe PM2O de la ROADEF est bien entendu souhaitable pour ce qui concerne l’application des métaheuristiques à des problèmes d’optimisation multiobjectif. Enfin, des liens pourront être établis avec le groupe JET, qui organise environ deux fois par an les " Journées Evolutionnaires ".

Fonctionnement proposé pour le groupe META :

Nous programmerons des journées thématiques, de préférence couplées avec des manifestations (colloques ou congrès) qui se tiennent régulièrement au plan national. Certaines journées pourront être organisées en commun, ou avec le soutien, de groupes existants : EU/ME, PM2O, Club EEA et JET notamment. Les thèmes abordés concerneront tous les aspects des métaheuristiques : avancées théoriques, nouvelles méthodes, extensions et applications. Pour ces dernières, nous privilégierons les séries d’exposés décrivant plusieurs manières d’aborder un même problème, en liaison avec des industriels spécialistes du domaine concerné. Un autre objectif pourra être la constitution de groupes de chercheurs issus de plusieurs équipes, en vue de répondre à un appel d’offres ministériel ciblé.