SDR: A Better Trigger for Adaptive Variance Scaling in Normal EDAs

Recently, advances have been made in continuous, normal-distribution-based Estimation-of-Distribution Algorithms (EDAs) by scaling the variance up from the maximum-likelihood estimate. When done properly, such scaling has been shown to prevent premature convergence on slope-like regions of the search space. In this paper we specifically focus on one way of scaling that was previously introduced as Adaptive Variance Scaling (AVS). It was found that when using AVS, the average number of fitness evaluations grows subquadratically with the dimensionality on a wide range of unimodal test-problems, competitively with the CMA-ES. Still, room for improvement exists because the variance doesn't always have to be scaled. A previously introduced trigger based on correlation that determines when to apply scaling was shown to fail on higher dimensional problems. Here we provide a new solution called the Standard-Deviation Ratio (SDR) trigger that is integrated with the Iterated Density-Estimation Evolutionary Algorithm (IDEA). Intuitively put, scaling is triggered with SDR only if improvements are found to be far away from the mean. SDR works even in high dimensions as a result of factorizing the decision rule behind the trigger according to the estimated Bayesian factorization. We evaluate SDR-AVS-IDEA on the same set of benchmark problems and compare it with AVS-IDEA and CMA-ES. We find that the addition of SDR gives AVS-IDEA an important extra edge for it to be used in future research and in applications both in single-objective optimization as well as in multi-objective and dynamic optimization. In addition, we provide practical rules of thumb for parameter settings for using SDR-AVS-IDEA that result in an asymptotic scale-up behavior that is sublinear for the population size (O(l^{0.85})) and subquadratic (O(l^{1.85})) for the number of evaluations.