@article{DoerrKrejca2020,
  author    = {Doerr, Benjamin and Krejca, Martin S.},
  title     = {Significance-based estimation-of-distribution algorithms},
  series = {IEEE transactions on evolutionary computation},
  volume    = {24},
  journal   = {IEEE transactions on evolutionary computation},
  number    = {6},
  publisher = {Institute of Electrical and Electronics Engineers},
  address   = {New York, NY},
  issn      = {1089-778X},
  doi       = {10.1109/TEVC.2019.2956633},
  pages     = {1025 -- 1034},
  year      = {2020},
  abstract  = {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.},
  language  = {en}
}