Apprentissage automatique pour la résolution de problèmes discrets
21/11/2022 à 14h00
M.Boris DOUX présente ses travaux en soutenance le 21/11/2022 à 14h00
À l'adresse suivante : Université Paris Dauphine - PSL - Pl. du Maréchal de Lattre de Tassigny, 75016 Paris, France Salle des thèses D520
En vue de l'obtention du diplôme : Doctorat en Informatique
La soutenance est publique
Titre des travaux
Apprentissage automatique pour la résolution de problèmes discrets
École doctorale
École doctorale Dauphine SDOSE
Équipe de recherche
UMR 7243 - Laboratoire d’Analyse et de Modélisation de Systèmes d’Aide à la Décision
Section CNU
27 - Informatique
Directeur(s)
M. Tristan CAZENAVE
Membres du jury
| Nom | Qualité | Établissement | Rôle |
|---|---|---|---|
| M. Tristan CAZENAVE | Professeur des universités | UNIVERSITE PARIS DAUPHINE - PSL | Directeur de thèse |
| M. Benjamin NEGREVERGNE | Maître de conférences | UNIVERSITE PARIS DAUPHINE - PSL | Co-encadrant de thèse |
| M. Bruno BOUZY | Maître de conférences | UNIVERSITE PARIS DESCARTES | Rapporteur |
| M. Nicolas JOUANDEAU | Professeur | UNIVERSITE PARIS 8 | Rapporteur |
| Mme Hind CASTEL-TALEB | Professeur | TELECOM SUDPARIS | Examinatrice |
Résumé
Les industriels sont confrontés quotidiennement aux problèmes discrets, que ce soit pour la gestion des stocks, le remplissage de conteneurs ou la recherche du plus court chemin. Il existe de nombreuses techniques d'optimisation mathématiques, cependant sur un ensemble discret, le problème est plus délicat. En effet, les propriétés de continuité et dérivabilité ne sont pas exploitables. Les approches classiques pour ce type de problèmes consistent en une énumération astucieuse des solutions possibles. Dans cette thèse, nous proposons une méthode de résolution pour les problèmes discrets, en particulier les casse-têtes, basée sur l'apprentissage de réseaux de neurones combiné avec un algorithme de recherche Monte-Carlo. Nous considérons comme casse-tête tout jeu à un joueur. Nous démontrons sur deux problèmes les performances de cette approche. Dans un premier temps, nous considérons le Morpion Solitaire, un problème d'optimisation dont le but est de jouer le plus de coups possibles et dans un second temps, nous considérons le Perfect Rectangle Packing, un problème de décision dont le but est de déterminer comment placer un ensemble donné de rectangles sur un plateau de dimension fixe.