TY - GEN

T1 - Robustness of ant colony optimization to noise

AU - Friedrich, Tobias

AU - Kötzing, Timo

AU - Krejca, Martin S.

AU - Sutton, Andrew M.

PY - 2015/7/11

Y1 - 2015/7/11

N2 - 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.

AB - 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.

KW - Ant colony optimization

KW - Noisy fitness

KW - Run time analysis

KW - Theory

UR - http://www.scopus.com/inward/record.url?scp=84963657378&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84963657378&partnerID=8YFLogxK

U2 - 10.1145/2739480.2754723

DO - 10.1145/2739480.2754723

M3 - Conference contribution

AN - SCOPUS:84963657378

T3 - GECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference

SP - 17

EP - 24

BT - GECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference

A2 - Silva, Sara

PB - Association for Computing Machinery, Inc

T2 - 16th Genetic and Evolutionary Computation Conference, GECCO 2015

Y2 - 11 July 2015 through 15 July 2015

ER -