Membres du thème
| NOM Prénom | Statut |
|---|---|
| AMRI SAKHRI Mohammed Salim | Postdoctorant |
| ASSAF Rita-Natalia | Doctorant |
| BELLANGER Thibaut | Doctorant |
| DUPIN Nicolas | Maître de conférences |
| GOËFFON Adrien | Professeur |
| GRELIER Cyril | Ingénieur de recherche |
| GUERIN Axel | Doctorant |
| HAMIEZ Jean-Philippe | Maître de conférences |
| HAO Jin-Kao | Professeur |
| LEI Zhenyu | Doctorant |
| LIU Haichao | Doctorant |
| RICHER Jean-Michel | Maître de conférences |
| SAOUT Thomas | Doctorant |
| SAUBION Frédéric | Professeur |
| YANG Wei | Doctorant |
| ZOU Yuji | Doctorant |
Les activités du thème MOC se concentrent sur la résolution des problèmes combinatoires difficiles en s’appuyant principalement sur des méthodes approchées et hybrides (livret détaillé). Le thème se positionne donc naturellement à la croisée de la recherche opérationnelle et de l’intelligence artificielle. Dans ce contexte, nous visons trois types d’objectifs scientifiques complémentaires :
- Étude de problèmes de référence NP-difficiles et développement d’algorithmes performants dédiés pour repousser la limite en termes de résolution pratique. Pour cela, nous nous focalisons sur les méthodes métaheuristiques (e.g., recherche locale, algorithmes évolutionnaires) et développons des algorithmes qui exploitent au mieux les caractéristiques de chaque problème étudié. Par ailleurs, nous approfondissons les liens entre apprentissage artificiel (e.g., apprentissage par renforcement) et optimisation pour améliorer la conception et la performance des nos approches de résolution (guider les heuristiques, régler et contrôler les paramètres…). Étant donné que les problèmes de référence sont typiquement des modèles généraux permettant la formalisation de nombreuses applications pratiques, les avancées dans ce domaine pourront avoir des impacts importants allant bien au dela des problèmes étudiés.
- Études et développement de méthodes et stratégies de résolution génériques. Pour enrichir notre spectre en termes d’approches de résolution, en fort lien avec l’étude de problèmes de référence particuliers, le thème MOC s’attache aussi à élaborer des stratégies de résolution innovantes. Un grand travail expérimental est nécessaire, non seulement pour tester les solutions algorithmiques originales, mais aussi pour comprendre le comportement des mécanismes évolutionnaires, la structure des problèmes étudiés et l’adaptabilité des algorithmes de recherche aux différents problèmes (→ Analyse des paysages de fitness).
- Résolution de problèmes pratiques. De manière naturelle, nos approches d’optimisation combinatoire trouvent des applications variées. En collaboration avec des partenaires industriels mais également académiques d’autres disciplines (e.g., biologie), nous apportons notre expertise en modélisation et en résolution.
Résolution de problèmes de référence NP-difficiles
Les problèmes NP-difficiles, par leur difficulté intrinsèque, constituent une classe de problèmes privilégiés pour les métaheuristiques. Une grande partie de ces problèmes sont étudiés depuis longtemps et certains d’entre eux (e.g. coloration, max-clique) ont fait l’objet de compétitions internationales. Par conséquent, la recherche dans ce domaine reste très concurrentielle. Par ailleurs, ces problèmes permettant la modélisation de nombreuses applications réelles, les avancées sur leur résolution pourront avoir des impacts conséquents dans de nombreux domaines applicatifs. Nous avons développé des algorithmes performants pour plusieurs problèmes bien connus : coloration de graphe (sum coloring, equitable coloring, weighted vertex coloring, bandwidth coloring, Latin square completion), problèmes de clique (max-clique, s-plex, balanced bi-clique), knapsack problems (set-union knapsack, quadratic knapsack, multidimensional knapsack), partitionnement de graphe (clique partitioning, bisection, max-k-cut, conductance minimization), problèmes de dispersion et groupement (capacitated clustering, maximum min-sum dispersion). Évalués sur les « benchmarks » de la littérature de ces problèmes, nos algorithmes se sont souvent avérés très compétitifs par rapport aux meilleures méthodes de l’état de l’art. Pour élaborer ces algorithmes, nous avons travaillé sur différentes approches incluant la recherche à trajectoire unique (recherche locale), la recherche à base d’une population (recherche évolutionnaire) et la transformation de modèles. Ainsi, nous avons mené des analyses fines des propriétés des problèmes cibles et conçu des stratégies et opérateurs de recherche dédiés, qui ont contribué aux performances observées. Une grande partie de ces travaux ont été réalisés en collaboration avec des membres des thèmes RIC et ARC ainsi que des chercheurs à l’international. Ces résultats, obtenus dans le cadre de recherche doctorale/post-doctorale, ou grâce à des collaborations à l’extérieur, ont donné lieu à une quarantaine de publications dans des revues (dont plus de 98% sont classées Q1 Scimago): IEEE Transactions on Evolutionary Computation, IEEE Transactions on Cybernetics (2019), Annals of Operations Research, Applied Soft Computing, Computers & Operations Research, European Journal of Operational Research, Engineering Applications of Artificial Intelligence, Expert Systems with Applications, Future Generation Computer Systems, Information Science, Informs Journal on Computing, Knowledge-based Systems, Journal of Heuristics, Natural Computing. Pour assurer une large diffusion de nos travaux, nous avons mis à disposition de la communauté le code source d’une grande partie des algorithmes publiés (ce qui représente une trentaine de codes depuis 2015).
Méthodes et stratégies génériques de résolution
En plus de nos travaux sur les problèmes de références cités ci-dessus, nous avons travaillé sur l’élaboration de méthodes et stratégies généralement applicables pour résoudre différents problèmes combinatoires. Les métaheuristiques comportent en général de nombreux paramètres qui déterminent leur comportement lors de la résolution de problèmes et ont un impact sur leurs performances. Il est alors possible de rechercher, dans l’espace des algorithmes possibles, la meilleure configuration ou le meilleur réglage en abordant cette tâche comme un problème d’optimisation. Un de nos objectifs est donc de produire des algorithmes plus autonomes, dépendant moins de connaissances expertes ou empiriques des utilisateurs. En utilisant des techniques issues de l’apprentissage par renforcement, nous avons proposé de nouvelles approches pour mieux contrôler les paramètres de métaheuristiques classiques mais aussi d’algorithmes de recherche exhaustive (Branch and Bound). Nous avons développé ainsi un contrôleur générique qui permet de gérer de manière dynamique les paramètres d’algorithmes de résolution. Cette approche a pu être étendue avec succès au domaine de l’optimisation multi-objectif (sac à dos multi-dimensionnel avec des approches exactes mais aussi à base de recherche locale). Les algorithmes évolutionnaires ont également vocation à générer de nouveaux concepts, notamment dans le cadre de la programmation génétique. Dans ce contexte, nous avons abordé l’apprentissage de stratégies pour des solveurs complexes (SAT Modulo Theory). Ceci revient à de l’optimisation de code pour les langages de stratégies des systèmes SMT, et plus particulièrement pour Z3 de Microsoft. Également profitant du principe de l’apprentissage par renforcement, nous avons défini “Probability learning based local search” pour des problèmes de groupement (dont la coloration est un cas particulier), qui utilise l’apprentissage de probabilités pour apprendre à générer des solutions initiales pour la recherche locale. Nous avons aussi proposé la méthode “Frequent pattern based search” qui unifie la fouille de données et l’approche évolutionnaire mémétique. Nous avons élaboré “Variable population memetic search” qui intègre un mécanisme adaptatif pour ajuster dynamiquement la taille de la population d’un algorithme mémétique pour mieux équilibrer l’exploration et l’exploitation du processus de recherche. Les autres méthodes génériques combinant l’apprentissage (au sens large) et l’optimisation que nous avons développées comprennent “Opposition-based memetic search”, “Diversification-based learning”, et “Distance-guided local search”. Ces travaux, réalisés dans le cadre de plusieurs thèses ou grâce à des collaborations à l’extérieur, ont donné lieu à une dizaine de publications dans des revues (classées Q1 Scimago) telles que IEEE Transactions on Evolutionary Computation (2017), IEEE Transactions on Systems, Man, and Cybernetics: Systems (2015), Applied Soft Computing (2015, 2016, 2018), Expert Systems with Applications (2016), Journal of Heuristics (2017, 2019, 2020), International Transactions on Operational Research (2020), ainsi que des conférences internationales du domaine : EuroGP (2016), ICTAI (2016), HPCS (2018).
Analyse des paysages de fitness
Le thème MOC s’attache aussi bien à résoudre des problèmes d’optimisation spécifiques qu’à élaborer des stratégies de résolution innovantes. Un grand travail expérimental est nécessaire, non seulement pour tester les solutions algorithmiques originales, mais aussi pour comprendre le comportement des mécanismes évolutionnaires, la structure des problèmes étudiés et l’adaptabilité des algorithmes de recherche aux différents problèmes. Les travaux centrés autour des paysages de fitness permettent d’apporter des éléments plus fondamentaux de compréhension de la dynamique des algorithmes de recherche locale et évolutionnaires pour explorer des espaces de recherche combinatoires, en fonction des caractéristiques des instances et des problèmes à résoudre. Nous avons en particulier étudié l’influence des mécanismes d’exploitation et d’exploration de la recherche, comme l’influence des critères de sélection de voisins sur la qualité des trajectoires évolutionnaires. Un effort particulier a été porté sur les paysages de fitness artificiels paramétrables au moyen de fonctions NK, ainsi que sur l’étude de paysages de problèmes de référence, pseudo-booléens ou à base de permutations. Caractériser un paysage de fitness permet de comprendre et d’anticiper la performance d’un algorithme de recherche sur une instance de problème. Partant de ces résultats, nous avons également initié des travaux dans lesquels les paysages de fitness évoluent eux-mêmes par des mécanismes évolutionnaires de manière à ce que l’algorithme de résolution et l’instance à résoudre puissent s’adapter favorablement. Les contributions spécifiquement axées sur les paysages de fitness ont été présentées à plusieurs reprises dans des conférences internationales, particulièrement celles spécialisées en calcul évolutionnaire (GECCO, EvoCOP, EA) et publiées dans plusieurs revues (Applied Soft Computing, International Transactions on Operational Research, Natural Computing).
Autres contributions
- Bioinformatique Nous avons développé de nouvelles méthodes pour la reconstruction phylogénétique à partir de séquences moléculaires et pour l’analyse logique de données (projets régional et PICS CNRS), qui permettent en particulier de fournir des explications pour mieux caractériser des groupes de données biologiques. Nos travaux ont permis la mise en œuvre d’un test d’identification pour une certaine famille de bactéries phytopathogènes. Nous avons également collaboré sur un algorithme d’identification de molécules en chimie organique via spectrographie RMN. Ces travaux collaboratifs inscrivent durablement les liens entre le pôle MathSTIC et le pôle végétal de l’université d’Angers.
- Secteur social et médico-social Comme dans tous les pays développés, le secteur social et médico-social connaît en France une évolution rapide en raison de la croissance continue de son vieillissement et du handicap. Dans ce secteur, nous avons contribué via 2 contrats CIFRE au développement d’algorithmes et d’outils d’aide à la décision pour l’élaboration de plans d’actions dans les établissements sociaux et médico-sociaux d’une part et la planification du projet personnalisé d’autre part.
- Réseaux de capteurs et systèmes embarqués Dans le domaine de réseaux de capteurs sans fil et systèmes embarqués, nous avons proposé des algorithmes d’optimisation pour le suivi de cibles, la maximisation de la durée de vie du réseau et l’amélioration de performance de systèmes. Ces travaux ont été réalisés dans le cadre de 2 projets régionaux et des collaborations locales ou internationales. Certains résultats issus de ces travaux (e.g., outils de planification d’actions dans les établissements sociaux et médico-sociaux) sont en exploitation dans des produits commerciaux.
- Logistique Dans le cadre de chaînes d’approvisionnement en boucle fermée, nous avons proposé un outil de planification pour la distribution d’équipements avec réinjection potentielle suite à réparation. Cet outil s’appuie sur une nouvelle métaheuristique travaillant sur des séquences d’actions de transfert et de réparation permettant de générer des plans de manière itérative. Une validation à l’échelle industrielle a permis de valider cette approche et a mené à un dépôt de brevet.