Relevance Estimation and Value Calibration of Evolutionary Algorithm Parameters

Volker Nannen, A. E. EibenIJCAI 2007

Introduction

Evolutionary Algorithms (EAs) are powerful optimization tools, but their performance is highly dependent on a suite of parameters—mutation rates, crossover probabilities, and population sizes. Traditionally, selecting these values has been a "black art," relying on heuristic "folk wisdom" or exhaustive trial-and-error. This paper introduces REVAC (Relevance Estimation and Value Calibration), a systematic framework that uses information theory to not only find optimal parameter settings but also quantify how much each parameter actually matters to the final outcome.

The REVAC Methodology

REVAC is built on the principles of Estimation of Distribution Algorithms (EDAs). Rather than searching for a single optimal point in the parameter space, REVAC maintains a probability distribution over the possible values for each parameter.

The core of the approach is the use of Shannon entropy to measure parameter relevance. In this context, a parameter with high relevance is one where the algorithm must converge to a very narrow, specific range of values to achieve high performance. Conversely, a parameter with low relevance is one where a wide range of values yields similar results.

The process is iterative:

  1. Initialization: Start with a uniform distribution (maximum entropy) for all parameters.
  2. Evaluation: Sample parameter vectors from the current distributions and run the target EA.
  3. Selection & Smoothing: Select the top-performing parameter sets and use them to refine the probability density functions (PDFs). REVAC employs an $h$-th neighbor smoothing technique to ensure robustness against noise.
  4. Convergence: As the process repeats, the distributions "sharpen" around high-performing regions.
Calibration of parameters with varying relevance levels. Parameter 1 (left) shows rapid convergence to a narrow range, indicating high relevance, while Parameter 7 (right) remains broad.

Key Insights: Relevance as Sharpness

A central finding of the REVAC framework is that the "relevance" of a parameter is visually represented by the sharpness of its calibrated distribution. As seen in the calibration plots, a highly relevant parameter results in a needle-like peak, whereas an irrelevant parameter produces a flat, high-entropy plateau.

This distinction is crucial for practitioners. It reveals, for instance, that while the mutation rate ($p_m$) often requires precise tuning (typically around 0.01), the crossover rate ($p_c$) is frequently less sensitive, performing adequately across a much broader range (e.g., 0.6 to 1.0).

Experimental Results and Validation

The authors validated REVAC using both synthetic "response surfaces"—mathematical landscapes designed to mimic the noise and non-linearity of real EA tuning—and standard GA benchmark functions (Sphere, Rosenbrock, etc.).

The final relevance scores calculated by REVAC for a 10-parameter test case, clearly distinguishing critical parameters from those with negligible impact.

The results consistently demonstrated that REVAC could:

  • Recover Hidden Hierarchies: In cases where the importance of one parameter depended on the value of another, REVAC successfully identified the underlying structure.
  • Quantify Sensitivity: By providing 25th and 75th percentile confidence intervals, the method gives researchers a "safe zone" for parameter settings.
  • Handle Noisy Environments: REVAC proved robust against heavy-tailed, non-normal noise, which often compromises traditional statistical tuning methods.

Conclusion

REVAC moves EA parameter tuning from ad-hoc experimentation to a rigorous, information-theoretic foundation. By automating the discovery of both optimal values and their relative importance, it provides a powerful tool for understanding the dynamics of evolutionary search and ensuring robust algorithmic performance.

Summary updated

BibTeX
@inproceedings{nannen2007relevance,
  author = {Volker Nannen and A. E. Eiben},
  title = {{Relevance Estimation and Value Calibration of Evolutionary Algorithm Parameters}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
}
Figure