Runtime analysis aims at contributing to our understanding of evolutionary algorithms through mathematical analyses of their runtimes. In the context of discrete optimization problems, runtime analysis classically studies the time needed to find an optimal solution. However, both from a practical and from a theoretical viewpoint, more fine-grained performance measures are needed to gain a more detailed understanding of the main working principles and their resulting performance implications. Two complementary approaches have been suggested: fixed-budget analyses and fixed-target analyses. In this work, we conduct an in-depth study on the advantages and the limitations of fixed-target analyses. We show that, different from fixed-budget analyses, many classical methods from the runtime analysis of discrete evolutionary algorithms yield fixed-target results without greater effort. We use this to conduct a number of new fixed-target analyses. However, we also point out examples where an extension of existing runtime results to fixed-target results is highly non-trivial.


翻译:运行时间分析的目的是通过对运行时间进行数学分析,促进我们对演进算法的理解。在离散优化问题的背景下,运行时间分析典型地研究寻找最佳解决方案所需的时间。然而,从实际和理论的角度来看,需要更精细的绩效措施,以便更详细地了解主要工作原则及其所产生的绩效影响。建议了两种互补办法:固定预算分析和固定目标分析。在这项工作中,我们深入研究固定目标分析的优势和局限性。我们表明,与固定预算分析不同的是,与对离散演进算法的运行时间分析不同的许多经典方法都产生了固定目标结果,但没有作出更大的努力。我们用这种方法进行一些新的固定目标分析。然而,我们还指出了将现有运行时间结果扩大到固定目标结果的高度非三边性的例子。

0
下载
关闭预览

相关内容

专知会员服务
42+阅读 · 2020年12月18日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
专知会员服务
39+阅读 · 2020年9月6日
迁移学习简明教程,11页ppt
专知会员服务
107+阅读 · 2020年8月4日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
已删除
将门创投
7+阅读 · 2018年10月12日
视觉机械臂 visual-pushing-grasping
CreateAMind
3+阅读 · 2018年5月25日
神经网络学习率设置
机器学习研究会
4+阅读 · 2018年3月3日
Python机器学习教程资料/代码
机器学习研究会
8+阅读 · 2018年2月22日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
Arxiv
0+阅读 · 2021年11月28日
Arxiv
0+阅读 · 2021年11月26日
Arxiv
5+阅读 · 2017年12月14日
VIP会员
相关VIP内容
专知会员服务
42+阅读 · 2020年12月18日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
专知会员服务
39+阅读 · 2020年9月6日
迁移学习简明教程,11页ppt
专知会员服务
107+阅读 · 2020年8月4日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
相关资讯
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
已删除
将门创投
7+阅读 · 2018年10月12日
视觉机械臂 visual-pushing-grasping
CreateAMind
3+阅读 · 2018年5月25日
神经网络学习率设置
机器学习研究会
4+阅读 · 2018年3月3日
Python机器学习教程资料/代码
机器学习研究会
8+阅读 · 2018年2月22日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
Top
微信扫码咨询专知VIP会员