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