Monte Carlo Tree Search in Finding Feasible Solutions for Course Timetabling Problem

Say Leng Goh, Graham Kendall, Nasser R. Sabar

Abstract


We are addressing the course timetabling problem in this work. In a university, students can select their favorite courses each semester. Thus, the general requirement is to allow them to attend lectures without clashing with other lectures. A feasible solution is a solution where this and other conditions are satisfied. Constructing reasonable solutions for course timetabling problem is a hard task. Most of the existing methods failed to generate reasonable solutions for all cases. This is since the problem is heavily constrained and an effective method is required to explore and exploit the search space. We utilize Monte Carlo Tree Search (MCTS) in finding feasible solutions for the first time. In MCTS, we build a tree incrementally in an asymmetric manner by sampling the decision space. It is traversed in the best-first manner. We propose several enhancements to MCTS like simulation and tree pruning based on a heuristic. The performance of MCTS is compared with the methods based on graph coloring heuristics and Tabu search. We test the solution methodologies on the three most studied publicly available datasets. Overall, MCTS performs better than the method based on graph coloring heuristic; however, it is inferior compared to the Tabu based method. Experimental results are discussed.

Keywords


combinatorial optimization; timetabling; monte carlo tree search; graph coloring heuristics; tabu search.

Full Text:

PDF

References


R. Coulom, “Monte-Carlo Tree Search in Crazy Stone,†in 12th Game Programming Workshop, 2007.

M. Enzenberger, M. Muller, B. Arneson, and R. Segal, “Fuego-An Open-Source Framework for Board Games and Go Engine Based on Monte Carlo Tree Search,†{IEEE} Trans. Comput. Intell. {AI} Games, vol. 2, no. 4, pp. 259–270, 2010.

C. S. Lee et al., “The Computational Intelligence of {MoGo} Revealed in Taiwan’s Computer Go Tournaments,†IEEE Trans. Comput. Intell. {AI} Games, vol. 1, no. 1, pp. 73–89, 2009.

T. P. Runarsson, M. Schoenauer, and M. Sebag, “Pilot, rollout and monte carlo tree search methods for job shop scheduling,†in Learning and Intelligent Optimization, Springer, 2012, pp. 160–174.

M. P. D. Schadd, M. H. M. Winands, H. J. Van Den Herik, G. M.-B. Chaslot, and J. W. H. M. Uiterwijk, “Single-player monte-carlo tree search,†in Computers and Games, Springer, 2008, pp. 1–12.

S. Matsumoto, N. Hirosue, K. Itonaga, N. Ueno, and H. Ishii, “Monte-Carlo Tree Search for a reentrant scheduling problem,†in Computers and Industrial Engineering (CIE), 2010 40th International Conference on, 2010, pp. 1–6.

G. Chaslot, S. De Jong, J.-T. Saito, and J. Uiterwijk, “Monte-Carlo tree search in production management problems,†in Proceedings of the 18th BeNeLux Conference on Artificial Intelligence, 2006, pp. 91–98.

N. R. Sabar, M. Ayob, G. Kendall, and R. Qu, “A honey-bee mating optimization algorithm for educational timetabling problems,†Eur. J. Oper. Res., vol. 216, no. 3, pp. 533–543, 2012.

H. Arntzen and A. Lokketangen, “A local search heuristic for a university timetabling problem,†nine, vol. 1, no. T2, p. T45, 2003.

S. Abdullah, K. Shaker, B. McCollum, and P. McMullan, “Construction of course timetables based on great deluge and tabu search,†in Metaheuristics Int. Conf., VIII Meteheuristic, 2009, pp. 13–16.

H. Cambazard, E. Hebrard, B. O’Sullivan, and A. Papadopoulos, “Local search and constraint programming for the post enrolment-based course timetabling problem,†Ann. Oper. Res., vol. 194, no. 1, pp. 111–135, 2012.

S. L. Goh, G. Kendall, and N. R. Sabar, “Improved Local Search Approaches to Solve Post Enrolment Course Timetabling Problem,†Eur. J. Oper. Res., 2017.

S. L. Goh, G. Kendall, and N. R. Sabar, “Simulated annealing with improved reheating and learning for the post enrolment course timetabling problem,†J. Oper. Res. Soc., pp. 1–16, 2018.

I. Blochliger and N. Zufferey, “A graph colouring heuristic using partial solutions and a reactive tabu scheme,†Comput. Oper. Res., vol. 35, no. 3, pp. 960–975, 2008.

R. Lewis and J. Thompson, “Analysing the effects of solution space connectivity with an effective metaheuristic for the course timetabling problem,†Eur. J. Oper. Res., vol. 240, no. 3, pp. 637–648, 2015.

M. Chiarandini, C. Fawcett, and H. H. Hoos, “A modular multiphase heuristic solver for post enrollment course timetabling,†in Proceedings of the 7th International Conference on the Practice and Theory of Automated Timetabling (PATAT 2008), 2008.

A. Abuhamdah, M. Ayob, G. Kendall, and N. R. Sabar, “Population based Local Search for university course timetabling problems,†Appl. Intell., vol. 40, no. 1, pp. 44–53, 2014.

G. Chaslot, “Monte-carlo tree search,†PhD thesis, Maastricht University, 2010.

V. Kumar, “Algorithms for Constraint-Satisfaction Problems: A Survey,†AI Mag., vol. 13, no. 1, p. 32, 1992.

L. A. Taylor, “Local search methods for the post enrolment-based course timetabling problem,†Cardiff University, 2013.

P. Drake and S. Uurtamo, “Move Ordering vs Heavy Playouts: Where Should Heuristics Be Applied in Monte Carlo Go?,†in Proceedings of the 3rd North American Game-On Conference, 2007.

D. Silver and G. Tesauro, “Monte-Carlo Simulation Balancing,†in Proceedings of the 26th Annual International Conference on Machine Learning, 2009, pp. 945–952.

B. Arneson, R. B. Hayward, and P. Henderson, “Monte Carlo Tree Search in Hex,†{IEEE} Trans. Comput. Intell. {AI} Games, vol. 2, no. 4, pp. 251–258, 2010.

S. He et al., “Game Player Strategy Pattern Recognition and How {UCT} Algorithms Apply Pre-knowledge of Player’s Strategy to Improve Opponent {AI},†in 2008 International Conference on Computational Intelligence for Modelling Control Automation, 2008, pp. 1177–1181.

J. Huang, Z. Liu, B. Lu, and F. Xiao, “Pruning in {UCT} Algorithm,†in 2010 International Conference on Technologies and Applications of Artificial Intelligence, 2010, pp. 177–181.




DOI: http://dx.doi.org/10.18517/ijaseit.9.6.10224

Refbacks

  • There are currently no refbacks.


Published by INSIGHT - Indonesian Society for Knowledge and Human Development