A Variant Genetic Algorithm for a Specific Examination Timetabling Problem in a Japanese University - Li, Jiawei; Gonsalves, Tad (The Chinese Journal of Artificial Intelligence, 2022)
BackgroundExamination Timetabling Problem that tries to find an optimal examination schedule for schools, colleges, and universities, is a well-known NP-hard problem. This paper presents a Genetic Algorithm variant approach to solve a specific examination timetabling problem common in Japanese colleges and universities.MethodsThe proposed algorithm uses a direct chromosome representation Genetic Algorithm and implements constraint-based initialization and constraint-based crossover operations to satisfy the hard and soft constraints. An island model with varying crossover and mutation probabilities and an improvement approach called pre-training are applied to the algorithm to further improve the result quality.ResultsThe proposed model is tested on synthetic as well as real datasets obtained from Sophia University, Japan and shows acceptable results. The algorithm was fine-tuned with different penalty point combinations and improvement combinations.ConclusionThe comparison results support the idea that the initial population pre-training and the island model are effective approaches to improve the result quality of the proposed model. Although the current island model used only four islands, incorporating a greater number of islands, and some other diversity maintenance approaches such as memetic structures are expected to further improve the diversity and the result quality of the proposed algorithm on large scale problems.
Keywords: meta-heuristic algorithms