7 Introduction to Optimisation
239
instead of using standard genetic operators used in traditional EAs, in EDAs
new candidate solutions to the problem are generated using regression, i.e.
estimating a probabilistic model based on the statistics collected from the set
of candidate solutions (regression), and sampling the achieved probabilistic
model, bringing a new paradigm in evolutionary computation. Because of the
different natures of both optimisation and probabilistic modelling in discrete
and continuous domains, developed EDAs also have differences depending on
the representation type they use for the problem. Many of the early continuous
EDAs as well as their recent improvements are based on the assumption that
design variables can be characterised by Gaussian distribution. The continuous
population-based incremental learning (PBIL C ) [27] extends the original discrete
version to continuous domains by updating a vector of independent Gaussian distributions. The continuous univariate marginal distribution algorithm (UMDA C )
[28] uses maximum likelihood estimation to learn the parameters of the Gaussian
distribution for each variable from the population of solutions. The continuous
mutual information maximisation for input clustering (MIMIC C ) [28] learns the
chain structured probabilistic model for continuous variables by adapting the
concept of conditional entropy for univariate and bivariate Gaussian distributions.
Other probabilistic models estimate a non-parametric distribution for the
variables have also been used in continuous EDAs. The multi-objective Parzenbased estimation of distribution (MOPED) [29] uses a Parzen estimator to build
the probabilistic model. Both Gaussian and Cauchy kernels are used alternatively
during evolution to exploit their complementary characteristics.
A review of methods and their characteristics can be found at [30].
• Differential evolution (DE) [31]: it is an optimisation method particularly
suitable for multidimensional multimodal functions, belonging to the class of
evolution strategy (ES). The main idea is to generate a variation vector by taking
the weighted difference between two other solution vectors randomly chosen
within a population of solution vectors and to add that difference to the vector
difference between the considered solution and a third solution vector.
An approach used to create new algorithms is to hybridise existing ones
by appropriately mixing some of their building blocks. By following this
approach, and based on some new theoretical results on the convergence of
DE, the inflationary differential evolution algorithm (IDEA) [32] was proposed,
combining DE with the restarting procedure of monotonic basin hopping (MBH)
algorithm [33, 34]. Although IDEA showed very good results when applied to
problems with a single or multi-funnel landscape, its performance was found to
depend on the parameters controlling both the convergence of DE and MBH and
the inflationary stopping criterion used to terminate the DE search.
Despite its simplicity, the standard DE alone shows good performance on
a broad range of problems featuring multimodal, separable and non-separable
structures, but the performance is strongly influenced by three parameters: the
population size, n pop ; the crossover probability, CR; and the differential weight
(or step parameter), F . In addition, it was reckoned that the chosen strategies for
mutation and crossover [35] plays an important role.
239
instead of using standard genetic operators used in traditional EAs, in EDAs
new candidate solutions to the problem are generated using regression, i.e.
estimating a probabilistic model based on the statistics collected from the set
of candidate solutions (regression), and sampling the achieved probabilistic
model, bringing a new paradigm in evolutionary computation. Because of the
different natures of both optimisation and probabilistic modelling in discrete
and continuous domains, developed EDAs also have differences depending on
the representation type they use for the problem. Many of the early continuous
EDAs as well as their recent improvements are based on the assumption that
design variables can be characterised by Gaussian distribution. The continuous
population-based incremental learning (PBIL C ) [27] extends the original discrete
version to continuous domains by updating a vector of independent Gaussian distributions. The continuous univariate marginal distribution algorithm (UMDA C )
[28] uses maximum likelihood estimation to learn the parameters of the Gaussian
distribution for each variable from the population of solutions. The continuous
mutual information maximisation for input clustering (MIMIC C ) [28] learns the
chain structured probabilistic model for continuous variables by adapting the
concept of conditional entropy for univariate and bivariate Gaussian distributions.
Other probabilistic models estimate a non-parametric distribution for the
variables have also been used in continuous EDAs. The multi-objective Parzenbased estimation of distribution (MOPED) [29] uses a Parzen estimator to build
the probabilistic model. Both Gaussian and Cauchy kernels are used alternatively
during evolution to exploit their complementary characteristics.
A review of methods and their characteristics can be found at [30].
• Differential evolution (DE) [31]: it is an optimisation method particularly
suitable for multidimensional multimodal functions, belonging to the class of
evolution strategy (ES). The main idea is to generate a variation vector by taking
the weighted difference between two other solution vectors randomly chosen
within a population of solution vectors and to add that difference to the vector
difference between the considered solution and a third solution vector.
An approach used to create new algorithms is to hybridise existing ones
by appropriately mixing some of their building blocks. By following this
approach, and based on some new theoretical results on the convergence of
DE, the inflationary differential evolution algorithm (IDEA) [32] was proposed,
combining DE with the restarting procedure of monotonic basin hopping (MBH)
algorithm [33, 34]. Although IDEA showed very good results when applied to
problems with a single or multi-funnel landscape, its performance was found to
depend on the parameters controlling both the convergence of DE and MBH and
the inflationary stopping criterion used to terminate the DE search.
Despite its simplicity, the standard DE alone shows good performance on
a broad range of problems featuring multimodal, separable and non-separable
structures, but the performance is strongly influenced by three parameters: the
population size, n pop ; the crossover probability, CR; and the differential weight
(or step parameter), F . In addition, it was reckoned that the chosen strategies for
mutation and crossover [35] plays an important role.