Présentation du groupe META

Le groupe  META   ( Théorie et Applications des Métaheuristiques ) a été créé, en  mai 2002, comme groupe de travail de l’association ROADEF (Association Française de Recherche Opérationnelle et Aide à la Décision). Il a été ensuite intégré au GdR ALP (« Algorithmique, Langage et Programmation »), en tant que Groupe de Travail du pôle « Optimisation Combinatoire » globalement constitué, au sein de ce GdR, en octobre 2002.

Le groupe META est dirigé conjointement par Patrick SIARRY, professeur à l’Université de Paris XII Val-de-Marne ( 61ème section du CNU ) et par E.G. Talbi, professeur à l’Université des Sciences et Technologies de Lille ( 27ème section du CNU ).

META compte actuellement 111 membres, universitaires ou industriels.

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 est clairement partie prenante dans les diverses participations aux GdRs de la communauté de Recherche Opérationnelle. Il faut aussi 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 sont établis avec le groupe JET, qui organise les « Journées Evolutionnaires Trimestrielles ».

Fonctionnement du groupe META

Nous programmons 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 sont organisées en commun, ou avec le soutien, de groupes existants : EU/ME, PM2O, Club EEA et JET notamment. Les thèmes abordés concernent 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é.

Les manifestations organisées au 1er semestre 2003 ont été les suivantes :
7/02/03 (Université de Lille) : Journée d’étude « Ordonnancement et Métaheuristiques », en commun avec le groupe Bermudes, dédié aux systèmes à évènements discrets ;
26-28/02/03 : organisation de deux sessions du Congrès 2003 de l’association ROADEF, à Avignon ;
20/03/03 (Université de Paris 12, Créteil) : Journée d’étude « Automatique et Optimisation », en commun avec la section Automatique du Club EEA ;
21/03/03 (Université de Lille) : Journée d’étude ACI GRID2 « Optimisation combinatoire et data mining sur Grille », en commun avec le GdR ARP.

En 2002-03, META prend part à l’Action Spécifique Recherche Opérationnelle Inter-GdR.