检索结果-内蒙古大学图书馆

level-based analysis of the Univariate Marginal Distribution Algorithm

ALGORITHMICA 2019年第2期81卷 668-702页

作者： Duc-Cuong Dang Lehre, Per Kristian Phan Trung Hai Nguyen Univ Birmingham Sch Comp Sci Birmingham B15 2TT W Midlands England

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.

关键词： Estimation of distribution algorithms Runtime analysis level-based analysis Anti-concentration

来源：评论

学校读者我要写书评

暂无评论

level-based analysis of the Population-based Incremental Learning Algorithm 15th

Level-Based Analysis of the Population-Based Incremental Lea...

引用

15th International Conference on Parallel Problem Solving from Nature (PPSN)

作者： Lehre, Per Kristian Phan Trung Hai Nguyen Univ Birmingham Birmingham W Midlands England

ISBN: (纸本)9783319992594;9783319992587

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 O (nA log lambda + n(2)) for a population size lambda = Omega(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.

关键词： Population-based incremental learning LeadingOnes BinVal Running time analysis level-based analysis Theory

来源：评论

学校读者我要写书评

暂无评论

Simplified Runtime analysis of Estimation of Distribution Algorithms 15

Simplified Runtime Analysis of Estimation of Distribution Al...

引用

17th Genetic and Evolutionary Computation Conference (GECCO)

作者： Duc-Cuong Dang Lehre, Per Kristian Univ Nottingham Sch Comp Sci ASAP Res Grp Nottingham NG7 2RD England

ISBN: (纸本)9781450334723

Estimation of distribution algorithms (EDA) are stochastic search methods that look for optimal solutions by learning and sampling from probabilistic models. Despite their popularity, there are only few rigorous theoretical analyses of their performance. Even for the simplest EDAs, such as the Univariate Marginal Distribution Algorithm (UMDA) which assumes independence between decision variables, there are only a handful of results about its runtime, and results for simple functions such as ONEMAX are still missing. In this paper, we show that the recently developed level-based theorem for non-elitist populations is directly applicable to runtime analysis of EDAs. To demonstrate this approach, we derive easily upper bounds on the expected runtime of the UMDA.

关键词： Runtime analysis level-based analysis Estimation of Distribution Algorithm

来源：评论

学校读者我要写书评

暂无评论

Runtime Analyses of the Population-based Univariate Estimation of Distribution Algorithms on LeadingOnes

引用

ALGORITHMICA 2021年第10期83卷 3238-3280页

作者： Lehre, Per Kristian Nguyen, Phan Trung Hai Univ Birmingham Sch Comp Sci Birmingham B15 2TT W Midlands England Univ Exeter Dept Comp Sci Exeter EX4 4QJ Devon England

We perform rigorous runtime analyses for the univariate marginal distribution algorithm (UMDA) and the population-based incremental learning (PBIL) Algorithm on LeadingOnes. For the UMDA, the currently known expected runtime on the function is O(n lambda log lambda + n(2)) under an offspring population size lambda = Omega(log n) and a parent population size mu <= lambda/(e(1 + delta)) for any constant delta > 0 (Dang and Lehre, GECCO 2015). There is no lower bound on the expected runtime under the same parameter settings. It also remains unknown whether the algorithm can still optimise the LeadingOnes function within a polynomial runtime when mu >= lambda/(e(1+delta)). In case of the PBIL, an expected runtime of O(n(2+c)) holds for some constant c is an element of(0,1) (Wu, Kolonko and Mohring, IEEE TEVC 2017). Despite being a generalisation of the UMDA, this upper bound is significantly asymptotically looser than the upper bound of O(n(2) of the UMDA for lambda=Omega(log n) boolean AND O. Furthermore, the required population size is very large, i.e., lambda=Omega(n(1+c)). Our contributions are then threefold: (1) we show that the UMDA with mu=Omega(log n) and lambda <= mu e(1-epsilon)/(1+delta) for any constants epsilon is an element of(0,1) and 0 < delta <= e(1-epsilon)-1 requires an expected runtime of e(Omega(mu)) on LEADINGONES, (2) an upper bound of O(n lambda log lambda + n(2)) is shown for the PBIL, which improves the current bound O(n(2+c)) by a significant factor of Theta(n(c)), and (3) we for the first time consider the two algorithms on the LeadingOnes function in a noisy environment and obtain an expected runtime of O(n(2)) for appropriate parameter settings. Our results emphasise that despite the independence assumption in the probabilistic models, the UMDA and the PBIL with fine-tuned parameter choices can still cope very well with variable interactions.

关键词： Estimation of distribution algorithms Running time analysis level-based analysis Noisy optimisation Theory of randomised search heuristics

来源：评论

学校读者我要写书评

暂无评论

Self-Adaptation in Nonelitist Evolutionary Algorithms on Discrete Problems With Unknown Structure

引用

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION 2020年第4期24卷 650-663页

作者： Case, Brendan Lehre, Per Kristian Univ Vermont Sch Comp Sci Burlington VT 05405 USA Univ Vermont Complex Syst Ctr Burlington VT 05405 USA Univ Birmingham Sch Comp Sci Birmingham B15 2TT W Midlands England

A key challenge to make effective use of evolutionary algorithms (EAs) is to choose appropriate settings for their parameters. However, the appropriate parameter setting generally depends on the structure of the optimization problem, which is often unknown to the user. Nondeterministic parameter control mechanisms adjust parameters using information obtained from the evolutionary process. Self-adaptation-where parameter settings are encoded in the chromosomes of individuals and evolve through mutation and crossover-is a popular parameter control mechanism in evolutionary strategies. However, there is little theoretical evidence that self-adaptation is effective, and self-adaptation has largely been ignored by the discrete evolutionary computation community. Here, we show through a theoretical runtime analysis that a nonelitist, discrete EA which self-adapts its mutation rate not only outperforms EAs which use static mutation rates on LEADINGONES(k) but also improves asymptotically on an EA using a state-of-the-art control mechanism. The structure of this problem depends on a parameter k, which is a priori unknown to the algorithm, and which is needed to appropriately set a fixed mutation rate. The self-adaptive EA achieves the same asymptotic runtime as if this parameter was known to the algorithm beforehand, which is an asymptotic speedup for this problem compared to all other EAs previously studied. An experimental study of how the mutation-rates evolve show that they respond adequately to a diverse range of problem structures. These results suggest that self-adaptation should be adopted more broadly as a parameter control mechanism in discrete, nonelitist EAs.

关键词： Evolutionary algorithm (EA) level-based analysis runtime analysis self-adaptation

来源：评论

学校读者我要写书评

暂无评论

Improved Runtime Bounds for the Univariate Marginal Distribution Algorithm via Anti-Concentration 17

Improved Runtime Bounds for the Univariate Marginal Distribu...

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Lehre, Per Kristian Phan Trung Hai Nguyen Univ Birmingham Sch Comp Sci Birmingham B15 2TT W Midlands England

ISBN: (纸本)9781450349208

Unlike traditional evolutionary algorithms which produce offspring via genetic operators, Estimation of Distribution Algorithms (EDAs) sample solutions from probabilistic models which are learned from selected individuals. It is hoped that EDAs may improve optimisation performance on epistatic fitness landscapes by learning variable interactions. However, hardly any rigorous results are available to support claims about the performance of EDAs, even for fitness functions without epistasis. The expected runtime of the Univariate Marginal Distribution Algorithm (UMDA) on OneMax was recently shown to be in O (n lambda log lambda) [9]. Later, Krejca and WiS proved the lower bound Omega(lambda root n + n logn) via an involved dri% analysis [16]. We prove a O (n lambda) bound, given some restrictions on the population size. Ois implies the tight bound Theta (n logn) when lambda = O (logn), matching the runtime of classical EAs. Our analysis uses the level-based theorem and anti-concentration properties of the Poisson-binomial distribution. We expect that these generic methods will facilitate further analysis of EDAs.

关键词： Runtime analysis level-based analysis Estimation of Distribution Algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：