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.

Meeting Name

2019 Genetic and Evolutionary Computation Conference, GECCO 2019 (2019: Jul. 13-17, Prague, Czech Republic)


Computer Science


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.

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)


Document Type

Article - Conference proceedings

Document Version


File Type





© 2019 Association for Computing Machinery (ACM), All rights reserved.