Analyzing the landscape of a graph based hyper-heuristic for timetabling problems

Citation

Ochoa G, Qu R & Burke E (2009) Analyzing the landscape of a graph based hyper-heuristic for timetabling problems. In: Proceeding GECCO '09 Proceedings of the 11th Annual conference on Genetic and evolutionary computation. 11th Annual Genetic and Evolutionary Computation Conference (GECCO-2009), Montréal, Canada, 08.07.2009-12.07.2009. New York, NY: ACM, pp. 341-348. http://dl.acm.org/citation.cfm?id=1569949&CFID=230982929&CFTOKEN=65117036; https://doi.org/10.1145/1569901.1569949

Abstract
Hyper-heuristics can be thought of as "heuristics to choose heuristics". They are concerned with adaptively finding solution methods, rather than directly producing a solution for the particular problem at hand. Hence, an important feature of hyper-heuristics is that they operate on a search space of heuristics rather than directly on a search space of problem solutions. A motivating aim is to build systems which are fundamentally more generic than is possible today. Understanding the structure of these heuristic search spaces is therefore, a research direction worth exploring. In this paper, we use the notion of fitness landscapes in the context of constructive hyper-heuristics. We conduct a landscape analysis on a heuristic search space conformed by sequences of graph coloring heuristics for timetabling. Our study reveals that these landscapes have a high level of neutrality and positional bias. Furthermore, although rugged, they have the encouraging feature of a globally convex or big valley structure, which indicates that an optimal solution would not be isolated but surrounded by many local minima. We suggest that using search methodologies that explicitly exploit these features may enhance the performance of constructive hyper-heuristics.

Keywords
; Operations Research/Decision Theory; Organization/Planning; Operations research; Business logistics; Economics/Management Science; Operations Research/Decision Theory; Mathematical Programming

People

Professor Gabriela Ochoa

Professor, Computing Science