Robustness of Ant Colony Optimization to Noise

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 One Max test function, but with additive posterior noise sampled from a Gaussian distribution. Without noise the classical (mu, + 1)-EA outperforms any ACO algorithm, with smaller mu being better; however, with large noise, the (mu, 1)-EA fails, even for high values of mu (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 rho is small enough dependent on the parameter sigma(2) of the noise and the dimension n of the search space (rho = o(1/(n(n a log n)(2) log n))), optimization will be successful.