Fitness-AUC bandit adaptive strategy selection vs. the probability matching one within differential evolution: an empirical comparison on the bbob-2010 noiseless testbed

Álvaro Fialho, Marc Schoenauer, Michèle SebagGECCO (Companion) 2010 · DOI

TL;DR

This paper compares two adaptive strategy selection methods for Differential Evolution (DE), a popular optimization algorithm. The F-AUC-Bandit method, which uses a novel comparison-based approach, generally outperforms the simpler Probability Matching method, especially on certain classes of optimization problems, demonstrating the value of its more sophisticated credit assignment.

What Problem Does This Paper Address?

Differential Evolution (DE) is a powerful algorithm for solving complex optimization problems. However, DE relies on selecting from a variety of "strategies" (e.g., different ways to generate new candidate solutions). Choosing the right strategy for a given problem and at different stages of the optimization process is a significant challenge. It's not a one-size-fits-all situation; what works best can depend heavily on the problem's characteristics and how far along the optimization is. This paper addresses this by investigating "Adaptive Strategy Selection" (ASS) techniques that automatically adjust strategy choices during the optimization process, aiming to improve performance without requiring extensive manual tuning.

Methods

The paper focuses on comparing two ASS techniques within the DE framework:

  • F-AUC-Bandit: This method uses a "comparison-based" credit assignment mechanism. It assesses strategy performance by calculating the Area Under the Receiver Operating Characteristic (ROC) Curve (AUC) based on the ranks of fitness values of generated offspring. This rank-based approach makes it invariant to monotonic transformations of the fitness function. A multi-armed bandit algorithm (specifically, a UCB variant) is then used to select the next strategy based on these AUC scores. Key parameters include a scaling factor (C), a decay factor (D), and a sliding window size (W).
  • PM-AdapSS-DE: This is presented as a simpler baseline. Its credit assignment mechanism uses the absolute average of raw fitness improvements from recent offspring. The strategy selection is based on "Probability Matching" (PM), where strategies are chosen proportionally to their estimated quality, with an adaptation rate (α) and an optional minimum probability (pmin).

The authors also detail the standard Differential Evolution algorithm used, including population size, mutation scaling factor (F), and crossover rate (CR), noting that these were kept standard to focus on the ASS methods.

Datasets

The evaluation was performed using the BBOB-2010 noiseless testbed. This benchmark suite consists of 24 diverse functions designed to represent various challenges in continuous black-box optimization, categorized into:

  • Separable functions
  • Moderate functions
  • Ill-conditioned functions
  • Multi-modal functions
  • Weak structure functions

The experiments were conducted across several dimensions, specifically 2, 3, 5, 10, 20, and 40 dimensions.

Key Insights and Ideas

  • The Power of Rank-Based Comparison: The F-AUC-Bandit's use of ranks for fitness evaluation is a significant advantage. It means the method is robust to how the fitness values are scaled, making it more generally applicable across different problems without needing re-tuning.
  • Exploration vs. Exploitation Dynamics: Adaptive strategy selection is crucial because optimization problems often require different behaviors at different stages. Early on, broad exploration is key, while later, fine-grained exploitation near the optimum is needed. ASS methods aim to dynamically balance these.
  • Complexity vs. Performance Trade-off: While F-AUC-Bandit is more complex computationally (especially its credit assignment), it often yields better results, suggesting that the added complexity is justified for improved performance on certain problem types.
  • Tuning Robustness: The paper found that the optimal hyper-parameters for both ASS methods were consistent across different dimensions for the tested functions. This suggests a degree of robustness in their parameter settings, reducing the burden of manual tuning for new problems.

Key Results

  • F-AUC-Bandit Outperforms PM-AdapSS-DE: Across many of the BBOB-2010 functions, especially separable, moderate, and ill-conditioned ones, the F-AUC-Bandit achieved significantly better Expected Running Time (ERT) ratios compared to PM-AdapSS-DE. This indicates it found solutions faster.
  • Performance on Different Function Classes: The advantage of F-AUC-Bandit was most pronounced on separable, moderate, and ill-conditioned functions. For multi-modal and weak-structured functions, the performance difference between the two methods was minimal, and both struggled to achieve competitive results.
  • Computational Cost: The F-AUC-Bandit was found to be computationally more expensive per function evaluation than PM-AdapSS-DE, primarily due to its more complex AUC calculation. However, its improved performance often compensated for this overhead in terms of overall time to solution.

Limitations and Future Work

  • Computational Overhead: The F-AUC-Bandit's credit assignment mechanism is more computationally intensive than simpler methods like PM-AdapSS-DE.
  • Performance on Certain Function Classes: Both methods showed limitations on multi-modal and weak-structured functions, suggesting that more advanced techniques might be needed for these challenging problem types.
  • Future Work Suggestions:
    • Explore combining diversity measures with fitness for credit assignment, as this has shown promise in other contexts.
  • Investigate automatic adaptation of other DE parameters (like F and CR), similar to what is done in schemes like SaDE.
  • Further validate the hyper-parameter robustness by conducting off-line tuning for specific function classes rather than globally.

Summary updated

BibTeX
@inproceedings{fialho2010fitness,
  author = {Álvaro Fialho and Marc Schoenauer and Michèle Sebag},
  title = {{Fitness-AUC bandit adaptive strategy selection vs. the probability matching one within differential evolution: an empirical comparison on the bbob-2010 noiseless testbed}},
  booktitle = {GECCO (Companion)},
  year = {2010},
  doi = {10.1145/1830761.1830770},
}
Figure