Is there Anisotropy in Structural Bias?

Diederick Vermetten, Anna V. Kononova, Fabio Caraffini, Hao Wang, Thomas Bäck

Abstract

Structural Bias (SB) is an important type of algorithmic deficiency within iterative optimisation heuristics. However, methods for detecting structural bias have not yet fully matured, and recent studies have uncovered many interesting questions. One of these is the question of how structural bias can be related to anisotropy. Intuitively, an algorithm that is not isotropic would be considered structurally biased. However, there have been cases where algorithms appear to only show SB in some dimensions. As such, we investigate whether these algorithms actually exhibit anisotropy, and how this impacts the detection of SB. We find that anisotropy is very rare, and even in cases where it is present, there are clear tests for SB which do not rely on any assumptions of isotropy, so we can safely expand the suite of SB tests to encompass these kinds of deficiencies not found by the original tests. We propose several additional testing procedures for SB detection and aim to motivate further research into the creation of a robust portfolio of tests. This is crucial since no single test will be able to work effectively with all types of SB we identify.

Introduction

Heuristic optimization algorithms, such as Differential Evolution (DE) or Particle Swarm Optimization (PSO), are designed to explore mathematical landscapes to find optimal solutions. However, the internal operators of these algorithms can introduce "structural bias" (SB)—a flaw where the algorithm inherently prefers certain regions of the search space regardless of the objective function.

Traditionally, SB is detected by running algorithms on a purely stochastic "dummy" objective function. If an algorithm is unbiased, its final search points should be uniformly distributed. Current detection methods, like the Anderson-Darling (AD) test, typically evaluate this uniformity on a per-dimension basis. This often leads to a puzzling observation: an algorithm may fail the test in some dimensions but pass in others. This research investigates whether this represents true anisotropy—where an algorithm treats dimensions differently—or if it is merely a failure of statistical power.

Methods and Experimental Setup

The study evaluated 41 optimization algorithms, including various DE configurations and Estimation of Distribution Algorithms, across 30-dimensional random noise functions. To analyze the resulting search positions, the researchers employed the standard per-dimension AD test alongside new, more robust procedures:

  1. Spacing-based test: Analyzes distances between consecutive points to detect unnatural clustering.
  2. Boundary-Related (Domain Transformation) test: Folds the search space to increase sensitivity to center-seeking biases.
  3. Aggregated AD test: Pools data across all dimensions to increase the sample size from 100 to 3,000, significantly boosting statistical power.

The Illusion of Anisotropy

A key finding of this research is that true anisotropic structural bias is extremely rare. In most cases where an algorithm appears biased in only a subset of dimensions, the result is a false negative in the remaining dimensions.

Figure 2: Swarm plot showing search values across 30 dimensions. Red 'x' marks indicate dimensions where the null hypothesis of uniformity was rejected, illustrating how tests often fail to detect bias consistently across all dimensions despite visual similarities.

As shown in the visual analysis of search distributions, many algorithms exhibit clear visual patterns of bias that the standard per-dimension AD test fails to flag consistently. This "illusion of anisotropy" is primarily a consequence of small sample sizes (typically 100 runs), which provide insufficient power for standard tests to reject the null hypothesis of uniformity for milder biases.

Key Results

The proposed new tests successfully identified biases that were previously hidden. For instance, the 1-spacing test flagged clustering in the SPSA-COTN algorithm that the standard AD test missed entirely. Similarly, the domain transformation test detected center-bias in all 30 dimensions for specific DE configurations where the original test only caught a handful.

Figure 1: Number of rejected dimensions per algorithm configuration. The variation across dimensions for many algorithms highlights the inconsistency of standard per-dimension testing.

The Aggregated AD test proved particularly effective. By pooling dimensions, it overcame the sample size bottleneck, identifying significantly more structurally biased configurations than the per-dimension approach. This confirms that what appeared to be dimension-specific behavior was actually a systemic bias present across the entire search space.

Conclusion

Structural bias is not a monolithic phenomenon; it can manifest as center-seeking, clustering, or boundary-attraction. Because no single statistical test can capture every topology of bias, especially at low sample sizes, this research motivates the development of a comprehensive "portfolio" of SB tests. By moving beyond simple per-dimension uniformity checks and utilizing aggregated or transformed data, algorithm designers can more reliably diagnose and mitigate these fundamental heuristic flaws.

Summary updated

Abstract

Structural Bias (SB) is an important type of algorithmic deficiency within iterative optimisation heuristics. However, methods for detecting structural bias have not yet fully matured, and recent studies have uncovered many interesting questions. One of these is the question of how structural bias can be related to anisotropy. Intuitively, an algorithm that is not isotropic would be considered structurally biased. However, there have been cases where algorithms appear to only show SB in some dimensions. As such, we investigate whether these algorithms actually exhibit anisotropy, and how this impacts the detection of SB. We find that anisotropy is very rare, and even in cases where it is present, there are clear tests for SB which do not rely on any assumptions of isotropy, so we can safely expand the suite of SB tests to encompass these kinds of deficiencies not found by the original tests. We propose several additional testing procedures for SB detection and aim to motivate further research into the creation of a robust portfolio of tests. This is crucial since no single test will be able to work effectively with all types of SB we identify.
BibTeX
@inproceedings{vermetten2021is,
  author = {Diederick Vermetten and Anna V. Kononova and Fabio Caraffini and Hao Wang and Thomas Bäck},
  title = {{Is there Anisotropy in Structural Bias?}},
  booktitle = {GECCO Companion},
  year = {2021},
  doi = {10.1145/3449726.3463218},
}
Figure