[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Searching the Hyper-heuristic Design Space

  • Published:
Cognitive Computation Aims and scope Submit manuscript

Abstract

We extend a previous mathematical formulation of hyper-heuristics to reflect the emerging generalization of the concept. We show that this leads naturally to a recursive definition of hyper-heuristics and to a division of responsibility that is suggestive of a blackboard architecture, in which individual heuristics annotate a shared workspace with information that may also be exploited by other heuristics. Such a framework invites consideration of the kind of relaxations of the domain barrier that can be achieved without loss of generality. We give a concrete example of this architecture with an application to the 3-SAT domain that significantly improves on a related token-ring hyper-heuristic.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. http://www.cs.ubc.ca/hoos/SATLIB/benchm.html

Reference

  1. Bishop JM, Erden YJ. Computational creativity, intelligence and autonomy. Cognit Comput. 2012;4(3):209–1.

    Article  Google Scholar 

  2. Kendall G, Su Y. Imperfect evolutionary systems, Evolutionary Computation. IEEE Trans. 2007;11(3):294–7 doi:10.1109/TEVC.2006.887348.

    Google Scholar 

  3. d’Inverno M, Luck M. Creativity through autonomy and interaction. Cognit Comput. 2012;4(3):332–46.

    Article  Google Scholar 

  4. Burke EK, Hyde M, Kendall G, Ochoa G, Ozcan E, Woodward JR. A classification of hyper-heuristics approaches. In: Gendreau M, Potvin J-Y, editors. Handbook of metaheuristics, 2nd Edition, vol 57 of international series in operations research & management science. Berlin:Springer; 2010. Ch. 15, p. 449–68.

  5. Hayes-Roth B. A blackboard architecture for control. Artif Intell. 1985;26(3):251–21.

    Article  Google Scholar 

  6. Denzinger J, Fuchs M, Fuchs M. High performance ATP systems by combining several AI methods, Tech. rep., University of Kaiserslautern 1997.

  7. Burke EK, Kendall G, Soubeiga E . A tabu-search hyperheuristic for timetabling and rostering. J Heuristics. 2003;9(6):451–70.

    Article  Google Scholar 

  8. Rattadilok P, Gaw A, Kwan RK. Distributed choice function hyper-heuristics for timetabling and scheduling. In: Burke E, Trick M, editors. Practice and theory of automated timetabling, vol. 3616 of Lecture Notes in Computer Science. Springer: Berlin; 2005. p. 51–67.

  9. Cowling P, Chekhlevitch K. Hyperheuristics for managing a large collection of low-level heuristics to schedule personnel. In: The 2003 congress on evolutionary computation (CEC ‘03), vol. 2; 2003. p. 1214–21.

  10. Woodward J, Parkes A, Ochoa G. A mathematical formalization of hyper-heuristics, Presented to the ’Workshop on Hyper-Heuristics’ at 10th international conference on parallel problem solving from nature (PPSN-08), Technische University Dortmund, Germany. (September 2008).

  11. Peyton Jones S, et al. The Haskell 98 language and libraries: the revised report. J Funct Program. 2003;13(1):0–255 http://www.haskell.org/definition/

  12. Battiti R, Tecchiolli G. The reactive tabu search. INFORMS J Comput 1994;6(2):126–40.

    Article  Google Scholar 

  13. Spinellis D. Another level of indirection. In: Oram A, Wilson G editors. Beautiful code: leading programmers explain how they think. Sebastopol: O’Reilly and Associates; 2007. Ch. 17, p. 279–91.

  14. Swan J, Özcan E, Kendall G. Hyperion - a recursive hyper-heuristic framework. In: Coello C editors. Learning and intelligent optimization, Vol. 6683 of Lecture Notes in Computer Science. Springer: Berlin; 2011. p. 616–30.

  15. Glover F. Tabu search-Part I. INFORMS J Comput 1989;1(3):190–206

    Article  Google Scholar 

  16. Kaelbling LP, Littman ML, Moore AW. Reinforcement learning: a survey. J Artif Intell Res (JAIR) 1996;4:237–85.

    Google Scholar 

  17. Glover F. Tabu search-Part II. INFORMS J Comput 1990;2(1):4–32.

    Article  Google Scholar 

  18. Eiben AE, Ruttkay Z. Self-adaptivity for constraint satisfaction: learning penalty functions In: International conference on evolutionary computation. 1996, p. 258–61.

  19. Marín-Blázquez JG, Schulenburg S. A hyper-heuristic framework with xcs: learning to create novel problem-solving algorithms constructed from simpler algorithmic ingredients. In: IWLCS, 2005, p. 193–218.

  20. Burke EK, Petrovic S, Qu R. Case-based heuristic selection for timetabling problems. J Sched. 2006;9(2):115–32.

    Article  Google Scholar 

  21. Burke EK, Hyde MR, Kendall G, Ochoa G, Ozcan E, Woodward JR. Exploring hyper-heuristic methodologies with genetic programming. In: Mumford CL, Jain LC editors. Computational intelligence, Vol. 1 of intelligent systems reference library. Berlin:Springer; 2009. Ch. 6, p. 177–201.

  22. Stadler PF. Landscapes and their correlation functions. J Math Chem. 1996;20:1–45. doi:10.1007/BF01165154.

    Article  CAS  Google Scholar 

  23. Stadler PF. Towards a theory of landscapes. In: Lpez-Pena R, Capovilla R, Garca-Pelayo R, Waelbroeck H, Zertuche F editors. Complex systems and binary networks, Vol. 461 of Lecture notes in physics. Berlin: Springer; 1995. p. 77–163.

    Google Scholar 

  24. Hordijk W. A measure of landscapes. Evol Comput 1997;4(4):335–60.

    Article  Google Scholar 

  25. Reeves CR. Landscapes, operators and heuristic search. Ann Oper Res 1999;86:473–90.

    Article  Google Scholar 

  26. Reeves CR. Fitness landscapes and evolutionary algorithms. In: AE ’99: selected papers from the 4th European conference on artificial evolution. London: Springer; 2000. p. 3–20.

  27. Kallel L, Naudts B, Reeves CR. Properties of fitness functions and search landscapes. London: Springer; 2001. p. 175–206.

    Google Scholar 

  28. Weinberger E. Correlated and uncorrelated fitness landscapes and how to tell the difference. Biol Cybern 1990;63(5):325–36.

    Article  Google Scholar 

  29. Berry DA, Fristedt B. Bandit problems: sequential allocation of experiments. Berlin: Springer; 1985.

    Book  Google Scholar 

  30. Dzeroski S, Todorovski L. Discovering dynamics: From inductive logic programming to machine discovery. J Intell Inf Syst 1995;4:89–108 doi:10.1007/BF00962824.

    Article  Google Scholar 

  31. Milano M, Roli A. Magma: a multiagent architecture for metaheuristics, systems, man, and cybernetics, part B: cybernetics. IEEE Trans. 2004;34(2):925–941 doi:10.1109/TSMCB.2003.818432.

    Google Scholar 

  32. Ouelhadj D, Petrovic S. A cooperative hyper-heuristic search framework. J Heuristics 2009;1–23 doi:10.1007/s10732-009-9122-6.

  33. Brooks R. Intelligence without representation. Artif Intell 1991;47:139–59.

    Article  Google Scholar 

  34. Burke E, Kendall G, Newall J, Hart E, Ross P, Schulenburg S. Hyper-heuristics: an emerging direction in modern search technology. In: Glover F, Kochenberger G, Hillier FS, editors. Handbook of Metaheuristics, Vol. 57 of international series in operations research and management science. New York: Springer; 2003. p. 457–74.

    Chapter  Google Scholar 

  35. Booch G, Maksimchuk RA, Engle MW, Young BJ, Connallen J, Houston KA. Object-oriented analysis and design with applications, third edition, ACM SIGSOFT software engineering notes 33(5).

  36. Carver N, Lesser V. The evolution of blackboard control architectures, Tech. rep., Amherst, USA; 1992.

  37. al Rifaie MM, Bishop JM, Caines S. Creativity and autonomy in swarm intelligence systems. Cognit Comput 2012;4(3):320–31.

    Article  Google Scholar 

  38. Kirkpatrick S, Gelatt CD, Vecchi MP. Optimization by simulated annealing. Science 1983;220:671–80.

    Article  CAS  PubMed  Google Scholar 

  39. White S. Concepts of scale in simulated annealing. In: Proceedings of international conference on computer design; 1984, p. 646–51.

  40. Hoos HH, Stützle T. SATLIB: An online resource for research on SAT. In: Gent IP, Maaren Hv, Walsh T, editors. SAT 2000, SATLIB is available online at http://www.satlib.org 2000.

  41. Xu L, Hutter F, Hoos HH, Leyton-Brown K. Satzilla: portfolio-based algorithm selection for sat. J Artif Int Res 2008;32(1):565–606.

    Google Scholar 

  42. Gaspero LD, Schaerf A. Easylocal++: an object-oriented framework for the flexible design of local-search algorithms. Softw Pract Exper 2003;33(8):733–765.

    Article  Google Scholar 

  43. Jones T, Forrest S. Fitness distance correlation as a measure of problem difficulty for genetic algorithms. In: Proceedings of the sixth international conference on genetic algorithms. Morgan Kaufmann; 1995. p. 184–92.

  44. Birattari M, Stützle T, Paquete L, Varrentrapp K. A racing algorithm for configuring metaheuristics. In: Proceedings of the genetic and evolutionary computation conference, GECCO ’02. San Francisco :Morgan Kaufmann Publishers Inc.; 2002. p. 11–18.

Download references

Author information

Authors and Affiliations

  1. Computing Science and Mathematics, School of Natural Sciences, University of Stirling, Stirling, FK9 4LA, Scotland, UK

    Jerry Swan, John Woodward & Edmund Burke

  2. School of Computer Science, University of Nottingham, Jubilee Campus, Wollaton Road, Nottingham, NG8 1BB, UK

    Ender Özcan & Graham Kendall

Authors
  1. Jerry Swan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. John Woodward
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ender Özcan
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Graham Kendall
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Edmund Burke
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jerry Swan.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Swan, J., Woodward, J., Özcan, E. et al. Searching the Hyper-heuristic Design Space. Cogn Comput 6, 66–73 (2014). https://doi.org/10.1007/s12559-013-9201-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12559-013-9201-8

Keywords

Search

Navigation