DocumentCode :
2729416
Title :
Constructive hyper-heuristics in class timetabling
Author :
Ross, Peter ; Marfn-Blazquez, J.G.
Author_Institution :
Sch. of Comput., Napier Univ., Edinburgh, UK
Volume :
2
fYear :
2005
fDate :
2-5 Sept. 2005
Firstpage :
1493
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Evolutionary Computation, 2005. The 2005 IEEE Congress on
Print_ISBN :
0-7803-9363-5
Type :
conf
DOI :
10.1109/CEC.2005.1554866
Filename :
1554866
Link To Document :
بازگشت