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

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):

  1. Genetic Programming (GP): An evolutionary algorithm that treats mathematical expressions as trees, using crossover and mutation to evolve formulas that satisfy a specific goal.
  2. 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

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.

Comparison of Wasserstein distances for functions evolved via GP (pink) versus a Random Function Generator (green) across 24 BBOB target functions.

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.

Evolved functions targeting the BBOB Sphere function (F1). Despite low Wasserstein distances (indicated on plots), many evolved landscapes differ significantly from the target's global structure.

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

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.
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},
}
Figure