首页> 外文期刊>Algorithmica >Level-Based Analysis of the Univariate Marginal Distribution Algorithm
【24h】

Level-Based Analysis of the Univariate Marginal Distribution Algorithm

机译:基于水平的单变量边际分布算法分析

获取原文
获取原文并翻译 | 示例

摘要

Estimation of Distribution Algorithms (EDAs) are stochastic heuristics that search for optimal solutions by learning and sampling from probabilistic models. Despite their popularity in real-world applications, there is little rigorous understanding of their performance. Even for the Univariate Marginal Distribution Algorithm (UMDA)-a simple population-based EDA assuming independence between decision variables-the optimisation time on the linear problem OneMaxwas until recently undetermined. The incomplete theoretical understanding of EDAs is mainly due to the lack of appropriate analytical tools. We show that the recently developed level-based theorem for non-elitist populations combined with anti-concentration results yield upper bounds on the expected optimisation time of the UMDA. This approach results in the bound O(n lambda log lambda + n(2))on the LeadingOnes and BinVal problems for population sizes lambda mu = Omega(log n), where mu and lambda are parameters of the algorithm. We also prove that the UMDA with population sizes mu is an element of O (root n) boolean AND Omega (log n) optimises OneMax in expected time O(lambda n), and for larger population sizes mu = Omega(root n log n), in expected time O (lambda root n) The facility and generality of our arguments suggest that this is a promising approach to derive bounds on the expected optimisation time of EDAs.
机译:分布算法(EDA)的估计是随机启发式算法,通过从概率模型中学习和采样来寻找最佳解决方案。尽管它们在实际应用中很受欢迎,但对其性能却缺乏严格的了解。即使对于单变量边际分布算法(UMDA)-一种简单的基于人口的EDA,假设决策变量之间具有独立性-线性问题的优化时间OneMax直到最近还没有确定。对EDA的理论理解不全面,主要是由于缺乏适当的分析工具。我们表明,最近开发的针对非精英人群的基于水平的定理与反集中结果相结合,在UMDA的预期优化时间上产生了上限。对于人口规模为lambda> mu = Omega(log n)的种群大小,此方法导致LeadingOnes和BinVal问题上的约束O(n lambda log lambda + n(2)),其中mu和lambda是算法的参数。我们还证明,人口规模为mu的UMDA是O(根n)布尔值的一个元素,而Omega(log n)在预期时间O(λn)中优化了OneMax,对于更大的人口规模,mu = Omega(根n log n) ),在预期时间O(λ根n)中,我们的论点的便利性和普遍性表明,这是一种有希望的方法,可以得出EDA预期优化时间的界限。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号