On binary unbiased operators returning multiple offspring

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

Abstract

The notion of unbiased black-box complexity plays an important role in theory of randomized search heuristics. A black-box algorithm is usually defined as an algorithm which uses unbiased variation operations. In all known papers, the analysed variation operators take k arguments and produce one offspring. On the other hand, many practitioners use crossovers which produce two offspring, and in many living organisms a diploid cell produces two distinct haploid genotypes. We investigate how the binary-To-binary, or (2 → 2), unbiased variation operators look like, and how they can be used to improve randomized search heuristics. We show that the (2 → 2) unbiased black-box complexity of Needle coincides with its unrestricted black-box complexity. We also show that it can be used to put strong worst-case guarantees for solving OneMax.

Original languageEnglish
Title of host publicationGECCO 2017 - Proceedings of the Genetic and Evolutionary Computation Conference Companion
PublisherAssociation for Computing Machinery, Inc
Pages1395-1398
Number of pages4
ISBN (Electronic)9781450349390
DOIs
Publication statusPublished - 15 Jul 2017
Externally publishedYes
Event2017 Genetic and Evolutionary Computation Conference Companion, GECCO 2017 - Berlin, Germany
Duration: 15 Jul 201719 Jul 2017

Publication series

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

Conference

Conference2017 Genetic and Evolutionary Computation Conference Companion, GECCO 2017
Country/TerritoryGermany
CityBerlin
Period15 Jul 201719 Jul 2017

Keywords

  • Black-box complexity
  • Crossovers
  • Needle
  • OneMax.

Fingerprint

Dive into the research topics of 'On binary unbiased operators returning multiple offspring'. Together they form a unique fingerprint.

Cite this