Skip to main content

Research Repository

Advanced Search

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

Drake, John H.; Özcan, Ender; Burke, Edmund

Authors

John H. Drake

Edmund Burke



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 http://eprints.nottingham.ac.uk/id/eprint/32189
Publisher URL https://www.mitpressjournals.org/doi/abs/10.1162/EVCO_a_00145
Copyright Statement Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf
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.

Files


xover_MKP.pdf (213 Kb)
PDF

Copyright Statement
Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf





You might also like



Downloadable Citations