Memetic algorithms for timerabling problems in pricate schools


Thesis Type: Postgraduate

Institution Of The Thesis: Middle East Technical University, Faculty of Engineering, Department of Computer Engineering, Turkey

Approval Date: 2005

Thesis Language: English

Student: Deniz Aldoğan

Supervisor: FERDA NUR ALPASLAN

Abstract:

The aim of this study is to introduce a real-world timetabling problem that exists in some private schools in Turkey and to solve such problem instances utilizing memetic algorithms. Being a new type of problem and for privacy reasons, there is no real data available. Hence for benchmarking purposes, a random data generator has been implemented. Memetic algorithms (MAs) combining genetic algorithms and hill-climbing are applied to solve synthetic problem instances produced by this generator. Different types of recombination and mutation operators based on the hierarchical structure of the timetabling problem are proposed. A modified version of the violation directed hierarchical hill-climbing method (VDHC), introduced by A. Alkan and E. Ozcan, coordinates the process of 12 different low-level hill-climbing operators grouped in two distinct arrangements that attempt to resolve corresponding constraint violations. VDHC is an adaptive method advocating cooperation of hill-climbing operators. In addition, MAs with VDHC are compared with different versions of multimeme algorithms and pure genetic algorithms. Experimental results on synthetic benchmark data set indicate the success of the proposed MA.