Stage - Paysages d'Heuristiques pour les Recherches Arborescentes H/F - INRIA

A propos d'Inria

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 et personnels d'appui, en partenariat avec les universités et l'écosystème numérique (entreprises, entrepreneurs, acteurs publics). Ensemble, nous explorons des domaines clés comme l'intelligence artificielle, la cybersécurité, l'informatique quantique, le Cloud, la transformation numérique de la santé, les jumeaux numériques ou encore les technologies numériques pour la défense. Nous construisons des solutions concrètes telles que des logiciels, des startups technologiques, des partenariats avec les entreprises du tissu national et des formations de pointe. Notre objectif : l'impact scientifique, technologique et industriel au service de la souveraineté numérique de la France.

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

Type de contrat : Stage

Niveau de diplôme exigé : Bac +4 ou équivalent

Fonction : Stagiaire de la recherche

A propos du centre ou de la direction fonctionnelle

Le centre Inria de l'Université de Lille, créé en 2008, emploie 360 personnes dont 305 scientifiques répartis dans 16 équipes de recherche. Reconnu pour sa forte implication dans le développement socio-économique de la région Hauts-De-France, le centre Inria de l'Université de Lille poursuit une relation étroite avec les grandes entreprises et les PME. En favorisant les synergies entre chercheurs et industriels, Inria participe au transfert de compétences et d'expertises dans le domaine des technologies numériques et donne accès au meilleur de la recherche européenne et internationale au profit de l'innovation et des entreprises, notamment dans la région.

Depuis plus de 10 ans, le centre Inria de l'Université de Lille est situé au coeur de l'écosystème universitaire et scientifique de Lille, ainsi qu'au coeur de la Frenchtech, avec un showroom technologique basé avenue de Bretagne à Lille, sur le site d'excellence économique d'EuraTechnologies dédié aux technologies de l'information et de la communication (TIC).

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énieurinté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égalementse 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 heuristiques de recherche arborescente. Nous utiliserons ces résultats pour inférer et construire des heuristiques d'ordre, dans le but de les employer dans le cadre d'hyperheuristiques. Nous chercherons également à élaborer des fonctions de fitness prédictives.

Compétences

Compétences techniques et niveau requis : informatique, algorithmique, optimisation

Langues :français et/ou anglais

Compétences additionnelles appréciées :goût pour les travaux de recherche de nature fondamentale avec une composante expérimentale forte

Avantages

• Restauration subventionnée
• Transports publics remboursés partiellement
• Congés:le nombre de jours de congés dépend du nombre de jours de présence effective du stagiaire au sein du centre
• Équipements professionnels à disposition (visioconférence, prêts de matériels informatiques, etc.)

Rémunération

Gratification selon la règlementation en vigueur (4,50 € / heure)