Empirical Evidence of the Effectiveness of Primitive Granularity Control for Hyper-Heuristics
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.
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
2019 Genetic and Evolutionary Computation Conference, GECCO 2019 (2019: Jul. 13-17, Prague, Czech Republic)
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)
Article - Conference proceedings
© 2019 Association for Computing Machinery (ACM), All rights reserved.