论文标题
随机搜索启发式的运行时指数上限
Exponential Upper Bounds for the Runtime of Randomized Search Heuristics
论文作者
论文摘要
我们认为，在经典算法中建立的既定领域在Runtimes上经过验证的指数上限，在启发式搜索中也很有趣，我们证明了一些这样的结果。我们表明，任何算法随机的本地搜索，大都市算法，模拟退火，（1+1）进化算法都可以优化任何在大多数指数的噪声假设下，在大多数指数的噪声假设下，在问题上的指数下降〜$ n $ n $ n $ n $。这大幅度扩展了以前的结果，仅限（1+1）EA，引导器功能以及最多$ 1/2 $的噪声概率，同时简化其证明。有了同样的一般论点，除其他论点外，当后代人口大小$λ$是对数，但低于效率阈值时，我们还为$（1，λ）$进化算法的运行时得出了亚指数上限。为了证明我们的方法还可以处理非平凡的父人群规模，我们证明了基于突变的简单遗传算法在OneMAX基准测试上的基于突变的版本的指数上限，与已知的指数下界匹配。
We argue that proven exponential upper bounds on runtimes, an established area in classic algorithms, are interesting also in heuristic search and we prove several such results. We show that any of the algorithms randomized local search, Metropolis algorithm, simulated annealing, and (1+1) evolutionary algorithm can optimize any pseudo-Boolean weakly monotonic function under a large set of noise assumptions in a runtime that is at most exponential in the problem dimension~$n$. This drastically extends a previous such result, limited to the (1+1) EA, the LeadingOnes function, and one-bit or bit-wise prior noise with noise probability at most $1/2$, and at the same time simplifies its proof. With the same general argument, among others, we also derive a sub-exponential upper bound for the runtime of the $(1,λ)$ evolutionary algorithm on the OneMax problem when the offspring population size $λ$ is logarithmic, but below the efficiency threshold. To show that our approach can also deal with non-trivial parent population sizes, we prove an exponential upper bound for the runtime of the mutation-based version of the simple genetic algorithm on the OneMax benchmark, matching a known exponential lower bound.
