The Compact Genetic Algorithm is Efficient Under Extreme Gaussian Noise
The Compact Genetic Algorithm is Efficient Under Extreme Gaussian Noise
复制标题
DOI：
10.1109/tevc.2016.2613739
复制
发表时间：
2017-06-01
影响因子：
14.3
通讯作者：
Sutton, Andrew M.
中科院分区：
文献类型：
--
作者：
Friedrich, Tobias;Koetzing, Timo;Sutton, Andrew M.
实际的优化问题经常包括质量度量的不确定性，例如，由于噪声评估而导致的不确定性。因此，它们不允许直接应用传统优化技术。在这些设置中，随机搜索启发式（例如进化算法）是一种流行的选择，因为它们通常被认为具有某种抗噪声能力。经验证据表明，某些算法（例如分布估计算法 (EDA)）对于噪声强度的缩放具有鲁棒性，即使不采用显式噪声处理技术（例如重采样）也是如此。在本文中，我们希望用数学严谨性来支持这些主张。我们引入了优雅缩放的概念，其中算法的运行时间随噪声强度进行多项式缩放。我们研究了二进制串上的单调适应度函数，其加性噪声取自高斯分布。我们表明，在没有任何明确的噪声处理的情况下，短视启发式方法无法在任意强度的噪声下有效地优化函数。此外，我们证明使用总体没有帮助。最后，我们证明了一种称为紧凑遗传算法的简单 EDA 可以克服仅突变启发式算法的短视性，从而能够在噪声下优雅地扩展。我们推测重组遗传算法也具有这种性质。
Practical optimization problems frequently include uncertainty about the quality measure, for example, due to noisy evaluations. Thus, they do not allow for a straightforward application of traditional optimization techniques. In these settings, randomized search heuristics such as evolutionary algorithms are a popular choice because they are often assumed to exhibit some kind of resistance to noise. Empirical evidence suggests that some algorithms, such as estimation of distribution algorithms (EDAs) are robust against a scaling of the noise intensity, even without resorting to explicit noise-handling techniques such as resampling. In this paper, we want to support such claims with mathematical rigor. We introduce the concept of graceful scaling in which the run time of an algorithm scales polynomially with noise intensity. We study a monotone fitness function over binary strings with additive noise taken from a Gaussian distribution. We show that myopic heuristics cannot efficiently optimize the function under arbitrarily intense noise without any explicit noise-handling. Furthermore, we prove that using a population does not help. Finally, we show that a simple EDA called the compact genetic algorithm can overcome the short-sightedness of mutation-only heuristics to scale gracefully with noise. We conjecture that recombinative genetic algorithms also have this property.