Application of Deep Reinforcement Learning to Routing and Scheduling

Récemment, on a assisté à une montée en puissance des techniques d'apprentissage automatique dans le domaine de l'optimisation. Les méthodes d'apprentissage supervisé peuvent exploiter des structures sous-jacentes dans des multitudes de problèmes et utiliser cette expertise pour aider à trouver plus efficacement la solution de nouvelles instances de ces problèmes. Dans l'apprentissage par renforcement (Reinforcement Learning, RL), cependant, un agent interagit avec l'environnement contrôlé par les contraintes d'un problème d'optimisation. Une fonction de récompense qui s'aligne sur la fonction objectif du problème d'optimisation conduit le processus de recherche itératif à prendre de meilleures décisions pour atteindre la politique optimale. Comme les problèmes d'optimisation combinatoire peuvent généralement être formulés comme des problèmes de prise de décision séquentielle, ils peuvent être modélisés comme des processus de décision de Markov (Markov Decision Process, MDP). L'utilisation de méthodes de recherche exhaustive peut devenir prohibitive pour ces problèmes, c'est pourquoi des méthodes d'apprentissage par renforcement peuvent être utilisées pour les résoudre. En raison de la nature combinatoire de ces problèmes, dans de nombreux cas, les algorithmes de programmation en nombres entiers standard des logiciels de programmation mathématique commerciaux ne peuvent pas résoudre efficacement les modèles correspondants. D'un autre point de vue, de nombreux problèmes issus de cas pratiques réels sont de nature online, ce qui signifie que certaines informations ne sont pas disponibles au départ et qu'elles seront révélées au fil du temps. Dans ce cas, l'information des paramètres stochastiques n'est pas connue à l'avance. L'utilisation de la programmation linéaire mixte en nombres entiers pour ce type de problèmes serait coûteuse en termes de calculs. Néanmoins, les méthodes d'apprentissage par renforcement fonctionnent également très bien pour ces problèmes dynamiques. En outre, la majorité des problèmes d'optimisation combinatoire peuvent être définis sur des graphes. Les récentes avancées dans le domaine de l'apprentissage profond, en particulier les réseaux de neurones graphiques, ont permis de remarquer l'application des méthodes d'apprentissage par renforcement à ces problèmes. Les réseaux neuronaux graphiques capturent l'information relationnelle cachée entre tous les éléments (nœuds et arêtes) des graphes pour faire de meilleures prédictions. Dans cette thèse, nous tirons parti de l'apprentissage par renforcement et des réseaux neuronaux graphiques pour développer des algorithmes efficaces pour les problèmes d'optimisation combinatoire dans diverses applications. Dans le premier projet, nous développons une méthode d'apprentissage profond par renforcement pour trouver les meilleures orientations de faisceaux pour irradier les patients sous radiothérapie pour le traitement du cancer en utilisant le système Cyberknife. Nous trouvons simultanément la trajectoire pour les traverser afin de réduire le temps de traitement tout en maintenant la qualité du traitement par rapport à l'utilisation de toutes les orientations possibles du faisceau. En utilisant l'agent entraîné, nous pouvons générer des plans de traitement spécifiques au patient au lieu d'utiliser un ensemble fixe de faisceaux pour chaque patient et chaque site cancéreux. À cette fin, nous représentons le problème par un graphe et appliquons des réseaux neuronaux de graphe pour apprendre une nouvelle représentation du graphe et les caractéristiques de ses éléments correspondants. Grâce à cette méthode, nous pouvons utiliser de nombreuses caractéristiques différentes concernant l'anatomie des patients et les informations dosimétriques. Nous proposons un algorithme de Q-Learning profond pour entraîner un agent à sélectionner un sous-ensemble de faisceaux et l'ordre dans lequel les visiter. Les résultats sont ensuite transmis à un problème d'optimisation directe de l'ouverture où d'autres paramètres de traitement sont calculés. Les résultats montrent que l'utilisation de la méthode proposée réduit le temps de traitement tout en maintenant la qualité du traitement par rapport aux traitements cliniques de base. Dans le deuxième projet, nous proposons un algorithme d'apprentissage par renforcement profond basé sur les réseaux de neurones graphiques pour résoudre le problème de routage dynamique et d'affectation de longueurs d'onde dans un contexte de problème d'optimisation des réseaux de télécommunications. Les demandes de trafic entrant arrivent dynamiquement en suivant une distribution inconnue. Nous modélisons ce problème comme un MDP. En raison de la nature dynamique du problème, nous développons un algorithme RL profond avec l'objectif de maximiser les demandes de trafic admises. Les résultats montrent que l'algorithme proposé est plus performant que les heuristiques largement utilisées (tant dans la littérature de recherche que dans la pratique). En adoptant cet algorithme, nous fournissons un modèle qui résout le routage et l'affectation des ressources (longueurs d'onde) en même temps. Nous considérons un cas d'information parfaite, où toutes les informations sont connues de l'optimiseur, et avons formulé un modèle de programmation mathématique résolu avec des solveurs commerciaux comme base de référence (limite supérieure) pour comparer les résultats de l'algorithme. Dans le troisième projet, nous abordons le problème d'ordonnancement dynamique sous contraintes multi-ressources qui découle d'un problème réel dans l'industrie. Nous considérons un cas où chaque tâche a une date limite spécifique et une date d'expiration. Nous appliquons des Q-Networks avec approximation de fonction pour générer des solutions qui minimisent les coûts totaux de retard et les coûts d'expiration. Nous définissons d'abord le problème comme un graphe et attribuons plusieurs caractéristiques à chaque nœud. Pour capturer toutes les relations latentes entre les éléments, nous appliquons des Graph Attention Networks comme décodeurs pour apprendre une nouvelle représentation du graphe d'entrée à chaque instant de décision. L'agent RL sélectionne une tâche (parmi l'ensemble des tâches arrivées) et lui affecte des ressources afin de minimiser les pénalités cumulées attendues. Nous comparons les résultats avec différentes méthodes de la littérature. Nous formulons également le problème avec une information parfaite à l'aide de la programmation par contraintes, afin d'obtenir une borne inférieure pour les solutions.