TY  - JOUR
A1  - Friedrich, Tobias
A1  - Kötzing, Timo
A1  - Krejca, Martin Stefan
T1  - Unbiasedness of estimation-of-distribution algorithms
JF  - Theoretical computer science
N2  - In the context of black-box optimization, black-box complexity is used for understanding the inherent difficulty of a given optimization problem. Central to our understanding of nature-inspired search heuristics in this context is the notion of unbiasedness. Specialized black-box complexities have been developed in order to better understand the limitations of these heuristics - especially of (population-based) evolutionary algorithms (EAs). In contrast to this, we focus on a model for algorithms explicitly maintaining a probability distribution over the search space: so-called estimation-of-distribution algorithms (EDAs). We consider the recently introduced n-Bernoulli-lambda-EDA framework, which subsumes, for example, the commonly known EDAs PBIL, UMDA, lambda-MMAS(IB), and cGA. We show that an n-Bernoulli-lambda-EDA is unbiased if and only if its probability distribution satisfies a certain invariance property under isometric automorphisms of [0, 1](n). By restricting how an n-Bernoulli-lambda-EDA can perform an update, in a way common to many examples, we derive conciser characterizations, which are easy to verify. We demonstrate this by showing that our examples above are all unbiased. (C) 2018 Elsevier B.V. All rights reserved.
KW  - Estimation-of-distribution algorithm
KW  - Unbiasedness
KW  - Theory
Y1  - 2019
U6  - https://doi.org/10.1016/j.tcs.2018.11.001
SN  - 0304-3975
SN  - 1879-2294
VL  - 785
SP  - 46
EP  - 59
PB  - Elsevier
CY  - Amsterdam
ER  -