IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v285y2020i2p405-428.html
   My bibliography  Save this article

Recent advances in selection hyper-heuristics

Author

Listed:
  • Drake, John H.
  • Kheiri, Ahmed
  • Özcan, Ender
  • Burke, Edmund K.

Abstract

Hyper-heuristics have emerged as a way to raise the level of generality of search techniques for computational search problems. This is in contrast to many approaches, which represent customised methods for a single problem domain or a narrow class of problem instances. The term hyper-heuristic was defined in the early 2000s as a heuristic to choose heuristics, but the idea of designing high-level heuristic methodologies can be traced back to the early 1960s. The current state-of-the-art in hyper-heuristic research comprises a set of methods that are broadly concerned with intelligently selecting or generating a suitable heuristic for a given situation. Hyper-heuristics can be considered as search methods that operate on lower-level heuristics or heuristic components, and can be categorised into two main classes: heuristic selection and heuristic generation. Here we will focus on the first of these two categories, selection hyper-heuristics. This paper gives a brief history of this emerging area, reviews contemporary selection hyper-heuristic literature, and discusses recent selection hyper-heuristic frameworks. In addition, the existing classification of selection hyper-heuristics is extended, in order to reflect the nature of the challenges faced in contemporary research. Unlike the survey on hyper-heuristics published in 2013, this paper focuses only on selection hyper-heuristics and presents critical discussion, current research trends and directions for future research.

Suggested Citation

  • Drake, John H. & Kheiri, Ahmed & Özcan, Ender & Burke, Edmund K., 2020. "Recent advances in selection hyper-heuristics," European Journal of Operational Research, Elsevier, vol. 285(2), pages 405-428.
  • Handle: RePEc:eee:ejores:v:285:y:2020:i:2:p:405-428
    DOI: 10.1016/j.ejor.2019.07.073
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221719306526
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2019.07.073?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Li, Wenwen & Özcan, Ender & John, Robert, 2017. "Multi-objective evolutionary algorithms and hyper-heuristics for wind farm layout optimisation," Renewable Energy, Elsevier, vol. 105(C), pages 473-482.
    2. Nelishia Pillay, 2016. "A review of hyper-heuristics for educational timetabling," Annals of Operations Research, Springer, vol. 239(1), pages 3-38, April.
    3. Raidl, Günther R., 2015. "Decomposition based hybrid metaheuristics," European Journal of Operational Research, Elsevier, vol. 244(1), pages 66-76.
    4. Soria-Alcaraz, Jorge A. & Ochoa, Gabriela & Swan, Jerry & Carpio, Martin & Puga, Hector & Burke, Edmund K., 2014. "Effective learning hyper-heuristics for the course timetabling problem," European Journal of Operational Research, Elsevier, vol. 238(1), pages 77-86.
    5. Pierre Hansen & Nenad Mladenović & José Moreno Pérez, 2010. "Variable neighbourhood search: methods and applications," Annals of Operations Research, Springer, vol. 175(1), pages 367-407, March.
    6. Soria-Alcaraz, Jorge A. & Ochoa, Gabriela & Sotelo-Figeroa, Marco A. & Burke, Edmund K., 2017. "A methodology for determining an effective subset of heuristics in selection hyper-heuristics," European Journal of Operational Research, Elsevier, vol. 260(3), pages 972-983.
    7. J A Vázquez-Rodríguez & S Petrovic, 2013. "A mixture experiments multi-objective hyper-heuristic," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 64(11), pages 1664-1675, November.
    8. George Henrique Godim Fonseca & Haroldo Gambini Santos & Túlio Ângelo Machado Toffolo & Samuel Souza Brito & Marcone Jamilson Freitas Souza, 2016. "GOAL solver: a hybrid local search based solver for high school timetabling," Annals of Operations Research, Springer, vol. 239(1), pages 77-97, April.
    9. Chen, Yujie & Cowling, Peter & Polack, Fiona & Remde, Stephen & Mourdjis, Philip, 2017. "Dynamic optimisation of preventative and corrective maintenance schedules for a large scale urban drainage system," European Journal of Operational Research, Elsevier, vol. 257(2), pages 494-510.
    10. Ahmed, Leena & Mumford, Christine & Kheiri, Ahmed, 2019. "Solving urban transit route design problem using selection hyper-heuristics," European Journal of Operational Research, Elsevier, vol. 274(2), pages 545-559.
    11. Edmund K Burke & Michel Gendreau & Matthew Hyde & Graham Kendall & Gabriela Ochoa & Ender Özcan & Rong Qu, 2013. "Hyper-heuristics: a survey of the state of the art," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 64(12), pages 1695-1724, December.
    12. López-Ibáñez, Manuel & Dubois-Lacoste, Jérémie & Pérez Cáceres, Leslie & Birattari, Mauro & Stützle, Thomas, 2016. "The irace package: Iterated racing for automatic algorithm configuration," Operations Research Perspectives, Elsevier, vol. 3(C), pages 43-58.
    13. Ahmed Kheiri & Ender Özcan & Andrew J. Parkes, 2016. "A stochastic local search algorithm with adaptive acceptance for high-school timetabling," Annals of Operations Research, Springer, vol. 239(1), pages 135-151, April.
    14. Edmund Burke & Rong Qu & Amr Soghier, 2014. "Adaptive selection of heuristics for improving exam timetables," Annals of Operations Research, Springer, vol. 218(1), pages 129-145, July.
    15. Eduardo Segredo & Carlos Segura & Coromoto León, 2014. "Memetic algorithms and hyperheuristics applied to a multiobjectivised two-dimensional packing problem," Journal of Global Optimization, Springer, vol. 58(4), pages 769-794, April.
    16. Mustafa Misir & Pieter Smet & Greet Vanden Berghe, 2015. "An analysis of generalised heuristics for vehicle routing and personnel rostering problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 66(5), pages 858-870, May.
    17. Zhao, Ju & Zhou, Yong-Wu & Wahab, M.I.M., 2016. "Joint optimization models for shelf display and inventory control considering the impact of spatial relationship on demand," European Journal of Operational Research, Elsevier, vol. 255(3), pages 797-808.
    18. Edmund K. Burke & Matthew Hyde & Graham Kendall & Gabriela Ochoa & Ender Özcan & John R. Woodward, 2010. "A Classification of Hyper-heuristic Approaches," International Series in Operations Research & Management Science, in: Michel Gendreau & Jean-Yves Potvin (ed.), Handbook of Metaheuristics, chapter 0, pages 449-468, Springer.
    19. B Kiraz & A Ş Etaner-Uyar & E Özcan, 2013. "Selection hyper-heuristics in dynamic environments," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 64(12), pages 1753-1769, December.
    20. G Kendall & J Li, 2013. "Competitive travelling salesmen problem: A hyper-heuristic approach," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 64(2), pages 208-216, February.
    21. Aleksandra Swiercz & Edmund Burke & Mateusz Cichenski & Grzegorz Pawlak & Sanja Petrovic & Tomasz Zurkowski & Jacek Blazewicz, 2014. "Unified encoding for hyper-heuristics with application to bioinformatics," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 22(3), pages 567-589, September.
    22. Karapetyan, Daniel & Punnen, Abraham P. & Parkes, Andrew J., 2017. "Markov Chain methods for the Bipartite Boolean Quadratic Programming Problem," European Journal of Operational Research, Elsevier, vol. 260(2), pages 494-506.
    23. Kheiri, Ahmed & Özcan, Ender, 2016. "An iterated multi-stage selection hyper-heuristic," European Journal of Operational Research, Elsevier, vol. 250(1), pages 77-90.
    24. Burke, Edmund K. & Bykov, Yuri, 2017. "The late acceptance Hill-Climbing heuristic," European Journal of Operational Research, Elsevier, vol. 258(1), pages 70-78.
    25. Burke, Edmund K. & McCollum, Barry & Meisels, Amnon & Petrovic, Sanja & Qu, Rong, 2007. "A graph-based hyper-heuristic for educational timetabling problems," European Journal of Operational Research, Elsevier, vol. 176(1), pages 177-192, January.
    26. Silvano Martello & David Pisinger & Paolo Toth, 1999. "Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem," Management Science, INFORMS, vol. 45(3), pages 414-424, March.
    27. Rahimian, Erfan & Akartunalı, Kerem & Levine, John, 2017. "A hybrid Integer Programming and Variable Neighbourhood Search algorithm to solve Nurse Rostering Problems," European Journal of Operational Research, Elsevier, vol. 258(2), pages 411-423.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Yannik Zeiträg & José Rui Figueira, 2023. "Automatically evolving preference-based dispatching rules for multi-objective job shop scheduling," Journal of Scheduling, Springer, vol. 26(3), pages 289-314, June.
    2. Gahm, Christian & Uzunoglu, Aykut & Wahl, Stefan & Ganschinietz, Chantal & Tuma, Axel, 2022. "Applying machine learning for the anticipation of complex nesting solutions in hierarchical production planning," European Journal of Operational Research, Elsevier, vol. 296(3), pages 819-836.
    3. Derya Deliktaş, 2022. "Self-adaptive memetic algorithms for multi-objective single machine learning-effect scheduling problems with release times," Flexible Services and Manufacturing Journal, Springer, vol. 34(3), pages 748-784, September.
    4. Zeren, Bahadır & Özcan, Ender & Deveci, Muhammet, 2024. "An adaptive greedy heuristic for large scale airline crew pairing problems," Journal of Air Transport Management, Elsevier, vol. 114(C).
    5. Ferreira, Cristiane & Figueira, Gonçalo & Amorim, Pedro, 2022. "Effective and interpretable dispatching rules for dynamic job shops via guided empirical learning," Omega, Elsevier, vol. 111(C).
    6. Lagos, Felipe & Pereira, Jordi, 2024. "Multi-armed bandit-based hyper-heuristics for combinatorial optimization problems," European Journal of Operational Research, Elsevier, vol. 312(1), pages 70-91.
    7. Gianfranco Chicco & Andrea Mazza, 2020. "Metaheuristic Optimization of Power and Energy Systems: Underlying Principles and Main Issues of the ‘Rush to Heuristics’," Energies, MDPI, vol. 13(19), pages 1-38, September.
    8. Ruiz-Meza, José & Montoya-Torres, Jairo R., 2022. "A systematic literature review for the tourist trip design problem: Extensions, solution techniques and future research lines," Operations Research Perspectives, Elsevier, vol. 9(C).
    9. Zhang, Yuchang & Bai, Ruibin & Qu, Rong & Tu, Chaofan & Jin, Jiahuan, 2022. "A deep reinforcement learning based hyper-heuristic for combinatorial optimisation with uncertainties," European Journal of Operational Research, Elsevier, vol. 300(2), pages 418-427.
    10. Jorge Pérez-Aracil & Carlos Camacho-Gómez & Eugenio Lorente-Ramos & Cosmin M. Marina & Laura M. Cornejo-Bueno & Sancho Salcedo-Sanz, 2023. "New Probabilistic, Dynamic Multi-Method Ensembles for Optimization Based on the CRO-SL," Mathematics, MDPI, vol. 11(7), pages 1-22, March.
    11. Swan, Jerry & Adriaensen, Steven & Brownlee, Alexander E.I. & Hammond, Kevin & Johnson, Colin G. & Kheiri, Ahmed & Krawiec, Faustyna & Merelo, J.J. & Minku, Leandro L. & Özcan, Ender & Pappa, Gisele L, 2022. "Metaheuristics “In the Large”," European Journal of Operational Research, Elsevier, vol. 297(2), pages 393-406.
    12. Butterwick, Thomas & Kheiri, Ahmed & Lulli, Guglielmo & Gromicho, Joaquim & Kreeft, Jasper, 2023. "Application of selection hyper-heuristics to the simultaneous optimisation of turbines and cabling within an offshore windfarm," Renewable Energy, Elsevier, vol. 208(C), pages 1-16.
    13. Hamdi Abdi, 2023. "A Survey of Combined Heat and Power-Based Unit Commitment Problem: Optimization Algorithms, Case Studies, Challenges, and Future Directions," Mathematics, MDPI, vol. 11(19), pages 1-36, October.
    14. Goerigk, Marc & Hartisch, Michael, 2023. "A framework for inherently interpretable optimization models," European Journal of Operational Research, Elsevier, vol. 310(3), pages 1312-1324.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Swan, Jerry & Adriaensen, Steven & Brownlee, Alexander E.I. & Hammond, Kevin & Johnson, Colin G. & Kheiri, Ahmed & Krawiec, Faustyna & Merelo, J.J. & Minku, Leandro L. & Özcan, Ender & Pappa, Gisele L, 2022. "Metaheuristics “In the Large”," European Journal of Operational Research, Elsevier, vol. 297(2), pages 393-406.
    2. Zhang, Yuchang & Bai, Ruibin & Qu, Rong & Tu, Chaofan & Jin, Jiahuan, 2022. "A deep reinforcement learning based hyper-heuristic for combinatorial optimisation with uncertainties," European Journal of Operational Research, Elsevier, vol. 300(2), pages 418-427.
    3. Johnes, Jill, 2015. "Operational Research in education," European Journal of Operational Research, Elsevier, vol. 243(3), pages 683-696.
    4. Lagos, Felipe & Pereira, Jordi, 2024. "Multi-armed bandit-based hyper-heuristics for combinatorial optimization problems," European Journal of Operational Research, Elsevier, vol. 312(1), pages 70-91.
    5. Kheiri, Ahmed & Özcan, Ender, 2016. "An iterated multi-stage selection hyper-heuristic," European Journal of Operational Research, Elsevier, vol. 250(1), pages 77-90.
    6. Soria-Alcaraz, Jorge A. & Ochoa, Gabriela & Sotelo-Figeroa, Marco A. & Burke, Edmund K., 2017. "A methodology for determining an effective subset of heuristics in selection hyper-heuristics," European Journal of Operational Research, Elsevier, vol. 260(3), pages 972-983.
    7. Chen, Yujie & Cowling, Peter & Polack, Fiona & Remde, Stephen & Mourdjis, Philip, 2017. "Dynamic optimisation of preventative and corrective maintenance schedules for a large scale urban drainage system," European Journal of Operational Research, Elsevier, vol. 257(2), pages 494-510.
    8. W. B. Yates & E. C. Keedwell, 2019. "An analysis of heuristic subsequences for offline hyper-heuristic learning," Journal of Heuristics, Springer, vol. 25(3), pages 399-430, June.
    9. Venkatesh Pandiri & Alok Singh, 2020. "Two multi-start heuristics for the k-traveling salesman problem," OPSEARCH, Springer;Operational Research Society of India, vol. 57(4), pages 1164-1204, December.
    10. Longlong Leng & Yanwei Zhao & Zheng Wang & Jingling Zhang & Wanliang Wang & Chunmiao Zhang, 2019. "A Novel Hyper-Heuristic for the Biobjective Regional Low-Carbon Location-Routing Problem with Multiple Constraints," Sustainability, MDPI, vol. 11(6), pages 1-31, March.
    11. Lale Özbakır & Gökhan Seçme, 2022. "A hyper-heuristic approach for stochastic parallel assembly line balancing problems with equipment costs," Operational Research, Springer, vol. 22(1), pages 577-614, March.
    12. Ahmed Kheiri, 2020. "Heuristic Sequence Selection for Inventory Routing Problem," Transportation Science, INFORMS, vol. 54(2), pages 302-312, March.
    13. Aleksandra Swiercz & Edmund Burke & Mateusz Cichenski & Grzegorz Pawlak & Sanja Petrovic & Tomasz Zurkowski & Jacek Blazewicz, 2014. "Unified encoding for hyper-heuristics with application to bioinformatics," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 22(3), pages 567-589, September.
    14. Nelishia Pillay, 2016. "A review of hyper-heuristics for educational timetabling," Annals of Operations Research, Springer, vol. 239(1), pages 3-38, April.
    15. Yanwei Zhao & Longlong Leng & Chunmiao Zhang, 2021. "A novel framework of hyper-heuristic approach and its application in location-routing problem with simultaneous pickup and delivery," Operational Research, Springer, vol. 21(2), pages 1299-1332, June.
    16. Ahmed Kheiri & Alina G. Dragomir & David Mueller & Joaquim Gromicho & Caroline Jagtenberg & Jelke J. Hoorn, 2019. "Tackling a VRP challenge to redistribute scarce equipment within time windows using metaheuristic algorithms," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(5), pages 561-595, December.
    17. Gahm, Christian & Uzunoglu, Aykut & Wahl, Stefan & Ganschinietz, Chantal & Tuma, Axel, 2022. "Applying machine learning for the anticipation of complex nesting solutions in hierarchical production planning," European Journal of Operational Research, Elsevier, vol. 296(3), pages 819-836.
    18. Derya Deliktaş, 2022. "Self-adaptive memetic algorithms for multi-objective single machine learning-effect scheduling problems with release times," Flexible Services and Manufacturing Journal, Springer, vol. 34(3), pages 748-784, September.
    19. Carlos Contreras Bolton & Gustavo Gatica & Víctor Parada, 2013. "Automatically Generated Algorithms for the Vertex Coloring Problem," PLOS ONE, Public Library of Science, vol. 8(3), pages 1-9, March.
    20. Kallestad, Jakob & Hasibi, Ramin & Hemmati, Ahmad & Sörensen, Kenneth, 2023. "A general deep reinforcement learning hyperheuristic framework for solving combinatorial optimization problems," European Journal of Operational Research, Elsevier, vol. 309(1), pages 446-468.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:285:y:2020:i:2:p:405-428. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.