IDEAS home Printed from https://ideas.repec.org/a/spr/joheur/v25y2019i3d10.1007_s10732-018-09404-7.html
   My bibliography  Save this article

An analysis of heuristic subsequences for offline hyper-heuristic learning

Author

Listed:
  • W. B. Yates

    (University of Exeter)

  • E. C. Keedwell

    (University of Exeter)

Abstract

A selection hyper-heuristic is used to minimise the objective functions of a well-known set of benchmark problems. The resulting sequences of low level heuristic selections and objective function values are used to generate a database of heuristic selections. The sequences in the database are broken down into subsequences and the mathematical concept of a logarithmic return is used to discriminate between “effective” subsequences, which tend to decrease the objective value, and “disruptive” subsequences, which tend to increase the objective value. These subsequences are then employed in a sequenced based hyper-heuristic and evaluated on an unseen set of benchmark problems. Empirical results demonstrate that the “effective” subsequences perform significantly better than the “disruptive” subsequences across a number of problem domains with 99% confidence. The identification of subsequences of heuristic selections that can be shown to be effective across a number of problems or problem domains could have important implications for the design of future sequence based hyper-heuristics.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:joheur:v:25:y:2019:i:3:d:10.1007_s10732-018-09404-7
    DOI: 10.1007/s10732-018-09404-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10732-018-09404-7
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10732-018-09404-7?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

    for a different version of it.

    References listed on IDEAS

    as
    1. 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.
    2. 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.
    3. 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.
    4. Ender Özcan & Mustafa Misir & Gabriela Ochoa & Edmund K. Burke, 2010. "A Reinforcement Learning - Great-Deluge Hyper-Heuristic for Examination Timetabling," International Journal of Applied Metaheuristic Computing (IJAMC), IGI Global Scientific Publishing, vol. 1(1), pages 39-59, January.
    Full references (including those not matched with items on IDEAS)

    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. 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.
    2. Johnes, Jill, 2015. "Operational Research in education," European Journal of Operational Research, Elsevier, vol. 243(3), pages 683-696.
    3. Surafel Luleseged Tilahun & Mohamed A. Tawhid, 2019. "Swarm hyperheuristic framework," Journal of Heuristics, Springer, vol. 25(4), pages 809-836, October.
    4. Ahmed Kheiri, 2020. "Heuristic Sequence Selection for Inventory Routing Problem," Transportation Science, INFORMS, vol. 54(2), pages 302-312, March.
    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. 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.
    7. Nelishia Pillay, 2016. "A review of hyper-heuristics for educational timetabling," Annals of Operations Research, Springer, vol. 239(1), pages 3-38, April.
    8. 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.
    9. 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.
    10. Folarin B. Oyebolu & Jeroen Lidth de Jeude & Cyrus Siganporia & Suzanne S. Farid & Richard Allmendinger & Juergen Branke, 2017. "A new lot sizing and scheduling heuristic for multi-site biopharmaceutical production," Journal of Heuristics, Springer, vol. 23(4), pages 231-256, August.
    11. 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.
    12. 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.
    13. Wilson, Dennis & Rodrigues, Silvio & Segura, Carlos & Loshchilov, Ilya & Hutter, Frank & Buenfil, Guillermo López & Kheiri, Ahmed & Keedwell, Ed & Ocampo-Pineda, Mario & Özcan, Ender & Peña, Sergio Iv, 2018. "Evolutionary computation for wind farm layout optimization," Renewable Energy, Elsevier, vol. 126(C), pages 681-691.
    14. Andrzej Kozik, 2017. "Handling precedence constraints in scheduling problems by the sequence pair representation," Journal of Combinatorial Optimization, Springer, vol. 33(2), pages 445-472, February.
    15. 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.
    16. Raidl, Günther R., 2015. "Decomposition based hybrid metaheuristics," European Journal of Operational Research, Elsevier, vol. 244(1), pages 66-76.
    17. Yikai Ma & Wenjuan Zhang & Juergen Branke, 2024. "Genetic programming hyper-heuristic for evolving a maintenance policy for wind farms," Journal of Heuristics, Springer, vol. 30(5), pages 423-451, December.
    18. 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.
    19. Stefan Vonolfen & Michael Affenzeller, 2016. "Distribution of waiting time for dynamic pickup and delivery problems," Annals of Operations Research, Springer, vol. 236(2), pages 359-382, January.
    20. Olacir R. Castro & Gian Mauricio Fritsche & Aurora Pozo, 2018. "Evaluating selection methods on hyper-heuristic multi-objective particle swarm optimization," Journal of Heuristics, Springer, vol. 24(4), pages 581-616, August.

    More about this item

    Keywords

    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:spr:joheur:v:25:y:2019:i:3:d:10.1007_s10732-018-09404-7. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.