论文标题
通过负乘法漂移的非精美进化算法的下限
Lower Bounds for Non-Elitist Evolutionary Algorithms via Negative Multiplicative Drift
论文作者
论文摘要
到目前为止，已经显示了基于非精英人群的进化算法的不相当的下限。由于（难以避免）使用负漂移定理（一般结果），他们中的大多数人在技术上要求很高 - 这将预期的进度从目标转化为高点击时间。 我们为乘法漂移方案提出了一个简单的负漂移定理，并表明它可以简化现有分析。我们更详细地讨论了Lehre的（PPSN 2010）\ Emph {人群中的负漂移}方法，这是证明离散搜索空间的基于非私人突变的进化算法的运行时最低界限的最通用工具之一。与其他参数一起，我们获得了一个替代性和简单的证明，这也可以增强并简化此方法。特别是，现在必须验证先前结果的五个技术条件中的三个。我们获得的下限是显式的，而不仅仅是渐近学。这允许计算混凝土算法的混凝土下限，但也使我们能够表明，当复制速率仅为$（1-ω（n^{ - 1/2}}））$以下时，超级多项式运行时间已经出现。对于使用标准位突变的特殊情况，具有随机突变速率（称为均匀混合术语的语言），我们证明了Dang and Lehre（PPSN 2016）所述的结果，并将其扩展到包括$θ（1/N）$以外的突变速率，其中包括doerr，leerr，le eerr，makhmare（包括重型突变运营商的建议），并将其扩展到Makhmare（Makhmare），并将其扩展到。最终，我们将我们的方法和一个新颖的统治论点用于显示\ onemax上仅突变的仅突变简单遗传算法的指数下限，以实现任意种群的大小。
A decent number of lower bounds for non-elitist population-based evolutionary algorithms has been shown by now. Most of them are technically demanding due to the (hard to avoid) use of negative drift theorems -- general results which translate an expected progress away from the target into a high hitting time. We propose a simple negative drift theorem for multiplicative drift scenarios and show that it can simplify existing analyses. We discuss in more detail Lehre's (PPSN 2010) \emph{negative drift in populations} method, one of the most general tools to prove lower bounds on the runtime of non-elitist mutation-based evolutionary algorithms for discrete search spaces. Together with other arguments, we obtain an alternative and simpler proof, which also strengthens and simplifies this method. In particular, now only three of the five technical conditions of the previous result have to be verified. The lower bounds we obtain are explicit instead of only asymptotic. This allows to compute concrete lower bounds for concrete algorithms, but also enables us to show that super-polynomial runtimes appear already when the reproduction rate is only a $(1 - ω(n^{-1/2}))$ factor below the threshold. For the special case of algorithms using standard bit mutation with a random mutation rate (called uniform mixing in the language of hyper-heuristics), we prove the result stated by Dang and Lehre (PPSN 2016) and extend it to mutation rates other than $Θ(1/n)$, which includes the heavy-tailed mutation operator proposed by Doerr, Le, Makhmara, and Nguyen (GECCO 2017). We finally apply our method and a novel domination argument to show an exponential lower bound for the runtime of the mutation-only simple genetic algorithm on \onemax for arbitrary population size.
