1. UKM Learning and Research Repository
2. PHD Thesis / Tesis PHD
3. Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat

Title:	Diversification and intensification strategies in population-based metaheuristics for post-enrolment course timetabling problems
Authors:	Ghaith Mohammad Hassan Jaradat (P45973)
Supervisor:	Masri Ayob, Assoc. Prof. Dr.
Keywords:	Diversification strategies Intensification strategies Population-based metaheuristics Post-enrolment course timetabling problems Heuristic programming
Issue Date:	26-Mar-2012
Description:	This work focuses on the university post-enrolment course timetabling problem, which is difficult to solve to optimality. Metaheuristic approaches are usually used to tackle this problem. Metaheuristics are categorised into two classes: population-based and local search. The population-based metaheuristics are capable of exploring the search space (diversify strategy), whilst the local search metaheuristics are capable of exploiting the solution space (intensify strategy). Thus, the hybridisation of both metaheursitic classes could produce an effective approach that can complement their limitation. Therefore, the thesis aims to investigate the means to maintain balance between diversification and intensification of the search in order to produce effective population-based approaches. To fulfill this aim, we introduce three variants of population-based metaheuristics. These are: Elitist-Ant System (Elitist-AS), Big Bang-Big Crunch (BB-BC) and Scatter Search (SS). These variants are chosen due to their limited ability to provide a guided search toward elite solutions while being capable of maintaining search diversity. The research begins with enhancing the capability of the Elitist-AS in maintaining a balance between diversity and quality of the solutions in the population. This is achieved by incorporating diversification and intensification mechanisms and an external memory. However, incorporating these mechanisms into the original Elitist-AS makes it impractical when dealing with complex scenarios. Therefore, we then proposed a variant of BB-BC, where it is inspired by the theory of the universe evolution. It is characterised by a fast search space exploration and aggressive solution space exploitation (via population size reduction). Although, several results obtained by the Elitist-AS are better than those of the BB-BC, the BB-BC has faster and more effective convergence toward elite solutions. Finally, we proposed a SS metaheuristic that performs structured combinations on a collection of elite and diverse solutions. This approach overcomes the shortages of the previous two approaches as well as the original SS; it also outperformed them in terms of quality and consistency that has the ability to balance between diversification and intensification. In order to evaluate the effectiveness of the approaches, we run the experiments on the 1st and 2nd timetabling competitions and Socha's datasets. Our metaheuristics obtained a number of optimal solutions and some best known results. They are able to obtain feasible and good quality timetables across all datasets. Overall, our enhanced algorithms (Elitist-AS, BB-BC and SS) have shown significant differences in the obtained results compared to their original algorithms.,PhD
Pages:	196
Call Number:	T57.84 .J345 2012 3
Publisher:	UKM, Kuala Lumpur
Appears in Collections:	Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.