A Case Study of Controlling Crossover in a Selection Hyper-heuristic Framework Using the Multidimensional Knapsack Problem

Abstract

© 2016 by the Massachusetts Institute of Technology. Hyper-heuristics are high-level methodologies for solving complex problems that operate on a search space of heuristics. In a selection hyper-heuristic framework, a heuristic is chosen from an existing set of low-level heuristics and applied to the current solution to produce a new solution at each point in the search. The use of crossover lowlevel heuristics is possible in an increasing number of general-purpose hyper-heuristic tools such as HyFlex and Hyperion. However, little work has been undertaken to assess how best to utilise it. Since a single-point search hyper-heuristic operates on a single candidate solution, and two candidate solutions are required for crossover, a mechanism is required to control the choice of the other solution. The frameworks we propose maintain a list of potential solutions for use in crossover. We investigate the use of such lists at two conceptual levels. First, crossover is controlled at the hyper-heuristic level where no problem-specific information is required. Second, it is controlled at the problem domain level where problem-specific information is used to produce good-quality solutions to use in crossover. A number of selection hyperheuristics are compared using these frameworks over three benchmark libraries with varying properties for an NP-hard optimisation problem: the multidimensional 0-1 knapsack problem. It is shown that allowing crossover to be managed at the domain level outperforms managing crossover at the hyper-heuristic level in this problem domain.

Citation

Drake, J. H., Özcan, E., & Burke, E. (2016). A Case Study of Controlling Crossover in a Selection Hyper-heuristic Framework Using the Multidimensional Knapsack Problem. Evolutionary Computation, 24(1), 113-141. https://doi.org/10.1162/EVCO_a_00145

• Journal Article Type: Article
• Online Publication Date: Mar 10, 2016
• Publication Date: Mar 10, 2016
• Deposit Date: Mar 10, 2016
• Publicly Available Date: Mar 10, 2016
• Journal: Evolutionary Computation
• Print ISSN: 1063-6560
• Electronic ISSN: 1530-9304
• Publisher: Massachusetts Institute of Technology Press
• Peer Reviewed: Peer Reviewed
• Volume: 24
• Issue: 1
• Pages: 113-141
• DOI: https://doi.org/10.1162/EVCO_a_00145
• Keywords: Combinatorial optimisation, Hyper-heuristics, Local Search, Multidimensional Knapsack Problem, Metaheuristic
• Public URL: https://nottingham-repository.worktribe.com/output/742210
• Publisher URL: https://www.mitpressjournals.org/doi/abs/10.1162/EVCO_a_00145
• Additional Information: © Massachussets Institue of Technology. Drake, John H and Özcan, Ender and Burke, Edmund. A case study of controlling crossover in a selection hyper-heuristic framework using the multidimensional knapsack problem. Evolutionary computation, 2015.