344
L. Gentile et al.
and no equality and inequality constraints are used. Importantly, the spatial correlation of the data is encoded within a kernel or correlation function. A frequently
employed correlation function that models the correlation between samples (or
candidate solutions) is the Gaussian kernel k(x, x ) = exp
−
n
i=1 θ i |x i − x
i | 2
.
Here, n is the number of modeled variables (search space dimension) and θ i is a
parameter of the kernel (determined by maximum likelihood estimation (MLE)).
Furthermore, x as well as x are potential candidate solutions (or samples).
Employing such a kernel, a Kriging model produces the following predictor:
ˆ
y(z
∗ ) = ˆ
μ + k
T K
−1 (y − 1 ˆ
μ),
(10.2)
where y are the training observations, ˆ
y(z ∗ ) is the predicted function value of a new
sample z ∗ , ˆ
μ represents the process mean determined by MLE, 1 is a vector of ones,
K is the matrix that collects all pair-wise correlations of the training samples Z and
k is the column vector of correlations between the set of training samples Z and
the new sample z ∗ . After appropriate training, such a predictor may be employed to
replace an expensive objective function.
The success of Kriging in the field of real-world application problems mostly
relies on the possibility to estimate the uncertainty of the predictor. This feature
assumes a prominent role in applications in which the limited number of observations that can be performed inhibits an exhaustive exploration of the search
space. In these cases, the estimate of the uncertainty can be used to balance
exploration and exploitation by computing the expected improvement (EI) of
candidate solutions [35]. The uncertainty of the model is computed with
ˆ
s
2 (z
∗ ) = σ
2
process (1 − k
T K
−1 k),
(10.3)
where σ 2
process is the process variance, determined by MLE. If the uncertainty is
zero, the EI is also zero. Else, the uncertainty is non-zero, and the EI is
EI(z
∗ ) = y imp
y imp
ˆ
s(z ∗ )
+ ˆ
s(z
∗ )φ
y imp
ˆ
s(z ∗ )
,
where y imp = min(y) − ˆ
y(z ∗ ). () indicates the normal cumulative distribution
function. Respectively, φ() is the probability density function.
It has to be noted that the above description of Kriging presents an interpolating
model, which assumes zero error at already observed locations. Clearly, this does
not take noise or uncertainty into account. One way to account for noise is to
introduce the so-called nugget effect. This essentially adds a constant value η to
the diagonal of the kernel matrix K. The parameter η is determined by MLE. The
nugget effect enables the model to regress the observed data and hence smoothens
noisy observations.
Until now, we discussed Kriging in the context of real-valued search spaces. It
is also applicable to “mixed” search space, where an appropriate kernel is available.
L. Gentile et al.
and no equality and inequality constraints are used. Importantly, the spatial correlation of the data is encoded within a kernel or correlation function. A frequently
employed correlation function that models the correlation between samples (or
candidate solutions) is the Gaussian kernel k(x, x ) = exp
−
n
i=1 θ i |x i − x
i | 2
.
Here, n is the number of modeled variables (search space dimension) and θ i is a
parameter of the kernel (determined by maximum likelihood estimation (MLE)).
Furthermore, x as well as x are potential candidate solutions (or samples).
Employing such a kernel, a Kriging model produces the following predictor:
ˆ
y(z
∗ ) = ˆ
μ + k
T K
−1 (y − 1 ˆ
μ),
(10.2)
where y are the training observations, ˆ
y(z ∗ ) is the predicted function value of a new
sample z ∗ , ˆ
μ represents the process mean determined by MLE, 1 is a vector of ones,
K is the matrix that collects all pair-wise correlations of the training samples Z and
k is the column vector of correlations between the set of training samples Z and
the new sample z ∗ . After appropriate training, such a predictor may be employed to
replace an expensive objective function.
The success of Kriging in the field of real-world application problems mostly
relies on the possibility to estimate the uncertainty of the predictor. This feature
assumes a prominent role in applications in which the limited number of observations that can be performed inhibits an exhaustive exploration of the search
space. In these cases, the estimate of the uncertainty can be used to balance
exploration and exploitation by computing the expected improvement (EI) of
candidate solutions [35]. The uncertainty of the model is computed with
ˆ
s
2 (z
∗ ) = σ
2
process (1 − k
T K
−1 k),
(10.3)
where σ 2
process is the process variance, determined by MLE. If the uncertainty is
zero, the EI is also zero. Else, the uncertainty is non-zero, and the EI is
EI(z
∗ ) = y imp
y imp
ˆ
s(z ∗ )
+ ˆ
s(z
∗ )φ
y imp
ˆ
s(z ∗ )
,
where y imp = min(y) − ˆ
y(z ∗ ). () indicates the normal cumulative distribution
function. Respectively, φ() is the probability density function.
It has to be noted that the above description of Kriging presents an interpolating
model, which assumes zero error at already observed locations. Clearly, this does
not take noise or uncertainty into account. One way to account for noise is to
introduce the so-called nugget effect. This essentially adds a constant value η to
the diagonal of the kernel matrix K. The parameter η is determined by MLE. The
nugget effect enables the model to regress the observed data and hence smoothens
noisy observations.
Until now, we discussed Kriging in the context of real-valued search spaces. It
is also applicable to “mixed” search space, where an appropriate kernel is available.