Robustness of Ant Colony Optimization to Noise
Robustness of Ant Colony Optimization to Noise
复制标题
DOI：
10.1145/2739480.2754723
复制
发表时间：
2015-07
影响因子：
6.8
通讯作者：
T. Friedrich;Timo Kötzing;Martin S. Krejca;Andrew M. Sutton
中科院分区：
文献类型：
--
作者：
T. Friedrich;Timo Kötzing;Martin S. Krejca;Andrew M. Sutton
摘要近年来，蚁群优化（ACO）算法已被证明是有效的不确定环境中，如噪声或动态变化的适应度函数。大多数这些分析集中在组合问题，如路径查找。我们严格分析了加性后验噪声下优化线性伪布尔函数的蚁群算法。我们研究噪声分布的尾巴指数衰减快，包括经典的情况下加性高斯噪声。在没有噪声的情况下，经典的EA优于任何ACO算法，越小越好;然而，在大噪声的情况下，EA失败，即使对于高值（已知有助于对抗小噪声）。在这篇文章中，我们表明，ACO是能够处理任意大的噪声在一个优雅的方式，也就是说，只要蒸发因子足够小，依赖于噪声的方差和搜索空间的维数n，优化将是成功的。我们还简要地考虑了先验噪声的情况下，证明了蚁群算法也可以有效地优化线性函数在这种噪声模型。
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 EA outperforms any ACO algorithm, with smaller being better; however, in the case of large noise, the 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 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.