Technical Summary: MO-ELA

Problem Statement

Automated Algorithm Selection (AAS) is a mature field for single-objective (SO) optimization, where machine learning models predict the best-performing algorithm for a specific problem instance based on "exploratory landscape analysis" (ELA) features. However, in the domain of continuous multi-objective (MO) optimization, the landscape of available features is sparse. Existing approaches often rely on calculating SO features for each objective individually, which fails to capture complex interactions between objectives, or on constrained MO features that are not directly applicable to unconstrained (box-constrained) continuous problems. There is a need for a rigorous, complementary set of features specifically designed to characterize the landscape of box-constrained continuous multi-objective optimization problems (MOPs) to improve AAS performance.

Methodology

The authors propose MO-ELA, a novel set of 226 features for bi-objective and 233 features for tri-objective problems. These features are derived from a random sample of points in both the decision and objective spaces, utilizing dominance relationships and various structural analyses. The features are categorized into five distinct groups:

1. Non-Dominated Sorting (NDS) Based Features:

   • Utilizes the non-dominated sorting procedure (inspired by NSGA-II) to partition the sample into layers ($L_1, L_2, \dots$).
   • Calculates metrics such as the number of non-dominated points, the number of layers, and average points per layer.
   • Computes Hypervolume (HV) and Solow-Polasky (SP) measures for the first five layers.
   • Fits polynomial regressions (degrees 1–4) to the HV values across layers to capture the non-linearity of the Pareto front distribution, using $R^2$ as a feature.

2. Descriptive Statistics of Non-Dominated Points:

   • Applies statistical measures (min, max, avg, std) to the objective vectors of the first non-dominated layer ($L_1$).
   • Includes pairwise Spearman correlations between objectives and the absolute difference in standard deviations for bi-objective cases.

3. PCA-Based Features:

   • Performs Principal Component Analysis (PCA) on three sets: the decision space points ($X$), the objective space points ($Y$), and the concatenated set ($XY$) of the non-dominated layer.
   • Extracts the minimum, maximum, and average explained variance from the principal components of these sets.

4. Graph-Based Features:

   • Constructs graphs based on the non-dominated layer $L_1$ in both decision and objective spaces.
   • MST and kNN Graphs: Builds Minimum Spanning Trees (MST) and k-Nearest Neighbor (kNN) graphs ($k=1$) in the decision space ($G_D$) and objective space ($G_O$).
   • Edge Transfer: Transfers the edge structure of one graph to the other (e.g., MST edges from decision space applied to objective points, denoted $G_{D \to O}$).
   • Metrics: Calculates edge weights (distances), node closeness centrality, angles between connected nodes, and properties of connected components (number of components, nodes per component, longest path).
   • Includes ratios of features between decision and objective space graphs to capture the distortion between spaces.

5. Gradient-Based Features:

   • Computes absolute per-variable slopes between connected nodes in the MST of the objective space ($G^O_{ST}$).
   • Aggregates these slopes across all objectives and edges to form a multi-objective gradient vector, from which min, max, std, and average values are extracted.

Experimental Setup:

• Benchmarks: A comprehensive set of 1,165 problem instances derived from BiObjBBOB, ZDT, DTLZ, and MPM2, covering 2 and 3 objectives and dimensions $d \in \{2, 5, 10, 20\}$.
• Algorithms: Three solvers (NSGA-II, SMS-EMOA, MOEA/D) were run 20 times per instance.
• AAS Framework: Machine learning models (SVM, XGBoost, Random Forest) were trained to predict the best solver. Feature selection was performed using a forward-backward exhaustive search to identify the most influential subset.
• Metrics: Performance was evaluated using the Normalized Hypervolume (HVN) and the Relative Improvement (RI) in closing the gap between the Single Best Solver (SBS) and the Virtual Best Solver (VBS).

Key Results

• Algorithm Selection Performance: The proposed features significantly improved AAS performance. For bi-objective problems, the best selector (XGBoost with feature selection) achieved an RI of 0.963, effectively closing the gap to the VBS. For tri-objective problems, an RI of 0.272 was achieved.
• Feature Contribution: After feature selection, the newly proposed MO-ELA features were frequently among the top contributors.
  • For bi-objective problems, 14 of the 32 selected features were new (dominated by NDS features).
  • For tri-objective problems, 17 of the 36 selected features were new (dominated by kNN graph features).
• Feature Stability: The features demonstrated high stability across different random samples and sample sizes, with average pairwise correlations of ~0.8 for all features and nearly 1.0 for the selected subset.
• Feature Expressiveness: The selected features showed low mutual correlation (avg ~0.30 for bi, ~0.23 for tri), indicating they capture distinct aspects of the problem landscape.
• Sample Size Sensitivity: A sample size of 500 yielded the best results for dimensions 5, 10, and 20. For dimension 2, a sample size of 200 was optimal. Notably, larger sample sizes improved performance even when the remaining budget for solver runs was reduced, suggesting that feature expressiveness is critical.

Significance and Claims

The paper claims that MO-EDA provides a rigorous expansion of exploratory landscape features for continuous multi-objective optimization. Its primary significance lies in:

1. Bridging the Gap: It addresses the scarcity of features for MO problems by introducing a comprehensive set that captures interactions between objectives and the geometry of both decision and objective spaces.
2. Proven Utility: The features are not merely theoretical; they empirically enable machine learning models to distinguish between problem instances and select algorithms with near-optimal accuracy (approaching the VBS for bi-objective cases).
3. Complementarity: The new features complement existing MO-ELA features (from Liefooghe et al., 2021), with feature selection consistently retaining a mix of both, suggesting that different feature groups capture different necessary properties of the landscape.
4. Practicality: The features are stable and effective even with relatively small sample sizes (e.g., 200–500 points), making them feasible for practical application where computational budgets are limited.

The authors conclude that while the research is in early stages, these features provide meaningful insights into problem structure and significantly enhance the state-of-the-art in automated algorithm selection for continuous multi-objective optimization.