IA COGNITO – EP09 – La Recherche Opérationnelle

Quatrième et dernier épisode de notre série s’intéressant aux domaines d’application de l’IA. Au menu du jour, nous retrouvons la fameuse Recherche Opérationnelle.

A première vue, ce terme ne vous dit peut être pas grand chose mais nous pouvons vous assurer – sans l’ombre d’un doute – que vous utilisez très régulièrement des applications basées sur la Recherche Opérationnelle (RO pour les intimes).

Définition du domaine

Pour entrer dans le vif du sujet, quoi de mieux qu’une définition ?

Concrètement, la RO vient associer les mathématiques – notamment les probabilités et la logique – à la modélisation de processus plus ou moins complexes.

La Recherche Opérationnelle regroupe une grande variété de techniques algorithmiques visant à rechercher le meilleur choix lors d’une prise de décision. Plutôt intéressant dit comme cela !

Appliquée, la Recherche Opérationnelle se mue en véritable aide à la décision – il est d’ailleurs courant de l’appeler ainsi – et en un atout essentiel, que ce soit dans le secteur public comme privé. Ce domaine d’application trouve de nombreux débouchés relatifs à l’ingénierie des systèmes et au système d’information. Mais pas que, et nous le verrons un peu plus loin.

Pour retrouver les origines de ce domaine, il faut remonter quelques siècles en arrière, jusqu’au 17eme. Oui ça fait loin ! Si elle n’est pas vieille comme le monde, la Recherche Opérationnelle est donc un domaine de recherche existant depuis plusieurs siècles. Tour à tour, plusieurs éminents scientifiques se sont penchés dessus. Nous pouvons citer Blaise Pascal – cocorico – qui s’est intéressé à la résolution de problèmes de décisions grâce à l’espérance mathématique. Mais la Recherche Opérationnelle telle que nous la connaissons serait plutôt née au début du siècle dernier, en 1913 grâce à Harris et Wilson, et leur formule éponyme – ou formule du lot économique, ou même Quantité Économique de Commande. Ceux-ci étudièrent la gestion des stocks et des commandes. Le but était de déterminer le volume de commande optimal en prenant en compte plusieurs variables telles que le niveau de demande d’un produit, le coût associé à la commande et le coût de stockage.

Toutefois, si ces travaux marquent la naissance de la discipline, elle ne prendra une véritable ampleur qu’avec la Seconde Guerre Mondiale et la création d’une équipe de Recherche Opérationnelle par le Royaume-Uni, dirigée par un certain Patrick Blackett. La première application est donc militaire et cherche à déterminer l’implantation idéale de radars notamment.

Après guerre, la Recherche Opérationnelle va connaître un boom, comme de nombreuses autres disciplines grâce aux nouveaux ordinateurs disposant de puissances de calcul décuplées.

Grandes familles d’applications

Pour faire simple, le domaine de la Recherche Opérationnelle se divise assez aisément en trois grandes catégories d’applications portant sur la nature même des problèmes qu’elle vise à résoudre. A savoir, des problèmes dits aléatoires, combinatoires ou concurrentiels.

Si vous le voulez bien, commençons par les problèmes aléatoires.

Problèmes aléatoires :

Comme son nom l’indique si bien, un problème aléatoire comprend une dimension incertaine. Pour mieux comprendre, illustrons cela avec un problème aléatoire bien concret auquel nous avons tous fait face. Combien faut-il ouvrir de caisses dans un supermarché pour ne pas attendre plus de 20 minutes ? Ce problème compte plusieurs incertitudes dont deux variables déterminantes : le nombre de clients entrant dans le magasin et la quantité de produits que chacun d’eux achète.

Face à la complexité de ce problème, il est assez aisé de comprendre pourquoi il est intéressant d’avoir recours à des méthodes mathématiques pour pouvoir le résoudre. En modélisant ces phénomènes aléatoires par des distributions de probabilité, on peut essayer de prendre la décision la plus juste.

Problèmes combinatoires :

Contrairement aux problèmes aléatoires, les variables sont mieux maîtrisées et connues dans un problème combinatoire. Mais cela ne le rend pas forcément plus simple à résoudre.

Un problème combinatoire se caractérise par la grande quantité de solutions possibles. L’idée étant de choisir la solution la plus optimale. Prenons un exemple bien connu à Neovision, l’optimisation de tournées. Comment affecter le bon conducteur au bon secteur et comment concevoir la meilleure tournée possible en connaissant tous les points de passage dans le but de limiter le kilométrage. En couplant la difficulté de conception de la tournée et la bonne affectation des conducteurs, nous pouvons énumérer des millions de solutions. Nous nous retrouvons ainsi face à une explosion combinatoire.

Ce type de problème ne peut pas être résolu par un humain, qui ne pourra choisir qu’une solution lui semblant optimale sans pouvoir en être sûr. D’où le recours à la Recherche Opérationnelle.

Problèmes combinatoires :

Enfin, dernier type de problème qu’il est possible de résoudre grâce à la Recherche Opérationnelle, les problèmes dits concurrentiels. Ici, nous retrouvons des caractéristiques propres aux problèmes aléatoires et combinatoires.
Comme son nom l’indique, un problème concurrentiel consiste à trouver un optimum dans un contexte où ses propres décisions sont également liées à celles d’autres décideurs. Les variables sont interdépendantes et vont s’influencer mutuellement. Il existe à la fois une vraie incertitude concernant celles provenant des autres acteurs et un grand nombre de solutions potentielles.

L’exemple le plus parlant est celui des actions promotionnelles. Il existe tout un tas de décisions possibles : -10 ou -20%, un gratuit pour l’achat de 2, le second à moitié remboursé… En plus de cette multitude d’actions possibles, il faut également prendre en compte les actions promotionnelles de vos concurrents, qui auront un impact direct sur les résultats de vos choix.

Nous voyons donc que lorsqu’il est question de Recherche Opérationnelle, nous pouvons opter pour différentes approches. Un choix qui n’en est pas vraiment un puisque la nature du problème, ses caractéristiques, contraintes et autres variables définiront l’approche la plus pertinente.

Quel type de données et méthode algorithmique visée ?

Effectivement, il n’existe pas de méthode définie pour résoudre un problème de recherche opérationnel parce que – comme présenté précédemment – les problèmes en question peuvent être très variés. La méthode choisie est dépendante de la situation dans laquelle on se trouve et, même pour un problème donné, il va évidemment exister de nombreuses façons différentes de le résoudre.

Néanmoins tout n’est pas perdu : une première étape fondamentale de tout problème de RO est de réussir à modéliser le problème pour le ramener sous une forme abstraite que l’on sait résoudre. Prenons l’exemple discuté plus tôt de l’optimisation de tournée. Il peut se réduire à ce qu’on appelle le problème du voyageur de commerce. Ce problème mathématique bien connu consiste à trouver le chemin le plus court passant par un ensemble de villes définies.

Une fois que l’on est capable de ramener notre problème à un autre plus général de cette façon, on peut alors chercher à le modéliser, c’est-à-dire à le traduire sous une forme mathématique simple qui permettra de le résoudre. Dans le cas du voyageur de commerce, on peut classiquement représenter le problème sous la forme d’un graphe mathématique. C’est-à-dire qu’on fait une abstraction du problème pour ne le représenter plus que comme un ensemble de noeuds (les villes) connectés par des arêtes (les liens entre les villes), ces arêtes étant plus ou moins “chères” (la distance entre les villes). Une fois cette abstraction réalisée, il est plus simple de trouver une solution.

De manière plus générale, c’est la modélisation mathématique qui va déterminer la méthode que l’on utilise. Nous allons en citer quelques-unes ici pour donner un aperçu du domaine sans viser l’exhaustivité.

Une méthode régulièrement utilisée en RO est la programmation linéaire. Contrairement à ce que peut laisser penser son nom, il s’agit avant tout d’une méthode mathématique souvent utilisée pour trouver la solution d’un problème combinatoire. C’est-à-dire que l’on va chercher à trouver une combinaison de valeurs permettant, par exemple, de minimiser une fonction de coût. Un algorithme connu du domaine pour résoudre ce problème est celui du Simplex. Le problème devient plus complexe lorsque les valeurs que l’on cherche à trouver sont, au moins en partie, des nombres entiers.

Et puisque nous parlions un peu plus tôt de graphes, de nombreux algorithmes spécifiques ont été développés pour ce genre de modélisation. Une branche des mathématiques, la théorie des graphes, s’intéresse en effet à la résolution de problématiques liés à des graphes. Il s’agit notamment du genre de modélisation utilisée pour résoudre automatiquement un certain nombre de jeux tels que les échecs ou le go.

Si le problème est plus complexe et qu’il ne peut être modélisé sous cette forme mathématique, on va alors s’orienter vers des méthodes qui recherchent une approximation. C’est-à-dire qu’on n’est pas sûr de trouver le résultat optimal mais qu’on va chercher à en donner une approximation la plus proche possible. Ceci est par exemple le cas pour les problèmes que l’on dit NP-complet. Pour résumer grossièrement, ce que signifie ce terme c’est qu’il s’agit de problèmes dont il est rapide de vérifier la faisabilité d’une solution mais presque impossible d’énumérer l’ensemble des solutions possibles. Pour ce genre de problèmes, on va utiliser ce qu’on appelle des méta-heuristiques.

Ce terme un peu barbare décrit des méthodes générales qui vont spécifier une procédure de recherche itérative permettant de s’approcher petit à petit d’une solution. Elles sont basées sur des processus aléatoires pour trouver de nouvelles solutions et sont souvent inspirées de processus naturels. Par exemple, l’algorithme du recuit simulé tire son inspiration de la physique, les algorithmes évolutionnaires s’inspirent de l’évolution naturelle et l’algorithme de la colonie de fourmis du comportement de ces insectes.

C’est donc la modélisation du problème qui est capitale en RO et par conséquent, l’apport des données est très différent lorsqu’on compare à d’autres domaines applicatifs de l’IA présentés dans les épisodes précédents. Dans le cadre de la RO, ce qui est important c’est de connaître les problématiques métiers afin de fournir une modélisation la plus précise possible. Dans certains cas, il peut être nécessaire de créer une simulation informatique du problème avant d’être capable de le résoudre. C’est notamment le cas pour un certain nombre d’utilisation d’apprentissage par renforcement.

Pour ce genre de problèmes complexes où une résolution purement mathématique n’est pas possible, on utilise aussi parfois de l’apprentissage par renforcement. Ce type d’apprentissage automatique est très différent dans son fonctionnement des apprentissages supervisés et non-supervisés. Nous en avons déjà parlé dans les premiers épisodes et un épisode plus conséquent y sera consacré mais, pour résumer rapidement, le modèle apprend par la distribution de récompenses en fonction d’actions prises au cours du temps. Le but d’un algorithme d’apprentissage par renforcement est d’optimiser la séquence d’actions prises pour maximiser la récompense et ainsi résoudre le problème.

Bon, toute cette théorie, c’est bien, cela nous aide à mieux comprendre comment fonctionne la RO, mais comment est-elle réellement appliquée dans les entreprises ? D’ailleurs, l’est-elle vraiment ?

Applications concrètes et en production

La recherche opérationnelle est utilisée dans les entreprises à différents niveaux. À un niveau stratégique, elle permet de venir en aide sur des prises de décision, qui peuvent aussi bien concerner des investissements que des changements structurels. Et, sur un niveau plus opérationnel, elle intervient sur certains processus complexes.

Quand on va faire un tour du côté de la logistique et des transports, le premier cas d’usage qui apparaît est l’optimisation des tournées. Fini les kilomètres inutiles et bonjour les économies de temps, d’argent, mais également d’énergie ! Et à la clé, un pas de plus vers la réduction de notre impact sur l’environnement.

Mais cela ne s’arrête pas là. La recherche opérationnelle peut également améliorer le conditionnement des colis. En effet, combien de fois avez-vous déjà reçu un tout petit article dans un colis de taille disproportionnée ? Ici, il s’agit donc de venir identifier quel sera le meilleur empaquetage en fonction de la commande passée par le client.

Du côté des chaînes de production industrielles, la recherche opérationnelle optimise les plans de production, en donnant notamment un petit coup de pouce à la gestion des stocks en s’adaptant aux contraintes logistiques spécifiques par exemple. Elle peut aussi assurer entre autres l’optimisation des plans de découpe. De quoi faire, là encore, des économies en évitant le gaspillage des matières premières.

Assistant pour l'optimisation de l'empaquetage

Côté finance, la recherche opérationnelle résout des problématiques relatives aux investissements. Vous l’aurez deviné, ici on cherche avant tout à maximiser le profit de l’investisseur en combinant au mieux les différentes opportunités qui lui sont offertes.

En matière de santé, la recherche opérationnelle permet, par exemple, de proposer de nouvelles molécules candidates. Mais nous y reviendrons dans la dernière partie de notre podcast.

Une fois n’est pas coutume, on finit par vous parler d’énergie. La recherche opérationnelle permet aussi bien de résoudre des problématiques stratégiques d’investissements sur le réseau que des questions plus opérationnelles. Elle intervient ainsi sur des questions de gestion de l’énergie, notamment pour assurer la stabilité du réseau.

Dernières avancées scientifiques

Dans le cadre d’un domaine aussi large et aux méthodes si diverses, il peut être difficile d’en lister efficacement les dernières avancées. Nous faisons alors le choix, pour terminer cet épisode, de nous concentrer sur les dernières applications de l’apprentissage par renforcement au domaine de la RO. Ceci nous évite de nous disperser dans des disciplines très différentes qui nécessiteraient un épisode à elles seules et se concentrer notamment sur les apports du deep learning à ce domaine.

Car, en effet, le deep learning a aussi trouvé des applications en apprentissage par renforcement. Ceci a par exemple rendu possible le développement par la société DeepMind d’AlphaZero, un modèle d’IA capable de jouer au Go, Shogi et aux échecs et, surtout, battre les meilleurs humains à ce jeu. AlphaZero est notamment basé sur AlphaGo, qui était devenu célèbre après avoir battu le meilleur joueur mondial de Go, une performance qui, pendant longtemps, était considérée comme inatteignable pour une machine.

Par rapport au sujet qui nous intéresse aujourd’hui, la résolution de jeux tels que les échecs ou le Go est un problème classique de recherche opérationnelle. Il s’agit en effet de prendre des décisions complexes en choisissant parmi un ensemble de combinaisons aux répercussions profondes.

Plus récemment DeepMind s’est attaqué à un autre problème de RO avec son modèle AlphaFold : celui du repliement des protéines. Le but de ce problème combinatoire est de trouver, à partir d’une séquence de nucléotides de l’ADN, la forme de la protéine qui sera synthétisée. Ceci a une grande importance scientifique car c’est la forme 3D d’une protéine qui détermine sa fonction. Être capable de déterminer cette forme juste à partir des nucléotides représente alors un problème scientifique difficile et aux implications importantes. Plus récemment en Juillet 2021, avec des techniques différentes mais dans le même domaine, a été publié RoseTTAFold par Baek et collègues. Ce réseau dépasse de nouveau l’état de l’art dans le problème de repliement des protéines.

Il est à penser que les avancées du Deep Learning auront de plus en plus d’applications dans des problèmes de RO à la combinatoire jugée jusqu’ici trop grande pour être efficacement traité par des machines.

Nous voici arrivés au terme de cet épisode, qui marque également la fin de notre saga sur les domaines applicatifs de l’IA : computer vision, Nlp, Analyse prédictive et donc Recherche opérationnelle. Pour la suite, nous chercherons à nous rapprocher de l’usage et des bénéfices concrets qu’apporte l’Intelligence Artificielle dans différents secteurs d’activité. Et comme nous aimons savoir de quoi nous parlons sur IACOGNITO, nous nous concentrerons sur des marchés que nous maîtrisons, à savoir, la Santé, l’Industrie, l’Energie et l’Environnement. Au programme, nous vous ferons des retours d’expériences tout en vous présentant les dernières technologies déployées au niveau mondial.

Sur ce petit au revoir, nous vous remercions pour votre fidélité et on vous dit à très bientôt sur IACOGNITO.

Sources :

  • https://educnet.enpc.fr/file.php/297/CoursROPonts.pdf
  • https://fr.wikipedia.org/wiki/Recherche_op%C3%A9rationnelle
  • https://www.universalis.fr/encyclopedie/recherche-operationnelle/4-strategies-en-situation-de-concurrence/
  • https://www.roadef.org/pdf/LIVRE_BLANC_A5_juin.pdf
  • https://fr.wikipedia.org/wiki/Recherche_op%C3%A9rationnelle
Mathieu Poissard
No Comments

Post a Comment

Neovision © 2022