Tunneling boîte grise pour l'optimisation combinatoire multi-objectifs

Type de contrat : Stage Mission confiée L'optimisation combinatoire multi-objectif vise à optimiser simultanément plusieurs fonctions objectifs, potentiellement conflictuelles, sur un espace de décision discret. Dans de nombreux problèmes d'optimisation combinatoire, les fonctions objectifs présentent une structure boîte grise (gray-box), e.g., lorsqu'elles peuvent être décomposées en sous-fonctions ne faisant intervenir qu'un nombre limité de variables de décision. Une telle structure peut être exploitée afin de concevoir des algorithmes d'optimisation spécialisés et efficaces sur le plan computationnel. Par exemple, pour de nombreux problèmes d'optimisation binaire, les fonctions objectifs peuvent être représentées à l'aide d'une transformée de Walsh/Fourier de degré borné, fournissant ainsi un cadre naturel pour analyser et exploiter les interactions entre variables. D'autres représentations de problèmes combinatoires peuvent également être considérées, dès lors qu'elles mettent en évidence une structure pouvant être exploitée par des opérateurs évolutionnaires et de recherche spécialisés pour les problèmes de type boîte grise. Bien que l'optimisation boîte grise suscite un intérêt croissant dans le contexte mono-objectif, l'étude de l'optimisation multi-objectifs à structure boîte grise reste encore largement inexplorée. Ce stage vise à contribuer à cette thématique émergente en développant de nouvelles approches algorithmiques permettant d'explorer efficacement les paysages de problèmes d'optimisation combinatoire multi-objectifs. Une attention particulière sera portée aux optima locaux de Pareto (Pareto Local Optima, PLO). Les PLO généralisent la notion d'optimum local au contexte multi-objectifs en considérant la relation de dominance. L'objectif général du stage est de développer de nouveaux mécanismes de tunneling permettant aux algorithmes d'optimisation de naviguer efficacement entre les solutions PLO, et ainsi de faciliter l'exploration de régions de haute qualité de l'ensemble de Pareto qui peuvent être difficiles à atteindre avec des méthodes classiques de recherche locale. Selon le profil et les intérêts du candidat, les travaux pourront porter sur l'analyse théorique, la conception algorithmique, l'évaluation expérimentale, ou une combinaison de ces différentes approches. Principales activités Le stage pourra porter sur un ou plusieurs des axes de recherche suivants : • Analyse des optima locaux de Pareto au travers de mécanismes de tunneling tels que le partition crossover. Étudier la structure et les propriétés des optima locaux de Pareto (PLO) pouvant être exploitées par le partition crossover et par des opérateurs de type boîte grise associés. • Conception de nouveaux mécanismes de tunneling multi-objectif. Développer et étudier des mécanismes fondés sur le partition crossover permettant de naviguer efficacement entre les PLO, avec un intérêt particulier pour (i) l'optimisation multi-objectif par décomposition et la coopération entre sous-problèmes et/ou (ii) les techniques fondées sur la dominance. • Intégration du tunneling dans des algorithmes de recherche multi-objectif efficaces et éventuellement parallèles. Intégrer le partition crossover et les mécanismes de tunneling associés dans des algorithmes évolutionnaires et de recherche locale spécialisés, notamment en exploitant le calcul parallèle et le calcul haute performance (HPC) afin d'accélérer la recherche. En conséquence, le stage pourra notamment comprendre : • une étude bibliographique sur l'optimisation boîte grise, l'optimisation multi-objectif, la recherche locale et les optima locaux de Pareto ; • l'analyse d'algorithmes existants d'optimisation boîte grise ; • des analyses théoriques ou empiriques des paysages de fitness et de la structure des PLO ; • la conception de nouveaux opérateurs de tunneling et mécanismes de recherche ; • l'implémentation et l'évaluation expérimentale de nouveaux algorithmes d'optimisation ; • la conception d'expérimentations computationnelles et l'analyse des performances algorithmiques ; • l'exploitation du calcul parallèle et du HPC lorsque cela est pertinent ; • la contribution à des publications scientifiques et/ou au développement de logiciels de recherche. Le stage s'inscrit dans une démarche de recherche, et les questions scientifiques ainsi que la méthodologie peuvent être affinées progressivement en fonction des résultats obtenus au cours du stage. Compétences Un intérêt pour la recherche fondamentale ainsi que pour l’exploration de problématiques algorithmiques appliquées et ouvertes est particulièrement apprécié. De bonnes compétences en programmation sont attendues. Inria, l'institut national de recherche dans les sciences et technologies du numérique, est en appui de l’État pour les stratégies nationales de recherche et d’innovation du numérique en tant qu'Agence de programmes. Inria mène plus de 300 projets de recherche et d’innovation avec ses 3500 scientifiques, ingénieurs