Choosing the Fittest Subset of Low Level Heuristics in a Hyperheuristic Framework | SpringerLink
Skip to main content
Springer Nature Link
Log in

Choosing the Fittest Subset of Low Level Heuristics in a Hyperheuristic Framework

  • Conference paper
Evolutionary Computation in Combinatorial Optimization (EvoCOP 2005)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3448))

  • 794 Accesses

Abstract

A hyperheuristic is a high level procedure which searches over a space of low level heuristics rather than directly over the space of problem solutions. The sequence of low level heuristics, applied in an order which is intelligently determined by the hyperheuristic, form a solution method for the problem. In this paper, we consider a hyperheuristic-based methodology where a large set of low level heuristics is constructed by combining simple selection rules. Given sufficient time, this approach is able to achieve high quality results for a real-world personnel scheduling problem. However, some low level heuristics in the set do not make valuable contributions to the search and only slow down the solution process. We introduce learning strategies into hyperheuristics in order to select a fit subset of low level heuristics tailored to a particular problem instance. We compare a range of selection approaches applied to a varied collection of real-world personnel scheduling problem instances.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Ernst, A.T., Jiang, H., Krishnamoorthy, M., Sier, D.: Staff Scheduling and Rostering: A Review of Applications. Methods and Models. European Journal of Operational Research 153, 3–27 (2004)

    MATH  MathSciNet  Google Scholar 

  2. Burke, E., Kendall, G., Newall, J., Hart, E., Ross, P., Schulenburg, S.: An Emerging Direction in Modern Search Technology. In: Glover, F., Kochenberger, G.A. (eds.) Handbook of Metaheuristics, pp. 457–474. Kluwer Academic Publishers, Dordrecht (2003)

    Google Scholar 

  3. Cowling, P., Kendall, G., Soubeiga, E.: A Hyperheuristic Approach to Scheduling a Sales Summit. In: Burke, E., Erben, W. (eds.) PATAT 2000. LNCS, vol. 2079, pp. 176–190. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  4. Gratch, J., Chien, S.: Adaptive Problem-Solving for Large-Scale Scheduling Problems: A Case Study. Journal of Artificial Intelligence Research 4, 365–396 (1996)

    Google Scholar 

  5. Nareyek, A.: Choosing Search Heuristics by Non-Stationary Reinforcement Learning. In: Resende, M., de Souza, J. (eds.) Metaheuristics: Computer Decision-Making, pp. 523–544. Kluwer Academic Publishers, Dordrecht (2003)

    Google Scholar 

  6. Ross, P., Schulenburg, S., Marín-Blázquez, J.G., Hart, E.: Hyper-Heuristics: Learning to Combine Simple Heuristics in Bin-packing Problems. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2002), pp. 942–948. Morgan Kauffmann, San Francisco (2002)

    Google Scholar 

  7. Hart, E., Ross, P., Nelson, J.: Solving a Real-World Problem Using an Evolving Heuristically Driven Schedule Builder. Evolutionary Computation 6, 61–80 (1998)

    Article  Google Scholar 

  8. Cowling, P., Kendall, G., Han, L.: An Investigation of a Hyperheuristic Genetic Algorithm Applied to a Trainer Scheduling Problem. In: Proceedings of 2002 Congress on Evolutionary Computation (CEC 2002), pp. 1185–1190. IEEE Computer Society Press, Honolulu (2002)

    Chapter  Google Scholar 

  9. Han, L., Kendall, G., Cowling, P.: An Adaptive Length Chromosome Hyperheuristic Genetic Algorithm for a Trainer Scheduling Problem. In: Proceedings of the 4th Asia-Pacific Conference on Simulated Evolution and Learning (SEAL 2002), Orchid Country Club, Singapore, pp. 267–271 (2002)

    Google Scholar 

  10. Burke, E., Kendall, G., Soubeiga, E.: A Tabu-Search Hyperheuristic for Timetabling and Rostering. Journal of Heuristics 9, 451–470 (2003)

    Article  Google Scholar 

  11. Cowling, P., Kendall, G., Soubeiga, E.: A Parameter-Free Hyperheuristic for Scheduling a Sales Summit. In: Proceedings of the Third Metaheuristic International Conference (MIC 2001), Porto, Portugal, pp. 127–131 (2001)

    Google Scholar 

  12. Corne, D., Ross, P.: Peckish Initialisation Strategies for Evolutionary Timetabling. In: Burke, E.K., Ross, P. (eds.) PATAT 1995. LNCS, vol. 1153, pp. 227–240. Springer, Heidelberg (1996)

    Google Scholar 

  13. Cowling, P., Chakhlevitch, K.: Hyperheuristics for Managing a Large Collection of Low Level Heuristics to Schedule Personnel. In: Proceedings of the 2003 IEEE Congress on Evolutionary Computation (CEC 2003), pp. 1214–1221. IEEE Computer Society Press, Canberra (2003)

    Chapter  Google Scholar 

  14. Chakhlevitch, K.: Hyperheuristics Which Manage Large Collections of Low Level Heuristics. PhD thesis (in preparation)

    Google Scholar 

  15. Glover, F., Laguna, M.: Tabu Search. Kluwer Academic Publishers, Dordrecht (1997)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. MOSAIC Research Centre, Department of Computing, University of Bradford, Bradford, BD7 1DP, United Kingdom

    Konstantin Chakhlevitch & Peter Cowling

Authors
  1. Konstantin Chakhlevitch
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Peter Cowling
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Institute of Computer Graphics and Algorithms, Vienna University of Technology, Favoritenstraße 9–11/1861, 1040, Vienna, Austria

    Günther R. Raidl

  2. SAP AG, Neurottstr. 16, P.O. Box, Walldorf, Germany

    Jens Gottlieb

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Chakhlevitch, K., Cowling, P. (2005). Choosing the Fittest Subset of Low Level Heuristics in a Hyperheuristic Framework. In: Raidl, G.R., Gottlieb, J. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2005. Lecture Notes in Computer Science, vol 3448. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-31996-2_3

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-31996-2_3

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-25337-2

  • Online ISBN: 978-3-540-31996-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation