Local Optimization in Monte-Carlo Tree Search for the Traveling Salesman Problem


This project was undertaken as part of my TIPE (Travail d’Initiative Personnelle Encadré), a French research project completed by students in “classes préparatoires.” I received a grade of 20/20 for this project in the ENS competitive entrance exam.

Even if the final method is not competitive with state-of-the-art methods, I believe some of the ideas presented in this project are interesting and could be used to improve MCTS for other problems, as it provides a means to incorporate any local optimization algorithm into MCTS.

You can find the full report here (in English) or here (in French).