Level-Based Analysis of the Univariate Marginal Distribution Algorithm
Level-Based Analysis of the Univariate Marginal Distribution Algorithm
复制标题
单变量边际分布算法的基于级别的分析
作者：
D. Dang;P. Lehre;P. Nguyen
分布估计算法（EDAs）是一种随机启发式算法，它通过从概率模型中学习和抽样来寻找最优解。尽管它们在实际应用程序中很受欢迎，但对其性能的严格理解却很少。即使对于单变量边际分布算法（UMDA）——一种简单的基于人口的EDA，假设决策变量之间的独立性——OneMax线性问题的优化时间直到最近才确定。对EDAs的理论认识不完整主要是由于缺乏适当的分析工具。我们证明了最近发展的非精英群体的基于水平的定理与反集中结果相结合，产生了UMDA预期优化时间的上界。这种方法产生了Onλlogλ+n2documentclass[12pt]{minimal} useppackageamsmath{ useppackagewasysym} useppackageamsfonts{ useppackageamssfs }useppackageamssyb{ setlengthoddsidemargin}-69pt{ }egindocument{}{}{}{}{}{}$$mathcal {O}left( nlambda log lambda +n^2
ight) $$ enddocument{关于人口大小的LeadingOnes}和BinVal问题λ>μ=Ω（logn）documentclass[12pt]minimal {useppackageamsmath }useppackagewasysym{ useppackageamsfonts} useppackageamssyb{ useppackageamssy} useppackagemathrsfs{ useppackageup希腊}setlengththoddsidemargin{ -69pt} egindocument {}{}{}{}{}{}$$lambda >mu =varOmega (log n)$$ enddocument；{其中}μdocumentclass[12pt]minimal {useppackageamsmath} useppackageamsfonts {useppackageamssyb} useppackageamsfs{ useppackageamsmath} setlengthoddsidemargin{-69pt }egindocument{}{}{}{}{}{}{}$$mu $$ enddocument{和λ}documentclass{[12pt}]minimal{ useppackageamsmath useppackageamssystem useppackageamsfonts }useppackageamssyb{ useppackageamssy} useppackageamsfs{ useppackageams}希腊{setlengthoddsidemargin}-{69pt egindocument }{}{}{}{}{}$$lambda $$ enddocument{是}算法{的参数。我们还}证明了具有{总体}大小{μ∈On∩Ω（logn）documentclass[}12pt]minimal{ usepackageamsmath useppackageamsfonts useppackageamssyb useppackageamssyb useppackageamssyb }useppackageamssyb{ setlengthoddsidemargin}-69pt{ egindocument }{}{}{}{}{}$$mu in mathcal {O}left( sqrt{n}
ight) cap varOmega (log n)$$ enddocument{在预期时间内优化OneMax} λ{ndocumentclass}[12pt{]minimal} useppackageamsmath {useppackageamssym} useppackageamsfonts{ useppackageamssyb useppackageamssys} useppackageamsfs useppackageamsfs uspackpackageup希腊{Setlengthoddsidemargin}-{69pt egindocument}{}{}{}{}{}$$mathcal {O}left( lambda n
ight) $$ enddocument{，对于更大的}人口{规模μ=Ω（}nlogn）documentclass{[12pt}]minimal{ usepackageamsmath} useppackagewasysym {useppackageamsfonts} useppackageamssyb {useppackageamssy} useppackagemathrsfs useppackageupgreek Setlengthoddsidemargin-{69pt egindocument}{}{}{}{}{}$$mu =varOmega (sqrt{n}log n)$$ enddocument{，在预期的}时间0 λndocumentclass{[12pt}]minimal{ usepackageamsmath} useppackageamsfonts{ useppackageamssymb useppackageamssy} useppackagemathrsfs{ setlengththoddsidemargin} -69pt egindocument {}{}{}{}{}{}{}$$mathcal {O}left( lambda sqrt{n}
ight) $$ enddocument{。}我们论证的便利性和通用性表明，这是一种很有前途的方法来推导eda的预期优化时间的界限。
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 OneMax was 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 Onλlogλ+n2documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$mathcal {O}left( nlambda log lambda +n^2
ight) $$end{document} on the LeadingOnes and BinVal problems for population sizes λ>μ=Ω(logn)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$lambda >mu =varOmega (log n)$$end{document}, where μdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$mu $$end{document} and λdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$lambda $$end{document} are parameters of the algorithm. We also prove that the UMDA with population sizes μ∈On∩Ω(logn)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$mu in mathcal {O}left( sqrt{n}
ight) cap varOmega (log n)$$end{document} optimises OneMax in expected time Oλndocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$mathcal {O}left( lambda n
ight) $$end{document}, and for larger population sizes μ=Ω(nlogn)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$mu =varOmega (sqrt{n}log n)$$end{document}, in expected time Oλndocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$mathcal {O}left( lambda sqrt{n}
ight) $$end{document}. The facility and generality of our arguments suggest that this is a promising approach to derive bounds on the expected optimisation time of EDAs.
DOI：
10.1145/2908812.2908895
发表时间：
2016-07
期刊：
Proceedings of the Genetic and Evolutionary Computation Conference 2016
影响因子：
--
作者：
T. Friedrich;Timo Kötzing;Martin S. Krejca
通讯作者：
T. Friedrich;Timo Kötzing;Martin S. Krejca
影响因子：
14.3
作者：
Friedrich, Tobias;Koetzing, Timo;Sutton, Andrew M.
通讯作者：
Sutton, Andrew M.