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

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