Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, March 14, 2023, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Duri Janett
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.
Automatic MiSe System Software Version 1.4803M | admin login