Tight Runtime Bounds for Static Unary Unbiased Evolutionary Algorithms on Linear Functions
Metadata only
Date
2024Type
- Journal Article
ETH Bibliography
yes
Altmetrics
Abstract
In a seminal paper in 2013, Witt showed that the (1+1) Evolutionary Algorithm with
standard bit mutation needs time (1 + o(1))n ln n/p1 to find the optimum of any
linear function, as long as the probability p1 to flip exactly one bit is (1). In this
paper we investigate how this result generalizes if standard bit mutation is replaced by an arbitrary unbiased mutation operator. This situation is notably different, since the
stochastic domination argument used for the lower bound by Witt no longer holds. In
particular, starting closer to the optimum is not necessarily an advantage, and OneMax
is no longer the easiest function for arbitrary starting positions. Nevertheless, we show
that Witt’s result carries over if p1 is not too small, with different constraints for upper
and lower bounds, and if the number of flipped bits has bounded expectation χ.
Notably, this includes some of the heavy-tail mutation operators used in fast genetic
algorithms, but not all of them. We also give examples showing that algorithms with
unbounded χ have qualitatively different trajectories close to the optimum. Show more
Publication status
publishedExternal links
Journal / series
AlgorithmicaVolume
Pages / Article No.
Publisher
SpringerSubject
Runtime analysis; Theory of evolutionary computation; Mutation operatorsOrganisational unit
08738 - Lengler, Johannes (Tit.-Prof.) / Lengler, Johannes (Tit.-Prof.)
More
Show all metadata
ETH Bibliography
yes
Altmetrics