标题： 紧凑遗传算法在LeadingOnes基准上的运行时间分析 显示英文标题

标题： Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes Benchmark

摘要： 紧凑遗传算法（cGA）是估计分布算法（EDAs）中最简单的一种。 除了单变量边缘分布算法（UMDA）——另一种简单的EDA——之外，cGA已经经历了广泛的数学运行时间分析，通常展示了与竞争方法相似甚至更优的性能。 然而令人惊讶的是，到目前为止，与UMDA和其他许多启发式方法不同，我们缺乏对cGA在LeadingOnes基准上的严格运行时间分析——这是进化计算领域中最受研究的理论基准之一。 我们通过在LeadingOnes上进行cGA的正式运行时间分析来填补这一文献空白。 对于cGA的单一参数——称为假设种群大小——至少比问题规模大多项对数，我们证明了cGA以高概率在函数评估次数接近于问题规模的线性数量和假设种群大小的线性数量内采样到LeadingOnes的最优解。 对于最佳假设种群大小，我们的结果在多项对数因子范围内与许多随机搜索启发式在LeadingOnes上表现出的典型二次运行时间相匹配。 我们的分析显示了两种算法在工作原理上的一些值得注意的差异，这些差异在以前的研究中并未显现。 显示英文摘要

摘要： The compact genetic algorithm (cGA) is one of the simplest estimation-of-distribution algorithms (EDAs). Next to the univariate marginal distribution algorithm (UMDA) -- another simple EDA -- , the cGA has been subject to extensive mathematical runtime analyses, often showcasing a similar or even superior performance to competing approaches. Surprisingly though, up to date and in contrast to the UMDA and many other heuristics, we lack a rigorous runtime analysis of the cGA on the LeadingOnes benchmark -- one of the most studied theory benchmarks in the domain of evolutionary computation. We fill this gap in the literature by conducting a formal runtime analysis of the cGA on LeadingOnes. For the cGA's single parameter -- called the hypothetical population size -- at least polylogarithmically larger than the problem size, we prove that the cGA samples the optimum of LeadingOnes with high probability within a number of function evaluations quasi-linear in the problem size and linear in the hypothetical population size. For the best hypothetical population size, our result matches, up to polylogarithmic factors, the typical quadratic runtime that many randomized search heuristics exhibit on LeadingOnes. Our analysis exhibits some noteworthy differences in the working principles of the two algorithms which were not visible in previous works.