9 Multilevel Optimisation
325
to certain regularity conditions at the lower level because of the requirement of
the KKT conditions. The upper level objective function and constraints, however,
can be more general and complex, as the reduced single-objective problem is
solved with an evolutionary algorithm. For example, Wang et al. reduced the
bilevel optimisation problem into a single-level optimisation problem using KKT
conditions and tested the algorithm in a number of standard test problems [49].
The algorithm managed to handle non-differentiability only at the upper level
objective function. Later, Wang et al. improved this algorithm, enabling it to
handle non-convexity of the lower level problem and thus obtaining better results
than their previous approach [50]. A serious drawback of both methods though is
the high number of function evaluations (requiring 100,000 function evaluations
for 2–5 variable bilevel optimisation problems).
• Meta-modeling-based methods: Meta-modeling-based methods are usually
used for optimisation problems when each true evaluation—meaning the exact
solution—is computationally expensive. Meta-model or surrogate model can be
defined as an approximation function of an actual model, which is simpler and
easier to evaluate. The surrogate model is trained and used in the optimisation,
based on a limited sample of true evaluations of the actual model. A relevant
review on the use of fitness approximation in the context of evolutionary
computation has been reported by Yin [47]. Since the bilevel optimisation
problems are inherently complex, the number of evaluations needed is large,
making meta-modeling, especially when used with population-based algorithms,
a very promising alternative [2]. Algorithms published until today, according to
Islam et al. [51], that use approximation models during the evolutionary bilevel
search are shown in Table 9.1.
• Co-evolutionary approaches: these approaches constitute the most general
methodology to solve multilevel optimisation problems. Many metaheuristics,
usually one for each level, are solving different levels of the problem in parallel
while they exchange information between them during the optimisation process.
Table 9.1 Meta-modeling-based algorithms
Meta-modeling-based methods
Modified NBLEA [52]
NBLEA is a basic nested algorithm in which each of the levels
is optimised using an EA and the lower level problem is first
modeled as a quadratic programming problem
BLEAQ [53]
BLEAQ is an efficient bilevel EA based on quadratic approximations, where the optimal lower level variable values are
approximated as a function of the upper level variables
Surrogate-assisted BIDE [54] BIDE uses an extensive differential evolution algorithm at both
levels, with a surrogate model that is built by approximating
the relationship between the upper level variables and the
corresponding lower level optimum
SABLA [51]
SABLA uses surrogate models of multiple types, in order
to provide the flexibility of approximating different types of
functions more accurately
325
to certain regularity conditions at the lower level because of the requirement of
the KKT conditions. The upper level objective function and constraints, however,
can be more general and complex, as the reduced single-objective problem is
solved with an evolutionary algorithm. For example, Wang et al. reduced the
bilevel optimisation problem into a single-level optimisation problem using KKT
conditions and tested the algorithm in a number of standard test problems [49].
The algorithm managed to handle non-differentiability only at the upper level
objective function. Later, Wang et al. improved this algorithm, enabling it to
handle non-convexity of the lower level problem and thus obtaining better results
than their previous approach [50]. A serious drawback of both methods though is
the high number of function evaluations (requiring 100,000 function evaluations
for 2–5 variable bilevel optimisation problems).
• Meta-modeling-based methods: Meta-modeling-based methods are usually
used for optimisation problems when each true evaluation—meaning the exact
solution—is computationally expensive. Meta-model or surrogate model can be
defined as an approximation function of an actual model, which is simpler and
easier to evaluate. The surrogate model is trained and used in the optimisation,
based on a limited sample of true evaluations of the actual model. A relevant
review on the use of fitness approximation in the context of evolutionary
computation has been reported by Yin [47]. Since the bilevel optimisation
problems are inherently complex, the number of evaluations needed is large,
making meta-modeling, especially when used with population-based algorithms,
a very promising alternative [2]. Algorithms published until today, according to
Islam et al. [51], that use approximation models during the evolutionary bilevel
search are shown in Table 9.1.
• Co-evolutionary approaches: these approaches constitute the most general
methodology to solve multilevel optimisation problems. Many metaheuristics,
usually one for each level, are solving different levels of the problem in parallel
while they exchange information between them during the optimisation process.
Table 9.1 Meta-modeling-based algorithms
Meta-modeling-based methods
Modified NBLEA [52]
NBLEA is a basic nested algorithm in which each of the levels
is optimised using an EA and the lower level problem is first
modeled as a quadratic programming problem
BLEAQ [53]
BLEAQ is an efficient bilevel EA based on quadratic approximations, where the optimal lower level variable values are
approximated as a function of the upper level variables
Surrogate-assisted BIDE [54] BIDE uses an extensive differential evolution algorithm at both
levels, with a surrogate model that is built by approximating
the relationship between the upper level variables and the
corresponding lower level optimum
SABLA [51]
SABLA uses surrogate models of multiple types, in order
to provide the flexibility of approximating different types of
functions more accurately