TY  - JOUR
A1  - Doerr, Benjamin
A1  - Krejca, Martin S.
T1  - Significance-based estimation-of-distribution algorithms
JF  - IEEE transactions on evolutionary computation
N2  - Estimation-of-distribution algorithms (EDAs) are randomized search heuristics that create a probabilistic model of the solution space, which is updated iteratively, based on the quality of the solutions sampled according to the model. As previous works show, this iteration-based perspective can lead to erratic updates of the model, in particular, to bit-frequencies approaching a random boundary value. In order to overcome this problem, we propose a new EDA based on the classic compact genetic algorithm (cGA) that takes into account a longer history of samples and updates its model only with respect to information which it classifies as statistically significant. We prove that this significance-based cGA (sig-cGA) optimizes the commonly regarded benchmark functions OneMax (OM), LeadingOnes, and BinVal all in quasilinear time, a result shown for no other EDA or evolutionary algorithm so far. For the recently proposed stable compact genetic algorithm-an EDA that tries to prevent erratic model updates by imposing a bias to the uniformly distributed model-we prove that it optimizes OM only in a time exponential in its hypothetical population size. Similarly, we show that the convex search algorithm cannot optimize OM in polynomial time.
KW  - heuristic algorithms
KW  - sociology
KW  - statistics
KW  - history
KW  - probabilistic
KW  - logic
KW  - benchmark testing
KW  - genetic algorithms
KW  - estimation-of-distribution
KW  - algorithm (EDA)
KW  - run time analysis
KW  - theory
Y1  - 2020
U6  - https://doi.org/10.1109/TEVC.2019.2956633
SN  - 1089-778X
SN  - 1941-0026
VL  - 24
IS  - 6
SP  - 1025
EP  - 1034
PB  - Institute of Electrical and Electronics Engineers
CY  - New York, NY
ER  -