Challenges of ELA-Guided Function Evolution Using Genetic Programming

Fu Xing Long, Diederick Vermetten, Anna V. Kononova, Roman Kalkreuth, Kaifeng Yang, Thomas Bäck, Niki van Stein

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:

  1. 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.
  2. 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

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 expensive real-world optimization problems. By generating fast-to-evaluate functions with similar optimization properties to the target problems, we can create a test set for algorithm selection and configuration purposes. 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 it is challenging to find satisfying functions through a genetic programming (GP) approach guided by the exploratory landscape analysis (ELA) properties. Our results suggest th
BibTeX
@inproceedings{long2023challenges,
  author = {Fu Xing Long and Diederick Vermetten and Anna V. Kononova and Roman Kalkreuth and Kaifeng Yang and Thomas Bäck and Niki van Stein},
  title = {{Challenges of ELA-Guided Function Evolution Using Genetic Programming}},
  booktitle = {IJCCI},
  year = {2023},
  url = {https://openreview.net/forum?id=kHeJlwI1Ge},
}

Loading related content...

Figure