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.
| Identifer | oai:union.ndltd.org:METU/oai:etd.lib.metu.edu.tr:http://etd.lib.metu.edu.tr/upload/3/12606218/index.pdf |
| Date | 01 July 2005 |
| Creators | Aldogan, Deniz |
| Contributors | Alpaslan, Ferda Nur |
| Publisher | METU |
| Source Sets | Middle East Technical Univ. |
| Language | English |
| Detected Language | English |
| Type | M.S. Thesis |
| Format | text/pdf |
| Rights | To liberate the content for public access |
Page generated in 0.0021 seconds