CE23 - Intelligence artificielle

Apprentissage profond pour l'optimisation et la satisfaction de contraintes – DELCO

Deep Learning for Combinatorial Optimization

Ce projet vise a s'appuyer sur les progrès récents en apprentissage profond et en apprentissage par renforcement pour définir une nouvelle génération de solveurs d'optimisation combinatoire capable d'apprendre des mécanismes de résolutions plus efficaces que les solveurs traditionnels.

Enjeux et objectifs

Ce projet vise à s'appuyer sur les progrès récents dans le domaine de l'apprentissage profond et de l'apprentissage par renforcement pour concevoir une nouvelle génération de solveurs de satisfaction de contraintes et d'optimisation plus généraux. <br /><br />A terme, ce projet contribuera à rendre les formulations de problèmes basiques (ou même naïfs) beaucoup plus efficaces à résoudre sans expertises et contribuera a rendre les solveurs de contraintes aussi accessibles que les systèmes de bases de données ne peuvent l'être aujourd'hui. <br /><br />Notre approche sera capable de redécouvrir des heuristiques de résolution de la même manière qu'AlphaGo a pu redécouvrir des connaissances stratégiques accumulées au fil des siècles. Dans un premier temps, nous utiliserons des réseaux neuronaux convolutifs (CNN) et nous nous appuierons sur l'apprentissage par imitation, et l'apprentissage supervisé pour obtenir des modèles capables de prendre de bonnes décisions de branchement à partir de données récoltées lors de la résolution de problèmes similaires. Dans un deuxième temps, le modèle sera spécialisé pour le problème en cours de résolution, en s'appuyant sur les données au cours de la résolution en cours.

L'objectif du projet est d'utiliser des techniques établies d'apprentissage par imitation et par renforcement pour définir une nouvelle catégorie de solveurs capables d'apprendre. Nous commencerons par générer de grandes quantités de données supervisées en utilisant des algorithmes Monte-carlo comme MCTS, et nous utiliserons ces données pour entraîner un réseau de neurones à imiter les décisions de branchement prises par MCTS, mais sans avoir a dérouler les très nombreuses simulations nécessaire à MCTS. Nous pouvons également utiliser les algorithmes d'apprentissage par renforcement comme REINFORCE pour améliorer la stratégie de résolution avec les données récoltées pendant la résolution du problème.

Pas de résultats pour l'instant.

Un solveur MIP basé sur SCIP capable d'apprendre des mécanismes de résolutions efficaces à partir de données historiques et de données récoltées pendant la résolution du problème.

1. Fréchet Mean Computation in Graph Space through Projected Block Gradient Descent. Boria, N., Negrevergne, B., & Yger, F. (2020). European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (ESANN).
2. The Minimum Edit Arborescence Problem and Its Use in Compressing Graph Collections. Gnecco, L., Boria, N., Bougleux, S., Yger, F., & Blumenthal, D. B. (2021). International Conference on Similarity Search and Applications.
3. Monte Carlo Graph Coloring. Cazenave, T., Negrevergne, B., & Sikora, F. (2020). Monte Carlo Search, IJCAI Workshop.
4. Deep Reinforcement Learning for Morpion Solitaire. Doux, B., Negrevergne, B., & Cazenave, T. (2021). Advances in Computer Games.
5. On the expressivity of bi-Lipschitz normalizing flows. Verine, A., Negrevergne, B., Rossi, F., & Chevaleyre, Y. (2021). ICML Workshop on Invertible Neural Networks, Normalizing Flows, and Explicit Likelihood Models.

Ce projet vise à concevoir une nouvelle génération de solveurs de programmation par contraintes plus généraux et plus performants. Pour y parvenir, nous nous appuieront sur les progrès récents effectués dans le domaine de l'apprentissage automatique (deep learning) et de l'apprentissage par renforcement.

Plus précisément, notre objectif est de développer une méthodologie pour apprendre des heuristiques de branchements apprises, capables de prendre des décisions pertinentes tout au long de l'exploration de l'espace de recherche. Pour atteindre cet objectif, nous utiliserons des réseaux de neurones convolutionels (CNNs) afin de modéliser les relations complexes qui peuvent exister entre l'état du problème en cours de résolution, et la variable de branchement optimale. Nous nous appuieront également sur l'apprentissage par renforcement pour entraîner les heuristiques en utilisant des récompenses éparses comme le temps d'exécution ou la taille de l'arbre de recherche. Combinées, ces deux techniques permettront de guider l'exploration rapidement vers les solutions au problème de satisfaction de contraintes.

Dans ce projet, nous évalueront le bien fondé de cette approche sur un ensemble de tâches de différentes natures. Nous commenceront par des problèmes représentés sous forme de grille puisque ces derniers peuvent être directement traités dans un CNNs classique. Puis nous explorerons des problèmes représentables sous forme de graphes, qui peuvent être abordés à l'aide de plongements de graphes.

Un deuxième axe de recherche visera à combiner les heuristiques apprises, avec différentes stratégies d'exploration. Tout d'abord, avec de simples stratégies gloutonnes, puis avec des algorithmes de recherche arborescente et enfin des solveurs de contraintes issus de l'état de l'art. Nous serons particulièrement attentifs aux possibles synergies entre les techniques de raisonnement (e.g. propagation de contraintes) et les techniques d'apprentissage automatique.

Ce projet portera également une attention particulière à la généralité et a la robustesse des approches développées. Nous tenterons d'adapter plusieurs techniques issues de l'apprentissage automatique traditionnellement utilisées pour produire des modèles plus généraux et plus robustes. En particulier nous nous intéresserons à la génération d'instances difficiles, ainsi qu'à la mise en oeuvre des réseaux antagonistes (generative adversarial networks) pour les problèmes abordés dans le cadre de ce projet. Cela nous permettra d'apprendre des heuristiques plus générales, plus robustes et performante dans les pires cas.

Le succès de ce projet repose en grande partie sur une méthodologie expérimentale solide. En effet, les compétences d'un ingénieur seront mobilisées pour mettre en place une plate-forme de tests entièrement automatisée. Cette plate-forme sera utilisée tout au long du projet pour obtenir une évaluation fiable des performances de notre approche, et pour produire des éléments de compréhension importants pour les aspects les plus fondamentaux.

En cas de succès, nous pouvons espérer des percées scientifiques importantes. Par exemple:
- Le développement de solveurs plus généraux. En particulier, de solveurs dont l'efficacité ne dépend pas de la manière d'encoder un problème sous forme de variables et de contraintes. Cela permettra de rendre les solveurs de programmation par contraintes plus accessibles aux utilisateurs novices.
- Des solveurs capables d'utiliser conjointement les techniques de raisonnement logique et d'apprentissage statistique. Cette perspective ouvre la voie à un nouveau paradigme pour la conception de solveurs.
- Des solveurs hybrides capables d'exploiter simultanément la puissance de calcul des architectures GPU (pour l'inférence dans les réseaux de neurones) et cette des CPU (pour la recherche arborescente et la propagation de contraintes).
- De nouvelles techniques d'apprentissages issues des travaux récents sur les réseaux antagonistes.

Coordination du projet

Benjamin Negrevergne (Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision)

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.

Partenaire

LAMSADE Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision

Aide de l'ANR 283 853 euros
Début et durée du projet scientifique : septembre 2019 - 48 Mois

Liens utiles

Explorez notre base de projets financés

 

 

L’ANR met à disposition ses jeux de données sur les projets, cliquez ici pour en savoir plus.

Inscrivez-vous à notre newsletter
pour recevoir nos actualités
S'inscrire à notre newsletter