Adapting artificial immune algorithms for university timetabling

Loading...
Thumbnail Image
Date
2009
Authors
Malim, Muhammad Rozi
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
University class and examination timetabling are highly constrained optimization problems. Metaheuristic approaches, and their hybrids, have successfully been applied to solve the problems. This thesis aims to develop artificial immune algorithms for university timetabling (class and examination). Three algorithms are considered; clonal selection (CSA), immune network (INA) and negative selection (NSA). The ultimate goal is to introduce the algorithms as new alternative approaches for university timetabling. In other words, to show that artificial immune algorithms can be adapted for solving class and examination timetabling problems. A unified model (UUTM) and three artificial immune algorithms (CSAUT, INAUT and NSAUT) for university timetabling are proposed. The algorithms have been tested on benchmark datasets (class and examination). The benchmark problems have been formulated as 0-1 integer programming using the unified model. Experimental results have shown that all algorithms are good optimization algorithms; have successfully produced good quality timetables. The main operators are cloning and mutation. Statistical tests of hypotheses have shown that INAUT is more effective than CSAUT and NSAUT, while CSAUT and NSAUT are equally effective. The algorithms can handle the hard and soft constraints very well, and may be accepted as new members of evolutionary algorithms for solving timetabling problems. The relative robustness measured for all algorithms on all datasets (class and examination) have significantly shown that the CSAUT timetables are more robust than those produced by INAUT and NSAUT; i.e. CSAUT timetables have large similarity compared to INAUT and NSAUT. The CPU times recorded on all algorithms have shown that INAUT has acquired the longest times on all datasets. Comparisons with published results have shown the effectiveness of the proposed artificial immune algorithms; all three algorithms are capable of producing good quality timetables as good as other methods. The three AIS algorithms have produced poor results in only two examination datasets (from 12 datasets). Initial population plays a crucial role in an optimization algorithm. The population size 10 is considerably small, and hence has limited the search space. A relatively small population size would results in premature convergence and decreases the optimization reliability. A better and larger size of initial population would produce better results. Unfortunately, the complexity of timetabling constraints has limited the population size.
Description
PhD
Keywords
Computer Science , Artificial immune algorithms , University timetabling
Citation