{"id":44,"date":"2021-11-12T17:28:37","date_gmt":"2021-11-12T16:28:37","guid":{"rendered":"https:\/\/leria.univ-angers.fr\/?page_id=44"},"modified":"2024-04-15T09:52:50","modified_gmt":"2024-04-15T07:52:50","slug":"metaheuristiques-et-optimisation-combinatoire","status":"publish","type":"page","link":"https:\/\/leria.univ-angers.fr\/?page_id=44","title":{"rendered":"M\u00e9taheuristiques et Optimisation Combinatoire"},"content":{"rendered":"\n<h3 class=\"wp-block-heading\">Membres du th\u00e8me<\/h3>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\" style=\"font-size:80%\">\n    <table>\n        <thead>\n            <tr>\n                <th>NOM Pr\u00e9nom<\/th>\n                <th>Statut<\/th>\n            <\/tr>\n        <\/thead>\n        <tbody>\n            <tr>\n                <td>AMRI SAKHRI Mohammed Salim<\/td>\n                <td> Postdoctorant<\/td>\n            <\/tr>\n            <tr>\n                <td>ASSAF Rita-Natalia<\/td>\n                <td> Doctorant<\/td>\n            <\/tr>\n            <tr>\n                <td>BELLANGER Thibaut<\/td>\n                <td>Doctorant<\/td>\n            <\/tr>\n            <tr>\n                <td>DUPIN Nicolas<\/td>\n                <td>Ma\u00eetre de conf\u00e9rences<\/td>\n            <\/tr>\n            <tr>\n                <td>GO\u00cbFFON Adrien<\/td>\n                <td>Professeur<\/td>\n            <\/tr>\n            <tr>\n                <td>GRELIER Cyril<\/td>\n                <td>Ing\u00e9nieur de recherche<\/td>\n            <\/tr>\n            <tr>\n                <td>GUERIN Axel<\/td>\n                <td>Doctorant<\/td>\n            <\/tr>\n            <tr>\n                <td>HAMIEZ Jean-Philippe<\/td>\n                <td> Ma\u00eetre de conf\u00e9rences<\/td>\n            <\/tr>\n            <tr>\n                <td>HAO Jin-Kao<\/td>\n                <td> Professeur<\/td>\n            <\/tr>\n            <tr>\n                <td>LEI Zhenyu<\/td>\n                <td>Doctorant<\/td>\n            <\/tr>\n            <tr>\n                <td>LIU Haichao<\/td>\n                <td>Doctorant<\/td>\n            <\/tr>\n            <tr>\n                <td>RICHER Jean-Michel<\/td>\n                <td> Ma\u00eetre de conf\u00e9rences<\/td>\n            <\/tr>\n            <tr>\n                <td>SAOUT Thomas<\/td>\n                <td>Doctorant<\/td>\n            <\/tr>\n            <tr>\n                <td>SAUBION Fr\u00e9d\u00e9ric<\/td>\n                <td>Professeur<\/td>\n            <\/tr>\n            <tr>\n                <td>YANG Wei<\/td>\n                <td>Doctorant<\/td>\n            <\/tr>\n            <tr>\n                <td>ZOU Yuji<\/td>\n                <td>Doctorant<\/td>\n            <\/tr>\n\n        <\/tbody>\n    <\/table>\n<\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Les activit\u00e9s du th\u00e8me MOC se concentrent sur la r\u00e9solution des probl\u00e8mes combinatoires difficiles en s\u2019appuyant principalement sur des m\u00e9thodes approch\u00e9es et hybrides (<a href=\"https:\/\/leria.univ-angers.fr\/wp-content\/uploads\/2021\/11\/MOC.pdf\" target=\"_blank\" rel=\"noreferrer noopener\">livret d\u00e9taill\u00e9<\/a>). Le th\u00e8me se positionne donc naturellement \u00e0 la crois\u00e9e de la recherche op\u00e9rationnelle et de l\u2019intelligence artificielle. Dans ce contexte, nous visons trois types d\u2019objectifs scientifiques compl\u00e9mentaires :<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><em>\u00c9tude de probl\u00e8mes de r\u00e9f\u00e9rence NP-difficiles et d\u00e9veloppement d\u2019algorithmes performants d\u00e9di\u00e9s pour repousser la limite en termes de r\u00e9solution pratique.<\/em> Pour cela, nous nous focalisons sur les m\u00e9thodes m\u00e9taheuristiques (e.g., recherche locale, algorithmes \u00e9volutionnaires) et d\u00e9veloppons des algorithmes qui exploitent au mieux les caract\u00e9ristiques de chaque probl\u00e8me \u00e9tudi\u00e9. Par ailleurs, nous approfondissons les liens entre apprentissage artificiel (e.g., apprentissage par renforcement) et optimisation pour am\u00e9liorer la conception et la performance des nos approches de r\u00e9solution (guider les heuristiques, r\u00e9gler et contr\u00f4ler les param\u00e8tres\u2026). \u00c9tant donn\u00e9 que les probl\u00e8mes de r\u00e9f\u00e9rence sont typiquement des mod\u00e8les g\u00e9n\u00e9raux permettant la formalisation de nombreuses applications pratiques, les avanc\u00e9es dans ce domaine pourront avoir des impacts importants allant bien au dela des probl\u00e8mes \u00e9tudi\u00e9s.<\/li>\n\n\n\n<li><em>\u00c9tudes et d\u00e9veloppement de m\u00e9thodes et strat\u00e9gies de r\u00e9solution g\u00e9n\u00e9riques.<\/em> Pour enrichir notre spectre en termes d\u2019approches de r\u00e9solution, en fort lien avec l\u2019\u00e9tude de probl\u00e8mes de r\u00e9f\u00e9rence particuliers, le th\u00e8me MOC s\u2019attache aussi \u00e0 \u00e9laborer des strat\u00e9gies de r\u00e9solution innovantes. Un grand travail exp\u00e9rimental est n\u00e9cessaire, non seulement pour tester les solutions algorithmiques originales, mais aussi pour comprendre le comportement des m\u00e9canismes \u00e9volutionnaires, la structure des probl\u00e8mes \u00e9tudi\u00e9s et l\u2019adaptabilit\u00e9 des algorithmes de recherche aux diff\u00e9rents probl\u00e8mes (\u2192 <em>Analyse des paysages de fitness<\/em>).<\/li>\n\n\n\n<li><em>R\u00e9solution de probl\u00e8mes pratiques.<\/em> De mani\u00e8re naturelle, nos approches d\u2019optimisation combinatoire trouvent des applications vari\u00e9es. En collaboration avec des partenaires industriels mais \u00e9galement acad\u00e9miques d\u2019autres disciplines (e.g., biologie), nous apportons notre expertise en mod\u00e9lisation et en r\u00e9solution.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"r\u00e9solution-de-probl\u00e8mes-de-r\u00e9f\u00e9rence-np-difficiles\">R\u00e9solution de probl\u00e8mes de r\u00e9f\u00e9rence NP-difficiles<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Les probl\u00e8mes NP-difficiles, par leur difficult\u00e9 intrins\u00e8que, constituent une classe de probl\u00e8mes privil\u00e9gi\u00e9s pour les m\u00e9taheuristiques. Une grande partie de ces probl\u00e8mes sont \u00e9tudi\u00e9s depuis longtemps et certains d\u2019entre eux (e.g. coloration, max-clique) ont fait l\u2019objet de comp\u00e9titions internationales. Par cons\u00e9quent, la recherche dans ce domaine reste tr\u00e8s concurrentielle. Par ailleurs, ces probl\u00e8mes permettant la mod\u00e9lisation de nombreuses applications r\u00e9elles, les avanc\u00e9es sur leur r\u00e9solution pourront avoir des impacts cons\u00e9quents dans de nombreux domaines applicatifs. Nous avons d\u00e9velopp\u00e9 des algorithmes performants pour plusieurs probl\u00e8mes bien connus : coloration de graphe (sum coloring, equitable coloring, weighted vertex coloring, bandwidth coloring, Latin square completion), probl\u00e8mes 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\u00e8mes de dispersion et groupement (capacitated clustering, maximum min-sum dispersion). \u00c9valu\u00e9s sur les \u00ab benchmarks \u00bb de la litt\u00e9rature de ces probl\u00e8mes, nos algorithmes se sont souvent av\u00e9r\u00e9s tr\u00e8s comp\u00e9titifs par rapport aux meilleures m\u00e9thodes de l\u2019\u00e9tat de l\u2019art. Pour \u00e9laborer ces algorithmes, nous avons travaill\u00e9 sur diff\u00e9rentes approches incluant la recherche \u00e0 trajectoire unique (recherche locale), la recherche \u00e0 base d\u2019une population (recherche \u00e9volutionnaire) et la transformation de mod\u00e8les. Ainsi, nous avons men\u00e9 des analyses fines des propri\u00e9t\u00e9s des probl\u00e8mes cibles et con\u00e7u des strat\u00e9gies et op\u00e9rateurs de recherche d\u00e9di\u00e9s, qui ont contribu\u00e9 aux performances observ\u00e9es. Une grande partie de ces travaux ont \u00e9t\u00e9 r\u00e9alis\u00e9s en collaboration avec des membres des th\u00e8mes RIC et ARC ainsi que des chercheurs \u00e0 l\u2019international. Ces r\u00e9sultats, obtenus dans le cadre de recherche doctorale\/post-doctorale, ou gr\u00e2ce \u00e0 des collaborations \u00e0 l\u2019ext\u00e9rieur, ont donn\u00e9 lieu \u00e0 une quarantaine de publications dans des revues (dont plus de 98% sont class\u00e9es Q1 Scimago): IEEE Transactions on Evolutionary Computation, IEEE Transactions on Cybernetics (2019), Annals of Operations Research, Applied Soft Computing, Computers &amp; 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 \u00e0 disposition de la communaut\u00e9 le code source d\u2019une grande partie des algorithmes publi\u00e9s (ce qui repr\u00e9sente une trentaine de codes depuis 2015).<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"m\u00e9thodes-et-strat\u00e9gies-g\u00e9n\u00e9riques-de-r\u00e9solution\">M\u00e9thodes et strat\u00e9gies g\u00e9n\u00e9riques de r\u00e9solution<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">En plus de nos travaux sur les probl\u00e8mes de r\u00e9f\u00e9rences cit\u00e9s ci-dessus, nous avons travaill\u00e9 sur l\u2019\u00e9laboration de m\u00e9thodes et strat\u00e9gies g\u00e9n\u00e9ralement applicables pour r\u00e9soudre diff\u00e9rents probl\u00e8mes combinatoires. Les m\u00e9taheuristiques comportent en g\u00e9n\u00e9ral de nombreux param\u00e8tres qui d\u00e9terminent leur comportement lors de la r\u00e9solution de probl\u00e8mes et ont un impact sur leurs performances. Il est alors possible de rechercher, dans l\u2019espace des algorithmes possibles, la meilleure configuration ou le meilleur r\u00e9glage en abordant cette t\u00e2che comme un probl\u00e8me d\u2019optimisation. Un de nos objectifs est donc de produire des algorithmes plus autonomes, d\u00e9pendant moins de connaissances expertes ou empiriques des utilisateurs. En utilisant des techniques issues de l\u2019apprentissage par renforcement, nous avons propos\u00e9 de nouvelles approches pour mieux contr\u00f4ler les param\u00e8tres de m\u00e9taheuristiques classiques mais aussi d\u2019algorithmes de recherche exhaustive (Branch and Bound). Nous avons d\u00e9velopp\u00e9 ainsi un contr\u00f4leur g\u00e9n\u00e9rique qui permet de g\u00e9rer de mani\u00e8re dynamique les param\u00e8tres d\u2019algorithmes de r\u00e9solution. Cette approche a pu \u00eatre \u00e9tendue avec succ\u00e8s au domaine de l\u2019optimisation multi-objectif (sac \u00e0 dos multi-dimensionnel avec des approches exactes mais aussi \u00e0 base de recherche locale). Les algorithmes \u00e9volutionnaires ont \u00e9galement vocation \u00e0 g\u00e9n\u00e9rer de nouveaux concepts, notamment dans le cadre de la programmation g\u00e9n\u00e9tique. Dans ce contexte, nous avons abord\u00e9 l\u2019apprentissage de strat\u00e9gies pour des solveurs complexes (SAT Modulo Theory). Ceci revient \u00e0 de l\u2019optimisation de code pour les langages de strat\u00e9gies des syst\u00e8mes SMT, et plus particuli\u00e8rement pour Z3 de Microsoft. \u00c9galement profitant du principe de l\u2019apprentissage par renforcement, nous avons d\u00e9fini \u201cProbability learning based local search\u201d pour des probl\u00e8mes de groupement (dont la coloration est un cas particulier), qui utilise l\u2019apprentissage de probabilit\u00e9s pour apprendre \u00e0 g\u00e9n\u00e9rer des solutions initiales pour la recherche locale. Nous avons aussi propos\u00e9 la m\u00e9thode \u201cFrequent pattern based search\u201d qui unifie la fouille de donn\u00e9es et l\u2019approche \u00e9volutionnaire m\u00e9m\u00e9tique. Nous avons \u00e9labor\u00e9 \u201cVariable population memetic search\u201d qui int\u00e8gre un m\u00e9canisme adaptatif pour ajuster dynamiquement la taille de la population d\u2019un algorithme m\u00e9m\u00e9tique pour mieux \u00e9quilibrer l\u2019exploration et l\u2019exploitation du processus de recherche. Les autres m\u00e9thodes g\u00e9n\u00e9riques combinant l\u2019apprentissage (au sens large) et l\u2019optimisation que nous avons d\u00e9velopp\u00e9es comprennent \u201cOpposition-based memetic search\u201d, \u201cDiversification-based learning\u201d, et \u201cDistance-guided local search\u201d. Ces travaux, r\u00e9alis\u00e9s dans le cadre de plusieurs th\u00e8ses ou gr\u00e2ce \u00e0 des collaborations \u00e0 l\u2019ext\u00e9rieur, ont donn\u00e9 lieu \u00e0 une dizaine de publications dans des revues (class\u00e9es 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\u00e9rences internationales du domaine : EuroGP (2016), ICTAI (2016), HPCS (2018).<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"analyse-des-paysages-de-fitness\">Analyse des paysages de fitness<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Le th\u00e8me MOC s\u2019attache aussi bien \u00e0 r\u00e9soudre des probl\u00e8mes d\u2019optimisation sp\u00e9cifiques qu\u2019\u00e0 \u00e9laborer des strat\u00e9gies de r\u00e9solution innovantes. Un grand travail exp\u00e9rimental est n\u00e9cessaire, non seulement pour tester les solutions algorithmiques originales, mais aussi pour comprendre le comportement des m\u00e9canismes \u00e9volutionnaires, la structure des probl\u00e8mes \u00e9tudi\u00e9s et l\u2019adaptabilit\u00e9 des algorithmes de recherche aux diff\u00e9rents probl\u00e8mes. Les travaux centr\u00e9s autour des paysages de fitness permettent d\u2019apporter des \u00e9l\u00e9ments plus fondamentaux de compr\u00e9hension de la dynamique des algorithmes de recherche locale et \u00e9volutionnaires pour explorer des espaces de recherche combinatoires, en fonction des caract\u00e9ristiques des instances et des probl\u00e8mes \u00e0 r\u00e9soudre. Nous avons en particulier \u00e9tudi\u00e9 l\u2019influence des m\u00e9canismes d\u2019exploitation et d\u2019exploration de la recherche, comme l\u2019influence des crit\u00e8res de s\u00e9lection de voisins sur la qualit\u00e9 des trajectoires \u00e9volutionnaires. Un effort particulier a \u00e9t\u00e9 port\u00e9 sur les paysages de fitness artificiels param\u00e9trables au moyen de fonctions NK, ainsi que sur l\u2019\u00e9tude de paysages de probl\u00e8mes de r\u00e9f\u00e9rence, pseudo-bool\u00e9ens ou \u00e0 base de permutations. Caract\u00e9riser un paysage de fitness permet de comprendre et d\u2019anticiper la performance d\u2019un algorithme de recherche sur une instance de probl\u00e8me. Partant de ces r\u00e9sultats, nous avons \u00e9galement initi\u00e9 des travaux dans lesquels les paysages de fitness \u00e9voluent eux-m\u00eames par des m\u00e9canismes \u00e9volutionnaires de mani\u00e8re \u00e0 ce que l\u2019algorithme de r\u00e9solution et l\u2019instance \u00e0 r\u00e9soudre puissent s\u2019adapter favorablement. Les contributions sp\u00e9cifiquement ax\u00e9es sur les paysages de fitness ont \u00e9t\u00e9 pr\u00e9sent\u00e9es \u00e0 plusieurs reprises dans des conf\u00e9rences internationales, particuli\u00e8rement celles sp\u00e9cialis\u00e9es en calcul \u00e9volutionnaire (GECCO, EvoCOP, EA) et publi\u00e9es dans plusieurs revues (Applied Soft Computing, International Transactions on Operational Research, Natural Computing).<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"autres-contributions\">Autres contributions<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li><em>Bioinformatique<\/em> Nous avons d\u00e9velopp\u00e9 de nouvelles m\u00e9thodes pour la reconstruction phylog\u00e9n\u00e9tique \u00e0 partir de s\u00e9quences mol\u00e9culaires et pour l\u2019analyse logique de donn\u00e9es (projets r\u00e9gional et PICS CNRS), qui permettent en particulier de fournir des explications pour mieux caract\u00e9riser des groupes de donn\u00e9es biologiques. Nos travaux ont permis la mise en \u0153uvre d\u2019un test d\u2019identification pour une certaine famille de bact\u00e9ries phytopathog\u00e8nes. Nous avons \u00e9galement collabor\u00e9 sur un algorithme d\u2019identification de mol\u00e9cules en chimie organique via spectrographie RMN. Ces travaux collaboratifs inscrivent durablement les liens entre le p\u00f4le MathSTIC et le p\u00f4le v\u00e9g\u00e9tal de l\u2019universit\u00e9 d\u2019Angers.<\/li>\n\n\n\n<li><em>Secteur social et m\u00e9dico-social<\/em> Comme dans tous les pays d\u00e9velopp\u00e9s, le secteur social et m\u00e9dico-social conna\u00eet en France une \u00e9volution rapide en raison de la croissance continue de son vieillissement et du handicap. Dans ce secteur, nous avons contribu\u00e9 via 2 contrats CIFRE au d\u00e9veloppement d\u2019algorithmes et d\u2019outils d\u2019aide \u00e0 la d\u00e9cision pour l\u2019\u00e9laboration de plans d\u2019actions dans les \u00e9tablissements sociaux et m\u00e9dico-sociaux d\u2019une part et la planification du projet personnalis\u00e9 d\u2019autre part.<\/li>\n\n\n\n<li><em>R\u00e9seaux de capteurs et syst\u00e8mes embarqu\u00e9s<\/em> Dans le domaine de r\u00e9seaux de capteurs sans fil et syst\u00e8mes embarqu\u00e9s, nous avons propos\u00e9 des algorithmes d\u2019optimisation pour le suivi de cibles, la maximisation de la dur\u00e9e de vie du r\u00e9seau et l\u2019am\u00e9lioration de performance de syst\u00e8mes. Ces travaux ont \u00e9t\u00e9 r\u00e9alis\u00e9s dans le cadre de 2 projets r\u00e9gionaux et des collaborations locales ou internationales. Certains r\u00e9sultats issus de ces travaux (e.g., outils de planification d\u2019actions dans les \u00e9tablissements sociaux et m\u00e9dico-sociaux) sont en exploitation dans des produits commerciaux.<\/li>\n\n\n\n<li><em>Logistique<\/em> Dans le cadre de cha\u00eenes d\u2019approvisionnement en boucle ferm\u00e9e, nous avons propos\u00e9 un outil de planification pour la distribution d\u2019\u00e9quipements avec r\u00e9injection potentielle suite \u00e0 r\u00e9paration. Cet outil s\u2019appuie sur une nouvelle m\u00e9taheuristique travaillant sur des s\u00e9quences d\u2019actions de transfert et de r\u00e9paration permettant de g\u00e9n\u00e9rer des plans de mani\u00e8re it\u00e9rative. Une validation \u00e0 l\u2019\u00e9chelle industrielle a permis de valider cette approche et a men\u00e9 \u00e0 un d\u00e9p\u00f4t de brevet.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Membres du th\u00e8me NOM Pr\u00e9nom Statut AMRI SAKHRI Mohammed Salim Postdoctorant ASSAF Rita-Natalia Doctorant BELLANGER Thibaut Doctorant DUPIN Nicolas Ma\u00eetre de conf\u00e9rences GO\u00cbFFON Adrien Professeur GRELIER Cyril Ing\u00e9nieur de recherche GUERIN Axel Doctorant HAMIEZ Jean-Philippe Ma\u00eetre de conf\u00e9rences HAO Jin-Kao &hellip; <a href=\"https:\/\/leria.univ-angers.fr\/?page_id=44\">Continuer la lecture <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":5,"featured_media":0,"parent":38,"menu_order":1,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-44","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/leria.univ-angers.fr\/index.php?rest_route=\/wp\/v2\/pages\/44","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/leria.univ-angers.fr\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/leria.univ-angers.fr\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/leria.univ-angers.fr\/index.php?rest_route=\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/leria.univ-angers.fr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=44"}],"version-history":[{"count":8,"href":"https:\/\/leria.univ-angers.fr\/index.php?rest_route=\/wp\/v2\/pages\/44\/revisions"}],"predecessor-version":[{"id":393,"href":"https:\/\/leria.univ-angers.fr\/index.php?rest_route=\/wp\/v2\/pages\/44\/revisions\/393"}],"up":[{"embeddable":true,"href":"https:\/\/leria.univ-angers.fr\/index.php?rest_route=\/wp\/v2\/pages\/38"}],"wp:attachment":[{"href":"https:\/\/leria.univ-angers.fr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=44"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}