Paper Info
Title
SDR: a better trigger for adaptive variance scaling in normal EDAs
Abstract
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.
Year
DOI
Venue
2007
10.1145/1276958.1277066
IEEE Transactions on Medical Imaging
Keywords
Field
DocType
adaptive variance scaling,average number offitness evaluation,sdr givesavs-idea,avs-ideaand cma-es,maximum-likelihood estimate,better trigger,inhigh dimension,normal edas,higher dimensional problem,important extra edgefor,anasymptotic scale-up behavior,evolutionary algorithms,estimation of distribution algorithms
Convergence (routing),EDAS,Mathematical optimization,Estimation of distribution algorithm,Evolutionary algorithm,Computer science,Curse of dimensionality,Factorization,Scaling,Bayesian probability
Conference
Citations 
PageRank 
References 
13
0.91
14
Authors
3
Name
Order
Citations
PageRank
Peter A. N. Bosman150749.04
Jörn Grahl219415.68
Franz Rothlauf31497160.29