AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

In this talk, we investigate static unary unbiased Evolutionary Algorithms (EAs). Such EAs can only generate offspring by mutation, i.e., from a single parent. Examples of unary unbiased mutation operators include randomized local search, standard bit mutation, and fast mutation. Unary unbiased mutation operators are uniquely described by a probability distribution on the set of possible search radii. We show that, up to lower order terms, the runtime of the (1 + 1)-EA equipped with an (almost) arbitrary but static unary unbiased mutation operator on linear functions is 1/p1 · n ln n, where p1 is the probability that the algorithm searches with radius 1 in a given iteration. This generalizes a seminal result of Witt [CPC ’13], where he showed that this holds for the (1 + 1)-EA using standard bit mutation with a constant mutation rate.

Roohani Sharma

+49 681 9325 1116

--email hidden

Zoom

527 278 8807

passcode not visible

logged in users only

If you wish to attend the talk online but do not have the zoom password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.