@article{FriedrichKoetzingKrejca2019,
  author    = {Friedrich, Tobias and K{\"o}tzing, Timo and Krejca, Martin Stefan},
  title     = {Unbiasedness of estimation-of-distribution algorithms},
  series = {Theoretical computer science},
  volume    = {785},
  journal   = {Theoretical computer science},
  publisher = {Elsevier},
  address   = {Amsterdam},
  issn      = {0304-3975},
  doi       = {10.1016/j.tcs.2018.11.001},
  pages     = {46 -- 59},
  year      = {2019},
  abstract  = {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.},
  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}
}