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

Carola Doerr, Duri Andrea Janett, Johannes Lengler

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/p_1$ to find the optimum of any linear function…