DOI : https://doi.org/10.18517/ijaseit.9.6.10224

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

Say Leng Goh (1), Graham Kendall (2), Nasser R. Sabar (3)
(1) Decision Sciences Lab, ISRG, Faculty of Computing and Informatics, Universiti Malaysia Sabah Labuan International Campus, Labuan, 87000, Malaysia.
(2) School of Computer Science, The University of Nottingham Malaysia Campus, Semenyih, Malaysia.
(3) Department of Computer Science and Information Technology, La Trobe University, Melbourne, Australia.
Fulltext View | Download
How to cite (IJASEIT) :
Goh, Say Leng, et al. “Monte Carlo Tree Search in Finding Feasible Solutions for Course Timetabling Problem”. International Journal on Advanced Science, Engineering and Information Technology, vol. 9, no. 6, Dec. 2019, pp. 1936-43, doi:10.18517/ijaseit.9.6.10224.
Citation Format :
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.

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.

Authors who publish with this journal agree to the following terms:

    1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
    2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
    3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).