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 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.
1. 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.
2. 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.
3. 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
4. Restauration subventionnée
5. Transports publics remboursés partiellement
6. 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
7. Équipements professionnels à disposition (visioconférence, prêts de matériels informatiques, etc.)
Rémunération
Selon barème légal: 4,50€ / heure
En cliquant sur "JE DÉPOSE MON CV", vous acceptez nos CGU et déclarez avoir pris connaissance de la politique de protection des données du site jobijoba.com.