Black-box optimization is a very active area of research, with many new algorithms being developed every year. This variety is needed, on the one hand, since different algorithms are most suitable for different types of optimization problems. But the variety also poses a meta-problem: which algorithm to choose for a given problem at hand? Past research has shown that per-instance algorithm selection based on exploratory landscape analysis (ELA) can be an efficient mean to tackle this meta-problem. Existing approaches, however, require the approximation of problem features based on a significant number of samples, which are typically selected through uniform sampling or Latin Hypercube Designs. The evaluation of these points is costly, and the benefit of an ELA-based algorithm selection over a default algorithm must therefore be significant in order to pay off. One could hope to by-pass the evaluations for the feature approximations by using the samples that a default algorithm would anyway perform, i.e., by using the points of the default algorithm's trajectory. We analyze in this paper how well such an approach can work. Concretely, we test how accurately trajectory-based ELA approaches can predict the final solution quality of the CMA-ES after a fixed budget of function evaluations. We observe that the loss of trajectory-based predictions can be surprisingly small compared to the classical global sampling approach, if the remaining budget for which solution quality shall be predicted is not too large. Feature selection, in contrast, did not show any advantage in our experiments and rather led to worsened prediction accuracy. The inclusion of state variables of CMA-ES only has a moderate effect on the prediction accuracy.


翻译:黑盒优化是一个非常活跃的研究领域,每年开发许多新的算法。一方面,这种多样性是必要的,因为不同的算法最适合不同类型的优化问题。但是,这种多样性也带来了一个元问题:对手头的某个问题选择哪种算法?过去的研究表明,基于探索性地貌分析(拉美经济体系)的永久性算法选择可能是解决这一元问题的一个有效手段。但是,现有的方法需要根据大量样本(通常通过统一取样或拉丁超立方设计来选择)来近似问题特征。这些样本通常是通过统一采样或拉丁超立方设计来选择的。这些点的评估费用很高,而基于拉美经济体系的算法选择对默认算法的好处也必须是巨大的,因此,人们可能希望通过使用默认算法的参数选择来通过对特征进行评价,也就是说,通过使用默认算法轨迹轨迹的轨迹,我们只能分析这种方法的稳定性优势如何。具体地说,我们测试基于轨迹的纳入这些点的准确性推算的准确度,而基于以拉美经济体系的算法选择方法的精确度推算的精确度选择方法,这样可以预测整个预算的精确地反映成本的精确度,我们对结果的精确的预测结果的精确的精确度的精确的精确度,然后才能对结果的精确度的精确度评估。

0
下载
关闭预览

相关内容

专知会员服务
123+阅读 · 2020年9月8日
【干货书】真实机器学习,264页pdf,Real-World Machine Learning
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
LibRec 精选:连通知识图谱与推荐系统
LibRec智能推荐
3+阅读 · 2018年8月9日
LibRec 精选:推荐的可解释性[综述]
LibRec智能推荐
10+阅读 · 2018年5月4日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
Arxiv
0+阅读 · 2021年4月1日
Efficient and Effective $L_0$ Feature Selection
Arxiv
5+阅读 · 2018年8月7日
VIP会员
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
LibRec 精选:连通知识图谱与推荐系统
LibRec智能推荐
3+阅读 · 2018年8月9日
LibRec 精选:推荐的可解释性[综述]
LibRec智能推荐
10+阅读 · 2018年5月4日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
Top
微信扫码咨询专知VIP会员