Similarity-based Portfolio Construction for Black-box Optimization

Black-box optimization is a critical research area that involves optimizing unknown or non-analytical objective functions. As optimization algorithms have diversified, selecting the right algorithm to solve specific problems has become a key challenge. Traditional algorithm selection methods often rely on machine learning techniques, using feature extraction and classification models to predict the optimal algorithm. However, these methods have inherent risks, as selecting the wrong algorithm can lead to poor performance. Additionally, many optimization algorithms are stochastic, meaning that even if the optimal algorithm is selected, it may still perform poorly in a single run. To address these challenges, researchers have begun exploring algorithm portfolio methods, which allocate the budget to multiple algorithms to improve overall performance.

The core problem is how to select the appropriate algorithm for a given problem in black-box optimization. Traditional algorithm selection methods often rely on choosing a single algorithm, which carries the risk of poor performance if the wrong algorithm is selected. Even well-performing algorithms can yield unsatisfactory results in a single run due to high variance. To mitigate this risk, the paper proposes a similarity-based algorithm portfolio construction method, which allocates the budget to multiple algorithms to improve overall performance.

The core innovation of this paper is transforming the algorithm selection problem into a budget allocation problem and proposing a k-nearest neighbor-based fine-tuning method to optimize the portfolio. Specific innovations include: 1) using the Discrete Empirical Attainment Function (EAF) as a performance metric, providing a new theoretical foundation for portfolio construction; 2) employing a greedy strategy to construct the initial portfolio, ensuring reasonable budget allocation; 3) using k-nearest neighbors to select similar training instances for fine-tuning, enhancing the portfolio's adaptability and robustness.

The methodology of this paper includes the following steps:

• �� Use the Discrete Empirical Attainment Function (EAF) as a performance metric to evaluate algorithm performance under different budgets.

• �� Construct an initial portfolio over the full training set using a greedy strategy to ensure reasonable budget allocation.

• �� Use k-nearest neighbors to select training instances similar to the unseen instance in the feature space.

• �� Fine-tune the selected similar instances to optimize the portfolio for specific problem instances.

• �� Validate the method's effectiveness through experiments, comparing the performance of portfolios before and after fine-tuning.

The experimental design is based on the multi-dimensional MA-BBOB benchmark function set, covering various optimization problem instances. The experiments use four optimization algorithms: CMA-ES, Diagonal CMA-ES, RCobyla, and Differential Evolution. Each algorithm is evaluated under a fixed budget to ensure fair comparison. The experiments use Exploratory Landscape Analysis (ELA) features as the feature representation, with cosine similarity used for similarity measurement in the feature space. The experimental results validate the method's effectiveness by comparing the performance of portfolios on the full training set and unseen instances.

Experimental results show that the initial portfolio constructed over the full training set already surpasses the Virtual Best Solver (VBS), demonstrating its superiority. The k-nearest neighbor fine-tuned portfolio further improves performance on unseen instances, with an average performance increase of about 10%. In multi-dimensional problems, locally optimized portfolios outperform globally optimized ones, especially in higher dimensions. The results also demonstrate that the portfolio method effectively leverages complementarities between algorithms to achieve significant performance gains.

This method has potential applications in various fields, including hyperparameter optimization of machine learning models, parameter tuning of complex systems, and multi-objective optimization in engineering design. By allocating the budget to multiple algorithms, the method can improve optimization performance in environments with high uncertainty. Additionally, the method can be applied to real-time systems that require rapid response, dynamically adjusting algorithm combinations to adapt to changing environments.

Despite its outstanding performance in multiple experiments, the method has some limitations. First, it has high computational complexity, especially when dealing with large training sets, as k-nearest neighbor search can increase computational overhead. Second, the performance of the method depends on the quality of the feature space; if the features do not effectively represent problem instances, it may affect the portfolio's effectiveness. Finally, in some cases, locally optimized portfolios may not be as stable as globally optimized ones. Future research directions include developing more efficient k-nearest neighbor search algorithms to reduce computational complexity, exploring richer feature spaces to improve the method's adaptability, and validating the method's effectiveness on larger and more complex optimization problems.