Une recherche arborescente Monte-Carlo avec biais dynamique pour le problème de tournées de véhicules
Julien Sentuc  1@  , Jean-Yves Lucas  2@  , Tristan Cazenave  1@  
1 : LAMSADE
université Paris Dauphine, PSL Resarch University
2 : EDF
EDF Recherche et Développement

La recherche arborescente Monte-Carlo (Monte-Carlo Tree Search, ou MCTS) a été appliquée avec succès dans de nombreux domaines, en particulier ceux des jeux et des problèmes combinatoires. Elle trouve sa première application dans la conception de programmes jouant au jeu de Go ([1]). Une variante du MCTS, le Nested Rollout Policy Adaptation (ou NRPA) a été introduite en 2011 ([2]). Elle a permis d'obtenir des résultats de meilleure qualité que les algorithmes précédents de recherche arborescente, sur de nombreux jeux (record du monde du Morpion Solitaire) et problèmes combinatoires classiques tels que le voyageur de commerce avec fenêtre de temps, ou les tournées de véhicules. Le NRPA a donné lieu à son tour à une extension nommée Generalized NRPA (ou GNRPA) ([3]). Dans le NRPA, le choix par tirage aléatoire d'un nœud de l'arbre de recherche se fait à partir de la politique de choix apprise au cours de la recherche arborescente. Dans le GNRPA, ce tirage est fait en pondérant la probabilité de chaque nœud par un biais dynamique heuristique, qui tient compte des caractéristiques du nœud lui-même. La valeur du biais sera donc différente d'un nœud à l'autre.


Personnes connectées : 1 Vie privée
Chargement...