Abstract
Within the optimization community, the question of how to generate new optimization problems has been gaining traction in recent years. Within topics such as instance space analysis (ISA), the generation of new problems can provide new benchmarks which are not yet explored in existing research. Beyond that, this function generation can also be exploited for solving complex real-world optimization problems. By generating functions with similar properties to the target problem, we can create a robust test set for algorithm selection and configuration. However, the generation of functions with specific target properties remains challenging. While features exist to capture low-level landscape properties, they might not always capture the intended high-level features. We show that a genetic programming (GP) approach guided by these exploratory landscape analysis (ELA) properties is not always able to find satisfying functions. Our results suggest that careful considerations of the weighting of landscape properties, as well as the distance measure used, might be required to evolve functions that are sufficiently representative to the target landscape.
Introduction
In mathematical optimization, benchmark suites like the Black-Box Optimization Benchmarking (BBOB) are standard for testing algorithm performance. However, these hand-crafted benchmarks often fail to represent the complex, irregular landscapes of real-world engineering problems. To bridge this gap, researchers aim to automatically generate "surrogate" benchmarks that mimic the high-level properties of specific target problems (e.g., smoothness, multi-modality, or separability) while remaining computationally inexpensive to evaluate.
Methodology
This study proposes an automated approach combining Genetic Programming (GP) and Exploratory Landscape Analysis (ELA):
- Genetic Programming (GP): An evolutionary algorithm that treats mathematical expressions as trees, using crossover and mutation to evolve formulas that satisfy a specific goal.
- Exploratory Landscape Analysis (ELA): A method to extract a statistical "fingerprint" of a function by calculating over 300 features (such as convexity and local search connectivity) based on sample points.
The GP's fitness function is defined as the Wasserstein distance between the ELA features of the evolved function and those of a target BBOB benchmark function. The study evaluated all 24 BBOB functions in 2D, 5D, and 10D, comparing the GP approach against a Random Function Generator (RFG) baseline.
Results and Key Insights
GP Performance vs. Random Search
The GP approach consistently outperformed random generation in minimizing the ELA distance across the majority of the 24 BBOB functions. As shown in the violin plots below, the GP (pink) generally achieves lower Wasserstein distances compared to the RFG (green) baseline, indicating that evolutionary pressure successfully navigates the ELA feature space.
The "Looks Can Be Deceiving" Problem
A critical finding was that statistical similarity does not always equate to structural similarity. For example, the GP often found "mathematical loopholes" when targeting the Sphere function (F1). It evolved functions that statistically mimicked the sphere's distribution of values (resulting in low Wasserstein distances) but possessed entirely different global structures.
Feature Weighting and Stability
The analysis revealed that treating all 300+ ELA features with equal weight is problematic. Some features are highly stable across instances, while others are noisy and irrelevant. Features related to linear model coefficients (ela_meta.lin_simple.coef) were particularly difficult for the GP to match accurately, suggesting that a more nuanced weighting or selection of features is required to guide evolution effectively.
Conclusion and Future Work
While GP is a viable tool for evolving functions with specific ELA fingerprints, significant challenges remain in ensuring these functions are representative of the target landscapes. Future work should focus on:
- Feature Selection: Identifying the specific subset of ELA features that truly define a target's landscape.
- Distance Metrics: Exploring alternative measures like Cosine similarity or Correlation, which may better distinguish function types than the Wasserstein distance.
- Computational Efficiency: Reducing the high cost of calculating hundreds of ELA features per generation to allow for larger populations and more extensive search.
Summary updated