Performance comparison of Genetic Algorithm's crossover operators on University Course Timetabling Problem

Abstract

University Course Timetabling Problem (UCTP) is an NP-hard problem, and has many factors to be considered. The Genetic Algorithm (GA) is one of the most popular methods used in UCTP. It is best suited and widely used for NP-hard and optimization problems. Selection, crossover, and mutation are key operators which can influence the GA's performance. Crossover is an important operator which combines the good properties of both parents in order to possibly yield new better children chromosomes. The aim of this paper is to compare the performance of GA's crossover operators (partially matched crossover, order crossover, and cycle crossover) on UCTP. The experimental result demonstrates that GA with order crossover works more effectively than the others for producing feasible timetables and cycle crossover is a great operator in finding the optimal feasible timetable.