Intégration d'apprentissage machine à un algorithme de recherche locale

Dans le domaine de l’optimisation combinatoire, l’intégration de modèles de Reinforcement Learning (RL) avec des algorithmes de recherche locale connaît un intérêt croissant. Le but recherché de cette approche est de tirer avantage des capacités d’apprentissage des modèles de RL et aussi de la robustesse des algorithmes de recherche locale. En effet, les méthodes de recherche locale sont connues pour rechercher des solutions de manière efficace. Cependant, elles peuvent parfois souffrir d’un manque d’adaptabilité lorsque l’espace des solutions se complexifie. Cette limitation peut être surmontée par le caractère évolutif des modèles de RL qui modifient leur stratégie à partir de leurs expériences passées. L’apport de RL aux algorithmes de recherche locale permet de développer une nouvelle méthode plus robuste et capable de mieux résoudre les problèmes d’optimisation complexes. Ce mémoire explore l’intégration de techniques de (RL) à une métaheuristique, l’Adaptive Large Neighborhood Search (ALNS), dans le contexte de la résolution d’un problème de planification et d’ordonnancement de soins à domicile. L’étude compare les performances de ALNS aux algorithmes ALNS-PPO et ALNS-SAC, correspondants à ALNS où la partie sur la sélection des opérateurs est remplacée respectivement par les algorithmes de RL Proximal Policy Optimization (PPO) et Soft Actor-Critic (SAC ). La comparaison des performances se fait en matière de qualité, de complexité et de vitesse de convergence des algorithmes. Les résultats montrent que ALNS trouve des solutions de meilleure qualité par rapport à ALNS-PPO et ALNS-SAC sur l’ensemble des données étudiées. ALNS a su mieux généraliser aux variations des paramètres d’instance tout en étant plus rapide en temps de calcul. Les méthodes expérimentales incluent notamment une génération de données à partir d’un ensemble de données réelles. Cette étude suggère plusieurs pistes de continuation, notamment la génération de données plus diversifiées et l’exploration d’autres architectures de RL comme les modèles en graphes ou les modèles par pointeurs (pointer networks). Elle suggère aussi l’exploration de nouvelles fonctions de récompense qui permettent de mieux rendre compte de la poursuite de l’objectif par le modèle.

Abstract

In the field of combinatorial optimization, there is growing interest in the integration of reinforcement learning models (RL) with local search algorithms. The aim of this approach is to take advantage of the learning capabilities of RL models and the robustness of local search algorithms. Indeed, local search methods are known to search for solutions efficiently. However, they can sometimes suffer from a lack of adaptability when the solution space becomes more complex. This limitation can be overcome by the evolutionary nature of RL models, which modify their strategy on the basis of past experience. The contribution of RL to local search algorithms makes it possible to develop a new, more robust method capable of better solving complex optimization problems. This master thesis explores the integration of (RL) techniques with a metaheuristic, Adap-tive Large Neighborhood Search (ALNS), in the context of solving a home care planning and scheduling problem. The study compares the performance of ALNS with the algorithms ALNS-PPO and ALNS-SAC, corresponding to ALNS where the operator selection part is replaced by algorithms Proximal Policy Optimization (PPO) and Soft Actor-Critic (SAC) respectively. Performance is compared in terms of algorithm quality, complexity and conver-gence speed. The results show that ALNS finds better quality solutions than PPO and SAC on the data set studied. ALNS generalizes better to variations in instance parameters, while being faster in computation time. Experimental methods included data generation from a real data set. This study suggests several avenues for further development, including the generation of more diversified data and the exploration of other RL architectures such as graph models or pointer networks. It also suggests the exploration of new reward functions to better account for the model’s pursuit of the goal.