Fitness Distance Correlation(FDC) As A Hardness Prediction For University Course Timetabling Problem

Abstract

Masalah penjadulan adalah masalah pengoptimuman kombinatorial. Kerap kali teknikteknik metaheuristik digunakan untuk menyelesaikan masalah sebegini. Metaheuristik adalah algoritma bercirikan stokastik dan biasanya prestasi sukar diramal. Kertas ini menerangkan kaedah kolerasi Jarak Kecerdasan (FDC) untuk meramal prestasi algoritma metaheuristik melalui teknik statistik. FDC adalah pengukur statistik kepada kesukaran carian bagi algoritma genetik. Keputusan awal yang dihasilkan dari pengujian oleh algoritma hibrid ke atas contoh masalah penjadualan piawai amat menggalakkan. Keputusan menunjukkan FDC boleh diperluaskan kepada kaedah analisis dan masalah lain. Kata kunci: Penjadualan; metaheuristik; algoritma genetik; korelasi jarak kecergasan; ramalan kesukaran The timetabling problem is a combinatorial optimization problem. Frequently, metaheuristic techniques have been employed to solve this problem. Metaheuristic is a stochastic types algorithm and its performance usually difficult to predict. This paper described the usage of Fitness Distance Correlation (FDC) method to predict the performance of metaheuristic algorithm through statistical techniques. FDC is a statistical measure of search hardness in relation to Genetic Algorithm. Initial result from the experiment by hybrid algorithm over standard timetabling instances is very promising. We propose new ways of FDC analysis. The result indicates that FDC could be expanding in different ways of analysis as well as different instances. Key words: Timetabling; metaheuristic; genetic algorithm; fitness distance correlation; hardness prediction