Optimisation des chaînes de production dans l’industrie sidérurgique

Problématique industrielle

   Le processus de fabrication de l’acier (du minerai brut à la livraison chez le client) implique de nombreuses étapes de production effectuées dans plusieurs usines. Tout au long de ce processus, de nombreuses contraintes hétérogènes doivent être prises en compte. Il y a tout d’abord les contraintes physiques et métallurgiques imposées tout le long du processus, qui elles-mêmes peuvent être très hétérogènes (pression de laminage, températures de recuit, planéité des tôles, et caetera). Il y a également de nombreuses contraintes logistiques (transport des produits entre usines, conséquences d’une panne ou d’un retard dans une usine, modification du carnet de commande, et caetera). Enfin il y a un certain nombre de contraintes environnementales telles que la minimisation de consommation d’énergie ou de production des déchets. Pour optimiser ce processus de production dans son ensemble, ces différentes contraintes doivent être considérées simultanément, plusieurs optimisations locales n’entraînant pas nécessairement une optimisation globale. De plus, les différents éléments à optimiser sont très hétéroclites, ce qui suggère l’utilisation d’un modèle le plus générique possible. Il faut également considérer le fait que si certains processus sont bien compris et par conséquent modélisables, d’autres ne peuvent être contrôlés que par des heuristiques (par des machines ou le savoir-faire humain). En fait, il est possible de contrôler certaines machines (de façon automatique), mais pour d’autres il n’y a pas d’alternative à l’expertise humaine. Dans ce contexte et sur le long terme, le projet PROFL-213 d’ArcelorMittal Research dans lequel s’inscrivent ces travaux a pour objectifs de :
– développer une méthodologie générale de façon à modéliser aussi globalement et génériquement que possible un large problème d’optimisation, malgré la malédiction de la dimensionnalité;
– développer des algorithmes qui permettent de trouver une solution au problème (optimale, voire sous-optimale mais de bonne qualité) ;
– utiliser ces algorithmes hors-ligne pour améliorer les routes métallurgiques respectivement aux contraintes mentionnées précédemment et en-ligne pour améliorer la réaction du processus dans le cas d’événements non prévus à l’origine. Il faut également noter que les problèmes d’optimisation envisagés peuvent être dynamiques, dans le sens où une décision à un moment donné doit être prise en tenant compte de l’évolution future du système et pas seulement en fonction de son état actuel.

Formalisme

   Avant de traiter les algorithmes de résolution de la programmation dynamique, le formalisme doit d’abord être posé. Nous introduisons les notions de processus décisionnel de Markov (modélisation de l’environnement à contrôler), de fonction de valeur (quantification de la qualité du contrôle), de politique (le contrôle lui même), ainsi que les équations de Bellman (caractérisation de la fonction de valeur d’une politique donnée et de la politique optimale) dont la résolution est l’une des composantes des algorithmes de programmation dynamique.

Processus décisionnel de Markov

   Le formalisme associé à la programmation dynamique (mais aussi très largement à l’apprentissage par renforcement) est celui des processus décisionnels de Markov [8, 55, 90, 11] (MDP pour Markov Decision Processes). Ils permettent de modéliser l’environnement illustré sur la figure 1.1. Nous en donnons une définition.
Définition 2.1 (Processus décisionnel de Markov). Un MDP est la donnée des éléments suivants :
– S l’espace des états (fini) ;
– A l’espace des actions (fini) ;
– P : s, a ∈ S × A → p(.|s, a) ∈ P(S) une famille de probabilités de transitions markoviennes ;
– R : s, a, s0 ∈ S × A × S → r ∈ R une fonction de récompense bornée ;
– γ ∈ [0, 1[ un facteur d’actualisation.
Un processus décisionnel de Markov est donc composé d’un espace d’état, qui décrit l’ensemble des configurations possibles du système dynamique ; d’un espace d’action, qui décrit l’ensemble des actions qui peuvent être appliquées à ce système ; d’une famille de probabilités de transitions markoviennes, qui décrit la dynamique du système ; d’une fonction de récompense, qui est une information locale et immédiate de la qualité du contrôle ; d’un facteur d’actualisation, qui participe à la définition de la fonction de valeur et qui rend compte en quelque sorte de l’horizon sur lequel on souhaite maximiser le cumul de récompenses. Nous dirons de façon générale que le modèle est connu si les probabilités de transitions et la fonction de récompense le sont. Nous insistons sur le caractère markovien des probabilités de transitions : la probabilité de passer dans un nouvel état s 0 ne dépend que de l’état courant s et de l’action a choisie et en aucun cas du chemin parcouru pour atteindre l’état courant. Plus formellement, pour une trajectoire s1, . . . , si+1 au cours de laquelle les actions a1, . . . , ai ont été prises, nous avons : p(si+1|si, ai, si−1, ai−1, . . . , s1, a1) = p(si+1|si, ai)

Position de l’apprentissage par renforcement par rapport à la programmation dynamique

   Pour les méthodes d’apprentissage par renforcement que nous considérons ici, le formalisme est le même que pour la programmation dynamique. L’environnement à contrôler est toujours modélisé par un processus décisionnel markovien et l’objectif est encore de déterminer la politique optimale, c’est-à-dire celle dont la fonction de valeur est maximale pour chaque état du système. Cependant, par rapport à la programmation dynamique, un certain nombre de contraintes sont levées. Premièrement, le modèle (c’est-à-dire, nous le rappelons, les probabilités de transitions et la fonction de récompense) n’est plus supposé connu a priori. Nous supposerons toutefois les espaces d’état et d’action connus. Il y a donc une composante d’apprentissage qui entre en compte, dans la mesure où l’on va chercher à apprendre le contrôle optimal à partir d’interactions avec l’environnement ; cela devient plus qu’un problème d’optimisation. De plus, une caractéristique souhaitée de cet apprentissage est qu’il se fasse en ligne, c’est-à-dire que la fonction de valeur (et/ou la politique) soit mise à jour après chaque interaction avec l’environnement et ce sans utiliser tout l’historique des interactions. Il est également probable que cette mise à jour soit locale et ne concerne pas tous les états, elle est donc asynchrone. L’apprentissage par renforcement (tel que nous le traitons ici) peut donc être vu comme une version en ligne, asynchrone et sans connaissance a priori du modèle de la programmation dynamique. Quand le modèle n’est pas connu, une première approche pourrait être de l’apprendre à partir d’interactions avec le système (|S|2|A| paramètres pour la fonction de récompense et autant pour le modèle de transition) pour lui appliquer les algorithmes classiques de programmation dynamique. Le problème de cette approche est qu’elle n’est pas en ligne et surtout qu’elle passe mal à l’échelle. Une autre approche pourrait être d’estimer la valeur des différents états à l’aide d’une méthode de Monte Carlo. Plus précisément, le principe serait de simuler un grand nombre de trajectoires partant d’un état s ∈ S donné et de moyenner les cumuls de récompenses observées pour chaque trajectoire. On pourrait alors remplacer l’évaluation de la politique (faite par résolution du système linéaire correspondant si le modèle est connu) par ce type d’approche dans l’algorithme d’itération de la politique (la phase d’amélioration de la politique nécessitant cependant également de recourir à Monte Carlo, le modèle n’étant pas connu), ce qui pourrait permettre d’aboutir à la politique optimale. Là encore le caractère en ligne est perdu, un simulateur serait nécessaire et de plus les estimateurs de Monte Carlo présentent généralement une forte variance, sans compter qu’un tel apprentissage serait lent (simuler un grand nombre de trajectoires pour chaque état du système). Les méthodes de différences temporelles que nous présentons maintenant conservent quant à elles les caractéristiques désirées : apprentissage en ligne sans connaissance du modèle.

Algorithmes de différences temporelles

   Les algorithmes que nous présentons ici visent à apprendre la fonction de valeur (ou la Q-fonction, que nous présentons par la suite) en ligne à partir d’interactions avec l’environnement. Ils reposent sur une comparaison entre la récompense que l’on s’attend à observer, cette prédiction étant basée sur l’estimation courante de la fonction de valeur et la récompense effectivement observée. Les mises à jour associées sont du type Widrow-Hoff et font partie du domaine de l’estimation stochastique (qui n’est pas propre à l’apprentissage par renforcement). Nous présentons d’abord les algorithmes TD, SARSA et Q-learning, ainsi que leurs extensions aux traces d’éligibilité (qui permettent une mise à jour plus globale de la fonction de valeur, c’est-à-dire pas seulement de l’état courant mais de tous les états visités jusqu’à celui-ci). Dans ce contexte, nous introduisons la notion d’itération de la politique généralisée, ainsi que les architectures acteur-critique qui en sont un cas particulier important. Enfin, nous présentons les problèmes induits par l’imbrication de l’apprentissage et du contrôle, notamment le dilemme entre exploration et exploitation et la non-stationnarité de la fonction de valeur cible. Les algorithmes et résultats donnés se retrouvent dans des ouvrages qui font référence [98, 105, 12].

De l’importance de traquer la fonction de valeur cible

   Le dernier point que nous passons en revue concernant l’imbrication de l’apprentissage et du contrôle est assez peu abordé dans la littérature. Dans le cas général d’un schéma d’itération de la politique généralisée, nous avons vu que des phases d’évaluation et d’amélioration de la politique se succèdent. En conséquence, la fonction de valeur que va chercher à estimer l’algorithme de différences temporelles va évoluer au cours du temps, en même temps que la politique courante. Cela se traduit par un problème de non-stationnarité de la fonction de valeur cible de l’algorithme d’apprentissage, ce qui peut être un problème s’il la suppose stationnaire. Cela apparaît notamment dans le cadre des architectures acteurcritique, ou la politique définie par l’acteur change potentiellement après chaque action. Pour y remédier, il est proposé dans [13] d’utiliser deux échelles de temps. En pratique, des taux d’apprentissage différents sont choisis pour l’acteur et le critique, de façon à ce que le premier apparaisse comme stationnaire au second. Nous y reviendrons chapitre 7. Pour notre part, nous pensons qu’il est préférable de “traquer” la fonction de valeur plutôt que de chercher à converger vers cette dernière. Cela devrait permettre de s’affranchir de ce problème causé par l’imbrication du contrôle et de l’apprentissage. Cela devrait également permettre de prendre en compte des environnements non-stationnaires. De plus, même en cas de stationnarité de la cible et de l’environnement, il existe des raisons pour préférer une traque à une convergence, comme présenté par [106]. Nous pensons ce point important et avons orienté nos travaux dans cette optique, comme nous le montrons par la suite.

Formulation espace-d’état

   Une première étape dans la construction du cadre de travail que nous proposons est de reformuler l’approximation de la fonction valeur en adoptant un point de vue statistique, sous la forme d’un problème de filtrage. La quantité que l’on cherche à estimer est l’ensemble des paramètres décrivant la fonction de valeur. Comme nous souhaitons pouvoir disposer d’une information d’incertitude sur ces estimations, nous modélisons les paramètres comme des variables aléatoires. De plus, comme l’on souhaite que les algorithmes aient un caractère adaptatif, c’est-à-dire qu’ils traquent la solution plutôt que de converger vers elle, il est nécessaire de spécifier un modèle d’évolution pour le vecteur de paramètres. Sans autre connaissance a priori, nous suivons le principe du rasoir d’Occam et adoptons un modèle de marche aléatoire. Les paramètres forment donc le processus caché que l’on souhaite estimer. Pour ce faire, il faut pouvoir l’observer, même indirectement. Dans notre cas, il est observé via les récompenses obtenues lors de l’interaction entre l’agent et son environnement. Il faut également spécifier un modèle d’observation, liant les paramètres aux récompenses. Nous avons déjà mentionné dans le chapitre 2 que la différence des valeurs en deux états consécutifs d’une transition pouvait servir de prédiction de la récompense associée. C’est ce modèle d’observation que nous adoptons. Même si la fonction de récompense est déterministe, ce processus d’observation est aléatoire, d’une part car il ne fait pas intervenir les probabilités de transition (et l’équation de Bellman ne peut être formellement vérifiée), d’autre part parce que le choix de la paramétrisation ne permet pas nécessairement une représentation exacte de la fonction de valeur d’intérêt. Ainsi, le problème d’approximation de la fonction de valeur est reformulé en deux équations, l’une décrivant le processus d’évolution des paramètres et l’autre le processus d’observation liant ces derniers aux récompenses. Nous présentons maintenant tout cela plus formellement.

Analyse de convergence

   Dans cette section, nous montrons que l’estimateur de XKTD minimise un coût quadratique pondéré qui associe à chaque valeur une estimation par Monte Carlo du cumul pondéré de récompenses. Nous en proposons deux preuves. La première est la plus générale, elle ne fait d’hypothèse ni sur le bruit d’évolution, ni sur la linéarité de la paramétrisation. Par contre, elle repose sur une conjoncture que nous introduisons d’abord et qui postule que si deux modèles espace-d’état sont équivalents et que l’estimateur de l’un est l’estimateur du maximum a posteriori, alors l’estimateur de l’autre l’est également, relativement à son propre modèle espace-d’état. La seconde preuve que nous proposons fournit le même résultat, sans utiliser cette conjoncture, mais avec des hypothèses restrictives supplémentaires (linéarité de la paramétrisation, pas de bruit d’évolution). Toute l’analyse théorique de cette section est faite dans le cadre de l’évaluation de la fonction de valeur, l’extension à l’évaluation de la fonction de qualité étant évidente (pour les raisons déjà énoncées, nous ne considérons pas l’extension à l’optimisation directe de la Q-fonction).

Table des matières

1 Position du problème 
1.1 Problématique industrielle
1.2 Approche adoptée 
1.3 Contributions et publications
1.4 Vue d’ensemble du manuscrit
2 Etat de l’art 
2.1 Programmation dynamique
2.1.1 Formalisme
2.1.2 Résolution
2.2 Apprentissage par renforcement 
2.2.1 Position de l’apprentissage par renforcement par rapport à la programmation dynamique
2.2.2 Algorithmes de différences temporelles
2.2.3 Apprentissage et contrôle
2.3 Approximation de la fonction de valeur 
2.3.1 Problématique
2.3.2 Etat de l’art
2.3.3 Propriétés souhaitables d’un approximateur de fonction de valeur
3 Différences temporelles de Kalman 
3.1 Formulation espace-d’état 
3.2 Formulation générale de l’algorithme 
3.2.1 Coût minimisé
3.2.2 Gain optimal
3.2.3 Algorithme
3.3 Cas linéaire 
3.4 La transformation non-parfumée 
3.5 Spécialisations
3.5.1 KTD-V
3.5.2 KTD-SARSA
3.5.3 KTD-Q
3.5.4 Illustration des algorithmes
3.5.5 Complexité des algorithmes
3.6 Analyse de convergence 
3.7 Travaux similaires et discussion 
3.8 Expérimentations 
3.8.1 Chaîne de Boyan
3.8.2 Pendule inversé
3.8.3 Mountain car
4 Biais de l’estimateur et bruit coloré 
4.1 Stochasticité des transitions et biais 
4.2 Un modèle de bruit coloré
4.2.1 Modélisation du bruit
4.2.2 Prise en compte d’un bruit à moyenne mobile dans un filtre de Kalman
4.2.3 Algorithmes résultants
4.3 XKTD pondéré 
4.4 Analyse de convergence 
4.5 Expérimentations 
4.5.1 Chaîne de Boyan
4.5.2 Chaîne contrôlée
4.5.3 Mountain car stochastique
4.6 Bilan
5 Une extension aux traces d’éligibilité 
5.1 Motivation d’une extension aux traces d’éligibilité 
5.2 Principe et algorithme 
5.2.1 Une nouvelle classe de bruits
5.2.2 Intégration à Kalman
5.2.3 Lien avec KTD et XKTD
5.3 Analyse de convergence
5.4 Expérimentations 
5.4.1 Chaîne de Boyan
5.4.2 Chaîne contrôlée
5.4.3 Mountain-car stochastique
5.4.4 Un labyrinthe pathologique
5.5 Bilan 
6 Utilisation de l’incertitude 
6.1 Calcul de l’incertitude
6.2 Apprentissage actif 
6.3 Dilemme exploration/exploitation 
6.3.1 Politique -gloutonne
6.3.2 Politique -gloutonne informée
6.3.3 Politique Bayes-gloutonne .
6.3.4 Estimation d’intervalle de confiance
6.3.5 Bonus d’exploration
6.3.6 Politique de Thompson
6.3.7 Estimation myope de la valeur de l’information parfaite
6.4 Expérimentations
6.4.1 Simple labyrinthe
6.4.2 Pendule inversé et apprentissage actif
6.4.3 Bandits
6.5 Bilan 
7 Un algorithme acteur-critique 
7.1 Un algorithme introductif 
7.2 Un peu de théorie 
7.2.1 Gradient de la performance
7.2.2 Gradient et approximation de la valeur
7.2.3 Gradient naturel
7.3 Algorithmes  
7.3.1 TD-NAC
7.3.2 KNAC
7.4 Expérimentation 
7.5 Bilan
8 Gestion de flux de gaz 
8.1 Description du problème
8.2 Modélisation du problème 
8.2.1 Nœuds élémentaires
8.2.2 Modélisation du réseau
8.2.3 Modélisation conforme à l’apprentissage par renforcement
8.3 Application de KTD 
8.3.1 Un réseau particulier
8.3.2 Semi-automatisation de la paramétrisation
8.3.3 Résultats
8.3.4 Perspectives
9 Contributions et perspectives 
9.1 Résumé du travail présenté 
9.2 Perspectives

Télécharger le rapport complet