Enhancement of ant colony optimization algorithm applied to University timetabling
- Undergraduate Thesis: (Bachelor of Science in Computer Science) - Pamantasan ng Lungsod ng Maynila) 2025
ABSTRACT: This study focuses on enhancing the Ant Colony Optimization (ACO) algorithm for solving university timetabling by addressing its core limitations: premature convergence, static parameter control, and limited local search refinement. Specifically, the enhancement aims to minimize premature convergence through memory-guided exploration and adaptive diversification, improve search adaptability by dynamically tuning parameters (α, β, and ρ), and refine feasible solutions using problem-specific local search operators such as neighborhood reassignments and Kempe-chain swaps. Standard benchmark datasets (ITC-2007) were used for training and evaluation. Results showed that these enhancements significantly improved optimization performance. The algorithm reduced penalties from an average of 1714.29 to as allow as 100.00, demonstrating strong optimization of soft constrains. Time-to-Best (TTB) improved substantially, with the best solution identified within 2.64 seconds compared to a total runtime of 335.24 seconds, reflecting high efficiency. However, feasibility remained a major limitation, with a 0% success rate in generating conflict-free timetables, and robustness was limited due to high variability in results across runs. These findings demonstrates that while the proposed enhancements make ACO more efficient in penalty minimization and convergence speed, further improvements are needed in feasibility preservation and robustness to ensure practical applicability for real-world university timetabling.