Level-Based Analysis of the Population-Based Incremental Learning Algorithm
Level-Based Analysis of the Population-Based Incremental Learning Algorithm
复制标题
基于群体的增量学习算法的基于级别的分析
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
P. Nguyen
中科院分区：
文献类型：
--
作者：
P. Lehre;P. Nguyen
基于种群的增量学习（PBIL）算法使用当前模型和经验模型的凸组合来构建下一个模型，然后对该模型进行采样以生成后代。单变量边际分布算法（UMDA）是PBIL的一种特殊情况，其中忽略当前模型。Dang和Lehre（GECCO 2015）表明，UMDA可以有效地优化领导者。问题仍然是开放的，如果PBIL表现同样好。在这里，通过应用基于水平的定理以及Dvoretzky-Kiefer-Wolfowitz不等式，我们证明了PBIL在期望时间内优化函数LeadingOnes（mathcal {O}left（nlambda log lambda +n^2
8）），其匹配UMDA的界限。最后，我们表明，结果结转到BinVal，给出第一个运行时的结果为PBIL的BinVal问题。
The Population-Based Incremental Learning (PBIL) algorithm uses a convex combination of the current model and the empirical model to construct the next model, which is then sampled to generate offspring. The Univariate Marginal Distribution Algorithm (UMDA) is a special case of the PBIL, where the current model is ignored. Dang and Lehre (GECCO 2015) showed that UMDA can optimise LeadingOnes efficiently. The question still remained open if the PBIL performs equally well. Here, by applying the level-based theorem in addition to Dvoretzky–Kiefer–Wolfowitz inequality, we show that the PBIL optimises function LeadingOnes in expected time (mathcal {O}left( nlambda log lambda +n^2
ight) ) for a population size (lambda =varOmega (log n)), which matches the bound of the UMDA. Finally, we show that the result carries over to BinVal, giving the fist runtime result for the PBIL on the BinVal problem.
影响因子：
14.3
作者：
Corus, Dogan;Oliveto, Pietro S.
通讯作者：
Oliveto, Pietro S.