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

Preview PDF FSKTM_2007_16.pdf Download (608kB)

Actions (login required)

View Item