Drift analysis and linear functions revisited
Drift analysis and linear functions revisited
复制标题
重新审视漂移分析和线性函数
DOI：
10.1109/cec.2010.5586097
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Carola Doerr
中科院分区：
文献类型：
--
作者：
Benjamin Doerr;Daniel Johannsen;Carola Doerr
本文研究了（1+1）进化算法优化任意线性伪布尔函数的经典问题。我们证明了任何这样的函数在时间（1 + o（1））1.39en ln（n）上是最优的，其中n是位串的长度。我们还证明了（1 −o（1））en ln（n）的一个下界，它实际上对所有具有唯一全局最优值的函数都成立。这表明，对于线性函数，即使优化行为可能不同，结果运行时也非常相似。我们的实验结果表明，真正的优化时间甚至比理论保证的承诺更接近。
We regard the classical problem how the (1+1) Evolutionary Algorithm optimizes an arbitrary linear pseudo-Boolean function. We show that any such function is optimized in time (1 + o(1)) 1.39en ln (n), where n is the length of the bit string. We also prove a lower bound of (1 −o(1))en ln(n), which in fact holds for all functions with a unique global optimum. This shows that for linear functions, even though the optimization behavior might differ, the resulting runtimes are very similar. Our experimental results suggest that the true optimization times are even closer than what the theoretical guarantees promise.