Résolution des problèmes d'optimisation combinatoire avec une stratégie de retour-arrière basée sur l'apprentissage par renforcement

Les problèmes d’optimisation combinatoire (Constraint Optimization Problems – COP) sont souvent difficiles à résoudre et le choix de la stratégie de recherche a une influence importante sur la performance du solveur. Pour de résoudre un problème d’optimisation combinatoire en explorant un arbre de recherche, il faut choisir une heuristique de choix de variable (qui définit l’ordre dans lequel les variables vont être instanciées), une heuristique de choix de valeur (qui spécifie l’ordre dans lequel les valeurs seront essayées), et une stratégie de retour-arrière (qui détermine vers quel noeud effectuer les retours-arrière lorsqu’une feuille de l’arbre est rencontrée). Pour les stratégies de retour-arrière, il y a celles dont les retours-arrière sont totalement déterministes (e.g. Depth-First Search – DFS) et d’autres qui s’appuient sur des mécanismes d’évaluation de noeuds plus dynamiques (e.g. Best-First Search). Certaines (e.g. Limited Discrepancy Search – LDS) peuvent être implémentées soit comme un algorithme itératif déterministe ou un évaluateur de noeud. Une stratégie est dite adaptative quand elle s’adapte dynamiquement à la structure du problème et identifie les zones de l’espace de recherche qui contiennent les “bonnes” solutions. Dans ce contexte, des stratégies de branchement adaptatives ont été proposées (e.g. Impact-Based Search – IBS) ainsi qu’une stratégie de retour-arrière adaptative (e.g. Adaptive Discrepancy Search – ADS), proposée pour les problèmes d’optimisation distribués. À notre connaissance, aucune stratégie adaptative qui utilise l’apprentissage par renforcement (Reinforcement Learning – RL) pour supporter son mécanisme d’apprentissage n’a été proposée dans la littérature. Nous pensons que les techniques de RL permettront un apprentissage plus efficace et qu’une stratégie de retour-arrière munie de ces techniques aura le potentiel de résoudre les problèmes d’optimisation combinatoire plus rapidement. Dans ce mémoire, nous proposons un algorithme (RLBS) qui “apprend” à faire des retours-arrière de manière efficace lors de l’exploration d’arbres non-binaires. Plus précisément, il s’agit une stratégie de retour-arrière qui se base sur l’apprentissage automatique pour améliorer la performance du solveur. En fait, nous utilisons l’apprentissage par renforcement pour identifier les zones de l’espace de recherche qui contiennent les bonnes solutions. Cette approche a été développée pour les problèmes d’optimisation combinatoire dont l’espace de recherche est encodé dans un arbre non-binaire. Comme les arbres sont non-binaires, on a l’occasion d’effectuer plusieurs retours-arrière vers chaque noeud durant l’exploration. Ceci permet d’apprendre quels noeuds mènent vers les meilleures récompenses en général (c’est-à-dire, vers les feuilles les plus intéressantes). Le branchement est effectué en utilisant une stratégie de choix de variable/valeur quelconque. Toutefois, quand un retour-arrière est nécessaire, la sélection du noeud cible s’appuie sur l’apprentissage par renforcement. RLBS est évalué sur cinq instances industrielles du problème de la planification des opérations du rabotage du bois et a été comparé à ADS et à LDS sur cette même application. RLBS dépasse LDS et ADS, en termes de temps de calcul nécessaire à la résolution, sur chacune de ces instances-là et trouve la solution optimale plus rapidement. Les expérimentations ont montré que RLBS est en moyenne 4 fois plus rapide que ADS, et 6 fois plus rapide que LDS. RLBS a aussi été évalué sur une instance jouet du même problème et a été comparé à IBS. RLBS surpasse largement IBS. Il est capable de trouver une solution optimale en explorant beaucoup moins de noeuds que le nombre nécessaire à IBS pour trouver une telle solution.Combinatorial optimization problems are often very difficult to solve and the choice of a search strategy has a tremendous influence over the solver’s performance. To solve a problem using search, one needs to choose a variable selection strategy (defining the order in which variables will be instantiated), a value selection strategy (that specifies the sequence in which we will try the variable possible values) and a backtracking strategy (that determines to which node we should backtrack/backjump, when a leaf is reached or a dead-end is encountered). When it comes to backtracking strategies, there are some that are encoded into full deterministic algorithms (e.g. Depth-First Search – DFS), and others that rely on more dynamic node evaluator mechanisms (e.g. Best-First Search). Others (e.g. Limited Discrepancy Search – LDS) can be implemented as a deterministic iterative algorithm or as a node evaluator. A strategy is said to be adaptive when it dynamically adapts to the structure of the problem and identifies the areas of the search space that contain good solutions. Some have proposed adaptive branching strategies (e.g. Impact-based Search – IBS) or a backtracking strategy (e.g. Adaptive Discrepancy Search – ADS) proposed for distributed optimization problems. To our current knowledge, no adaptive backtracking strategy that relies on Reinforcement Learning (RL) has been proposed yet. We believe that RL techniques could allow a more efficient learning process and that, provided with these techniques, a backtracking strategy has a great potential of solving combinatorial optimization problems in a faster way. In this thesis, we introduce an algorithm (RLBS) that learns to efficiently backtrack when searching non-binary trees. We consider a machine learning approach which improves the performance of the solver. More specifically, we use reinforcement learning to identify the areas of the search space that contain good solutions. The approach was developed for optimization problems for which the search space is encoded as a non-binary tree. Since the trees are non-binary, we have the opportunity to backtrack multiple times to each node during the search. This allows learning which nodes generally lead to the best rewards (that is, to the most interesting leaves). Branching can be carried on using any variable/value selection strategy. However, when backtracking is needed, the selection of the target node involves reinforcement learning. RLBS is evaluated on five instances of the lumber planing problem using real idustrial data, and it is compared to LDS and ADS. It outperforms classic (non-adaptive) search strategies (DFS, LDS), an adaptive branching strategy (IBS), and an adaptive backtracking strategy (ADS) on every instance of this problem. Experiments have shown that RLBS is on average 4 times faster than ADS, and 6 times faster than LDS. RLBS is also evaluated on a toy instance of the lumber planing problem and compared to IBS. RLBS substantially outperforms IBS by solving the problem to optimality much faster