Modified choice function heuristic selection for the Multidimensional Knapsack Problem

Abstract

Hyper-heuristics are a class of high-level search methods used to solve computationally difficult problems, which operate on a search space of low-level heuristics rather than solutions directly. Previous work has shown that selection hyper-heuristics are able to solve many combinatorial optimisation problems, including the multidimensional 0-1 knapsack problem (MKP). The traditional framework for iterative selection hyper-heuristics relies on two key components, a heuristic selection method and a move acceptance criterion. Existing work has shown that a hyper-heuristic using Modified Choice Function heuristic selection can be effective at solving problems in multiple problem domains. Late Acceptance Strategy is a hill climbing metaheuristic strategy often used as a move acceptance criteria in selection hyper-heuristics. This work compares a Modified Choice Function - Late Acceptance Strategy hyper-heuristic to an existing selection hyper-heuristic method from the literature which has previously performed well on standard MKP benchmarks.

Citation

Drake, J. H., Özcan, E., & Burke, E. K. (2014). Modified choice function heuristic selection for the Multidimensional Knapsack Problem. In Genetic and evolutionary computing (225–234). https://doi.org/10.1007/978-3-319-12286-1_23

• Conference Name: Eighth International Conference on Genetic and Evolutionary Computing
• Conference Location: Nanchang, China
• Start Date: Oct 18, 2014
• End Date: Oct 20, 2014
• Acceptance Date: Oct 18, 2014
• Online Publication Date: Sep 30, 2014
• Publication Date: Oct 27, 2014
• Deposit Date: Jun 13, 2016
• Electronic ISSN: 2194-5357
• Publisher: Springer Verlag
• Peer Reviewed: Peer Reviewed
• Issue: 329
• Pages: 225–234
• Series Title: Advances in Intelligent Systems and Computing
• Series Number: 329
• Series ISSN: 2194-5365
• Book Title: Genetic and evolutionary computing
• ISBN: 9783319122854
• DOI: https://doi.org/10.1007/978-3-319-12286-1_23
• Keywords: Hyper-heuristics, Choice Function, Heuristic Selection, Multidimensional Knapsack Problem, Combinatorial Optimization
• Public URL: https://nottingham-repository.worktribe.com/output/737958
• Publisher URL: http://link.springer.com/chapter/10.1007%2F978-3-319-12286-1_23