Hyper-heuristics: a survey of the state of the art

Article English OPEN
Burke, Edmund ; Gendreau, Michel ; Hyde, Matthew ; Kendall, Graham ; Ocha, Gabriela ; Özcan, Ender ; Qu, Rong (2013)
  • Publisher: Palgrave Macmillan
  • Journal: Journal of the Operational Research Society, volume 64, issue 12 December, pages 1,695-1,724
  • Related identifiers: doi: 10.1057/jors.2013.71

Hyper-heuristics comprise a set of approaches that are motivated (at least in part) by the goal of automating the design of heuristic methods to solve hard computational search problems. An underlying strategic research challenge is to develop more generally applicable search methodologies. The term hyper-heuristic is relatively new; it was first used in 2000 to describe heuristics to choose heuristics in the context of combinatorial optimisation. However, the idea of automating the design of heuristics is not new; it can be traced back to the 1960s. The definition of hyper-heuristics has been recently extended to refer to a search method or learning mechanism for selecting or generating heuristics to solve computational search problems. Two main hyper-heuristic categories can be considered: heuristic selection and heuristic generation. The distinguishing feature of hyper-heuristics is that they operate on a search space of heuristics (or heuristic components) rather than directly on the search space of solutions to the underlying problem that is being addressed. This paper presents a critical discussion of the scientific literature on hyper-heuristics including their origin and intellectual roots, a detailed account of the main types of approaches, and an overview of some related areas. Current research trends and directions for future research are also discussed.
  • References (21)
    21 references, page 1 of 3

    Adenso-Diaz B and Laguna M (2006). Fine-tuning of algorithms using fractional experimental designs and local search. Operations Research 54(1): 99-114.

    Ahmadi S, Barrone P, Cheng P, Burke EK, Cowling P and McCollum B (2003). Perturbation based variable neighbourhood search in heuristic space for examination timetabling problem. In: Kendall G, Burke EK, Petrovic S and Gendreau M (eds). Multidisciplinary International Scheduling: Theory and Applications. MISTA, Springer: New York, pp 155-171.

    Allen S, Burke EK, Hyde MR and Kendall G (2009). Evolving reusable 3d packing heuristics with genetic programming. In: Conference on Machine Learning. Morgan Kaufmann: Amherst, MA, pp 135-142.

    Grefenstette J (1986). Optimization of control parameters for genetic algorithms. IEEE Transactions on Systems, Man, and Cybernetics SMC 16(1): 122-128.

    Grobler J, Engelbrecht A, Kendall G and Yadavalli V (2012). Investigating the use of local search for improving meta-hyperheuristic performance. In: Evolutionary Computation (CEC). IEEE: Brisbane, Australia, pp 1-8.

    Han L and Kendall G (2003). Guided operators for a hyper - heuristic genetic algorithm. In: Gedeon TD and Fung LCC (eds). The 16th Australian Conference on Artificial Intelligence (AI 03). Springer: Perth, Australia, pp 807-820.

    Hart E and Ross P (1998). A heuristic combination method for solving job-shop scheduling problems. In: Eiben AE, Ba¨ck T, Schoenauer M and Schwefel H-P (eds). Parallel Problem Solving from Nature, PPSN V. Lecture Notes in Computer Science, Springer: Amsterdam, the Netherlands, pp 845-854.

    Hart E, Ross P and Nelson JAD (1998). Solving a real-world problem using an evolving heuristically driven schedule builder. Evolutionary Computing 6(1): 61-80.

    He J, He F and Dong H (2012). Pure strategy or mixed strategy?- An initial comparison of their asymptotic convergence rate and asymptotic hitting time. In: Hao JK and Middendorf M (eds). Evolutionary Computation in Combinatorial Optimization-12th European Conference, EvoCOP 2012. Málaga, Spain, 11-13 April 2012. Proceedings, Lecture Notes in Computer Science, Vol. 7245, Springer, pp 218-229.

    Ho NB and Tay JC (2005). Evolving dispatching rules for solving the flexible job-shop problem. In: IEEE Congress on Evolutionary Computation (CEC'05). IEEE: Edinburgh, UK, pp 2848-2855.

  • Metrics
    No metrics available
Share - Bookmark