<  Retour au portail Polytechnique Montréal

Apprentissage par renforcement d'heuristiques de branchement en programmation par contraintes

Bilel Omrani

Mémoire de maîtrise (2021)

Document en libre accès dans PolyPublie
[img]
Affichage préliminaire
Libre accès au plein texte de ce document
Conditions d'utilisation: Tous droits réservés
Télécharger (948kB)
Afficher le résumé
Cacher le résumé

Résumé

La résolution de problèmes combinatoires en programmation par contraintes (CP) se fait par énumération des solutions. Cette procédure exhaustive est très coûteuse et la conception d'heuristiques de branchement visant à accélérer l'exploration de l'espace des solutions est souvent indispensable. Néanmoins, la conception d'heuristiques dédiées est un processus long, nécessitant une expertise et ne se généralise pas à un large nombre de problèmes différents. Ce constat a motivé l'utilisation de modèles d'apprentissage machine pour automatiquement apprendre des heuristiques performantes sans expertise humaine. Ces modèles entraînés par apprentissage par renforcement (RL) peuvent alors être intégrés à des solveurs de programmation par contraintes au sein d'une méthode de recherche simple comme la fouille en profondeur pour explorer systématiquement l'espace des solutions. Inspiré par les récents développement du système AlphaZero, un algorithme générique combinant recherche arborescente et apprentissage par renforcement, nous proposons un nouvel algorithme de résolution de problèmes combinatoires combinant les avantages de la programmation par contraintes avec la possibilité d'apprendre automatiquement une stratégie d'exploration de l'espace des solutions.

Abstract

Discrete optimization with Constraint Programming (CP) requires an expensive enumeration of the whole solution space. In order to be tractable, CP uses carefully crafted branching heuristics to speed up the search. Designing these heuristics is time-consuming, requires a human expertise and is very problem-specific. This observation has motivated the use of Machine Learning models to automatically learn efficient heuristics from raw data, without human supervision. Models trained by Reinforcement Learning (RL) can then be integrated within CP solvers and used in combination with a simple search algorithm such as a Depth-First Search (DFS).We propose a new algorithm to solve combinatorial problems within the CP framework, inspired by the recent advent of AlphaZero, a generic hybrid method featuring a tree search algorithm with Reinforcement Learning models. This method combines all the benefits of CP with the ability to directly learn efficient heuristics directly from raw interactions with the problem to solve.

Département: Département de génie informatique et génie logiciel
Programme: Génie informatique
Directeurs ou directrices: Gilles Pesant et Quentin Cappart
URL de PolyPublie: https://publications.polymtl.ca/6571/
Université/École: Polytechnique Montréal
Date du dépôt: 14 juil. 2021 13:31
Dernière modification: 19 avr. 2023 12:51
Citer en APA 7: Omrani, B. (2021). Apprentissage par renforcement d'heuristiques de branchement en programmation par contraintes [Mémoire de maîtrise, Polytechnique Montréal]. PolyPublie. https://publications.polymtl.ca/6571/

Statistiques

Total des téléchargements à partir de PolyPublie

Téléchargements par année

Provenance des téléchargements

Actions réservées au personnel

Afficher document Afficher document