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

Stone, Christopher; Hart, Emma; Paechter, Ben

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.

Citation

Stone, C., Hart, E., & Paechter, B. (2021). A Cross-Domain Method for Generation of Constructive and Perturbative Heuristics. In N. Pillay, & R. Qu (Eds.), Automated Design of Machine Learning and Search Algorithms (91-107). Springer. https://doi.org/10.1007/978-3-030-72069-8_6

• 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