University of Birmingham Tail bounds on hitting times of randomized search heuristics using variable drift analysis
University of Birmingham Tail bounds on hitting times of randomized search heuristics using variable drift analysis
复制标题
伯明翰大学使用变量漂移分析确定随机搜索启发式命中时间的尾部界限
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
C. Witt
中科院分区：
文献类型：
--
作者：
P. Lehre;C. Witt
漂移分析是用于随机搜索启发式 (RSH) 运行时分析的最先进技术之一，例如进化算法 (EA)、模拟退火等。现有的绝大多数漂移定理都会对目标状态的命中时间的预期值（例如，目标状态）产生界限。 g.，最优解集，无需对时间的分布做额外的说明。我们通过提供一个通用漂移定理来解决这一缺陷，该定理包括击球时间分布的上尾部和下尾部的界限。新的尾部界限用于证明简单 EA 在标准基准问题（包括一般线性函数类）的运行时间上的非常精确的锐集中结果。令人惊讶的是，在所有这些问题上，预期时间的低阶项中偏离 r 因子的概率随着 r 呈指数下降。该定理在 RSH 理论之外的有用性通过推导随机排列中循环数的尾界来证明。所有这些结果都处理了位置相关（可变）漂移，该漂移没有被先前带有尾界的漂移定理所涵盖。最后，给出了一般漂移定理的用户友好的专门化。
Drift analysis is one of the state-of-the-art techniques for the runtime analysis of randomized search heuristics (RSHs) such as evolutionary algorithms (EAs), simulated annealing etc. The vast majority of existing drift theorems yield bounds on the expected value of the hitting time for a target state, e. g., the set of optimal solutions, without making addi-tional statements on the distribution of this time. We address this lack by providing a general drift theorem that includes bounds on the upper and lower tail of the hitting time distribution. The new tail bounds are applied to prove very precise sharp-concentration results on the running time of a simple EA on standard benchmark problems, including the class of general linear functions. Surprisingly, the probability of deviating by an r -factor in lower order terms of the expected time decreases exponentially with r on all these problems. The usefulness of the theorem outside the theory of RSHs is demonstrated by deriving tail bounds on the number of cycles in random permutations. All these results handle a position-dependent (variable) drift that was not covered by previous drift theorems with tail bounds. Finally, user-friendly specializations of the general drift theorem are given.
影响因子：
1.1
作者：
Benjamin Doerr;L. A. Goldberg
通讯作者：
Benjamin Doerr;L. A. Goldberg