On binary unbiased operators returning multiple offspring

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.