Knowledge-Based Systems 146 (2018) 142–151
Contents lists available at ScienceDirect
Knowle dge-Base d Systems
journal homepage: www.elsevier.com/locate/knosys
Anisotropic adaptive variance scaling for Gaussian estimation of
distribution algorithm
Zhigang Ren
a , ∗
, Yongsheng Liang
a
, Lin Wang
b
, Aimin Zhang
a
, Bei Pang
a
, Biying Li
a
a
Department of Automation Science and Technology, School of Electronic and Information Engineering, Xi’an Jiaotong University, No.28 Xianning West Road,
Xi’an, Shaanxi 710049, China
b
School of Information Science and Technology, Northwest University, Xi’an, China
a r t i c l e i n f o
Article history:
Received 12 September 2017
Revised 25 January 2018
Accepted 1 February 2018
Available online 2 February 2018
Keywords:
Gaussian estimation of distribution
algorithm
Premature convergence
Search direction
Anisotropic adaptive variance scaling
a b s t r a c t
Traditional Gaussian estimation of distribution algorithms (EDAs) are confronted with issues that the vari-
able variances decrease fast and the main search direction tends to become perpendicular to the improve-
ment direction of the fitness function, which reduces the search efficiency of Gaussian EDAs (GEDAs) and
makes them subject to premature convergence. In this paper, a novel anisotropic adaptive variance scal-
ing (AAVS) technique is proposed to improve the performance of traditional GEDAs and a new GEDA
variant named AAVS-EDA is developed. The advantages of AAVS over the existing variance scaling strate-
gies lie in its ability for tuning the variances and main search direction of GEDA simultaneously, which
are achieved by anisotropically scaling the variances along different eigendirections based on correspond-
ing landscape characteristics captured by a simple topology-based detection method. Besides, AAVS-EDA
also adopts an auxiliary global monitor to ensure its convergence by shrinking all the variances if no
improvement is achieved in a generation. The evaluation results on 30 benchmark functions of CEC2014
test suite demonstrate that AAVS-EDA possesses stronger global optimization efficiency than traditional
GEDAs. The comparison with other state-of-the-art evolutionary algorithms also shows that AAVS-EDA is
efficient and competitive.
©2018 Elsevier B.V. All rights reserved.
1.
Introduction
As a special class of evolutionary algorithm (EA) [1] , estima-
tion of distribution algorithm (EDA) [2–4] is characterized by the
way of generating new solutions, i.e., sampling solutions according
to a probability distribution, but not through crossover and muta-
tion operators as other kinds of EAs. The probability distribution
employed in each generation is generally estimated from the rel-
atively high-quality solutions obtained in previous generations. It
can capture the structure of the problem being solved to a cer-
tain extent and consequently guide the algorithm to more promis-
ing solution regions. During the past few decades, EDAs attracted
much research effort and achieved great success in both combina-
torial and continuous domains [5,6] . In this paper, EDAs for contin-
uous domain are studied.
Continuous EDAs usually adopt Gaussian probability model
[3,4] and histogram model [7] as the basic probability model. Ac-
cording to the way in representing variable dependencies, Gaussian
models for EDAs can be further categorized into three kinds. The
∗
Corresponding author.
E-mail address: renzg@mail.xjtu.edu.cn (Z. Ren).
simplest one is the univariate model which neglects all the variable
dependencies. A representative algorithm with this type of model
is the univariate marginal distribution algorithm (UMDA
c
) [3,4] . A
slightly more sophisticated model is the one that just considers
some important variable dependencies. To identify these depen-
dencies, Bayesian factorization is usually employed [3,8] . The mul-
tivariate model takes all the variable dependencies into account. A
representative algorithm of this type is estimation of multivariate
normal density algorithm (EMNA
g
) [4] .
Although possessing clear physical concept, traditional Gaus-
sian EDAs (GEDAs) often suffer from premature convergence [8,11–
15]
. Early improvement studies attributed this defect to the rapid
shrink of variances and developed many variance scaling strate-
gies. Ocenasek et al. [8] proposed a variance adaption operator for
the mixed Bayesian optimization algorithm [9] based on the well-
known 1/5-success-rule [10] . Yuan and Gallagher [11] claimed that
the performance of GEDA could be improved on certain problems
by compulsively keeping the variances at a value of at least 1. Pošík
[12] suggested enlarging variances by a constant factor. Grahl et al.
[13] proposed an adaptive variance scaling (AVS) strategy which in-
creases the variances when the best solution improves, otherwise
reduces them. Nevertheless, AVS does not directly tune variances
in each generation unless it identifies that the algorithm is travers-
https://doi.org/10.1016/j.knosys.2018.02.001
0950-7051/© 2018 Elsevier B.V. All rights reserved.