8 An Introduction to Many-Objective Evolutionary Optimization
295
more important because instead of a single solution, we are looking for a set of
them—the Pareto front—which increases the number of evaluations needed.
Surrogate modelling is an attempt to describe or approximate an unknown
function based on a number of previous samples. In optimization, it is a popular
method to approximate an expensive evaluation, replacing it with a much cheaper
function. A more detailed explanation of surrogate modelling can be found in
Chap. 12.
In the same vein as the problem described above, typically, EAs require a lot of
function evaluations to be successful. The number of function evaluations depends
on the problem and on which EA is being used, but normally, the number of
evaluations ranges from hundreds to thousands. Often, the available budget is not
enough to evaluate the objective that many times, and surrogate models have to be
used. This leads to methods known as surrogate-assisted EAs.
Surrogate-assisted EA for a single-objective problem is quite straightforward; it
replaces the objective function with a surrogate model. However, when we move on
to multi- and many-objective problems, there is a complication: how do we make
the surrogate model for several objectives? This section provides an answer to that
question, describing surrogate-assisted EAs applied in multi- and many-objective
problems.
In this section we will use the abbreviation MOP for multi- and many-objective
problems because surrogate model can be applied to both classes of problems in the
same way.
8.5.1 ParEGO
ParEGO [32] is a modification from a single-objective surrogate-assisted method
named EGO [30] (efficient global optimization). Originally, EGO was proposed
to handle single-objective problems with expensive evaluation. ParEGO stands for
Pareto EGO, which clearly indicates how it is different from the original EGO: it
searches for the Pareto front instead of a single optimum point.
To explain ParEGO, it is better if we start by describing what EGO does. EGO
is intended to be used on expensive black-box functions. EGO starts with a set of
initial designs obtained from Latin hypercube sampling, one of the several available
sampling methods. Based on these initial samples, the EGO creates a DACE kriging
model [30, 32], i.e., we try to fit the unknown function to a standard model. Using
the model, a new design is suggested based on its expected improvement.
Expected improvement is the expectation of a random variable called improvement I by Jones et al. [30]. From the initial samples that we have, we will obtain our
initial best design which has smallest or largest objective value (for minimization
and maximization problem, respectively). Let us call this best design x∗ and its
objective value f (x∗). The DACE kriging model will then provide a prediction and
standard error on all possible design points x. We then treat the objective function
f (x) as a normally distributed random variable Y with mean and standard deviation
295
more important because instead of a single solution, we are looking for a set of
them—the Pareto front—which increases the number of evaluations needed.
Surrogate modelling is an attempt to describe or approximate an unknown
function based on a number of previous samples. In optimization, it is a popular
method to approximate an expensive evaluation, replacing it with a much cheaper
function. A more detailed explanation of surrogate modelling can be found in
Chap. 12.
In the same vein as the problem described above, typically, EAs require a lot of
function evaluations to be successful. The number of function evaluations depends
on the problem and on which EA is being used, but normally, the number of
evaluations ranges from hundreds to thousands. Often, the available budget is not
enough to evaluate the objective that many times, and surrogate models have to be
used. This leads to methods known as surrogate-assisted EAs.
Surrogate-assisted EA for a single-objective problem is quite straightforward; it
replaces the objective function with a surrogate model. However, when we move on
to multi- and many-objective problems, there is a complication: how do we make
the surrogate model for several objectives? This section provides an answer to that
question, describing surrogate-assisted EAs applied in multi- and many-objective
problems.
In this section we will use the abbreviation MOP for multi- and many-objective
problems because surrogate model can be applied to both classes of problems in the
same way.
8.5.1 ParEGO
ParEGO [32] is a modification from a single-objective surrogate-assisted method
named EGO [30] (efficient global optimization). Originally, EGO was proposed
to handle single-objective problems with expensive evaluation. ParEGO stands for
Pareto EGO, which clearly indicates how it is different from the original EGO: it
searches for the Pareto front instead of a single optimum point.
To explain ParEGO, it is better if we start by describing what EGO does. EGO
is intended to be used on expensive black-box functions. EGO starts with a set of
initial designs obtained from Latin hypercube sampling, one of the several available
sampling methods. Based on these initial samples, the EGO creates a DACE kriging
model [30, 32], i.e., we try to fit the unknown function to a standard model. Using
the model, a new design is suggested based on its expected improvement.
Expected improvement is the expectation of a random variable called improvement I by Jones et al. [30]. From the initial samples that we have, we will obtain our
initial best design which has smallest or largest objective value (for minimization
and maximization problem, respectively). Let us call this best design x∗ and its
objective value f (x∗). The DACE kriging model will then provide a prediction and
standard error on all possible design points x. We then treat the objective function
f (x) as a normally distributed random variable Y with mean and standard deviation