QR Mutations Improve Many Evolution Strategies: A Lot On Highly Multimodal Problems

Fabien Teytaud, Olivier TeytaudGECCO (Companion) 2016 · DOI

TL;DR

This paper demonstrates that using quasi-random (QR) mutations, instead of standard pseudo-random ones, significantly improves the performance of several evolutionary algorithms, particularly on complex, highly multimodal optimization problems. This suggests QR mutations offer a more robust and efficient approach for a wider range of evolutionary computation tasks.

What Problem Does This Paper Address?

Evolutionary algorithms (EAs) are powerful tools for solving complex optimization problems. However, their performance can degrade significantly on "highly multimodal" problems, which have many local optima that can trap the search process. Traditional EAs often rely on pseudo-random numbers for generating mutations. This paper investigates whether replacing these pseudo-random mutations with quasi-random (QR) mutations can enhance EA performance, especially in these challenging multimodal scenarios. QR numbers are designed to be more uniformly distributed than pseudo-random numbers, potentially leading to a more thorough and efficient exploration of the search space.

Methods

The core of this paper is the application and evaluation of quasi-random mutations within several established continuous evolutionary algorithms. The authors extend previous work on CMA-ES (Covariance Matrix Adaptation Evolution Strategy) to include:

  • Quasi-Random Mutations: Instead of generating random numbers from a standard distribution (like Gaussian) using a pseudo-random number generator, the paper utilizes QR sequences. These sequences are generated using methods that aim for a more uniform distribution in the search space. The conversion from uniform QR numbers to Gaussian QR numbers is done using the inverse cumulative distribution function.
  • Algorithm Extensions: The QR mutation strategy is applied to:
  • CMA-ES (referred to as QRCMA)
    • Simulated Annealing (SA) (referred to as QRSA)
    • CMSA (Covariance Matrix Self-Adaptation) (referred to as QRCMSA)
    • CMA with restarts (referred to as CMA(R))
  • Test Functions: A suite of unimodal and multimodal functions are used for evaluation. This includes standard functions like Sphere, Cigar, Ellipsoid, Schwefel, Griewank, Rastrigin, and Schaffer, as well as some modified or newly introduced multimodal functions (Hump, Nsine, Randcuts, Randsines) designed to be particularly challenging.

Datasets

The paper does not use traditional "datasets" in the sense of pre-collected data. Instead, it employs a set of benchmark optimization functions for evaluation. These include:

  • Unimodal Functions: Sphere, Cigar, Ellipsoid, Schwefel (rescaled).
  • Multimodal Functions: Griewank, Rastrigin, Schaffer, Hump (modified), Nsine (modified), Randcuts, Randsines.

The authors note that some of these functions are standard in the field, while others have been modified to ensure unique optima or to better challenge algorithms.

Key Insights and Ideas

  • QR Mutations are Generally Beneficial: The study consistently shows that using QR mutations leads to improved performance across various evolutionary algorithms and test functions, compared to their pseudo-random counterparts.
  • Significant Gains on Highly Multimodal Problems: The benefits of QR mutations are most pronounced on highly multimodal functions. In some cases, QR mutations can turn an algorithm with a high failure rate into one with a negligible failure rate.
  • Generality of QR Mutations: The paper demonstrates that the advantage of QR mutations is not limited to CMA-ES but extends to other algorithms like SA and CMSA, highlighting the broad applicability of this technique.
  • QR Sequences Matter: The authors emphasize that the quality of the QR sequences themselves is crucial for achieving good performance, echoing findings from previous work.

Key Results

  • Consistent Improvement: In all tested scenarios, QR mutations provided a noticeable improvement over standard random mutations.
  • Dramatic Impact on Multimodal Functions: For challenging multimodal functions like Hump, Schaffer, SchwefelMult, RandomCuts, and RandomSines, QR mutations significantly reduced failure rates, often from around 80% to near zero.
  • Broader Algorithm Applicability: The positive impact of QR mutations was observed across multiple algorithms, including CMA, CMSA, and SA, suggesting it's a general enhancement rather than an algorithm-specific trick.

Limitations and Future Work

  • Unexplained Performance Anomaly: The paper notes an interesting case where CMA outperforms QRCMA (CMA with QR mutations) in a stable manner, and this phenomenon is not explained. This suggests there might be specific scenarios or problem structures where QR mutations are not beneficial or even detrimental.
  • Restarts with QR: The authors suggest that future work should explore the benefits of using quasi-random numbers for restart strategies in EAs, similar to how they've been applied to mutations. This could further enhance performance on difficult optimization landscapes.
  • Random Rotations: While not a limitation of the core findings, the paper mentions that experiments with random full rotations (built with Gram-Schmidt transformation) did not change the results, except for specific cases on the Cigar function, indicating robustness to certain transformations.

Summary updated

BibTeX
@inproceedings{teytaud2016qr,
  author = {Fabien Teytaud and Olivier Teytaud},
  title = {{QR Mutations Improve Many Evolution Strategies: A Lot On Highly Multimodal Problems}},
  booktitle = {GECCO (Companion)},
  year = {2016},
  doi = {10.1145/2908961.2909060},
}
Figure