Title :
Constructive hyper-heuristics in class timetabling
Author :
Ross, Peter ; Marfn-Blazquez, J.G.
Author_Institution :
Sch. of Comput., Napier Univ., Edinburgh, UK
Abstract :
Evolutionary and stochastic problem solving techniques are often regarded with caution by end users because of their apparent fragility and slowness. Typically each problem is solved in isolation, and results are sensitive to parameters. Users may thus prefer easily understood but worse performing heuristic methods. Hyper-heuristics represents a way around this; the idea is to use evolutionary methods to discover a novel non-evolutionary deterministic algorithm, based on simple and familiar heuristics that has good worst-case performance across a range of problems. We apply this idea to a set of non-trivial class timetabling problems, formerly used in an international timetabling technology competition. The learnt algorithm is fast, greedy, and does not involve additional search or backtracking. Although we use a messy GA to search for the algorithm, it also scales very well; the typical chromosome size is not directly related to the size of the problems to be solved.
Keywords :
deterministic algorithms; genetic algorithms; heuristic programming; learning (artificial intelligence); problem solving; algorithm learning; class timetabling; constructive hyperheuristics; evolutionary methods; evolutionary problem solving; nonevolutionary deterministic algorithm discovery; stochastic problem solving; Biological cells; Heuristic algorithms; Iterative algorithms; Optimization methods; Pattern matching; Problem-solving; Stochastic processes;
Conference_Titel :
Evolutionary Computation, 2005. The 2005 IEEE Congress on
Print_ISBN :
0-7803-9363-5
DOI :
10.1109/CEC.2005.1554866