In many real-world optimization problems, the objective function evaluation is subject to noise, and we cannot obtain the exact objective value. Evolutionary algorithms (EAs), a type of general-purpose randomized optimization algorithm, have been shown to be able to solve noisy optimization problems well. However, previous theoretical analyses of EAs mainly focused on noise-free optimization, which makes the theoretical understanding largely insufficient for the noisy case. Meanwhile, the few existing theoretical studies under noise often considered the one-bit noise model, which flips a randomly chosen bit of a solution before evaluation; while in many realistic applications, several bits of a solution can be changed simultaneously. In this paper, we study a natural extension of one-bit noise, the bit-wise noise model, which independently flips each bit of a solution with some probability. We analyze the running time of the (1+1)-EA solving OneMax and LeadingOnes under bit-wise noise for the first time, and derive the ranges of the noise level for polynomial and super-polynomial running time bounds. The analysis on LeadingOnes under bit-wise noise can be easily transferred to one-bit noise, and improves the previously known results. Since our analysis discloses that the (1+1)-EA can be efficient only under low noise levels, we also study whether the sampling strategy can bring robustness to noise. We prove that using sampling can significantly increase the largest noise level allowing a polynomial running time, that is, sampling is robust to noise.

翻译：在许多现实世界优化问题中,客观功能评价会受到噪音的影响,我们无法获得准确的客观价值。进化算法(EAs)是一种通用随机随机优化算法,已经证明它能够很好地解决噪音优化问题。然而,以往对EA的理论分析主要侧重于无噪音优化,这使得对噪音的理论理解对噪音案件来说基本不够。同时,在噪音下的现有理论研究往往考虑到一维噪音模型,该模型在评估之前会随意选择一个解决方案;而在许多现实应用中,一个解决方案的比特可以同时改变。在本文件中,我们研究一位噪音的自然延伸,即一种小点噪声模型,它独立地翻转出每一种解决方案的一位。我们第一次分析一个+1-EA在小点噪音下解决一兆和领导一号的运行时间时间,并得出一个多点噪音和超级极地段运行时间的噪音水平的范围。在比特的噪音等级上的分析可以很容易地转换为一位噪音,在先前的取样战略下,我们也可以大大地将一个小点噪音和最高级的频率分析。