IEEE Computational Intelligence Magazine - February 2021 - 35

R

I. Introduction

obustness is of particular importance in engineering design when the system to be designed must
operate in multiple scenarios [1], [2]. An ideal design
is expected to achieve the best performance in all
possible scenarios, which is often impossible for real-world
applications due to the trade-off among those scenarios [3]. In
other words, an optimal design in one single scenario might
not have good performance in others [4], making the formulation of optimizing the performance in a single fixed scenario impractical [5]. Optimizing the performance in the
worst-case scenario is one popular formulation of robust
optimization to deal with multiple scenarios [6], which is
known as minimax optimization [7]. In addition to the decision space of general optimization problems, a scenario space
also needs to be coped with in minimax optimization problems. Minimax optimization can usually be achieved in a
hierarchical way, where evaluating each solution in the design
space requires an optimization search in the whole scenario
space. Traditional optimization algorithms such as mathematical programming [8]-[11], approximation methods [12], and
branch-and-bound algorithms [13]-[15] have been employed
to solve minimax optimization problems. However, their performance is less than satisfactory on the problems with continuous scenario space or nonanalytic objective functions.
Over the past two decades, a number of evolutionary algorithms (EAs) have shown promising performance on minimax
optimization problems [16]-[19]. A straightforward fitness formulation for minimax optimization is to assess the worst-case
scenario performance, which however, requires a large number
of function evaluations. As a result, a hierarchical search of the
optimal solution for minimax optimization incurs high computational costs, particularly when each quality evaluation is
time-consuming.
Most minimax EAs adopt a coevolutionary approach [20]
with populations searching the design and scenario spaces separately [7], [21]-[23]. Such parallel rather than hierarchical
search used by these coevolutionary algorithms can considerably reduce the function evaluations required to achieve an
acceptable solution. However, they easily get stuck in an endless optimization cycle in finding the optima in the decision
and scenario spaces [24] when the symmetrical condition as
defined in [25] is not met. In fact, asymmetrical problems are
more commonly existed than symmetrical problems in the
real-world [19]. Therefore, several rank-based evaluation methods [24], [25] were proposed to tackle this weakness of minimax coevolutionary algorithms. As the endless optimization
cycle is caused by the coevolutionary structure, a few algorithms employ the hierarchical structure to deal with asymmetrical problems, where the scenario space is either traversed
[26] or randomly sampled [25] for each candidate solution. To
further improve the efficiency of the hierarchical structure, a
recent minimax differential evolution (MMDE) algorithm
[19] used a min heap to allocate computational costs in the
scenario space for different solutions. However, it still needs

100,000 function evaluations for problems with only two
decision variables.
Many real engineering optimization problems have medium-scale decision variables and are driven by time-consuming
function evaluations with a high degree of complexity [27].
For example, a three-dimensional computational fluid dynamics (CFD) simulation for one given scenario [5] might take
minutes to hours, making existing minimax EAs impractical.
Surrogate-assisted evolutionary algorithms (SAEAs) [28], [29]
have shown both effectiveness and efficiency in solving expensive optimization problems [30], in which the expensive fitness
evaluations are replaced by the computationally cheap surrogate models [31]-[33]. Those surrogate models are built and
updated using a small number of real function evaluations. So
far, surrogate models like the Gaussian processes (GP) [34]-
[36] and radial basis function (RBF) networks [37]-[39] have
been employed in two minimax EAs [31], [40] to reduce the
function evaluations for finding the worst-case scenario for
each candidate solution. However, neither of them can solve
expensive minimax optimization problems taking into account
multiple scenarios. The SAEA in [40] deals with the uncertainty in the decision space rather than that in the scenario
space. The SAEA in [31] assumes that the evaluation of a given
solution for the worst-scenario performance is expensive but
the evaluation for a given solution in a given scenario is cheap,
so it builds a GP model to approximate the worst-scenario
objective function.
Existing EAs for solving minimax optimization problems
consider all the worst-case scenario search processes for different solutions in the design space as independent optimization
processes, and they employ an optimizer to repeatedly search
the worst-case scenarios of all the individuals in the population.
In fact, similar solutions in the decision space might have similar worst-case scenarios, which means the worst-case scenario
search processes can be parallelized. Multitasking optimization
(MTO) techniques [41], [42] can simultaneously solve multiple
optimization problems in one single run, which takes advantage of the positive knowledge transfer between optimization
problems (i.e., the similarity of the population in the decision
space) [43], [44]. Equipped with an implicit parallelism, MTO
has shown high efficiency on multi-objective optimization
problems [45]-[48], bi-level optimization problems [49], ex--
pensive optimization problems [50], symbolic regression problems [51], sparse reconstruction [52], beneficiation processes
[46], and capacitated vehicle routing problems [53]. The methodology of MTO naturally fits minimax optimization problems, if we consider the worst-case scenario search for different
solutions in the population as different tasks.
In this paper, we make use of both surrogate and MTO to
solve expensive minimax optimization problems within a limited number of function evaluations. The proposed algorithm is
based on a popular MTO algorithm, the multifactorial evolutionary algorithm (MFEA) [42], in which function evaluations are replaced by a surrogate model (an RBF model).
We term the proposed algorithm surrogate-assisted minimax

FEBRUARY 2021 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE

35
IEEE Computational Intelligence Magazine - February 2021

Table of Contents for the Digital Edition of IEEE Computational Intelligence Magazine - February 2021
