Runtime analysis of selection hyper-heuristics with classical learning mechanisms

Fawaz Alanazi, Per Kristian Lehre

Research output: Chapter in Book/Report/Conference proceedingConference contribution

22 Citations (Scopus)

Abstract

The term selection hyper-heuristics refers to a randomised search technique used to solve computational problems by choosing and executing heuristics from a set of pre-defined low-level heuristic components. Selection hyper-heuristics have been successfully employed in many problem domains. Nevertheless, a theoretical foundation of these heuristics is largely missing. Gaining insight into the behaviour of selection hyper-heuristics is challenging due to the complexity and random design of these heuristics. This paper is one of the initial studies to analyse rigorously the runtime of selection hyper-heuristics with a number of the most commonly used learning mechanisms; namely, simple random, random gradient, greedy, and permutation. We derive the runtime of selection hyper-heuristic with these learning mechanisms not only on a classical example problem, but also on a general model of fitness landscapes. This in turn helps in understanding the behaviour of hyper-heuristics. Our results show that all the considered selections hyper-heuristics have roughly the same performance. This suggests that the learning mechanisms do not necessarily improve the performance of hyper-heuristics. A new learning mechanism that improves the performance of hyper-heuristic on our example problem is presented.

Original languageEnglish
Title of host publicationProceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages2515-2523
Number of pages9
ISBN (Electronic)978-1-4799-1488-3, 978-1-4799-6626-4 (CD)
DOIs
Publication statusPublished - 16 Sep 2014
Event2014 IEEE Congress on Evolutionary Computation, CEC 2014 - Beijing, China
Duration: 6 Jul 201411 Jul 2014

Publication series

NameIEEE Congress on Evolutionary Computation (CEC)
Volume2014
ISSN (Print)1089-778X
ISSN (Electronic)1941-0026

Conference

Conference2014 IEEE Congress on Evolutionary Computation, CEC 2014
Country/TerritoryChina
CityBeijing
Period6/07/1411/07/14

Keywords

  • Runtime
  • Learning systems
  • Tin
  • Search problems
  • Probability distribution
  • Linear programming
  • Cost function

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computational Theory and Mathematics
  • Theoretical Computer Science

Fingerprint

Dive into the research topics of 'Runtime analysis of selection hyper-heuristics with classical learning mechanisms'. Together they form a unique fingerprint.

Cite this