Objectif

L'objectif est de fournir des approches où les problèmes d'optimisation combinatoire sont résolus à l'aide de métaheuristiques et de techniques d'apprentissage automatique (soit en combinant métaheuristiques et 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 fabrication, etc. qui se posent dans de nombreux secteurs, tels que la logistique, l'industrie, l'énergie, la mobilité, les télécommunications et la santé. D'une manière générale, un problème d'optimisation consiste à trouver une combinaison de variables de décision qui est :

1. Optimal en fonction d'une certaine mesure des coûts
2. Faisable, dans le sens où il satisfait un nombre donné de contraintes.

Le nombre de combinaisons possibles qui peuvent former une solution rend les approches par force brute très peu pratiques, c'est pourquoi beaucoup d'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 en un temps relativement court. Ces méthodes vont des méthodes de construction et d'amélioration spécifiques à un problème aux algorithmes indépendants du problème qui ne requièrent que des composants spécifiques afin d'être appliqués à un scénario donné (qui sont appelés métaheuristique).

Le Machine learning (ML) est un domaine consacré à la résolution d'une large 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 apprendre d'abord un modèle et proposer ensuite une solution, au lieu d'un algorithme classique qui travaille sur un modèle défini par l'utilisateur.

Conceptuellement, les heuristiques et les méthodes ML proposent une approche similaire pour construire des solutions aux problèmes d'optimisation : à partir d'expériences tirées de situations réelles, on tente de concevoir une méthode de résolution où des raccourcis sont exploités pour accélérer l'identification d'une solution approximative assez rapidement avec une optimalité suffisante. La principale différence consiste à savoir si le modèle sous-jacent est développé manuellement ou dérivé automatiquement des données, c'est pourquoi 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 à la combinaison de ces approches en des approches hybrides pour accélérer les procédures de recherche.

Il est crucial, pour le bon fonctionnement de ces secteurs, d'être en mesure de fournir des solutions de haute qualité aux problèmes difficiles rencontrés dans les secteurs de la logistique, de l'industrie, de l'énergie, de la mobilité, des télécommunications, des soins de santé et autres, et ce, de la manière la plus efficace possible. En particulier, la réalisation des objectifs de l'accord vert européen visant à être neutre en carbone en 2050 exige cette efficacité pour nombre de ces secteurs, compte tenu de ses exigences en matière d'émissions et du besoin évident de remplacer les pratiques existantes. Par conséquent, les techniques construites à partir d'heuristiques et de ML suggèrent une direction de recherche intéressante.

Défi(s)

La recherche sur les approches hybrides n'en est encore qu'à ses débuts, et l'une des principales raisons en est que les communautés de la RO et de la ML ne collaborent pas encore beaucoup. Les praticiens de la RO, tant dans le milieu universitaire que dans l'industrie, se concentrent principalement sur la définition précise de 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'accent sur les données, tant pour la formation que pour la validation. Pour cette raison, alors que la ML a été largement acceptée 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 les modèles ML sont proposés comme solutions à des situations plus générales, le manque d'explicabilité de certains modèles ML soulève souvent des questions de la part des utilisateurs du monde réel. La proposition d'approches hybrides pourrait aider à lever l'opacité et donner naissance à des solutions d'IA explicables.

Le premier défi non technique consiste à accroître le niveau de collaboration entre ces communautés. D'un point de vue technique, des solutions sont recherchées pour :

• Optimiser des problèmes complexes qui nécessitent de prendre simultanément différents types de décisions, comme le routage, l'ordonnancement et la localisation.
• Fournir des solutions explicables à des problèmes complexes.
• Optimisation des problèmes avec incertitude, en particulier lorsque peu de données réelles sont disponibles.

Solution envisageable pour l'IA(s)

(Parmi beaucoup d'autres à proposer par les chercheurs)

• Application de l'apprentissage supervisé ou par renforcement pour accélérer un composant d'une procédure métaheuristique.
• Exploitation du ML pour identifier l'heuristique la plus appropriée à utiliser comme stratégie de recherche pour un problème donné.

Thèmes clés de l'IA

• Machine Learning
• Supervised Learning
• Reinforcement Learning

Contactez-nous

• Stefano Michelini (stefano.michelini@cetic.be)
• Renaud De Landtsheer (renaud.delandtsheer@cetic.be)