Research Output

On the Synthesis of Perturbative Heuristics for Multiple Combinatorial Optimisation Domains

  Hyper-heuristic frameworks, although intended to be cross-domain at the highest level, rely on a set of domain-specific low-level heuristics at lower levels. For some domains, there is a lack of available heuristics, while for novel problems, no heuristics might exist. We address this issue by introducing a novel method, applicable in multiple domains, that constructs new low-level heuristics for a domain. The method uses grammatical evolution to construct iterated local search heuristics: it can be considered cross-domain in that the same grammar can evolve heuristics in multiple domains without requiring any modification, assuming that solutions are represented in the same form. We evaluate the method using benchmarks from the travelling-salesman (TSP) and multi-dimensional knapsack (MKP) domain. Comparison to existing methods demonstrates that the approach generates low-level heuristics that out-perform heuristic methods for TSP and are competitive for MKP.

  • Date:

    14 May 2018

  • Publication Status:

    Accepted

  • Library of Congress:

    QA75 Electronic computers. Computer science

  • Dewey Decimal Classification:

    005 Computer programming, programs & data

  • Funders:

    Edinburgh Napier Funded

Citation

Stone, C., Hart, E., & Paechter, B. (in press). On the Synthesis of Perturbative Heuristics for Multiple Combinatorial Optimisation Domains. In Proceedings of PPSN Conference 2018

Authors

Keywords

Hyper-heuristic frameworks, novel method, multiple domains, grammatical evolution,

Monthly Views: