| Titre : | University Timetable Optimization Using Genetic and Reinforcement Learning Algorithms: A Performance Evaluation |
| Auteurs : | Malak Hasni, Auteur ; Djamila Nawal Slimani, Auteur ; Imene Aloui, Directeur de thèse |
| Type de document : | Mémoire magistere |
| Editeur : | Biskra [Algérie] : Faculté des Sciences Exactes et des Sciences de la Nature et de la Vie, Université Mohamed Khider, 2025 |
| Format : | 1 vol. (77 p.) / ill.couv.ill.encoul / 30cm |
| Langues: | Anglais |
| Langues originales: | Anglais |
| Résumé : |
University scheduling is a classic combinatorial optimization problem, involving the allocation of courses,lecturers, classrooms, and time periods to satisfy numerous strict and non strict constraints. This problem is NP-hard due to the vast number of possible schedules and the need to balance institutional rules, resource availability, and fairness. Manual methods for generating schedules are not only inefficient but also error-prone, underscoring the need for intelligent, automated solutions.
This thesis addresses the university scheduling problem by proposing and evaluating advanced computational techniques rooted in artificial intelligence. Specifically, it compares the effectiveness of genetic algorithms (GAs) and proximal policy optimization (PPO), a reinforcement learning method, in generating practical and optimized schedules. GAs, a heuristic algorithm inspired by natural selection, excel at exhaustive searches across large solution spaces, while PPOs allow an agent to learn scheduling strategies by interacting with the environment and rewarding feedback. The work also explores a hybrid approach that combines genetic algorithms and hill climbing to further optimize solutions through a local search.The system consists of three stages: modeling university constraints, generating student schedulesusing different algorithms, and evaluating performance using a multi-objective fitness function.The results show that each algorithm has advantages in terms of meeting constraints, computation time, and performance speed, with the PPO algorithm demonstrating the ability to continuously improvethrough learning.This study demonstrates how combining evolutionary computing and reinforcement learning canlead to scalable, flexible, and intelligent scheduling systems, contributing to the expansion of automated scheduling in complex environments |
| Sommaire : |
Dedication . . . i
Acknowledgements . . . . . ii Abstract iii Liste Of Figures vi Liste Of Tables vii General Introduction 1 I Combinatorial Optimization Problems 3 I.1 Introduction . . . . . . 3 I.2 Definition of Combinatorial optimization . . 3 I.2.1 Combinatorial problems . . . . .. 3 I.3 Types of optimization problems . . . . . 4 I.3.1 Mono-Objective optimization problems: . . . 4 I.3.2 Multi-Objective optimization problems: . . . 4 I.3.2.1 Multi-objective into mono-objective . . . . . . . . . . . . . . . . . . . . 5 I.3.2.2 Multi-objective as multi-objective . . . . . . . . . . . . . . . . . . . . . . 5 I.4 Complexity . . .. . 5 I.4.1 Complexity classes . . . . . 6 I.5 Classification of optimization methods . . . 6 I.5.1 Exact methods . . .. 7 I.5.2 Approximate methods . . 7 I.5.2.1 Heuristic algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 I.5.2.2 Metaheuristic algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 8 I.6 Genetic algorithm : . . . 10 I.6.1 Terminology . . . . . 10 I.6.2 The Genetic Algorithm process : . . . 10 I.6.3 Key concepts in genetic algorithm: . . . . 11 I.6.3.1 Coding . . . . . . . . . . . . . . . . . . . . . . . . . 12 I.6.3.2 Fitness function . . . . . . . . . . . . . . . . . . . . . . 13 I.6.4 Operators used by GA’s . . . 13 I.6.4.1 Selection . . . . . . . . . . . . . . . 13 I.6.4.2 Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 I.6.4.3 Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 I.7 Conclusion .. 15 II Scheduling problems 16 II.1 Introduction . . . . . . .. 16 II.2 Scheduling and Timetabling problems . . . . 17 II.2.1 Scheduling problem . . . . 17 II.2.2 Timetabling problem . .. 18 II.3 History . 18 II.4 Purpose . . . . 19 II.5 Constraints . . . . .. . 19 II.6 University timetabling . . . . 20 II.6.1 University hard constraints .. 20 II.6.2 University soft constraints . . . 20 II.7 Types of university timetable . . . . . . . . 21 II.8 Formulation of university timetabling .. 21 II.9 Problem Classification . . . 22 II.10 Solving timetabling problem . . . . 22 II.10.1 Complexity of timetabling problem . . . 22 II.10.2 University timetabling solving approaches . . . 23 II.10.2.1 Sequential methods . . . . . . . . . . . . . . . . . . . . . . . 23 II.10.2.2 Metaheuristics methods . . . . . . . . . . . . . . . . . . . . . . 23 II.10.2.3 Hybrid methods . . . . . . . . .. . . . . . . . . . . . . . . 24 II.10.2.4 Multi-agent systems approaches . . . . . . . . . . . . . . . . . . . . . . . 24 II.11 Related Works . . . . . . . . . . . 25 II.11.1 Discussion of Related Literature . . . . . . . . . . . . . . . . . . . 25 II.11.2 Summary and Comparison of Related Works . . . . . . . . . . . . 27 II.12 Reinforcement Learning Background . . . . . 28 II.12.1 Reinforcement Learning . . . 28 II.12.2 Fundamental Concepts . . . . . . . . . . . . . . . . . . . 28 II.12.3 Differences with Supervised and Unsupervised Learning . . . . . . . . . 29 II.12.4 Markov Decision Process . . . . .. . . . . . . . . . 29 II.12.5 Advantages of Reinforcement Learning for timetable problem : . . . . . . 30 II.13 Policy gradient methods . . . . . . . . . . . . . . . . . . . 30 II.13.1 Proximal Policy Optimization (PPO) Algorithm . . . . . . . . . 31 II.13.2 Clipped Surrogate Objective . . . . . . . . . . . . . 31 II.13.3 Proximal Policy Optimization and Actor-Critic Framework . . . . . . . . 33 II.13.4 Generalized Advantage Estimator (GAE) . . . . . . . . . . . . . . . 34 II.14 Conclusion . . . 34 III System Design 35 III.1 Introduction . . . 35 III.1.1 General System Architecture . . .. 35 III.1.2 Requirement specification .. . 36 III.1.3 Actors . . . . . . 36 III.1.4 Functional requirements . . 36 III.1.5 Non-functional requirements . 37 III.2 General use case diagram . . 37 III.3 Class Diagrams . . . 38 III.3.1 Configuration and Utilities Module . .. 38 III.3.2 Data Management Module . . 39 III.3.3 Genetic Algorithm Optimization Module . 39 III.3.4 Reinforcement Learning Module . 40 III.3.5 Schedule Management Module . 40 III.3.6 University Structure Module . . . 41 III.4 Sequence Diagrams . . . . 42 III.4.1 Data Fetching Sequence Diagram . . . . 42 III.4.2 Genetic Algorithm Sequence Diagram . 43 III.4.3 Hybrid Algorithm Sequence Diagram . . . .. . . . . . . . 44 III.4.4 Proximal Policy Optimization Algorithm Sequence Diagram . . . . . . . . . . . . 45 III.4.5 Upload Generated Timetable Sequence Diagram . . . . . . . . . 46 III.4.6 Main Sequence Diagram . . . 47 III.4.7 Timetable generator Activity Diagram . . . . 48 III.5 Timetable generation algorithm . . . 49 III.5.1 Data formatting . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 III.5.2 Genetic algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 51 III.5.2.1 Initial Population : . . . . . . . . . . . . . . . . . . . . . 51 III.5.2.2 Fitness Evaluation : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 III.5.2.3 Parent selection : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 III.5.2.4 Crossover : . . . . . . . . . . . . . . . 55 III.5.2.5 Mutation : . . . . . . . . . . . . . . . . . . . . . . . . . 56 III.5.3 Hybrid Algorithm . . . 58 III.5.3.1 Local Search method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 III.5.4 Proximal Policy Optimization algorithm . . .. 59 III.5.4.1 Timetable Environment Setup . . . . . . . . . . . . . . . . . . . . . . . 63 III.5.4.2 State Representation and Action Space . . . . . . . . . . . . . . . . . . 63 III.5.4.3 Reinforcement Learning Agent . . . . . . . . . . . . . . . . . . . . . . . 64 III.5.4.4 PPO Agent with Policy Gradient Updates . . . . . . . . . . . . . . . . 64 III.5.4.5 Reward Function and Constraint Checking . . . . . . . . . . . . . . . . 65 III.5.4.6 Training Loop and Optimization . . . . . . . . . . . . . . . . . . . . . . 66 III.5.4.7 Model Saving and Loading . . . . . . . . . . . . . . . . . . . . . . . . . 67 III.6 Conclusion . . . 67 IV System implementation 68 IV.1 Introduction . 68 IV.2 Work environments . . 68 IV.2.1 Software . . 68 IV.2.2 Programming languages and technologies . . . . . . . . . . . . . . . . . . . . . . . 69 IV.3 Results and analysis .. . 71 IV.3.1 Genetic Algorithm Results . . . 71 IV.3.1.1 Genetic Algorithm Best Fitness Curves level_id 184 . . . . . . . . . . . 71 IV.3.1.2 Analysis and Explanations . . . . . . . . . . . . . . . . . . . . . . . . . 71 IV.3.2 Hybrid Algorithm Results . . . . 75 IV.3.2.1 Analysis and Explanations . . . . . . . . . . . . . . . . . . . . . . . . . 75 IV.3.2.2 Genetic Algorithm Curves for level_id 184 . . . . . . . . . . . . . . . . 79 IV.3.2.3 Hybrid Curves for level_id 184 . . . . . . . . . . . . . . . . . . . . . . . 80 IV.3.2.4 Analysis and Explanations Average Fitness . . . . . . . . . . . . . . . . 81 IV.3.3 Time Per Generation Genetic and Hybrid Algorithm Comparison . . . . . . . . . . 83 |
| Type de document : | Mémoire master |
Disponibilité (1)
| Cote | Support | Localisation | Statut |
|---|---|---|---|
| MINF/928 | Mémoire master | bibliothèque sciences exactes | Consultable |
