Empirical Evidence of the Effectiveness of Primitive Granularity Control for Hyper-Heuristics
Abstract
The set of primitive operations available to a generative hyper-heuristic can have a dramatic impact on the overall performance of the heuristic search in terms of efficiency and final solution quality. When constructing a primitive set, users are faced with a tradeoff between generality and time spent searching. A set consisting of low-level primitives provides the flexibility to find most or all potential solutions, but the resulting heuristic search space might be too large to find adequate solutions in a reasonable time frame. Conversely, a set of high-level primitives can enable faster discovery of mediocre solutions, but prevent the fine-tuning necessary to find the optimal heuristics. By varying the set of primitives throughout evolution, the heuristic search can utilize the advantages of both high-level and low-level primitive sets. This permits the heuristic search to either quickly traverse parts of the search space as needed or modify the minutiae of the search to find optimal solutions in reasonable amounts of time not feasible with implicit levels of primitive granularity. This paper demonstrates this potential by presenting empirical evidence of improvements to solvers for the Traveling Thief Problem, a combination of the Traveling Salesman Problem and the Knapsack Problem, a recent and difficult problem designed to more closely emulate real world complexity.
Recommended Citation
A. Harter et al., "Empirical Evidence of the Effectiveness of Primitive Granularity Control for Hyper-Heuristics," GECCO 2019 Companion -- Proceedings of the 2019 Genetic and Evolutionary Computation Conference Companion, pp. 1478 - 1486, Association for Computing Machinery (ACM), Jul 2019.
The definitive version is available at https://doi.org/10.1145/3319619.3326860
Meeting Name
2019 Genetic and Evolutionary Computation Conference, GECCO 2019 (2019: Jul. 13-17, Prague, Czech Republic)
Department(s)
Computer Science
Keywords and Phrases
Combinatorial optimization; Heuristic algorithms; Heuristic methods; Modular robots; Traveling salesman problem, Granularity controls; Heuristic search; High level primitives; Hyper-heuristics; Knapsack problems; Optimal solutions; Primitive operations; Real-world complexity, Optimization
International Standard Book Number (ISBN)
978-145036748-6
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2019 Association for Computing Machinery (ACM), All rights reserved.
Publication Date
01 Jul 2019
Comments
This work was supported by Los Alamos National Laboratory via the Cyber Security Sciences Institute under subcontract 259565 and the Laboratory Directed Research and Development program of Los Alamos National Laboratory under project number 20170683ER.