Objectif
Le but est de fournir des approches où les problèmes d'optimisation combinatoire sont résolus en utilisant des techniques de métaheuristiques et d'apprentissage automatique (soit en combinant les métaheuristiques et l'apprentissage automatique pour résoudre le même problème, soit en les utilisant dans un flux de travail où chacun résout différentes parties d'un problème plus vaste).
Les enjeux
La Recherche Opérationnelle (RO) est un domaine d'étude qui s'intéresse aux problèmes d'optimisation liés à la planification d'itinéraires, l'ordonnancement, la gestion de la chaîne d'approvisionnement, la production, etc., survenant dans de nombreux secteurs tels que la logistique, l'industrie, l'énergie, la mobilité, les télécommunications et la santé. De manière générale, un problème d'optimisation consiste à trouver une combinaison de variables de décision qui soit :
- Optimale selon une certaine mesure de coût
- Réalisable, dans le sens où elle satisfait un certain nombre de contraintes.
Le très grand nombre de combinaisons possibles pouvant former une solution rend les approches par force brute totalement irréalisables, c'est pourquoi de nombreux efforts ont été consacrés au développement de méthodologies efficaces au cours des dernières décennies. Outre les méthodes exactes, qui visent à obtenir la solution optimale d'un problème donné, des approches heuristiques ont été proposées pour trouver des solutions de qualité suffisante pour une situation donnée dans un délai relativement court. Ces méthodes vont des méthodes de construction et d'amélioration spécifiques à un problème à des algorithmes indépendants du problème qui ne nécessitent que des composants spécifiques pour être appliqués à un scénario donné (appelés métaheuristiques).
L'apprentissage automatique (Machine Learning ou ML) est un domaine consacré à la résolution d'une vaste classe de problèmes qui sont non seulement difficiles à résoudre mais aussi à définir explicitement (vision par ordinateur, reconnaissance vocale, systèmes de recommandation, etc.) en développant des méthodes qui s'appuient sur des données existantes pour d'abord apprendre un modèle et ensuite proposer une solution, au lieu d'un algorithme classique qui fonctionne sur un modèle défini par l'utilisateur.
Conceptuellement, les méthodes heuristiques et de ML proposent une approche similaire pour construire des solutions aux problèmes d'optimisation : à partir d'expériences de situations du monde réel, on tente de concevoir une méthode de résolution exploitant des raccourcis pour identifier plus vite une solution approximative, avec un degré d'optimalité suffisant. La principale différence réside dans le fait que le modèle sous-jacent est développé manuellement ou dérivé automatiquement des données ; par conséquent, les méthodes de résolution se limitent généralement à l'une de ces deux approches. Récemment, cependant, les chercheurs se sont intéressés au mélange de ces approches en des approches hybrides pour accélérer les procédures de recherche.
Être capable de fournir des solutions de haute qualité pour les problèmes complexes rencontrés dans la logistique, l'industrie, l'énergie, la mobilité, les télécommunications, la santé et d'autres secteurs, de la manière la plus efficace possible, est crucial pour le bon fonctionnement de ces secteurs. En particulier, l'atteinte des objectifs du Pacte Vert pour l'Europe visant la neutralité carbone en 2050 exige cette efficacité pour beaucoup de ces secteurs, étant donné ses exigences en matière d'émissions et le besoin manifeste de remplacer les pratiques existantes. Par conséquent, les techniques basées sur les heuristiques et le ML suggèrent une direction de recherche intéressante.
Défi(s)
La recherche sur les approches hybrides n'en est qu'à ses débuts, et l'une des raisons majeures est que les communautés de la RO et du ML ne collaborent pas encore de manière intensive. L'un des principaux objectifs des praticiens de la RO, tant dans le monde universitaire que dans l'industrie, est de définir avec précision des modèles pour un problème donné avant de développer une méthode de résolution heuristique ou d'adapter une métaheuristique au problème. D'un autre côté, l'application des méthodologies de ML nécessite de déplacer considérablement l'attention sur les données, tant pour l'entraînement que pour la validation. Pour cette raison, bien que le ML soit largement accepté pour résoudre des problèmes très spécifiques qui sont difficiles à modéliser mais pour lesquels il est facile de fournir de grandes quantités de données, lorsque des modèles de ML sont proposés comme solutions à des situations plus générales, le manque d'explicabilité de certains modèles de ML soulève souvent des questions de la part des utilisateurs du monde réel. Proposer des approches hybrides pourrait aider à lever cette opacité, aboutissant à des solutions d'IA explicable.
Le premier défi non technique est d'accroître le niveau de collaboration entre ces communautés. D'un point de vue technique, des solutions sont recherchées pour :
- Optimiser les problèmes complexes qui nécessitent de prendre simultanément différents types de décisions, comme la définition d'itinéraires, l'ordonnancement et la localisation.
- Fournir des solutions explicables à des problèmes complexes.
- Optimiser les problèmes comportant de l'incertitude, en particulier lorsque peu de données du monde réel sont disponibles.
Pistes de solutions IA
(Parmi de nombreuses autres à proposer par les chercheurs)
- Appliquer l'apprentissage supervisé ou par renforcement pour accélérer un composant d'une procédure métaheuristique.
- Exploiter le ML pour identifier l'heuristique la plus appropriée à utiliser comme stratégie de recherche pour un problème donné.
Thèmes technologiques clés de l'IA
- Apprentissage automatique (Machine Learning)
- Apprentissage supervisé
- Apprentissage par renforcement
Contact
- Stefano Michelini (stefano.michelini@cetic.be)
- Renaud De Landtsheer (renaud.delandtsheer@cetic.be)