Le 06/12/2018 par Thibaut Lust :
Lieu : Sorbonne Université, LIP6, 4 place Jussieu, 75005 Paris
Encadrants :
Sujet :
Dans ce stage, nous visons à résoudre des problèmes d'optimisation combinatoire multi-objectifs à l'aide de méthodes interactives pour l'apprentissage de préférences d'un décideur.
Dans un premier temps, les préférences du décideur seront modélisées à l'aide d'une somme pondérée. L'interaction avec le décideur aura pour but d'apprendre les poids du modèle. Dans la littérature cette approche a été récemment développée par Benabbou et Perny~cite{Benabbou2018} où les poids sont appris en cours de génération des solutions, c'est-à-dire que les questions posées au décideur sont sous la forme de comparaisons entre solutions partielles. Cette approche est très efficace pour minimiser le nombre de questions posées, mais présente également quelques désavantages comme la difficulté d'adaptation à des problèmes de type « boîte noire » pour lesquels on a uniquement accès aux évaluations des solutions~cite{Audet_2012}. De plus comparer des solutions partielles peut poser quelques difficultés au décideur.
Dans ce sujet on se focalise à poser des questions portant sur la comparaison de solutions complètes (admissibles) du problème d'optimisation combinatoire considéré.
Les premiers problèmes étudiés seront des problèmes pour lesquels ils existent des algorithmes de résolution polynomiaux, par exemple le problème de l'arbre couvrant de poids minimum. Pour ces problèmes, étant donné que trouver une solution optimale pour une somme pondérée est facile et rapide, on peut générer un grand nombre de solutions pour pouvoir ensuite utiliser des critères de type min-max regret afin de sélectionner la meilleure paire de solutions à comparer~cite{DBLP:conf/recsys/ViappianiB09}. L'incertitude sur les poids du modèle pourra donc être rapidement réduite et ainsi limiter le nombre de questions posées au décideur.
Dans un deuxième temps, les problèmes étudiés seront des problèmes pour lesquels il n'existe pas d'algorithmes de résolution polynomiaux, par exemple le problème du voyageur de commerce. Pour ces problèmes, évaluer une solution optimale selon une somme pondérée est coûteux en temps de calcul et il est important de limiter le nombre d'évaluations afin de garder un temps de résolution raisonnable. Moins d'information sera donc disponible pour la sélection de la meilleure paire de solutions à comparer et le nombre de questions posées risque d'augmenter.
Le but principal de ce stage est donc de proposer et d'évaluer de nouvelles stratégies d'élicitation afin de trouver un bon compromis entre temps de calcul et nombre de questions posées afin de converger rapidement vers une solution optimale par rapport aux préférences du décideur.
Par la suite d'autres fonctions d'agrégations pourront être considérées, comme l'opérateur OWA ou l'intégrale de Choquet, ainsi que l'utilisation d'heuristiques pour la résolution des problèmes.
