RESEARCH ARTICLE
A Variant Genetic Algorithm for a Specific Examination Timetabling Problem in a Japanese University
Jiawei Li1, *, Tad Gonsalves1
Article Information
Identifiers and Pagination:
Year: 2022Volume: 1
Issue: 2
E-location ID: e100622205848
Publisher ID: e100622205848
DOI: 10.2174/2666782701666220610145137
Article History:
Received Date: 16/01/2022Revision Received Date: 20/02/2022
Acceptance Date: 04/04/2022
Electronic publication date: 25/08/2022
Abstract
Background
Examination 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.
Methods
The 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.
Results
The 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.
Conclusion
The 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.