Adapting artificial immune algorithms for university timetabling

Simple item page
dc.contributor.authorMalim, Muhammad Rozi
dc.date.accessioned2014-10-21T03:30:24Z
dc.date.available2014-10-21T03:30:24Z
dc.date.issued2009
dc.descriptionPhDen_US
dc.description.abstractUniversity 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.en_US
dc.identifier.urihttp://hdl.handle.net/123456789/132
dc.language.isoenen_US
dc.subjectComputer Scienceen_US
dc.subjectArtificial immune algorithmsen_US
dc.subjectUniversity timetablingen_US
dc.titleAdapting artificial immune algorithms for university timetablingen_US
dc.typeThesisen_US
Files
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Pusat Pengajian Sains Komputer - Tesis