Title:A Variant Genetic Algorithm for a Specific Examination Timetabling
Problem in a Japanese University
Volume: 1
Author(s): Jiawei Li*Tad Gonsalves
Affiliation:
- Department of Information & Communication Sciences, Faculty of Science and Technology, Sophia University, Tokyo,
Japan
Keywords:
Examination timetabling problem, genetic algorithm, direct chromosome representation, Island model, parallel genetic algorithm, evolutionary algorithms, meta-heuristic algorithms.
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.