Robustness of ant colony optimization to noise

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations

Abstract

Recently Ant Colony Optimization (ACO) algorithms have been proven to be efficient in uncertain environments, such as noisy or dynamically changing fitness functions. Most of these analyses focus on combinatorial problems, such as path finding. We analyze an ACO algorithm in a setting where we try to optimize the simple OneMax test function, but with additive posterior noise sampled from a Gaussian distribution. Without noise the classical (μ + 1)-EA outperforms any ACO algorithm, with smaller μ being better; however, with large noise, the (μ + 1)-EA fails, even for high values of μ (which are known to help against small noise). In this paper 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 parameter σ2 of the noise and the dimension n of the search space (ρ = o(1/(n(n+ σ log n)2 logn))), optimization will be successful.

Original languageEnglish (US)
Title of host publicationGECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference
EditorsSara Silva
PublisherAssociation for Computing Machinery, Inc
Pages17-24
Number of pages8
ISBN (Electronic)9781450334723
DOIs
StatePublished - Jul 11 2015
Event16th Genetic and Evolutionary Computation Conference, GECCO 2015 - Madrid, Spain
Duration: Jul 11 2015Jul 15 2015

Publication series

NameGECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference

Other

Other16th Genetic and Evolutionary Computation Conference, GECCO 2015
CountrySpain
CityMadrid
Period7/11/157/15/15

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

    Friedrich, T., Kötzing, T., Krejca, M. S., & Sutton, A. M. (2015). Robustness of ant colony optimization to noise. In S. Silva (Ed.), GECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference (pp. 17-24). (GECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference). Association for Computing Machinery, Inc. https://doi.org/10.1145/2739480.2754723