TL;DR
This paper investigates using Genetic Programming (GP) to evolve new mathematical optimization functions that mimic the "shape" of specific target problems. By guiding the evolution with Exploratory Landscape Analysis (ELA) features, the authors show that while GP can successfully navigate the feature space, matching a statistical "fingerprint" doesn't always result in a function that looks or behaves like the target—highlighting significant challenges in automated benchmark generation.
What Problem Does This Paper Address?
In the world of mathematical optimization, we rely on benchmark suites (like the popular BBOB suite) to test how well algorithms perform. However, these hand-crafted benchmarks often fail to represent the messy, complex landscapes of real-world engineering problems, such as automotive crash simulations.
If we want to tune an algorithm for a specific real-world task, we need "surrogate" benchmarks that share the same characteristics but are much cheaper to evaluate. The challenge is: How do we automatically generate a function that has specific "high-level" properties (like being smooth, multi-modal, or separable) on demand?
Methods
The authors combine two powerful tools:
- Genetic Programming (GP): An evolutionary algorithm that treats mathematical expressions as trees. It "breeds" these trees, using crossover and mutation to find expressions that satisfy a specific goal.
- Exploratory Landscape Analysis (ELA): A method to extract a "fingerprint" of a function. It calculates over 300 features (e.g., convexity, local search connectivity, distribution of values) based on a limited number of sample points.
The Approach: The GP's fitness function is defined as the distance (specifically the Wasserstein distance) between the ELA features of the evolved function and the ELA features of a target benchmark function. Essentially, the GP tries to evolve a math formula whose "fingerprint" matches the target.
Datasets
The study uses the BBOB (Black-Box Optimization Benchmarking) suite as the ground truth.
- Target Functions: All 24 functions in the BBOB suite (ranging from simple spheres to complex "Gallagher's Gaussian peaks").
- Dimensionality: Experiments were conducted in 2D, 5D, and 10D.
- Baseline: The results were compared against a Random Function Generator (RFG) to see if the evolutionary pressure of GP actually provided better results than random search.
Key Insights and Ideas
- The "Looks Can Be Deceiving" Problem: One of the most striking findings was that a function could have a very low ELA distance to a "Sphere" function (F1) without actually looking like a sphere. The GP found "mathematical loopholes"—functions that statistically mimicked the sphere's distribution of values but had entirely different global structures.
- Feature Weighting is Critical: The authors treated all ELA features as equally important. However, their analysis showed that some features are much more "stable" across different instances of the same function than others. Treating a noisy, irrelevant feature with the same weight as a defining characteristic (like multi-modality) confuses the GP.
- The Distance Metric Matters: While the authors initially used Wasserstein distance (a statistical measure), they found that simpler vector-based measures like Cosine similarity or Correlation might actually be better at distinguishing between different types of functions.
- GP vs. Randomness: GP consistently outperformed random generation (RFG) in finding functions closer to the target in ELA space, proving that the evolutionary approach is viable, even if the current "compass" (the fitness function) needs calibration.
Key Results
- Convergence: GP successfully minimized the Wasserstein distance over 50 generations, showing a clear improvement over the initial random population.
- Visual Similarity: For "Linear Slope" functions (F5), the GP-generated functions looked remarkably similar to the target. However, for the "Sphere" function (F1), even the "best" evolved functions were visually distinct from a true sphere.
- Feature Variance: The authors identified that features related to linear model coefficients (
ela_meta.lin_simple.coef) were highly variable in evolved functions compared to the targets, suggesting these are the "hardest" parts of the fingerprint to match accurately.
Limitations and Future Work
The authors are transparent about several hurdles:
- Computational Cost: Calculating 300+ ELA features for every individual in every generation is expensive, which limited the GP population size and number of runs.
- The "Black Box" of ELA: We don't yet fully understand which ELA features map to which "intuitive" human concepts (like "this function has three peaks").
- Future Direction - Feature Selection: The authors suggest that a "feature selection" mechanism is needed. Instead of matching all 300 features, the GP should focus on the subset of features that truly define the target's landscape.
- Tuning the GP: The study used mostly default GP hyperparameters; further tuning of mutation rates and "tree-cleaning" (to simplify the evolved formulas) could yield more robust results.
Summary updated