Offre de thèse 2023 : Association des techniques de machine learning et des métaheuristiques pour la résolution des problèmes d’optimisation combinatoire

La thèse aura lieu dans l’équipe Optimist du Loria , et sera encadrée par

Wahiba Ramdane Cherif-Khettaf (ramdanec@loria.fr)

Ammar Oulamara (oulamara@loria.fr)

Date limite pour candidater 10 mai 2023

Compétences attendues 

– Master recherche ou diplôme d’ingénieur dans au moins une des thématiques ci-dessous : Informatique, Mathématiques Appliquées, Recherche Opérationnelle, Intelligence artificielle et Sciences de données.

– Expérience en programmation

Dossier de candidature

CV détaillé

Relevé de notes M1 et M2

Lettre de motivation

Éventuelles recommandations, ou les noms des référents à contacter.

Description du sujet

L’optimisation combinatoire trouve des applications dans de nombreux domaines tels que le transport, la production, la mobilité, etc. La majorité des problèmes d’optimisation combinatoire sont difficiles à résoudre (p. ex. problème du voyageur de commerce, problème de packing, problèmes d’ordonnancement), et leur résolution repose souvent sur le développement d’heuristiques spécifiques permettant de trouver des solutions efficaces sans pour autant garantir l’optimalité, et souvent ces heuristiques nécessitent une adaptation dès qu’une restriction est ajoutée au problème. Les métaheuristiques offrent une alternative permettant de gommer certaines limites des heuristiques, puisqu’elles ont l’avantage d’être génériques, et de permettre de visiter un espace large de solutions faisables en alternant les processus d’exploration (diversification) et d’exploitation (intensification). Les métaheuristiques peuvent être utilisées pour tout problème d’optimisation, il est néanmoins difficile de garantir l’efficacité des résultats. La notion d’efficacité ici renvoie généralement à deux métriques : la rapidité d’exécution et la qualité des solutions trouvées. La rapidité d’exécution se réfère au temps de calcul, alors que la qualité se penche sur le gap entre la meilleure solution trouvée et l’optimum réel. Naturellement, si la majeure partie du temps de recherche est utilisée dans des régions faisables ne contenant pas à minima de bonnes solutions, la qualité de la métaheuristique ne peut être que mauvaise. L’expertise et l’intuition sont alors nécessaires pour intégrer dans la phase de recherche des règles pour guider les métahueristiques dans les régions les plus prometteuses. Les techniques d’apprentissage (machine learning – ML) peuvent remédier à la conception de règles, en les intégrant dans le processus de recherche permettant de découvrir de nouvelles règles et globalement d’accélérer le processus de recherche de régions faisables prometteuses. Ainsi l’apprentissage automatique a un double objectif. Le premier, vise à remplacer certains calculs dans les métaheuristiques par une approximation rapide, où l’apprentissage peut être utilisé pour construire de telles approximations comme par exemple l’estimation de la qualité d’une solution d’une manière générique, sans qu’il soit nécessaire de construire de nouveaux algorithmes explicites ou de recourir aux algorithmes explicites des métaheuristiques qui sont gourmands en temps de calcul. Le second objectif vise à explorer l’espace de recherche et d’apprendre de cette exploration le comportement le plus performant. L’intégration de l’apprentissage automatique dans la résolution des problèmes d’optimisation est très récente et les recherches dans ce domaine n’ont pas encore abouti à des résultats spectaculaires, néanmoins les premières études sont très prometteuses.

Dans ce sujet de thèse, on s’intéresse à l’association des métaheuristiques avec l’apprentissage par renforcement [1] [2] [6] (Reinforcement learning – RL) permettant d’orienter les décisions dans l’espace de recherche. Des résultats récents montrent l’intérêt de l’hybridation des métaheuristiques et RL pour résoudre des problèmes combinatoires comme les problèmes de tournées [3] [4] ou d’ordonnancement [5]. L’association ML-Optimisation a pour but de remplacer certains calculs dans les métaheuristiques par une approximation rapide, et vise à explorer l’espace de recherche et d’apprendre de cette exploration le comportement le plus performant. Dans le cas de recherche d’une approximation rapide, l’utilisation de ML permet d’exclure rapidement des solutions non prometteuses, alors que dans le cas de recherche de nouvelles règles de décision l’apprentissage par renforcement est adapté puisque dans l’apprentissage d’une politique où l’agent maximise le rendement, faire correspondre le signal de récompense avec l’objectif de l’optimisation permet à l’agent d’explorer des régions faisables prometteuses.

Le but de cette thèse est de construire un schéma hybride qui s’inscrit dans cette idée de coopération entre metaheuristique et ML/RL. Il s’agit ici de développer des modèles de ML/RL capables d’apprendre à partir des données des problèmes les meilleures stratégies de recherche de régions prometteuses (exploration) et les algorithmes d’optimisation se focalisent sur la partie de recherche de la meilleure solution de cette région faisable (exploitation). Le développement d’un schéma hybride se focalisera dans un premier temps sur les problèmes d’optimisation en lien avec les applications de tournées de véhicules.

 

Références

[1] Sutton, Richard S., and Andrew G. Barto. Reinforcement learning: An introduction. MIT press, 2018.

[2] Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial

optimization with reinforcement learning. arXiv preprint arXiv:1611.09940, 2016.

[3] Mohammadreza Nazari, Afshin Oroojlooy, Lawrence V. Snyder, Martin Takáč. Reinforcement Learning for Solving the Vehicle Routing Problem. arXiv:1802.04240, 2018.

[4] Peng B , Zhang Y, Lü Z, Cheng T.C.E, Glover F, A learning-based memetic algorithm for the multiple vehicle pickup and delivery problem with LIFO loading, Computer and Industrial Engineering, 2020

[5] Chen R, Yang B, Li S, Wang S. A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem, Computer and Industrial Engineering, 2020

[6] Seyyedabbasi, A. (2023). A reinforcement learning-based metaheuristic algorithm for solving global optimization problems. Advances in Engineering Software, 178, 103411.