offres d'emploi formations actualités contact accès annuaire intranet
Séminaires >

Introduction de statistiques en Optimisation

Fabien Teytaud, Université Paris Sud XI

jeudi 22 mars 2012 à 14h00

amphi C001


Ces travaux se situent dans le contexte de l’optimisation. Trois grandes parties s’en dégagent ; la première concerne l’utilisation d’algorithmes évolutionnaires pour résoudre des problèmes d’optimisation continue et sans dérivées. La seconde partie concerne l’optimisation de séquences de décisions dans un environnement discret et à horizon fini en utilisant des méthodes de type Monte-Carlo Tree Search. La troisième partie concerne l’utilisation d’algorithmes de recherche arborescente pour la résolution de problème combinatoire avec contraintes. Dans le cadre de l’optimisation évolutionnaire, nous nous intéressons particulièrement au cadre parallèle à grand nombre d’unités de calcul. Après avoir présenté les algorithmes de référence du domaine, nous montrons que ces algorithmes, sous leur forme classique, ne sont pas adaptés à ce cadre parallèle et sont loin d’atteindre les vitesses de convergence théoriques. Nous proposons donc ensuite différentes règles (comme la modification du taux de sélection, la réduction du biais, et différentes méthodes de réduction de variance) afin de corriger et améliorer ces algorithmes. Nous faisons un comparatif empirique de ces règles appliquées à certains algorithmes. Dans le cadre de l’optimisation de séquences de décisions, nous nous intéressons aux algorithmes de type Monte-carlo Tree Search et Nested Monte-Carlo. Ces algorithmes sont aujourd’hui très utilisés pour la prise de décisions dans l’incertain, en particulier lorsque la dimension est grande. Nous proposons de faire un apprentissage de la politique Monte-Carlo de ces algorithmes. Nous montrons à travers ces expériences que les résultats sont positifs. Dans le cadre de l’optimisation combinatoire, nous étudions particulièrement les algorithmes de type Nested Monte-Carlo et Nested Rollout Policy Adaptation. Ces algorithmes sont connus pour être efficaces lorsque les décisions lointaines sont aussi importantes que les premières. Nous montrons que ces algorithmes permettent de résoudre efficacement des problèmes d’optimisation combinatoire, et qu’il est possible de guider les simulations en utilisant des connaissances expertes.