Adaptive Drift Analysis

作者：Doerr Benjamin; Goldberg Leslie Ann^*

来源：Algorithmica, 2013, 65(1): 224-250.

DOI：10.1007/s00453-011-9585-3

We show that, for any c %26gt; 0, the (1+1) evolutionary algorithm using an arbitrary mutation rate p (n) =c/n finds the optimum of a linear objective function over bit strings of length n in expected time I similar to(nlogn). Previously, this was only known for ca parts per thousand currency sign1. Since previous work also shows that universal drift functions cannot exist for c larger than a certain constant, we instead define drift functions which depend crucially on the relevant objective functions (and also on c itself). Using these carefully-constructed drift functions, we prove that the expected optimisation time is I similar to(nlogn). By giving an alternative proof of the multiplicative drift theorem, we also show that our optimisation-time bound holds with high probability.

• 出版日期2013-1