Tight Runtime Bounds for Static Unary Unbiased Evolutionary Algorithms on Linear Functions
METADATA ONLY
Loading...
Author / Producer
Date
2024
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
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.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
86 (10)
Pages / Article No.
3115 - 3152
Publisher
Springer
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Runtime analysis; Theory of evolutionary computation; Mutation operators
Organisational unit
08738 - Lengler, Johannes (Tit.-Prof.) / Lengler, Johannes (Tit.-Prof.)