Nested Fitness Functions in Genetic Algorithms for Exam Scheduling
摘要
This paper presents a comparative study of two genetic algorithm-based approaches to optimize university exam scheduling by minimizing the numbers of various types of conflicts. Algorithm 1, referred to as the Single-Stage Weighted Sum Genetic Algorithm (SSWS-GA), operates by minimizing a weighted sum of the numbers of different conflict types in a single evolutionary process. It begins with a population of randomly generated schedules and evolves toward a solution that minimizes the cumulative weighted conflicts through standard genetic operations. Conversely, Algorithm 2, known as the Multi-Stage Weighted Sum Genetic Algorithm (MSWS-GA), adopts a sequential approach. It initially focuses on minimizing one type of conflict and, upon achieving a minimized state, progressively incorporates additional conflict types into the fitness function in subsequent stages. Each stage optimizes the weighted cumulative number of conflicts up to that point, building upon the population refined in the previous stage. The effectiveness, efficiency, and computational complexity of both algorithms are evaluated and compared using a set of metrics, including the quality of the final schedules, convergence speed, and resource consumption. The results aim to provide insights into the applicability and performance of these algorithms in real-world exam scheduling scenarios, contributing to the broader understanding of genetic algorithms in complex scheduling tasks. The comparative analysis seeks to guide the further development of algorithmic solutions for academic institutions striving for efficient exam scheduling.