Running time analysis of the (1+1)-EA for onemax and leadingones under bit-wise noise
Chao Qian, Chao Bian, Jiang Wu, Ke Tang · Proceedings of the Genetic and Evolutionary Computation Conference · 2017
Previous running time analyses of evolutionary algorithms (EAs) in noisy environments often studied the one-bit noise model, which flips a randomly chosen bit of a solution before evaluation. 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.