On the Synthesis of Perturbative Heuristics for Multiple Combinatorial Optimisation Domains

Stone, Christopher; Hart, Emma; Paechter, Ben

Abstract

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.

Citation

Stone, C., Hart, E., & Paechter, B. (2018). On the Synthesis of Perturbative Heuristics for Multiple Combinatorial Optimisation Domains. In Parallel Problem Solving from Nature – PPSN XV 15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part I. https://doi.org/10.1007/978-3-319-99253-2_14

• Conference Name: Fifteenth International Conference on Parallel Problem Solving from Nature (PPSN XV)
• Conference Location: Coimbra, Portugal
• Start Date: Sep 8, 2018
• End Date: Sep 12, 2018
• Acceptance Date: May 14, 2018
• Online Publication Date: Aug 22, 2018
• Publication Date: 2018
• Deposit Date: Jun 25, 2018
• Publicly Available Date: Jun 25, 2018
• Publisher: Springer
• Series Title: Lecture Notes in Computer Science
• Series Number: 11101
• Series ISSN: 0302-9743
• Book Title: Parallel Problem Solving from Nature – PPSN XV 15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part I
• ISBN: 978-3-319-99252-5
• DOI: https://doi.org/10.1007/978-3-319-99253-2_14
• Keywords: Hyper-heuristic frameworks, novel method, multiple domains, grammatical evolution
• Public URL: http://researchrepository.napier.ac.uk/Output/1234659