4.3 Article

Analysing the Robustness of Evolutionary Algorithms to Noise: Refined Runtime Bounds and an Example Where Noise is Beneficial

期刊

ALGORITHMICA
卷 83, 期 4, 页码 976-1011

出版社

SPRINGER
DOI: 10.1007/s00453-020-00671-0

关键词

Evolutionary algorithms; Noisy optimisation; Robustness; Runtime analysis; Theory; Uncertainty

向作者/读者索取更多资源

In this study, we analysed the performance of well-known evolutionary algorithms, the (1 + 1) EA and the (1 + similar to) EA, in the prior noise model. We discovered that the (1 + 1) EA on LeadingOnes is surprisingly sensitive to noise and showed that offspring populations of size similar to = 3.42 log n can effectively deal with much higher noise than previously known.
We analyse the performance of well-known evolutionary algorithms, the (1 + 1) EA and the (1 + similar to) EA, in the prior noise model, where in each fitness evaluation the search point is altered before the evaluation with probability p. We present refined results for the expected optimisation time of these algorithms on the function -LeadingOnes, where bits have to be optimised in sequence. Previous work showed that the (1 + 1) EA on LeadingOnes runs in polynomial expected time if p = O((log n)/n2) and needs superpolynomial expected time if p = similar to((log n)/n), leaving a huge gap for which no results were known. We close this gap by showing that the expected optimisation time is similar to(n2) . exp(similar to(min{pn2, n})) for all p = 1/2, allowing for the first time to locate the threshold between polynomial and superpolynomial expected times at p = similar to((log n)/n2). Hence the (1 + 1) EA on -LeadingOnes is surprisingly sensitive to noise. We also show that offspring populations of size similar to = 3.42 log n can effectively deal with much higher noise than known before. Finally, we present an example of a rugged landscape where prior noise can help to escape from local optima by blurring the landscape and allowing a hill climber to see the underlying gradient. We prove that in this particular setting noise can have a highly beneficial effect on performance.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.3
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据