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

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 opt...

Full description

Saved in:

Bibliographic Details
Main Author:	Md Sultan, Abu Bakar
Format:	Thesis
Language:	English English
Published:	2007
Subjects:	Universities and colleges - Management. Management - Time-tables.
Online Access:	http://psasir.upm.edu.my/id/eprint/5215/1/FSKTM_2007_16.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-upm-ir.5215
record_format	uketd_dc
spelling	my-upm-ir.52152013-05-27T07:21:13Z Hybrid Metaheuristic Algorithm and Metaheuristic Performance Measurement for Solving University Course Timetabling Problem 2007 Md Sultan, Abu Bakar 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. Universities and colleges - Management. Management - Time-tables. 2007 Thesis http://psasir.upm.edu.my/id/eprint/5215/ http://psasir.upm.edu.my/id/eprint/5215/1/FSKTM_2007_16.pdf application/pdf en public phd doctoral Universiti Putra Malaysia Universities and colleges - Management. Management - Time-tables. Computer Science and Information Technology English
institution	Universiti Putra Malaysia
collection	PSAS Institutional Repository
language	English English
topic	Universities and colleges - Management. Management - Time-tables.
spellingShingle	Universities and colleges - Management. Management - Time-tables. Md Sultan, Abu Bakar Hybrid Metaheuristic Algorithm and Metaheuristic Performance Measurement for Solving University Course Timetabling Problem
description	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.
format	Thesis
qualification_name	Doctor of Philosophy (PhD.)
qualification_level	Doctorate
author	Md Sultan, Abu Bakar
author_facet	Md Sultan, Abu Bakar
author_sort	Md Sultan, Abu Bakar
title	Hybrid Metaheuristic Algorithm and Metaheuristic Performance Measurement for Solving University Course Timetabling Problem
title_short	Hybrid Metaheuristic Algorithm and Metaheuristic Performance Measurement for Solving University Course Timetabling Problem
title_full	Hybrid Metaheuristic Algorithm and Metaheuristic Performance Measurement for Solving University Course Timetabling Problem
title_fullStr	Hybrid Metaheuristic Algorithm and Metaheuristic Performance Measurement for Solving University Course Timetabling Problem
title_full_unstemmed	Hybrid Metaheuristic Algorithm and Metaheuristic Performance Measurement for Solving University Course Timetabling Problem
title_sort	hybrid metaheuristic algorithm and metaheuristic performance measurement for solving university course timetabling problem
granting_institution	Universiti Putra Malaysia
granting_department	Computer Science and Information Technology
publishDate	2007
url	http://psasir.upm.edu.my/id/eprint/5215/1/FSKTM_2007_16.pdf
_version_	1747810375362936832

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

Similar Items