Skip to main content

Research Repository

Advanced Search

A Cross-Domain Method for Generation of Constructive and Perturbative Heuristics

Stone, Christopher; Hart, Emma; Paechter, Ben

Authors

Christopher Stone



Contributors

Nelishia Pillay
Editor

Rong Qu
Editor

Abstract

Hyper-heuristic frameworks, although intended to be cross-domain at the highest level, usually rely on a set of domain-specific low-level heuristics which exist below the domain-barrier and are manipulated by the hyper-heuristic itself. However, for some domains, the number of available heuristics can be very low, while for novel problems, no heuristics might exist at all. We address this issue by describing two general methods for the automated production of constructive and perturbative low-level heuristics. Grammatical evolution is used to evolve low-level heuristics that operate on an “intermediate” graph-based representation built over partial permutations. As the same grammar can be applied to multiple application domains, assuming they follow this representation, the grammar can be viewed as a cross-domain. The method is evaluated on two domains to indicate generality (the Travelling Salesman Problem and Multidimensional Knapsack Problem). Empirical results indicate that the approach can generate both constructive and perturbative heuristics that outperform well-known heuristic methods in a number of cases and are competitive with specialised methods for some instances.

Online Publication Date Jul 29, 2021
Publication Date 2021
Deposit Date Feb 22, 2022
Publicly Available Date Jul 30, 2023
Publisher Springer
Pages 91-107
Book Title Automated Design of Machine Learning and Search Algorithms
ISBN 978-3-030-72071-1
DOI https://doi.org/10.1007/978-3-030-72069-8_6
Public URL http://researchrepository.napier.ac.uk/Output/2846712

Files

A Cross-Domain Method For Generation Of Constructive And Perturbative Heuristics (accepted version) (388 Kb)
PDF






You might also like



Downloadable Citations