Stage - Paysages d’heuristiques pour les recherches arborescentes (F/H)

Type de contrat : Stage Contexte et atouts du poste Ce stage de recherche s'adresse aux étudiants en dernière année de Master ou d'école d’ingénieur intéressés par l’optimisation combinatoire, la programmation par contraintes, les (hyper-)heuristiques stochastiques. Le sujet se déroule au sein de l'équipe BONUS du centre Inria de l'Université de Lille, ceci dans le contexte d'un projet ANR (EVARISTE) en collaboration avec L'université d'Angers. L'étudiant sélectionné est amené à intéragir de façon régulière avec les différents collègues impliqués. Mission confiée Résoudre un problème de décision sous contraintes consiste à affecter une valeur à chacune de ses variables de sorte que l'ensemble de ses contraintes soit satisfait. La recherche de solutions s'aborde souvent au moyen de stratégies complètes non polynomiales basées sur des explorations arborescentes qui consistent à examiner successivement les variables et leurs valeurs possibles, considérant que certaines branches de l'arbre de recherche peuvent être coupées dès lors qu'elles ne peuvent mener à des solutions satisfiables. L'efficacité de ces techniques dépend grandement de l'heuristique d'ordre décrivant l'arborescence, qu'il s'agisse de l'ordre des variables ou l'ordre de parcours d'exploration des valeurs dans les domaines. Ce principe de recherche arborescante peut également se généraliser dans le cadre de la conception de meta-algorithmes de recherche ou d'hyper-heuristiques, où le choix de l'ordre de combinaison des différents composants algorithmiques (e.g., les voisinages de recherches, les stratégies de branchement, etc) peut avoir un impact significatif sur les performances. Le choix de ces paramètres dans les solveurs reste largement empirique et constitue un verrou majeur pour l'efficacité de la résolution. Un axe d'étude, dans le contexte du projet ANR EVARISTE, est d'être en capacité de mieux prédire l'efficacité d'une heuristique d'ordre en fonction des propriétés des instances de problèmes. Dans ce projet, nous nous concentrerons principalement sur l'analyse des heuristiques d'ordre en nous appuyant sur le formalisme des paysages de fitness. Un paysage de fitness est défini par un espace d'individus X, une fonction de distance d définissant une mesure de proximité entre individus, et une fonction de fitness f qui associe à chaque individu une valeur de fitness rendant compte de sa qualité et servant de référence pour établir une relation de préférence entre individus. Dans notre exemple le plus simple, X représentera un espace d'ordre de variables, et par extension un espace d'arborescences, structuré au moyen de la fonction d. L'espace d'ordre sur les variables correspondant à l'ensemble des permutations [n], nous envisagerons ainsi des structures de paysages de fitness variées au moyen de différentes restrictions sur [n], de différentes mesures de distances entre permutations, et de différentes fonctions de fitness qui auront à être définies. Ces fonctions serviront de mesures comparatives entre les arborescences, et permettront d'analyser les liens entre instances de problèmes, heuristiques, et performances des recherches. Nous nous intéresserons alors à caractériser des bonnes heuristiques d'ordre relativement aux fonctions de fitness, et à les interpréter. L'objectif est donc de découvrir de nouvelles stratégies de résolution, par l'analyse de ces paysages qui permettent d'abstraire les mécanismes de résolution dans un contexte plus simple. Principales activités De façon générale, les objectifs scientifiques se situent sur trois niveaux qui seront traité en fonction du profil du candidat et de son avancement tout au long du déroulé du stage.  • Définition des paysages : Cette première étape permettra de définir le socle formel du projet en abstrayant l'espace des (hyper-)heuristiques dans des représentations alternatives données par leurs paramètres variables. Différents modèles de définition des paysages d'arbres permettront d'analyser différentes correspondances entre représentation et évaluation. L'objectif est de formaliser des modèles d'espaces d'arbres à partir d'éléments définissant une heuristique, puis, de proposer des fonctions de fitness pertinentes pour indiquer la qualité d'un arbre. • Analyse de paysages d'ordres : Cette étape permettra de caractériser des descriptions d'heuristiques pertinentes relativement aux fonctions de fitness définies préalablement, en incorporant la problématique du passage à l'échelle. Nous chercherons à interpréter les ordres associés à de hautes fitness, mais aussi d'étudier comparativement les propriétés d'heuristiques de référence. Enfin, nous analyserons la robustesse et la cohérence des informations propres aux sous-paysages, afin de caractériser des informations pertinentes pouvant être extraites d'explorations partielles. • Emergence d'heuristiques d'ordre : Il s'agira ensuite d'interpréter les corrélations entre les propriétés des instances de problèmes et celles des heuris