SDR: a better trigger for adaptive variance scaling in normal EDAs

Recently, advances have been made in continuous, normal-distribution-based Estimation-of-DistributionAlgorithms (EDAs) by scaling the variance upfrom the maximum-likelihood estimate. When doneproperly, such scaling has been shown to preventpremature convergence on slope-like regions ofthe search space. In this paper we specificallyfocus on one way of scaling that was previouslyintroduced as Adaptive Variance Scaling (AVS). It wasfound that when using AVS, the average number offitness evaluations grows subquadratically withthe dimensionality on a wide range of unimodaltest-problems, competitively with the CMA-ES.Still, room for improvement exists because thevariance doesn't always have to be scaled. Apreviously introduced trigger based on correlationthat determines when to apply scaling was shownto fail on higher dimensional problems. Here weprovide a new solution called the Standard-DeviationRatio (SDR) trigger that is integrated with theIterated Density-Estimation Evolutionary Algorithm(IDEA). Intuitively put, scaling istriggered with SDR only if improvements are foundto be far away from the mean. SDR works even inhigh dimensions as a result of factorizing thedecision rule behind the trigger according to theestimated Bayesian factorization. We evaluateSDR-AVS-IDEA on the same set ofbenchmark problems and compare it with AVS-IDEAand CMA-ES. We find that the addition of SDR givesAVS-IDEA an important extra edgefor it to be used in future research and inapplications both in single-objective optimizationas well as in multi-objective and dynamicoptimization. In addition, we provide practical rulesof thumb for parameter settings for usingSDR-AVS-IDEA that result in anasymptotic scale-up behavior that is sublinearfor the population size (O(l^{0.85})) andsubquadratic (O(l^{1.85})) for thenumber of evaluations.