TY - GEN
T1 - On binary unbiased operators returning multiple offspring
AU - Bulanova, Nina
AU - Buzdalov, Maxim
N1 - Publisher Copyright:
© 2017 ACM.
PY - 2017/7/15
Y1 - 2017/7/15
N2 - 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.
AB - 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.
KW - Black-box complexity
KW - Crossovers
KW - Needle
KW - OneMax.
UR - http://www.scopus.com/inward/record.url?scp=85026871927&partnerID=8YFLogxK
U2 - 10.1145/3067695.3082505
DO - 10.1145/3067695.3082505
M3 - Conference Proceeding (Non-Journal item)
AN - SCOPUS:85026871927
T3 - GECCO 2017 - Proceedings of the Genetic and Evolutionary Computation Conference Companion
SP - 1395
EP - 1398
BT - GECCO 2017 - Proceedings of the Genetic and Evolutionary Computation Conference Companion
PB - Association for Computing Machinery
T2 - 2017 Genetic and Evolutionary Computation Conference Companion, GECCO 2017
Y2 - 15 July 2017 through 19 July 2017
ER -