Limited memory, limited arity unbiased black-box complexity: First insights

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)

Abstract

Limited arity unbiased black-box complexity was proven to be a successful tool for understanding the working principles of randomized search heuristics and delivered insights to develop new efficient algorithms. While good upper bounds for simple problems were found long time ago, there are still no matching lower bounds. On a road towards closing this gap, we introduce the notion of limited-memory, limited arity unbiased black-box complexity. We show that some efficient binary unbiased algorithms (almost) satisfy the memory-2 requirement, and present an algorithm to compute, for a given problem size, the exact lower bound on the runtime of any memory-m k-ary algorithm on any unimodal function.

Original languageEnglish
Title of host publicationGECCO 2019 Companion - Proceedings of the 2019 Genetic and Evolutionary Computation Conference Companion
PublisherAssociation for Computing Machinery, Inc
Pages2020-2023
Number of pages4
ISBN (Electronic)9781450367486
DOIs
Publication statusPublished - 13 Jul 2019
Externally publishedYes
Event2019 Genetic and Evolutionary Computation Conference, GECCO 2019 - Prague, Czech Republic
Duration: 13 Jul 201917 Jul 2019

Publication series

NameGECCO 2019 Companion - Proceedings of the 2019 Genetic and Evolutionary Computation Conference Companion

Conference

Conference2019 Genetic and Evolutionary Computation Conference, GECCO 2019
Country/TerritoryCzech Republic
CityPrague
Period13 Jul 201917 Jul 2019

Keywords

  • Memory-resticted
  • Unbiased complexity
  • Unimodal functions

Fingerprint

Dive into the research topics of 'Limited memory, limited arity unbiased black-box complexity: First insights'. Together they form a unique fingerprint.

Cite this