核心发现
方法论
本文提出了一种基于相似度的算法投资组合构建方法，用于解决黑箱优化中的算法选择问题。该方法首先在完整的训练集上构建一个初始投资组合，然后利用k近邻方法对未见实例进行微调。通过这种方式，投资组合能够更好地适应特定问题实例的特征，从而提高优化性能。具体而言，方法包括：1) 使用离散经验达成函数（EAF）作为性能度量；2) 采用贪婪策略构建投资组合；3) 利用k近邻方法在特征空间中选择相似的训练实例进行微调。
关键结果
- 结果1：在完整训练集上构建的初始投资组合已经超过了虚拟最佳求解器（VBS），显示出其优越性。
- 结果2：通过k近邻微调后的投资组合在未见实例上的表现进一步提升，平均性能提高了约10%。
- 结果3：在多维度问题上，局部优化的投资组合表现优于全局优化的投资组合，尤其是在高维问题上。
研究意义
该研究在算法选择领域具有重要意义。传统的算法选择方法通常依赖于单一算法的选择，而本文提出的投资组合方法通过分配预算给多个算法，显著提高了优化性能。这种方法不仅降低了选择错误算法的风险，还通过算法间的互补性实现了性能的提升。对于固定预算的黑箱优化问题，该方法提供了一种更为精细的解决方案。
技术贡献
本文的技术贡献在于将算法选择问题转化为预算分配问题，并提出了一种基于k近邻的微调方法来优化投资组合。与现有方法相比，该方法能够更好地利用算法间的互补性，并在多种问题维度上展示了其鲁棒性和适应性。此外，本文还引入了离散经验达成函数（EAF）作为性能度量工具，为投资组合的构建提供了新的理论基础。
新颖性
本文首次将k近邻方法应用于算法投资组合的微调，显著提高了黑箱优化的性能。与传统的单一算法选择方法相比，本文的方法在处理多样化问题实例时表现出更高的灵活性和适应性。
局限性
- 局限1：该方法在计算复杂度上较高，尤其是在处理大规模训练集时，k近邻搜索可能导致计算开销增加。
- 局限2：方法的性能依赖于特征空间的质量，如果特征不能有效表征问题实例，可能影响投资组合的效果。
- 局限3：在某些情况下，局部优化的投资组合可能不如全局优化的投资组合稳定。
未来方向
未来的研究方向包括：1) 开发更高效的k近邻搜索算法以降低计算复杂度；2) 探索更丰富的特征空间以提高方法的适应性；3) 在更大规模和更复杂的优化问题上验证方法的有效性。
AI 总览摘要
在黑箱优化领域，选择合适的算法来解决给定问题一直是一个挑战。传统的算法选择方法通常依赖于单一算法的选择，这种方法存在选择错误算法的风险，并且即使是性能良好的算法在单次运行中也可能表现不佳。为了解决这一问题，本文提出了一种基于相似度的算法投资组合构建方法。
该方法首先在完整的训练集上构建一个初始投资组合，然后利用k近邻方法对未见实例进行微调。具体而言，方法包括：使用离散经验达成函数（EAF）作为性能度量，采用贪婪策略构建投资组合，并利用k近邻方法在特征空间中选择相似的训练实例进行微调。
实验结果表明，在完整训练集上构建的初始投资组合已经超过了虚拟最佳求解器（VBS），显示出其优越性。通过k近邻微调后的投资组合在未见实例上的表现进一步提升，平均性能提高了约10%。在多维度问题上，局部优化的投资组合表现优于全局优化的投资组合，尤其是在高维问题上。
该研究在算法选择领域具有重要意义。传统的算法选择方法通常依赖于单一算法的选择，而本文提出的投资组合方法通过分配预算给多个算法，显著提高了优化性能。这种方法不仅降低了选择错误算法的风险，还通过算法间的互补性实现了性能的提升。对于固定预算的黑箱优化问题，该方法提供了一种更为精细的解决方案。
然而，该方法在计算复杂度上较高，尤其是在处理大规模训练集时，k近邻搜索可能导致计算开销增加。此外，方法的性能依赖于特征空间的质量，如果特征不能有效表征问题实例，可能影响投资组合的效果。未来的研究方向包括开发更高效的k近邻搜索算法以降低计算复杂度，探索更丰富的特征空间以提高方法的适应性，并在更大规模和更复杂的优化问题上验证方法的有效性。
深度分析
研究背景
黑箱优化是一个重要的研究领域，涉及在未知或不可解析的目标函数上进行优化。随着优化算法的多样化，选择合适的算法来解决特定问题成为一个关键挑战。传统的算法选择方法通常依赖于机器学习技术，通过特征提取和分类模型来预测最优算法。然而，这些方法存在固有的风险，因为选择错误的算法可能导致性能不佳。此外，许多优化算法具有随机性，即使选择了最优算法，也可能在单次运行中表现不佳。为了应对这些挑战，近年来研究者开始探索算法投资组合的方法，通过分配预算给多个算法来提高整体性能。
核心问题
核心问题在于如何在黑箱优化中选择合适的算法来解决给定问题。传统的算法选择方法通常依赖于单一算法的选择，这种方法存在选择错误算法的风险，并且即使是性能良好的算法在单次运行中也可能表现不佳。为了降低这种风险，本文提出了一种基于相似度的算法投资组合构建方法，通过分配预算给多个算法来提高整体性能。
核心创新
本文的核心创新在于将算法选择问题转化为预算分配问题，并提出了一种基于k近邻的微调方法来优化投资组合。具体创新包括：1) 使用离散经验达成函数（EAF）作为性能度量工具，为投资组合的构建提供了新的理论基础；2) 采用贪婪策略构建投资组合，确保预算的合理分配；3) 利用k近邻方法在特征空间中选择相似的训练实例进行微调，提高了投资组合的适应性和鲁棒性。
方法详解
本文的方法论包括以下几个步骤：
- �� 使用离散经验达成函数（EAF）作为性能度量，评估算法在不同预算下的表现。
- �� 在完整的训练集上采用贪婪策略构建初始投资组合，确保预算的合理分配。
- �� 利用k近邻方法在特征空间中选择与未见实例相似的训练实例。
- �� 对选定的相似实例进行微调，优化投资组合以适应特定问题实例。
- �� 通过实验验证方法的有效性，比较微调前后的投资组合性能。
实验设计
实验设计基于多维度的MA-BBOB基准函数集，涵盖了不同的优化问题实例。实验中使用了四种优化算法：CMA-ES、对角CMA-ES、RCobyla和差分进化算法。每种算法在固定的预算下进行评估，确保公平比较。实验中采用了探索性地形分析（ELA）特征作为特征表示，通过余弦相似度在特征空间中进行相似性度量。实验结果通过在完整训练集和未见实例上的性能比较来验证方法的有效性。
结果分析
实验结果表明，在完整训练集上构建的初始投资组合已经超过了虚拟最佳求解器（VBS），显示出其优越性。通过k近邻微调后的投资组合在未见实例上的表现进一步提升，平均性能提高了约10%。在多维度问题上，局部优化的投资组合表现优于全局优化的投资组合，尤其是在高维问题上。实验结果还显示，投资组合方法能够有效利用算法间的互补性，实现性能的显著提升。
应用场景
该方法在多个领域具有潜在应用，包括机器学习模型的超参数优化、复杂系统的参数调优以及工程设计中的多目标优化。通过分配预算给多个算法，该方法能够在不确定性较高的环境中提高优化性能。此外，该方法还可以应用于需要快速响应的实时系统中，通过动态调整算法组合来适应变化的环境。
局限与展望
尽管该方法在多个实验中表现出色，但仍存在一些局限性。首先，计算复杂度较高，尤其是在处理大规模训练集时，k近邻搜索可能导致计算开销增加。其次，方法的性能依赖于特征空间的质量，如果特征不能有效表征问题实例，可能影响投资组合的效果。最后，在某些情况下，局部优化的投资组合可能不如全局优化的投资组合稳定。未来的研究方向包括开发更高效的k近邻搜索算法以降低计算复杂度，探索更丰富的特征空间以提高方法的适应性，并在更大规模和更复杂的优化问题上验证方法的有效性。
通俗解读 非专业人士也能看懂
想象一下你在一个大型超市购物，你需要买一些食材来做一顿大餐。超市里有很多种类的食材，每种食材都有自己的优缺点。你不知道哪种食材最适合你的菜谱，因为你从未做过这种菜。这就像黑箱优化中的问题选择：你不知道哪个算法最适合解决你的问题。
为了确保你的大餐成功，你决定不只选择一种食材，而是选择多种食材组合。你先在超市里挑选了一些你认为可能合适的食材，这就像在训练集上构建初始投资组合。接着，你询问了超市里的顾客，看看他们通常会选择哪些食材来做类似的菜，这就像使用k近邻方法微调你的选择。
通过这种方式，你最终选择了一组食材，它们的组合能够最大限度地提高你的菜肴成功的可能性。这种方法不仅降低了选择错误食材的风险，还通过不同食材间的互补性提升了菜肴的整体风味。
同样地，在黑箱优化中，基于相似度的投资组合方法通过分配预算给多个算法，确保在不确定性较高的环境中获得更好的优化结果。
简单解释 像给14岁少年讲一样
嘿，小伙伴！想象一下你在玩一个超级复杂的游戏，游戏里有很多关卡，每一关都需要不同的技能才能过关。你有一个工具箱，里面有很多工具，每个工具都有自己的特长。问题是，你不知道哪个工具最适合当前的关卡！
这就像科学家们在做黑箱优化时遇到的问题：他们不知道哪个算法最适合解决当前的问题。为了确保能顺利过关，你决定不只依赖一个工具，而是组合多个工具一起使用。首先，你在工具箱里挑选了一些你认为可能有用的工具，就像科学家们在训练集上构建初始投资组合。
然后，你去问了其他玩家，看看他们在类似关卡中用过哪些工具，这就像科学家们使用k近邻方法微调他们的选择。通过这种方式，你最终选择了一组工具，它们的组合能让你在游戏中表现得更好。
所以，科学家们也是这样做的！他们通过分配预算给多个算法，确保在不确定性较高的环境中获得更好的优化结果。这样一来，即使遇到超级难的关卡，他们也能顺利过关！
术语表
黑箱优化 (Black-box Optimization)
一种优化问题，其中目标函数不可解析或未知，通常需要通过实验或模拟来评估。
在本文中，黑箱优化问题是研究的核心背景。
算法选择 (Algorithm Selection)
在给定问题实例上选择最合适的算法，以获得最佳性能的过程。
本文探讨了如何通过投资组合方法改进算法选择。
投资组合 (Portfolio)
在优化中，指同时使用多个算法以提高整体性能的策略。
本文提出了一种基于相似度的算法投资组合构建方法。
k近邻 (k-Nearest Neighbors)
一种基于距离度量的分类和回归方法，通过选择特征空间中最接近的k个实例来进行预测。
本文利用k近邻方法微调算法投资组合。
离散经验达成函数 (Discrete Empirical Attainment Function)
一种用于评估算法性能的度量工具，基于算法在不同预算下实现目标的概率。
本文使用EAF作为投资组合性能的度量工具。
虚拟最佳求解器 (Virtual Best Solver)
一种理论上的基准，表示在每个问题实例上选择表现最好的算法。
本文的实验结果表明，初始投资组合超过了虚拟最佳求解器。
探索性地形分析 (Exploratory Landscape Analysis)
一种通过样本描述符来表征优化地形特征的方法。
本文使用ELA特征作为问题实例的特征表示。
余弦相似度 (Cosine Similarity)
一种度量两个向量之间相似度的方法，基于它们的夹角而非长度。
本文在特征空间中使用余弦相似度进行相似性度量。
贪婪策略 (Greedy Strategy)
一种算法设计策略，每一步选择当前最优解，以期获得全局最优解。
本文在构建初始投资组合时采用了贪婪策略。
多维度问题 (Multi-dimensional Problem)
涉及多个变量或参数的复杂问题，通常需要更复杂的优化策略。
本文在多维度问题上验证了方法的有效性。
开放问题 这项研究留下的未解疑问
- 1 在黑箱优化中，如何有效地选择特征以表征问题实例仍然是一个开放问题。当前的方法依赖于预定义的特征空间，但这些特征可能无法充分捕捉问题的复杂性。未来的研究需要探索更丰富和动态的特征表示，以提高算法选择和投资组合的性能。
- 2 尽管k近邻方法在微调投资组合中表现出色，但其计算复杂度较高，尤其是在大规模数据集上。如何开发更高效的k近邻搜索算法以降低计算开销是一个值得研究的问题。
- 3 在多样化的优化问题中，如何构建具有更高鲁棒性的投资组合仍然是一个挑战。当前的方法在某些情况下可能不如全局优化的投资组合稳定。未来的研究可以探索更为灵活的组合策略，以应对不同问题的变化。
- 4 当前的投资组合方法主要依赖于算法间的互补性，但如何更好地量化和利用这种互补性仍然需要进一步研究。特别是在高维问题上，算法间的相互作用可能更加复杂。
- 5 在实时系统中应用投资组合方法面临许多挑战，包括如何快速响应环境变化以及如何动态调整算法组合。这需要开发新的动态优化策略，以适应实时系统的需求。
应用场景
近期应用
机器学习模型超参数优化
通过分配预算给多个优化算法，可以提高机器学习模型的超参数优化效率，尤其是在高维参数空间中。
复杂系统参数调优
在工程设计中，使用投资组合方法可以更有效地调优复杂系统的参数，提高系统性能和稳定性。
实时系统中的动态优化
在需要快速响应的实时系统中，投资组合方法可以通过动态调整算法组合来适应变化的环境。
远期愿景
多目标优化
在多目标优化问题中，投资组合方法可以通过分配预算给不同算法来同时优化多个目标，提供更全面的解决方案。
智能决策系统
未来，投资组合方法可以应用于智能决策系统，通过组合多种算法来提高决策的准确性和效率。
原文摘要
In black-box optimization, a central question is which algorithm to use to solve a given, previously unseen, problem. Selecting a single algorithm, however, entails inherent risks: inaccuracies in the selector may lead to poor choices, and even well-performing algorithms with high variance can yield unsatisfactory results in a single run. A natural remedy is to split the evaluation budget across multiple runs of potentially different algorithms. Such sequential algorithm portfolios benefit from variance reduction and complementarities between algorithms, often outperforming approaches that allocate the entire budget to a single solver. While effective portfolios can be constructed post-hoc, transferring this idea to the algorithm selection setting is non-trivial. We show that a naive portfolio constructed over the full training set already outperforms the strongest traditional baseline, the virtual best solver. We then propose a simple yet effective k-nearest-neighbor-based finetuning approach to construct portfolios tailored to unseen instances, yielding further improvements and highlighting the effectiveness of portfolio selection in fixed-budget black-box optimization.
参考文献 (14)
A Direct Search Optimization Method That Models the Objective and Constraint Functions by Linear Interpolation
M. Powell
Efficient Online Automated Algorithm Selection in the Face of Data-Drift in Optimisation Problem Instances
Jeroen G. Rook, Quentin Renau, H. Trautmann 等
Cross-disciplinary perspectives on meta-learning for algorithm selection
K. Smith‐Miles
Learning the characteristics of engineering optimization problems with applications in automotive crash
Fu Xing Long, Niki van Stein, M. Frenzel 等
A survey of features used for representing black-box single-objective continuous optimization
Gjorgjina Cenikj, Ana Nikolikj, G. Petelin 等
Inferential Performance Assessment of Stochastic Optimisers and the Attainment Function
V. G. D. Fonseca, C. Fonseca, Andreia O. Hall
Learning Techniques for Automatic Algorithm Portfolio Selection
A. Guerri, M. Milano
A Simple Modification in CMA-ES Achieving Linear Time and Space Complexity
Raymond Ros, Nikolaus Hansen
An algorithm for the selection problem
R. Dromey
Differential Evolution – A Simple and Efficient Heuristic for global Optimization over Continuous Spaces
R. Storn, K. Price
A Portfolio Approach to Algorithm Selection
H. Zender, G. Kruijff, Ivana Kruijff-Korbayová
Automated Algorithm Selection: Survey and Perspectives
P. Kerschke, H. Hoos, F. Neumann 等
Per-run Algorithm Selection with Warm-starting using Trajectory-based Features
Ana Kostovska, Anja Jankovic, D. Vermetten 等
Exploratory landscape analysis
Olaf Mersmann, B. Bischl, H. Trautmann 等