Probabilistic Tools for the Analysis of Randomized Optimization Heuristics
Probabilistic Tools for the Analysis of Randomized Optimization Heuristics
复制标题
DOI：
10.1007/978-3-030-29414-4_1
复制
发表时间：
2018-01
期刊：
影响因子：
--
通讯作者：
Benjamin Doerr
中科院分区：
文献类型：
--
作者：
Benjamin Doerr
本章收集了几个概率工具，这些工具在分析随机搜索策略时被证明是有用的。这包括经典的材料，如马尔可夫，切比雪夫，和Chebyshev不等式，但也鲜为人知的主题，如随机控制和耦合，和Chebyshev界的几何分布的随机变量和负相关的随机变量。这里介绍的大多数结果以前已经出现过，但有些只是在最近的会议出版物。虽然重点是提供用于分析随机搜索启发式的工具，但其中许多工具对于分析经典随机算法或离散随机结构也可能很有用。
This chapter collects several probabilistic tools that have proven to be useful in the analysis of randomized search heuristics. This includes classic material such as the Markov, Chebyshev, and Chernoff inequalities, but also lesser-known topics such as stochastic domination and coupling, and Chernoff bounds for geometrically distributed random variables and for negatively correlated random variables. Most of the results presented here have appeared previously, but some only in recent conference publications. While the focus is on presenting tools for the analysis of randomized search heuristics, many of these may be useful as well for the analysis of classic randomized algorithms or discrete random structures.