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.