Les problèmes d'optimisation combinatoire ont été largement étudiés, notamment en raison de leurs nombreuses applications (planification, logistique, distribution, investissement, production...) et de leur complexité. Coûteux à résoudre de manière exacte, les approches les plus populaires s'appuient sur des heuristiques pour prendre leurs décisions. Cependant, produire des heuristiques efficaces et performantes est un exercice difficile, d'autant plus dans des environnements réalistes avec de l'incertitude ou de la stochasticité. Dans cette thèse de doctorat, nous étudions comment l'apprentissage par renforcement peut être utilisé en optimisation combinatoire pour automatiser la production de telles heuristiques. Après nous être intéressés à un exemple concret, l'ordonnancement de tâches, nous isolons plusieurs caractéristiques clés de ces problèmes, rencontrées en pratique: une possible incertitude sur les données, les décisions à prendre, voire la définition même du problème, et une structure forte, qui a la particularité d'être souvent connue ou partiellement connue a priori. Nous explorons différentes façons de tenir compte de ces caractéristiques dans le cadre de l'apprentissage par renforcement pour une large gamme de problèmes, sortant parfois du cadre strict de l'optimisation combinatoire.
M. Philippe PREUX Université de Lille Directeur de thèse M. Sylvain LAMPRIER Université d'Angers Rapporteur M. Ludovic DENOYER Ubisoft / Sorbonne Université Rapporteur Mme Clarisse DHAENENS Université de Lille Examinatrice M. Emmanuel RACHELSON ISAE-SUPAERO Examinateur M. Zhiguang CAO Agency for Science Technology and Research Examinateur
Thèse de l'équipe SCOOL soutenue le 15/06/2023
français
English