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

Qian, Chao1; Bian, Chao1; Jiang, Wu1; Tang, Ke2

2019-02

10.1007/s00453-018-0488-4

ALGORITHMICA   影响因子和分区

0178-4617

1432-0541

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.

Noisy optimization Evolutionary algorithms Sampling Running time analysis Computational complexity

SCI ; EI

英语

通讯

Royal Society Newton Advanced Fellowship[NA150123]

Computer Science ; Mathematics

Computer Science, Software Engineering ; Mathematics, Applied

WOS:000458280100014

SPRINGER

20183105633203

Computational complexity ; Optimization ; Polynomials ; Sampling

Computer Theory, Includes Formal Logic, Automata Theory, Switching Theory, Programming Theory:721.1 ; Algebra:921.1 ; Optimization Techniques:921.5

ENGINEERING

Web of Science

1.Univ Sci & Technol China, Sch Comp Sci & Technol, Anhui Prov Key Lab Big Data Anal & Applicat, Hefei 230027, Anhui, Peoples R China
2.Southern Univ Sci & Technol, Shenzhen Key Lab Computat Intelligence, Dept Comp Sci & Engn, Shenzhen 518055, Peoples R China

Qian, Chao,Bian, Chao,Jiang, Wu,et al. Running Time Analysis of the (1+1)-EA for OneMax and LeadingOnes Under Bit-Wise Noise[J]. ALGORITHMICA,2019,81(2):749-795.

Qian, Chao,Bian, Chao,Jiang, Wu,&Tang, Ke.(2019).Running Time Analysis of the (1+1)-EA for OneMax and LeadingOnes Under Bit-Wise Noise.ALGORITHMICA,81(2),749-795.

Qian, Chao,et al."Running Time Analysis of the (1+1)-EA for OneMax and LeadingOnes Under Bit-Wise Noise".ALGORITHMICA 81.2(2019):749-795.