Hybrid Metaheuristic Algorithm and Metaheuristic Performance Measurement for Solving University Course Timetabling Problem

Md Sultan, Abu Bakar (2007) Hybrid Metaheuristic Algorithm and Metaheuristic Performance Measurement for Solving University Course Timetabling Problem. PhD thesis, Universiti Putra Malaysia.

[img] PDF
594Kb

Abstract

Metaheuristics have received considerable interest in the fields of applied artificial intelligence and combinatorial optimization such as university course timetabling problem (UCTP). Metaheuristics begin with one or more initial solutions and iteratively employ search strategies to avoid local optima. Recently, it was observed that the combination of concepts of different metaheuristics, called hybrid metaheuristics, can provide a more efficient behavior and higher flexibility in dealing with real-world and large-scale problems. Frequently, hybridzing the metaheuristic components lie on how we can effectively structure metaheuristic components to efficiently explore and exploite search space. Acquiring the proper balance between intensification and diversification strategies is the crucial factor in obtaining an effective metaheuristic. This research focused on the implementation of an hybrid evolutionary metaheuristic namely Two_point Hybrid Evolutionary Algorithm (Tp_HEA) on university course timetabling problem instances (UCTP). Tp_HEA is based on two solutions that represent intensification at one point and diversification on the other point. Systematic exchange of information between these two points is to ensure the proper management of the balance between intensification and diversification. The proposed Tp_HEA was tested on twelve standard UCTP instances according to the specified experimental procedure. The result obtained from the average point analysis and percentage of invalid solution was very promising. Out of twelve datasets, eight produced better performance when comparison was made against five other metaheuristics. The performance was measured in terms of constraints solved. Experimental results revealed that the arrangement of the Tp_HEA component would affect the search landscape of most UCTP problem instances. The stochastic nature of metaheuristic including the Tp_HEA, results in inconsistent performance and the difficulty in obtaining accurate prediction from average point analyses. Thus, the second contribution of this research is the introduction of Metaheuristic Performance Measurement (MPM). MPM is the attempt of measuring metaheuristic performance statistically, thus accurate indices can be obtained. The validity of MPM as a new measuring technique was tested using selected results obtained from proposed Tp_HEA together with the result produced by genetic algorithm (GA). The analysis showed that MPM values obtained from both algorithms almost in line with the result obtained from average point analysis. The specific indices of performance produced by MPM were the major elements that differentiate MPM from average point analysis. The indices gave values for the performance, and thus the performance was more easily estimated. The reliability of MPM could be further observed when the analysis of variance showed that MPM values obtained from different independent runs were not significantly varied. Therefore, MPM was able to obtain a good estimation as compared to other commonly used metaheuristic measuring techniques.

Item Type:Thesis (PhD)
Subject:Universities and colleges - Management.
Subject:Management - Time-tables.
Chairman Supervisor:Associate Professor Ramlan Mahmod, PhD
Call Number:FSKTM 2007 16
Faculty or Institute:Faculty of Computer Science and Information Technology
ID Code:5215
Deposited By: Rosmieza Mat Jusoh
Deposited On:07 Apr 2010 02:57
Last Modified:27 May 2013 07:21

Repository Staff Only: Edit item detail


Universiti Putra Malaysia Institutional Repository

Universiti Putra Malaysia Institutional Repository is an on-line digital archive that serves as a central collection and storage of scientific information and research at the Universiti Putra Malaysia.

Currently, the collections deposited in the IR consists of Master and PhD theses, Master and PhD Project Report, Journal Articles, Journal Bulletins, Conference Papers, UPM News, Newspaper Cuttings, Patents and Inaugural Lectures.

As the policy of the university does not permit users to view thesis in full text, access is only given to the first 24 pages only.