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

Exponential slowdown for larger populations: The (μ+1)-EA on monotone functions

THEORETICAL COMPUTER SCIENCE 2021年 875卷 28-51页

作者： Lengler, Johannes Zou, Xun Swiss Fed Inst Technol Zurich Switzerland

Pseudo-Boolean monotone functions are unimodal functions which are trivial to optimize for some hillclimbers, but are challenging for a surprising number of evolutionary algorithms. A general trend is that evolutionary algorithms are efficient if parameters like the mutation rate are set conservatively, but may need exponential time otherwise. In particular, it was known that the (1 + 1)-EA and the (1 + lambda)-EA can optimize every monotone function in pseudolinear time if the mutation rate is c/n for some c < 1, but that they need exponential time for some monotone functions for c > 2.2. The second part of the statement was also known for the (mu + 1)-EA. In this paper we show that the first statement does notapply to the (mu + 1)-EA. More precisely, we prove that for every constant c > 0 there is a constant mu(0) is an element of N such that the (mu + 1)-EA with mutation rate c/n and population size mu(0) <= mu <= n needs superpolynomial time to optimize some monotone functions. Thus, increasing the population size by just a constant has devastating effects on the performance. This is in stark contrast to many other benchmark functions on which increasing the population size either increases the performance significantly, or affects performance only mildly. The reason why larger populations are harmful lies in the fact that larger populations may temporarily decrease the selective pressure on parts of the population. This allows unfavorable mutations to accumulate in single individuals and their descendants. If the population moves sufficiently fast through the search space, then such unfavorable descendants can become ancestors of future generations, and the bad mutations are preserved. Remarkably, this effect only occurs if the population renews itself sufficiently fast, which can only happen far away from the optimum. This is counter-intuitive since usually optimization becomes harder as we approach the optimum. Previous work missed the effect because it focus

关键词： Evolutionary algorithm Monotone functions Population size Mutation rate Runtime analysis hottopic functions

来源：评论

学校读者我要写书评

暂无评论

Exponential Slowdown for Larger Populations: The (μ+1)-EA on Monotone functions 19

Exponential Slowdown for Larger Populations: The (μ+1)-EA o...

引用

15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA)

作者： Lengler, Johannes Zou, Xun Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9781450362542

Pseudo-Boolean monotone functions are unimodal functions which are trivial to optimize for some hillclimbers, but are challenging for a surprising number of evolutionary algorithms. A general trend is that evolutionary algorithms are efficient if parameters like the mutation rate are set conservatively, but may need exponential time otherwise. In particular, it was known that the (1 + 1)-EA and the (1 + lambda)-EA can optimize every monotone function in pseudolinear time if the mutation rate is c/n for some c < 1, but that they need exponential time for some monotone functions for c > 2.2. The second part of the statement was also known for the (mu + 1)-EA. In this paper we show that the first statement does not apply to the (mu + 1)-EA. More precisely, we prove that for every constant c > 0 there is a constant mu(0) is an element of N such that the (mu + 1)-EA with mutation rate c/n and population size mu(0) <= mu <= n needs superpolynomial time to optimize some monotone functions. Thus, increasing the population size by just a constant has devastating effects on the performance. This is in stark contrast to many other benchmark functions on which increasing the population size either increases the performance significantly, or affects performance only mildly. The reason why larger populations are harmful lies in the fact that larger populations may temporarily decrease selective pressure on parts of the population. This allows unfavorable mutations to accumulate in single individuals and their descendants. If the population moves sufficiently fast through the search space, then such unfavorable descendants can become ancestors of future generations, and the bad mutations are preserved. Remarkably, this effect only occurs if the population renews itself sufficiently fast, which can only happen far away from the optimum. This is counter-intuitive since usually optimization becomes harder as we approach the optimum. Previous work missed the effect because it focused

关键词： evolutionary algorithm monotone functions population mutation rate runtime analysis hottopic functions

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：