It is an ongoing debate whether and how comma selection in evolutionary algorithms helps to escape local optima. We propose a new benchmark function to investigate the benefits of comma selection: OneMax with randomly planted local optima, generated by frozen noise. We show that comma selection (the $(1,\lambda)$ EA) is faster than plus selection (the $(1+\lambda)$ EA) on this benchmark, in a fixed-target scenario, and for offspring population sizes $\lambda$ for which both algorithms behave differently. For certain parameters, the $(1,\lambda)$ EA finds the target in $\Theta(n \ln n)$ evaluations, with high probability (w.h.p.), while the $(1+\lambda)$ EA) w.h.p. requires almost $\Theta((n\ln n)^2)$ evaluations. We further show that the advantage of comma selection is not arbitrarily large: w.h.p. comma selection outperforms plus selection at most by a factor of $O(n \ln n)$ for most reasonable parameter choices. We develop novel methods for analysing frozen noise and give powerful and general fixed-target results with tail bounds that are of independent interest.


翻译:论文题目翻译:逗号选择优于加号选择的OneMax问题中随机种下最优点的情况 摘要翻译:目前存在一个争论,即逗号选择在进化算法中是否有助于逃脱局部最优解及如何做到这一点。为了探究逗号选择的好处,我们提出了一个新的基准函数:带有随机种下局部最优点的OneMax问题,通过冻结噪声生成。我们证明,在确定目标的场景下,采用逗号选择($(1,\lambda)$ EA)比采用加号选择($(1+\lambda)$ EA)更快,并且只适用于不同的后代种群大小$\lambda$时。对于某些参数,$(1,\lambda)$ EA可以在$\Theta(n \ln n)$次评估内,高概率地找到目标,而$(1+\lambda)$ EA需要几乎$\Theta((n\ln n)^2)$次评估。我们进一步证明,逗号选择的优势并不是任意大的:在大多数合理的参数选择下,w.h.p. 逗号选择最多比加号选择快$O(n \ln n)$倍。我们开发了分析冻结噪声的新方法,并给出了强大且普遍的确定目标结果的尾部界限,对此非常感兴趣。

0
下载
关闭预览

相关内容

局部最优,是指对于一个问题的解在一定范围或区域内最优,或者说解决问题或达成目标的手段在一定范围或限制内最优。在应用数学和计算机科学中,优化问题的局部最优是在候选解决方案的相邻集合内最优(最大或最小)的解决方案。 这与全局最优相反,后者是所有可能的解决方案中的最优解决方案,而不仅仅是在特定值附近的最优解决方案。
【AAAI2023】基于Dirichlet元模型的事后不确定性学习
专知会员服务
15+阅读 · 2022年12月16日
【NeurIPS 2021】设置多智能体策略梯度的方差
专知会员服务
20+阅读 · 2021年10月24日
专知会员服务
17+阅读 · 2021年9月21日
【MIT】反偏差对比学习,Debiased Contrastive Learning
专知会员服务
90+阅读 · 2020年7月4日
如何用正则化防止模型过拟合?
PaperWeekly
0+阅读 · 2022年8月18日
一文理解Ranking Loss/Margin Loss/Triplet Loss
极市平台
16+阅读 · 2020年8月10日
一文读懂线性回归、岭回归和Lasso回归
CSDN
34+阅读 · 2019年10月13日
NAACL 2019 | 一种考虑缓和KL消失的简单VAE训练方法
PaperWeekly
20+阅读 · 2019年4月24日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
2+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Arxiv
0+阅读 · 2023年6月1日
VIP会员
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
2+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Top
微信扫码咨询专知VIP会员