Inductive Learning of Mutation Step-Size in Evolutionary Parameter Optimization

Michèle Sebag, Marc Schoenauer, Caroline RaviseEvolutionary Programming 1997 · DOI

TL;DR

This paper introduces a novel approach to control the mutation step-size in evolutionary algorithms (EAs) by using inductive learning. Instead of relying on fixed rules or self-adaptation, the system learns from past "errors" (mutations that led to worse offspring) to actively inhibit similar future mutations, potentially improving optimization efficiency.

What Problem Does This Paper Address?

Evolutionary Algorithms (EAs) are powerful optimization tools, but their performance heavily relies on the careful tuning of their parameters, particularly the mutation step-size. This step-size dictates how much an individual's parameters are altered during the mutation process. Too small a step-size can lead to slow exploration, while too large a step-size can cause premature convergence or prevent fine-tuning. Traditional methods for setting this step-size include exogenous rules (like the 1/5 rule) or endogenous self-adaptation mechanisms. However, these methods have limitations. Self-adaptation, while effective, can be computationally expensive. This paper proposes a new method that leverages Machine Learning (ML) to learn from the evolutionary process itself, specifically by identifying and avoiding past "mistakes" in mutation.

Methods

The core of the proposed method is an "inductive learning-based control of evolution." This involves:

  • Event Categorization: Mutation events are classified as "successes" or "errors" based on whether the offspring's fitness is higher or lower than the parent's.
  • Rule Induction: A machine learning algorithm (specifically, a learner named DIVS) is used to learn rules from these categorized events. These rules identify combinations of individual parameters and mutation characteristics that are likely to lead to errors.
  • Knowledge-Controlled Evolution: The learned rules are then used to "inhibit" or filter out mutation events that are predicted to be errors. This is a "deterministic inhibition" strategy, contrasting with the "stochastic recommendations" of self-adaptation.
  • Hybrid Scheme: The system integrates evolution and induction. Every $L$ generations, the ML component learns from the recent evolutionary history. During the intervening generations, mutations are filtered based on the learned rules. The rules are periodically updated to adapt to the evolving population.

Datasets

Not discussed in the paper. The experiments use standard benchmark functions for evaluation.

Key Insights and Ideas

  • Learning from Errors is Safer: The paper argues that learning from past errors is a safer strategy than learning from successes. Avoiding known pitfalls is less likely to mislead the evolution process than trying to replicate past successes, especially in complex fitness landscapes.
  • Deterministic Inhibition vs. Stochastic Recommendation: The proposed ML-based control offers a deterministic approach to guiding evolution by actively forbidding certain actions, contrasting with the probabilistic adjustments of self-adaptation. This could lead to more predictable and potentially faster convergence.
  • ML as a Complement, Not Replacement: The ML control is presented as an addition to existing EA mechanisms (like self-adaptation), aiming to enhance their performance rather than replace them entirely.
  • Rule Lifetime: The authors recognize that learned rules might become outdated as the population evolves and moves to different regions of the search space. Therefore, periodic updating of these rules is crucial.

Key Results

  • Sphere Problem: On the sphere problem, a standard test case for EAs, the addition of ML-control did not significantly improve performance over standard ES with self-adaptation. However, it also did not degrade performance, suggesting that the ML-control is safe and does not interfere with optimal strategies in simple landscapes.
  • Griewank Function: On the more complex, multi-modal Griewank function, the ML-controlled ES showed improved performance compared to standard ES. The best results were achieved with a learning frequency ($L=3$) where rules were updated more often.
  • Computational Cost: A significant drawback identified is the increased computational time due to the classification phase of the ML-control, which is independent of the fitness function's cost. This suggests ML-control is best suited for problems with very expensive fitness evaluations.

Limitations and Future Work

  • Computational Cost: The primary limitation is the substantial increase in computation time due to the ML classification step.
  • Rule Specificity vs. Generality: The paper explores a strategy where rules are tuned to reject about 50% of mutations, balancing specificity (avoiding known errors) with generality (not overly restricting exploration).
  • Future Work:
    • Learning the direction of mutation, not just the step-size.
  • Comparing the proposed method with other advanced techniques like generalized self-adaptation and arithmetic crossover.
  • Building a rule-based model of the fitness landscape itself to guide population generation.
  • Investigating the impact of learning frequency ($L$) more thoroughly.

Summary updated

BibTeX
@inproceedings{sebag1997inductive,
  author = {Michèle Sebag and Marc Schoenauer and Caroline Ravise},
  title = {{Inductive Learning of Mutation Step-Size in Evolutionary Parameter Optimization}},
  booktitle = {Evolutionary Programming},
  year = {1997},
  doi = {10.1007/bfb0014816},
}

Loading related content...

Figure