English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In a seminal paper in 2013, Witt showed that the (1+1) Evolutionary Algorithmwith standard bit mutation needs time $(1+o(1))n \ln n/p_1$ to find the optimumof any linear function, as long as the probability $p_1$ to flip exactly onebit is $\Theta(1)$. In this paper we investigate how this result generalizes ifstandard bit mutation is replaced by an arbitrary unbiased mutation operator.This situation is notably different, since the stochastic domination argumentused for the lower bound by Witt no longer holds. In particular, startingcloser to the optimum is not necessarily an advantage, and OneMax is no longerthe easiest function for arbitrary starting positions.  Nevertheless, we show that Witt's result carries over if $p_1$ is not toosmall, with different constraints for upper and lower bounds, and if the numberof flipped bits has bounded expectation~$\chi$. Notably, this includes some ofthe heavy-tail mutation operators used in fast genetic algorithms, but not allof them. We also give examples showing that algorithms with unbounded $\chi$have qualitatively different trajectories close to the optimum.

Tight Runtime Bounds for Static Unary Unbiased Evolutionary Algorithms on Linear Functions