A Cross-Domain Method for Generation of Constructive and Perturbative Heuristics
Stone, Christopher; Hart, Emma; Paechter, Ben
Prof Emma Hart E.Hart@napier.ac.uk
Prof Ben Paechter B.Paechter@napier.ac.uk
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.
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|
|Deposit Date||Feb 22, 2022|
|Publicly Available Date||Jul 30, 2023|
|Book Title||Automated Design of Machine Learning and Search Algorithms|
This file is under embargo until Jul 30, 2023 due to copyright reasons.
Contact email@example.com to request a copy for personal use.
You might also like
Evolving planar mechanisms for the conceptual stage of mechanical design
2-Dimensional Outline Shape Representation for Generative Design with Evolutionary Algorithms
On the Synthesis of Perturbative Heuristics for Multiple Combinatorial Optimisation Domains