On the robustness of median sampling in noisy evolutionary optimization  

作　　者：Chao BIAN Chao QIAN Yang YU Ke TANG 

机构地区：[1]State Key Laboratory for Novel Software Technology,Nanjing University,Nanjing 210023,China [2]Shenzhen Key Laboratory of Computational Intelligence,Department of Computer Science and Engineering,Southern University of Science and Technology,Shenzhen 518055,China

出　　处：《Science China(Information Sciences)》2021年第5期28-40,共13页中国科学（信息科学）（英文版）

基　　金：supported by National Key Research and Development Program of China(Grant No.2017YFB1003102);National Natural Science Foundation of China(Grant Nos.62022039,61672478,61876077);MOE University Scientific-Technological Innovation Plan Program。

摘　　要：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 1 s 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 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]