Utilisation de la recherche monte-carlo pour la génération de structure
13/12/2024 à 14h00
M. Milo ROUCAIROL présente ses travaux en soutenance le 13/12/2024 à 14h00
À l'adresse suivante : Université Paris Dauphine, PSL- Place du Maréchal de Lattre de Tassigny, 75016, Paris - Salle des thèses - D520
En vue de l'obtention du diplôme : Doctorat en Informatique
La soutenance est publique
Titre des travaux
Utilisation de la recherche monte-carlo pour la génération de structure
É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. Nicolas JOUANDEAU | Professeur des universités | UNIVERSITE PARIS 8 | Rapporteur |
| Mme Carola DOERR | Directeur de recherche | SORBONNE UNIVERSITE | Rapporteure |
| M. Alexandre VARNEK | Professeur | UNIVERSITE DE STRASBOURG | Examinateur |
Résumé
Ce document regroupe les article publiés lors de ma thèse dirigée par Tristan Cazenave au LAMSADE. La recherche Monte Carlo désigne une classe d'algorithmes de recherche stochastiques retournant une solution avec une garantie dans le temps, mais sans garantie de résultat. Ces algorithmes utilisent des techniques d'apprentissage par renforcement basées sur des exploration aléatoires ou guidées. Les capacités des algorithmes Monte Carlo sont limitées dans des domaines d'application mis en valeur récement, comme la génération d'image et de texte, ou les réseaux de neurones, LLM et autres algorithmes entrainés sur de larges bases de données dominent. Mais en revanche ils excellent sur les problèmes plus classiques et définis. L'usage le plus connu d'algorithme de recherche Monte Carlo est son utilisation en 2017 pour battre pour la première fois un champion de Go, chose qu'aucune autre famille d'algorithme n'était parvenue à faire. Mais les utilisations d'algorithmes de recherche Monte Carlo vont aussi bien au delà des jeux. Les algorithmes de recherche Monte Carlo sont largement utilisés dans la chimie, la recherche opérationelle, les transports, les mathématiques, et dans les jeux. Ils peuvent être appliqués à tout problème de décision séquentielle et de recherche dans un espace d'état tant que les fonctions d'évaluation et de modification d'un état sont définies. La définition de structure pour cette thèse est "système défini par les éléments qui le composent et les interactions entre ces éléments". Cette thèse explore plusieures applications de recherche Monte Carlo dans le contexte de la génération de structure. De nombreux espaces de recherche peuvent être représentés comme une structure en dehors des jeux, comme le circuit du problème de voyageur de commerce par exemple, mais aussi des molécules, des cristaux, des coalitions, des graphes, etc. Les points forts de cette thèse sont : - Des comparaisons entre algorithmes sur divers problèmes montrant la supériorité de la famille d'algorithmes "nested". - Une nouvelle variante de la Neste Monte Carlo Tree Search (NMCS) avec de meilleures performances. - Une bibliothèque d'algorithmes Monte Carlo codés en Rust. - Un projet de réfutation de conjectures des graphes. - Une implémentation du NMCS pour AiZynthFinder, le logiciel de rétrosynthèse open source d'AstraZeneca. - Un programme de génération de molécules valides et synthétisables. Les sujets abordés peuvent être séparés en deux groupes. D'un côté la chimie, avec le HP-model, la rétrosynthèse, et la génération de molécules. Et de l'autre les mathématiques, avec les structures de coalitions, la théorie spectrale des graphes, les réseaux de transport, et les nonograms. Ce sont deux de mes centres d'intérêt qui m'ont motivé: (1) l'envie de produire quelque chose d'utile et la chimie, et (2) les enigmes et problèmes plus abstraits, précis, et parfois amusants. Bien que cette thèse ne se consacre qu'à des applications de la recherche Monte Carlo, elle apporte aussi des aperçus plus généraux : une comparaison des familles d'algorithmes montrant la supériorité des "nested", une nouvelle variante du NMCS, et des heuristiques et modifications généralement utiles avec les problèmes NP.