• usa flag

Equipe : Métaheuristiques, Optimisation et Applications

Objectifs scientifiques

Face à la complexification des systèmes et à la croissance des volumes d'informations qu'engendrent les développements technologiques actuels, les différents acteurs du monde scientifique et industriel se trouvent confrontés à de nouvelles difficultés en terme de prise de décision, d’organisation ou de gestion optimale. Dans ce contexte, émergent alors des problèmes combinatoires difficiles (NP-complets, NP-difficiles,…) spécifiques ou plus généraux (Coloration, SAT, Voyageur de commerce, ...).

Nous visons particulièrement les deux objectifs suivants :

  • le passage à l'échelle, qui apparaît comme l'une des difficultés majeures lors de la mise au point d'algorithmes de résolution pour des problèmes de grande taille. Pour relever ce défi, il faut élaborer de nouveaux algorithmes performants et intégrer de nouveaux paradigmes de calcul.
  • la compréhension et l'analyse des mécanismes de résolution, qui s'imposent comme un socle indispensable pour l'optimisation de performances et la conception d'approches innovantes. Une telle démarche doit reposer sur une approche à la fois conceptuelle (modèles de représentation, modèles de calcul ...) et pratique (plates-formes d'expérimentation, contrôle de paramètres...).

Activités de recherche

Les recherches menées au sein de l’équipe concernent plus particulièrement les méthodes heuristiques modernes, dites métaheuristiques :

  • Recherche locale avancée (méthode tabou, recuit simulé...)
  • Approches évolutionnistes (algorithmes génétiques...)
  • Approches hybrides (génétique et recherche locale, recherche locale et méthodes exactes, ...)

Dans ce contexte, nos activités se développent selon plusieurs directions :

  • conception de nouveaux algorithmes et modèles :
    • Combinaisons de métaheuristiques pour la résolution de problèmes combinatoires NP-complets ou NP-difficiles classiques (SAT, MaxSAT, coloration, largeur-bande, MinLA, sac à dos multidimensionnel...)
    • Hybridation de méthodes complètes et incomplètes pour la résolution des problèmes de satisfaction de contraintes (CSP, MaxCSP, SAT et MaxSAT)
    • Heuristiques et hybridation pour l’optimisation multicritère et l’optimisation continue
  • Algorithmes heuristiques pour la bioinformatique et les biosciences (alignement multiple de séquences, reconstruction d’arbre phylogénétique, analyse de données de puces ADN...).
  • Métaheuristiques pour la fouille de données et la recherche documentaire.
  • Applications industrielles :
    • Inférence des accords d’interconnexion dans le réseau Internet (France Telecom R&D)
    • Planification intégrée de véhicules et de chauffeurs (Perinfo)
    • Affectation de fréquence pour les réseaux radio mobiles (France Telecom)
    • Positionnement d’antennes pour les réseaux radio mobiles (Projet européen Esprit IV)
    • Planification de prises de vue par satellite (application CNES)
    • Optimisation de l’architecture BSS (application Bouygues Telecom)
    • Planification de rencontres sportives et de l’emploi du temps

Mot-clés

Publications

Liste des publications >>

Membres de l'équipe MOA