On the robustness of median sampling in noisy evolutionary optimization

Bian, Chao1; Qian, Chao1; Yu, Yang1; Tang, Ke2

2021-05-01

10.1007/s11432-020-3114-y

Science China-Information Sciences   影响因子和分区

1674-733X

1869-1919

Evolutionary algorithms (EAs) are a sort of nature-inspired metaheuristics, which have wide applications in various practical optimization problems. In these problems, objective evaluations are usually inaccurate, because noise is almost inevitable in real world, and it is a crucial issue to weaken the negative effect caused by noise. Sampling is a popular strategy, which evaluates the objective a couple of times, and employs the mean of these evaluation results as an estimate of the objective value. In this work, we introduce a novel sampling method, median sampling, into EAs, and illustrate its properties and usefulness theoretically by solving OneMax, the problem of maximizing the number of 1s in a bit string. Instead of the mean, median sampling employs the median of the evaluation results as an estimate. Through rigorous theoretical analysis on OneMax under the commonly used onebit noise, we show that median sampling reduces the expected runtime exponentially. Next, through two special noise models, we show that when the 2-quantile of the noisy fitness increases with the true fitness, median sampling can be better than mean sampling; otherwise, it may fail and mean sampling can be better. The results may guide us to employ median sampling properly in practical applications.

evolutionary algorithms noisy optimization median sampling computational complexity runtime analysis

SCI ; EI

英语

其他

National Key Research and Development Program of China[2017YFB1003102] ; National Natural Science Foundation of China[62022039,61672478,61876077]

Computer Science ; Engineering

Computer Science, Information Systems ; Engineering, Electrical & Electronic

WOS:000639881800001

SCIENCE PRESS

20211610233397

Biomimetics ; Evolutionary algorithms

Biotechnology:461.8 ; Optimization Techniques:921.5

Web of Science

1.Nanjing Univ, State Key Lab Novel Software Technol, Nanjing 210023, Peoples R China
2.Southern Univ Sci & Technol, Dept Comp Sci & Engn, Shenzhen Key Lab Computat Intelligence, Shenzhen 518055, Peoples R China

Bian, Chao,Qian, Chao,Yu, Yang,et al. On the robustness of median sampling in noisy evolutionary optimization[J]. Science China-Information Sciences,2021,64(5).

Bian, Chao,Qian, Chao,Yu, Yang,&Tang, Ke.(2021).On the robustness of median sampling in noisy evolutionary optimization.Science China-Information Sciences,64(5).

Bian, Chao,et al."On the robustness of median sampling in noisy evolutionary optimization".Science China-Information Sciences 64.5(2021).