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

A propos d'Inria

Inria est l'institut national de recherche dédié aux sciences et technologies du numérique. Il emploie 2600 personnes. Ses 215 équipes-projets agiles, en général communes avec des partenaires académiques, impliquent plus de 3900 scientifiques pour relever les défis du numérique, souvent à l'interface d'autres disciplines. L'institut fait appel à de nombreux talents dans plus d'une quarantaine de métiers différents. 900 personnels d'appui à la recherche et à l'innovation contribuent à faire émerger et grandir des projets scientifiques ou entrepreneuriaux qui impactent le monde. Inria travaille avec de nombreuses entreprises et a accompagné la création de plus de 200 start-up. L'institut s'eorce ainsi de répondre aux enjeux de la transformation numérique de la science, de la société et de l'économie.Stage - Paysages d'heuristiques pour les recherches arborescentes (F/H)

Type de contrat : Convention de 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 et les 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.

Le stage pourra donner lieu à une poursuite de thèse.

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.
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 cette thèse, nous nous concentrerons principalement sur l'analyse et l'évaluation des ordres de variables pour la résolution de problèmes booléens, 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 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

Selon barème légal: 4,50€ / heure