论文标题
通过漂移分析改善了固定预算结果
Improved Fixed-Budget Results via Drift Analysis
论文作者
论文摘要
固定预算理论与在适应性函数评估的给定预算内通过随机搜索启发式方法来计算或界定适应性值。尽管固定预算理论最近取得了进展，但缺乏获得此类结果的一般工具。我们将漂移理论（将预期优化时间推导的关键工具转移到固定的透视视角上。与所谓的贪婪相关方案中迭代漂移有关的第一个易用的语句立即转化为预期功能值的界限。之后，我们考虑了一个基于众所周知的变量漂移定理的更通用工具。该技术在领导者基准功能上的应用比以前的最清晰的状态更精确。
Fixed-budget theory is concerned with computing or bounding the fitness value achievable by randomized search heuristics within a given budget of fitness function evaluations. Despite recent progress in fixed-budget theory, there is a lack of general tools to derive such results. We transfer drift theory, the key tool to derive expected optimization times, to the fixed-budged perspective. A first and easy-to-use statement concerned with iterating drift in so-called greed-admitting scenarios immediately translates into bounds on the expected function value. Afterwards, we consider a more general tool based on the well-known variable drift theorem. Applications of this technique to the LeadingOnes benchmark function yield statements that are more precise than the previous state of the art.
