Runtime analysis of selection hyper-heuristics with classical learning mechanisms

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

Authors

Colleges, School and Institutes

External organisations

  • University of Nottingham
  • NOTTINGHAM UNIVERSITY

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.

Details

Original languageEnglish
Title of host publicationProceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014
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
CountryChina
CityBeijing
Period6/07/1411/07/14

Keywords

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