Adaptive Drift Analysis
Adaptive Drift Analysis
复制标题
DOI：
10.1007/s00453-011-9585-3
复制
发表时间：
2010-09
期刊：
影响因子：
1.1
通讯作者：
Benjamin Doerr;L. A. Goldberg
中科院分区：
文献类型：
--
作者：
Benjamin Doerr;L. A. Goldberg
我们证明了，对于任意c>0，使用任意突变率pn =c/n的（1+1）进化算法在期望时间Θ（nlogn）的位串上找到线性目标函数的最优解。以前，这仅是已知的力c ≤1。由于以前的工作也表明，普遍的漂移功能不可能存在clarger比某个常数，我们而是定义漂移功能的关键依赖于相关的目标函数（也oncitself）。使用这些精心构造的漂移函数，我们证明了预期的优化时间是Θ（nlogn）。通过给出乘性漂移定理的另一种证明，我们还表明，我们的优化时间界保持高概率。
We show that, for anyc>0, the (1+1) evolutionary algorithm using an arbitrary mutation ratepn=c/nfinds the optimum of a linear objective function over bit strings of lengthnin expected time Θ(nlogn). Previously, this was only known forc≤1. Since previous work also shows that universal drift functions cannot exist forclarger than a certain constant, we instead define drift functions which depend crucially on the relevant objective functions (and also oncitself). Using these carefully-constructed drift functions, we prove that the expected optimisation time is Θ(nlogn). By giving an alternative proof of the multiplicative drift theorem, we also show that our optimisation-time bound holds with high probability.