Back to search

University of Sheffield

On the Runtime Analysis of Selection Hyper-heuristics for Pseudo-Boolean Optimisation

Abstract

dc:description.abstract

Rather than manually deciding on a suitable algorithm configuration for a given optimisation problem, hyper-heuristics are high-level search algorithms which evolve the heuristic to be applied. While there are numerous reported successful applications of hyper-heuristics to combinatorial optimisation problems, it is not yet fully understood how well they perform and on which problem classes they are effective. Selection hyper-heuristics (SHHs) employ smart methodologies to select from a pre-defined set of low-level heuristics which to apply in the next decision step. This thesis extends and improves upon the existing foundational understanding of the behaviour and performance of SHHs, providing insights into how and when they can be successfully applied by analysing the time complexity of SHHs on a variety of unimodal and multimodal problem classes. Through a rigorous theoretical analysis, we show that while four commonly applied simple SHHs from the literature do not learn to select the most promising low-level heuristics, generalising them such that application of the chosen heuristic occurs over a longer period of time allows for vastly improved performance. Furthermore, we prove that extending the size of the set of low-level heuristics can improve the performance of the generalised SHHs, outperforming SHHs with smaller sets of low-level heuristics. We show that allowing the SHH to automatically adapt the length of the learning period may further improve the performance and outperform non-adaptive variants. SHHs selecting between two move-acceptance operators are also analysed on two classes of multimodal benchmark functions. An analysis of the performance of simple SHHs on these functions provides insights into the effectiveness of the presented methodologies for escaping from local optima.

Degree

thesis:*
Name dc:type.qualificationname
Ph.D
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Sheffield
Year dc:date.issued
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Warwicker, John A
Advisor dc:contributor.advisor
  • Oliveto, Pietro S

Rights

Language dc:language.dcterms_iso639_2
eng

Identifiers

dc:identifier.*
Identifier
uk.bl.ethos.786561

Chain of custody

source
Harvested from
White Rose University Consortium
Base URL
etheses.whiterose.ac.uk/cgi/oai2
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Warwicker, John A. On the Runtime Analysis of Selection Hyper-heuristics for Pseudo-Boolean Optimisation. doctoral thesis, University of Sheffield, 2019.