- author = "John H. Drake",
- title = "Crossover Control in Selection Hyper-heuristics: Case Studies using {MKP} and {HyFlex}",
- school = "School of Computer Science, The University of Nottingham",
- year = "2014",
- address = "UK",
- month = jul,
- keywords = "genetic algorithms, genetic programming, hyper-heuristics, heuristic programming, knapsack problem, algorithms, search",
-
URL = "
http://eprints.nottingham.ac.uk/id/eprint/14276",
-
URL = "
http://eprints.nottingham.ac.uk/14276/1/thesis.pdf",
- size = "199 pages",
-
abstract = "Hyper-heuristics are a class of high-level search
methodologies which operate over a search space of
heuristics rather than a search space of solutions.
Hyper-heuristic research has set out to develop methods
which are more general than traditional search and
optimisation techniques. In recent years, focus has
shifted considerably towards cross-domain heuristic
search. The intention is to develop methods which are
able to deliver an acceptable level of performance over
a variety of different problem domains, given a set of
low-level heuristics to work with.
This thesis presents a body of work investigating the use of selection hyper-heuristics in a number of different problem domains. Specifically the use of crossover operators, prevalent in many evolutionary algorithms, is explored within the context of single-point search hyper-heuristics. A number of traditional selection hyper-heuristics are applied to instances of a well-known NP-hard combinatorial optimisation problem, the multidimensional knapsack problem. This domain is chosen as a benchmark for the variety of existing problem instances and solution methods available. The results suggest that selection hyper-heuristics are a viable method to solve some instances of this problem domain. Following this, a framework is defined to describe the conceptual level at which crossover low-level heuristics are managed in single-point selection hyper-heuristics. HyFlex is an existing software framework which supports the design of heuristic search methods over multiple problem domains, i.e. cross-domain optimisation. A traditional heuristic selection mechanism is modified in order to improve results in the context of cross-domain optimisation. Finally the effect of crossover use in cross-domain optimisation is explored.",
- notes = "Supervisors: Ender Ozcan",
