Adapting artificial immune algorithms for university timetabling
Loading...
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