@article{DoerrKrejca2021,
  author    = {Doerr, Benjamin and Krejca, Martin Stefan},
  title     = {A simplified run time analysis of the univariate marginal distribution algorithm on LeadingOnes},
  series = {Theoretical computer science},
  volume    = {851},
  journal   = {Theoretical computer science},
  publisher = {Elsevier},
  address   = {Amsterdam},
  issn      = {0304-3975},
  doi       = {10.1016/j.tcs.2020.11.028},
  pages     = {121 -- 128},
  year      = {2021},
  abstract  = {With elementary means, we prove a stronger run time guarantee for the univariate marginal distribution algorithm (UMDA) optimizing the LEADINGONES benchmark function in the desirable regime with low genetic drift. If the population size is at least quasilinear, then, with high probability, the UMDA samples the optimum in a number of iterations that is linear in the problem size divided by the logarithm of the UMDA's selection rate. This improves over the previous guarantee, obtained by Dang and Lehre (2015) via the deep level-based population method, both in terms of the run time and by demonstrating further run time gains from small selection rates. Under similar assumptions, we prove a lower bound that matches our upper bound up to constant factors.},
  language  = {en}
}
@article{FriedrichKoetzingKrejcaetal.2016,
  author    = {Friedrich, Tobias and K{\"o}tzing, Timo and Krejca, Martin Stefan and Sutton, Andrew M.},
  title     = {Robustness of Ant Colony Optimization to Noise},
  series = {Evolutionary computation},
  volume    = {24},
  journal   = {Evolutionary computation},
  publisher = {MIT Press},
  address   = {Cambridge},
  issn      = {1063-6560},
  doi       = {10.1162/EVCO_a_00178},
  pages     = {237 -- 254},
  year      = {2016},
  abstract  = {Recently, ant colony optimization (ACO) algorithms have proven to be efficient in uncertain environments, such as noisy or dynamically changing fitness functions. Most of these analyses have focused on combinatorial problems such as path finding. We rigorously analyze an ACO algorithm optimizing linear pseudo- Boolean functions under additive posterior noise. We study noise distributions whose tails decay exponentially fast, including the classical case of additive Gaussian noise. Without noise, the classical (mu + 1) EA outperforms any ACO algorithm, with smaller mu being better; however, in the case of large noise, the (mu + 1) EA fails, even for high values of mu (which are known to help against small noise). In this article, we show that ACO is able to deal with arbitrarily large noise in a graceful manner; that is, as long as the evaporation factor. is small enough, dependent on the variance s2 of the noise and the dimension n of the search space, optimization will be successful. We also briefly consider the case of prior noise and prove that ACO can also efficiently optimize linear functions under this noise model.},
  language  = {en}
}