John H. Drake
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
ENDER OZCAN ender.ozcan@nottingham.ac.uk
Professor of Computer Science and Operational Research
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 | 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. |
Files
xover_MKP.pdf
(213 Kb)
PDF
You might also like
CUDA-based parallel local search for the set-union knapsack problem
(2024)
Journal Article
A benchmark dataset for multi-objective flexible job shop cell scheduling
(2023)
Journal Article
Downloadable Citations
About Repository@Nottingham
Administrator e-mail: discovery-access-systems@nottingham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search