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

Bian, Chao1; Qian, Chao1; Tang, Ke2

10.1007/978-3-319-99259-4_14

2018

16113349

1611-3349

PARALLEL PROBLEM SOLVING FROM NATURE - PPSN XV, PT II

11102

165-177

Coimbra, Portugal

GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND

SPRINGER INTERNATIONAL PUBLISHING AG

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.

其他

英语

CPCI-S ; EI

Royal Society Newton Advanced Fellowship[NA150123]

Computer Science ; Engineering

Computer Science, Artificial Intelligence ; Computer Science, Theory & Methods ; Engineering, Electrical & Electronic

WOS:000458558500014

20183805847291

Artificial intelligence ; Computer science ; Computers

Artificial Intelligence:723.4

Web of Science

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

Bian, Chao,Qian, Chao,Tang, Ke. Towards a Running Time Analysis of the (1+1)-EA for OneMax and LeadingOnes Under General Bit-Wise Noise[C]. GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND:SPRINGER INTERNATIONAL PUBLISHING AG,2018:165-177.