Robustness of ant colony optimization to noise

Tobias Friedrich, Timo Kötzing, Martin S. Krejca, Andrew M. Sutton

Research output: Contribution to journalArticlepeer-review

26 Scopus citations

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 (μ + 1) EA outperforms any ACO algorithm, with smaller μ being better; however, in the case of large noise, the (μ + 1) EA fails, even for high values of μ (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 σ2 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.

Original languageEnglish (US)
Pages (from-to)237-254
Number of pages18
JournalEvolutionary Computation
Volume24
Issue number2
DOIs
StatePublished - Jun 1 2016

Keywords

  • Ant colony optimization
  • Noisy Fitness
  • Run time analysis
  • Theory

Fingerprint Dive into the research topics of 'Robustness of ant colony optimization to noise'. Together they form a unique fingerprint.

Cite this