Towards a Running Time Analysis of the (1+1)-EA for OneMax and LeadingOnes Under General Bit-Wise Noise

摘要

Running time analysis of evolutionary algorithms (EAs) under noisy environments has recently received much attention, which can help us understand the behavior of EAs in practice where the fitness evaluation is often subject to noise. One of the mainly investigated noise models is bit-wise noise, which is characterized by a pair (p, q) of parameters. However, previous analyses usually fix p or q, which makes our understanding on bit-wise noise incomplete. In this paper, we analyze the running time of the (1+1)-EA solving OneMax and LeadingOnes under general bit-wise noise. Our results largely extend the known ones in specific cases of bit-wise noise, and disclose that p and pq together decide the running time to be polynomial or super-polynomial.