Research Output
A Cross-Domain Method for Generation of Constructive and Perturbative Heuristics
  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.

  • Date:

    29 July 2021

  • Publication Status:


  • Publisher

    Springer International Publishing

  • DOI:


  • Cross Ref:


  • Funders:

    Edinburgh Napier Funded


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.


Monthly Views:

Available Documents