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

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.

REFERENCES

• 1: R. Bai, E. K. Burke, and G. Kendall, phHeuristic,meta--heuristic and hyper--heuristic approaches for fresh produce inventory control and shelf space allocation, Journal of the Operational Research Society 59 (2008), 1387 --- 1397.
• 2: E. K. Burke, E. Hart, G. Kendall, J. Newall, P. Ross, and S. Schulenburg, Hyper-heuristics: An emerging direction in modern search technology, Handbook of Metaheuristics (F. Glover and G. Kochenberger, eds.), Kluwer, 2003, pp. 457--474.
• 3: E. K. Burke , G. Kendall , E. Soubeiga, A Tabu-Search Hyperheuristic for Timetabling and Rostering, Journal of Heuristics, v.9 n.6, p.451-470, December 2003 [doi>10.1023/B:HEUR.0000012446.94732.b6]
• 4: E. K. Burke, B. McCollum, A. Meisels, S. Petrovic, and R. Qu, A graph-based hyper-heuristic for educational timetabling problems, European Journal of Operational Research 176 (2007), 177--192.
• 5: Edmund K. Burke , Sanja Petrovic , Rong Qu, Case-based heuristic selection for timetabling problems, Journal of Scheduling, v.9 n.2, p.115-132, April 2006 [doi>10.1007/s10951-006-6775-y]
• 6: Michael W. Carter , Gilbert Laporte, Recent Developments in Practical Course Timetabling, Selected papers from the Second International Conference on Practice and Theory of Automated Timetabling II, p.3-19, August 20-22, 1997
• 7: Peter I. Cowling , Graham Kendall , Eric Soubeiga, A Hyperheuristic Approach to Scheduling a Sales Summit, Selected papers from the Third International Conference on Practice and Theory of Automated Timetabling III, p.176-190, August 16-18, 2000
• 8: L. Davis, phHandbook of genetic algorithms, Van Nostrand Reinhold, New York, 1991.
• 9: K. A. Dowsland, E. Soubeiga, and E. K. Burke, A simulated annealing hyper-heuristic for determining shipper sizes, European Journal of Operational Research 179 (2007), no. 3, 759--774.
• 10: Holger Hoos , Thomas Sttzle, Stochastic Local Search: Foundations & Applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 11: Wim Hordijk, A measure of landscapes, Evolutionary Computation, v.4 n.4, p.335-360, Winter 1996 [doi>10.1162/evco.1996.4.4.335]
• 12: Terry Jones, Crossover, Macromutationand, and Population-Based Search, Proceedings of the 6th International Conference on Genetic Algorithms, p.73-80, July 15-19, 1995
• 13: B. Manderick, M. de Weger, and P. Spiessens, The genetic algorithm and the structure of the fitness landscape, Proceedings of the 4th International Conference on Genetic Algorithms, Morgan Kaufmann, 1991, pp. 143--150.
• 14: Peter Merz , Bernd Freisleben, Fitness Landscapes, Memetic Algorithms, and Greedy Operators for Graph Bipartitioning, Evolutionary Computation, v.8 n.1, p.61-91, March 2000 [doi>10.1162/106365600568103]
• 15: David Pisinger , Stefan Ropke, A general heuristic for vehicle routing problems, Computers and Operations Research, v.34 n.8, p.2403-2435, August, 2007 [doi>10.1016/j.cor.2005.09.012]
• 16: R. Qu and E.K. Burke, Hybridisations within a graph based hyper-heuristic framework for university timetabling problems, Journal of the Operational Research Society t.a. (2008), t.a, to appear, doi: 10.1057/jors.2008.102.
• 17: R. Qu, E. K. Burke, and B. McCollum, phAdaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems, European Journal of Operational Research t.a. (2008), t.a, online publication, doi:10.1016/j.ejor.2008.10.001.
• 18: R. Qu , E. K. Burke , B. Mccollum , L. T. Merlot , S. Y. Lee, A survey of search methodologies and automated system development for examination timetabling, Journal of Scheduling, v.12 n.1, p.55-89, February 2009 [doi>10.1007/s10951-008-0077-5]
• 19: P. Ross, phHyper-heuristics, Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques (E. K. Burke and G. Kendall, eds.), Springer, 2005, pp. 529--556.
• 20: P. Ross, J. G. Marin-Blazquez, S. Schulenburg, and E. Hart, phLearning a procedure that can solve hard bin-packing problems: A new ga-based approach to hyper-heuristics, Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2003, Springer, 2003, pp. 1295--1306.
• 21: P. F. Stadler, phTowards a theory of landscapes, Complex Systems and Binary Networks (R. López-Pena, R. Capovilla, R. García-Pelayo, H. Waelbroeck, and F. Zertuche, eds.), Lecture Notes in Physics, vol. 461, Springer-Verlag, Berlin, Heidelberg, New York, 1995, pp. 77--163.
• 22: H. Terashima-Marin, A. Moran-Saavedra, and P. Ross, phForming hyper-heuristics with GAs when solving 2D-regular cutting stock problems, Proceedings of the 2005 IEEE Congress on Evolutionary Computation (Edinburgh, Scotland, UK), vol. 2, IEEE Press, 2--5 September 2005, pp. 1104--1110.
• 23: H. Terashima-Marin, P. Ross, and M. Valenzuela-Rendon, Evolution of constraint satisfaction strategies in examination timetabling, Proc. of the Genetic and Evolutionary Computation Conf. GECCO-99 (San Francisco, CA), Morgan Kaufmann, 1999, pp. 635--642.
• 24: J. A. Vázquez-Rodríguez, S. Petrovic, and A. Salhi, A combined meta-heuristic with hyper-heuristic approach to the scheduling of the hybrid flow shop with sequence dependent setup times and uniform machines, Proceedings of the 3rd Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA 2007), 2007.
• 25: E. D. Weinberger, phCorrelated and uncorrelated fitness landscapes and how to tell the difference, Biological Cybernetics \textbf63 (1990), 325---336.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Measurement, Performance

Keywords:
graph coloring heuristics, hyper-heuristics, landscape analysis, timetabling