Toward comparison-based adaptive operator selection

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

TL;DR

This paper introduces novel "rank-based" adaptive operator selection (AOS) methods that are more robust to fitness function transformations and less sensitive to hyperparameter tuning than previous approaches. By focusing on the relative ranking of operator performance rather than absolute fitness gains, these new methods offer a more stable and adaptable way for evolutionary algorithms to dynamically choose their variation operators.

What Problem Does This Paper Address?

Evolutionary Algorithms (EAs) often employ various "variation operators" (like mutation or crossover) to explore the search space. Adaptive Operator Selection (AOS) aims to dynamically choose the best operator for the current stage of the search, improving efficiency. However, existing AOS methods often rely on "credit assignment" mechanisms that directly use the fitness gain between parents and offspring. This approach faces several issues:

  • Sensitivity to Fitness Scaling: The raw fitness values can vary wildly, making it hard to set universal parameters for the AOS.
  • Changing Fitness Landscape: As evolution progresses, fitness gains tend to decrease, making fixed parameters less effective over time.
  • Lack of Invariance: Critically, using raw fitness gains breaks the desirable property of "invariance" under monotonic fitness transformations. This invariance is a hallmark of robust EAs (like those using rank-based selection), as it means the algorithm's behavior doesn't change if you simply re-scale or re-map the fitness values. This is crucial for handling complex or poorly understood fitness landscapes.

This paper tackles these limitations by proposing AOS methods that are less dependent on absolute fitness values and more robust to transformations.

Methods

The core contribution lies in two new "Credit Assignment" mechanisms:

  • Sum of Ranks (SR): This method assigns credit based on the sum of the ranks of recent operator impacts. It uses a sliding window to track recent operator performances and assigns weights based on their position in the ranked list, with a decay factor to prioritize more recent or impactful results.
  • Area Under the Curve (AUC): Inspired by machine learning's ROC curves, this method calculates a reward by constructing a "Receiving Operator Curve" based on the ranked impacts of operators. The area under this curve, adjusted for decay, serves as the credit.

These SR and AUC methods are then integrated into a "Multi-Armed Bandit" (MAB) Operator Selection rule. The key innovation is that instead of using raw fitness improvements as rewards, they use the ranks of these improvements. This rank-based approach is designed to achieve invariance under monotonic fitness transformations.

The paper also introduces "comparison-based raw reward" variants (F-SR-B and F-AUC-B) where the credit is directly based on the rank of the offspring within the current population, making the entire AOS process comparison-based.

Datasets

The paper evaluates its proposed methods on two types of scenarios:

  • OneMax Problem: A standard, well-controlled benchmark for EAs, used here with its original fitness function and three monotonic transformations: logarithmic (log(F)), exponential (exp(F)), and squared (F^2). This allows for direct testing of robustness to fitness transformations.
  • Artificial Scenarios: These are designed to mimic dynamic environments and test the agility of AOS schemes. Three variants are used:
  • Uniform: Operators always receive positive rewards.
  • Boolean: Operators receive a non-null reward with a certain probability, but the reward value is always the same.
  • Outlier: Operators receive non-null rewards with the same probability, but the reward values differ significantly.

Key Insights and Ideas

  • Ranking is Key to Robustness: The most significant insight is that focusing on the relative performance (ranks) of operators, rather than their absolute fitness gains, is a powerful way to achieve invariance to fitness transformations. This is analogous to how rank-based selection in EAs provides robustness.
  • MAB with Ranks is Promising: Combining rank-based credit assignment with Multi-Armed Bandit selection rules (AUC-B and SR-B) leads to methods that are significantly more robust to fitness transformations than previous bandit-based AOS approaches.
  • Hyperparameter Sensitivity Reduced: The proposed rank-based methods are less sensitive to hyperparameter tuning. A single configuration can often perform well across a range of related problems or fitness landscapes, unlike older methods that require extensive re-tuning.
  • Comparison-Based AOS is Possible (but Challenging): The F-SR-B and F-AUC-B variants demonstrate that a fully comparison-based AOS is achievable. While their performance is currently lower than other methods, their complete invariance makes them a promising direction for future parameter-less AOS.

Key Results

  • Robustness on OneMax: The proposed AUC-B and SR-B methods showed significantly better performance and less degradation when the OneMax fitness function was transformed (log, exp, F^2) compared to traditional methods like PM and AP. While F-AUC-B and F-SR-B were less competitive, their invariance was verified.
  • Performance on Artificial Scenarios: AUC-B and SR-B generally performed comparably to or better than existing methods like AP and MAB on the artificial scenarios, especially considering their reduced sensitivity to hyperparameter tuning. DMAB, while often achieving the highest rewards, required a significantly more expensive tuning stage.
  • Hyperparameter Tuning: The paper demonstrates that a smaller set of hyperparameter configurations is sufficient for the new rank-based methods, reducing the burden of tuning compared to methods like DMAB.

Limitations and Future Work

  • Hyperparameter Tuning Still Exists: While reduced, the proposed SR and AUC methods still have three hyperparameters (window size W, decay factor D, and scaling factor C) that need to be set.
  • Comparison-Based Performance Gap: The fully comparison-based variants (F-SR-B, F-AUC-B) currently lag in performance, particularly on the OneMax problem, showing instabilities in certain areas.
  • Future Directions:
    • Adaptive Hyperparameters: The authors suggest making the hyperparameters (especially W and D) adaptive, as optimal settings can change throughout the search process.
  • Improving Comparison-Based AOS: Further research is needed to understand and address the performance issues of the fully comparison-based variants, potentially by analyzing and suppressing instabilities.
  • Exploring Other Credit Assignment Schemes: The paper's focus is on rank-based methods, but other credit assignment strategies could be explored.

Summary updated

BibTeX
@inproceedings{fialho2010toward,
  author = {Álvaro Fialho and Marc Schoenauer and Michèle Sebag},
  title = {{Toward comparison-based adaptive operator selection}},
  booktitle = {GECCO},
  year = {2010},
  doi = {10.1145/1830483.1830619},
}
Figure