A runtime analysis of simple hyper-heuristics: To mix or not to mix operators

Per Kristian Lehre*, Ender Özcan

*Corresponding author for this work

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

39 Citations (Scopus)

Abstract

There is a growing body of work in the field of hyper-heuristics. Hyper-heuristics are high level search methodologies that operate on the space of heuristics to solve hard computational problems. A frequently used hyper-heuristic framework mixes a predefined set of low level heuristics during the search process. While most of the work on such selection hyper-heuristics in the literature are empirical, we analyse the runtime of hyper-heuristics rigorously. Our initial analysis shows that mixing heuristics could lead to exponentially faster search than individual (deterministically chosen) heuristics on chosen problems. Both mixing of variation operators and mixing of acceptance criteria are investigated on some selected problems. It is shown that mixing operators is only efficient with the right mixing distribution (parameter setting). Additionally, some of the existing adaptation mechanisms for mixing operators are also evaluated.

Original languageEnglish
Title of host publicationFOGA 2013 - Proceedings of the 12th ACM Workshop on Foundations of Genetic Algorithms
Pages97-104
Number of pages8
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event12th ACM Workshop on Foundations of Genetic Algorithms, FOGA 2013 - Adelaide, SA, Australia
Duration: 16 Jan 201320 Jan 2013

Conference

Conference12th ACM Workshop on Foundations of Genetic Algorithms, FOGA 2013
Country/TerritoryAustralia
CityAdelaide, SA
Period16/01/1320/01/13

Keywords

  • Hyper-heuristic
  • Runtime analysis
  • Stochastic local search

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'A runtime analysis of simple hyper-heuristics: To mix or not to mix operators'. Together they form a unique fingerprint.

Cite this