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.