Annals of Operations Research

https://doi.org/10.1007/s10479-019-03435-4

S.I.: MOPGP 2017

Solving bi-objective uncertain stochastic resource allocation

problems by the CVaR-based risk measure and
decomposition-based multi-objective evolutionary
algorithms

Juan Li1 · Bin Xin2,3,4 · Panos M. Pardalos5 · Jie Chen2,3,4

© Springer Science+Business Media, LLC, part of Springer Nature 2019

Abstract
This paper investigates the uncertain stochastic resource allocation problem in which the
results of a given allocation of resources are described as probabilities and these probabili-
ties are considered to be uncertain from practical aspects. Here uncertainties are introduced
by assuming that these probabilities depend on random parameters which are impacted by
various factors. The redundancy allocation problem (RAP) and the multi-stage weapon-target
assignment (MWTA) problem are special cases of stochastic resource allocation problems.
Bi-objective models for the uncertain RAP and MWTA problem in which the conditional
value-at-risk measure is used to control the risk brought by uncertainties are presented in this
paper. The bi-objective formulation covers the objectives of minimizing the risk of failure
of completing activities and the resulting cost of resources. With the aim of determining
referenced Pareto fronts, a linearized formulation and an approximated linear formulation
are put forward for RAPs and MWTA problems based on problem-specific characteristics,
respectively. Two state-of-the-art decomposition-based multi-objective evolutionary algo-
rithms (i.e., MOEA/D-AWA and DMOEA-εC) are used to solve the formulated bi-objective
problem. In view of differences between MOEA/D-AWA and DMOEA-εC, two matching
schemes inspired by DMOEA-εC are proposed and embedded in MOEA/D-AWA. Numerical
experiments have been performed on a set of uncertain RAP and MWTA instances. Experi-
mental results demonstrate that DMOEA-εC outperforms MOEA/D-AWA on the majority of
test instances and the superiority of DMOEA-εC can be ascribed to the ε-constraint frame-
work.

This work was supported in part by the National Natural Science Foundation of China under Grant 61822304
and 61673058, the NSFC-Zhejiang Joint Fund for the Integration of Industrialization and Informatization
under Grant U1609214, the Foundation for Innovative Research Groups of the National Natural Science
Foundation of China under Grant 61621063, the Projects of Major International (Regional) Joint Research
Program NSFC under Grant 61720106011, the China Scholarship Council, and the Peng Cheng Laboratory.
Panos M. Pardalos is supported by the Paul and Heidi Brown Preeminent Professorship in Industrial and
Systems Engineering, University of Florida (USA) and a Humboldt Research Award (Germany).

B Bin Xin
brucebin@bit.edu.cn
Extended author information available on the last page of the article

123
 Annals of Operations Research

Keywords Stochastic resource allocation problem · Uncertain optimization · CVaR

measure · Decomposition-based multi-objective evolutionary algorithm · Matching scheme

1 Introduction

The stochastic resource allocation problem contains an extensive class of combinatorial

optimization problems encountered in many fields, such as the radio resource allocation
(RRA) problem in communication networks (Xu et al. 2014), the relay resources management
of wireless networks (Chu et al. 2016), the circuit design (Li et al. 2016b), the weapon target
assignment (WTA) problem in military operations research fields (Blodgett et al. 2003; Li
et al. 2016a), the redundancy allocation problem (RAP) in complex systems (Caserta and Voß
2016), and so on. A distinct feature of stochastic resource allocation problems is reflected
by the fact that when assigning a number of resources to an activity, the completion of
the activity is not definitely successful or failed, rather, it is stochastic and described as a
probability value. For example, the reliability of a component is a stochastic event and is
described as the reliability in the RAP. As to the WTA problem, the completion of weapons
destroy targets are described as kill probabilities.
The risk of failure of completing activities and the resulting cost of resources are two
commonly considered factors in stochastic resource allocation problems. In real situations,
many conflicting criteria should be taken into account when evaluating the performance of
decisions. Besides, many real-world applications are characterized by a host of uncertainties
induced by incomplete, unobtainable, and unquantifiable information. That is also the case
for stochastic resource allocation problems. Then, it is worth solving the stochastic resource
allocation problem by considering both its multi-objective and uncertain aspects. The RAP
and the MWTA problem are special cases of stochastic resource allocation problems and have
interested several researchers in the field of complex system. As reported in the literature
review which will be presented in the following, the previous studies did not simultaneously
consider multi-objective and uncertain aspects of the RAP and the MWTA problem.
This paper firstly investigates the uncertain stochastic resource allocation problem
and presents bi-objective formulations of the RAP and the MWTA problem. Then, the
CVaR measure proposed in Pavlikov and Uryasev (2018) is adopted to measure the
risk of failure of completing activities. Besides, two state-of-the-art decomposition-based
multi-objective evolutionary algorithms are employed to solve the formulated problems.
The two decomposition-based multi-objective evolutionary algorithms include the multi-
objective evolutionary algorithms based on decomposition with adaptive weight adjustment
(MOEA/D-AWA) (Qi et al. 2014) and the decomposition-based multi-objective evolution-
ary algorithm with the ε-constraint framework (DMOEA-εC) (Chen et al. 2017). The major
innovations and contributions of this paper include the following.

– This paper attempts to build bi-objective models for the uncertain stochastic resource
allocation problem by using the CVaR measure. The bi-objective formulation covers the
objectives of minimizing the risk of failure of completing activities and the resulting cost
of resources. In order to obtain referenced Pareto fronts, a linearized formulation and an
approximated linear formulation are put forward for RAPs and MWTA problems based
on problem-specific characteristics, respectively.
– Two state-of-the-art decomposition-based multi-objective evolutionary algorithms are
adopted for solving uncertain RAP and MWTA problems. Given the difference between
MOEA/D-AWA and DMOEA-εC, a solution-to-subproblem matching scheme and a

123
Annals of Operations Research

subproblem-to-solution matching scheme which adopt different matching criteria are

proposed for MOEA/D-AWA to have a fair comparison with DMOEA-εC.
The rest of this paper is organized as follows. Section 2 presents a literature review on
the RAP, the WTA problem, and uncertain optimization. Mathematical formulations of bi-
objective uncertain RAPs and MWTA problems are presented in Sect. 3. The linearization of
the RAP and the approximated lower bound formulation of the MWTA problem are proposed
in Sect. 4. Section 5 gives a brief introduction of two decomposition-based multi-objective
evolutionary algorithms and presents two matching schemes. Section 6 conducts parameter
tunings firstly and then shows results of comparison between MOEA/D-AWA and its variant.
Then, numerical experiments are conducted on RAP and MWTA instances to compare the
performance of two decomposition-based multi-objective evolutionary algorithms. Section 7
concludes this paper and identifies future studies.

2 Literature review

2.1 The RAP

System designers desire to achieve architectures and configurations with the highest possible
reliability. In general, there are two methods to increase system reliability. The first method is
increasing the reliability of components and the second one is using redundant components
within subsystems (Tillman et al. 1980). The use of redundant components in subsystems,
which is called the system redundancy design, is the most common and efficient approach of
enhancing the system reliability in industrial engineering activities. The RAP is one of the
representative problems in system redundancy design. It seeks to determine the number of
redundant components to be allocated in each subsystem with the purposes of improving the
reliability of a system and reducing associated costs (e.g., acquisition, operation, maintenance
costs, and so on) (Huang 2015).
Since redundancy allocation problem is known to be NP-hard (Chern 1992), there are
only a few exact algorithms which concentrate on reducing the search space of discrete opti-
mization methods. Sung and Cho (2000) developed lower and upper bounds of the system
reliability by using variable relaxation and Lagrangian relaxation techniques. Prasad and
Kuo (2000) presented a partial enumeration method for a wide range of complex optimiza-
tion problems based on a lexicographic search. Apart from exact methods, there are many
heuristic algorithms have been proposed and applied in optimal reliability design. Nahas and
Nourelfath (2005) combined a local search algorithm and a specific improvement algorithm
to improve the quality of a solution. Lee et al. (2002) developed a two-phase NN-hGA in
which the neural network (NN) is used as a rough search technique to devise the initial solu-
tions for a genetic algorithm (GA). An immune algorithms-based approach was proposed for
the RAP (Chen and You 2005). Zhu and Kuo (2014) dealt with a bi-objective RAP with the
aims of maximizing the system reliability and minimizing the cost.

2.2 The WTA problem

The WTA problem is a fundamental problem arising in defense-related applications of mili-

tary operations research (Ahuja et al. 2007), which deals with how to obtain a weapon-target
pair or a set of weapon-target pairs that meet decision makers’ operational goals regarding
combating effects and expenditures. The WTA problem is a classical constrained combinato-

123
 Annals of Operations Research

rial optimization problem and has been proved to be NP-complete (Lloyd and Witsenhausen
1986). The research on WTA problems dates back to 1950s and 1960s when Manne (1958),
Braford (1961) and Day (1966) investigated the WTA modeling issues. Before 1970s, the
research had been focused on some special areas, e.g., the missile-based aerial defense (Cai
et al. 2006). The general WTA problem was investigated systematically by Hosein et al. in
1980s Hosein et al. (1988).
Hosein et al. (1988) grouped the WTA problems into two categories: the static WTA
(SWTA) and the dynamic WTA (DWTA). In SWTA, all weapons engage with targets in a
single stage. On the contrary, DWTA is a multi-stage problem where some weapons engage
with targets at one stage, and the outcomes of this engagement are assessed. The strategy for
the next stage is decided based on the former assessment. DWTA is a global decision-making
process which takes the whole defense effects through all stages into account and incorporates
the concept of time window, and thus it is much more complicated than SWTA. In real combat
situations, after making decisions at one stage, there will be a damage assessment process
during which a number of new targets may appear or some old targets may exit (Wu et al.
2008). Following with that, a new decision making process of the next stage will be triggered.
This process is the same as the previous one, except that the computational complexity is
normally decreased due to the reduction of the number of weapons and targets. Thus, there
is a cyclic computation: “Decision Making → Damage assessment → Decision Making”
in the actual DWTA problem. The MWTA problem falls between the SWTA problem and
the DWTA one. It also takes time windows into account, but does not possess the dynamic
process. The MWTA problem which lays a foundation for DWTA is considered in this paper.
There are few cases of exact approaches for the WTA due to its NP-completeness. den-
Broeder et al. (1959) showed the first optimal solution technique in their maximum marginal
return (MMR) algorithm by assuming that the kill probability of each weapon to any target
is the same. Ahuja et al. (2007) implemented three lower bounding strategies for SWTA
problems, i.e., a generalized network flow solution, an MMR solution, and a minimum cost
flow solution. Due to the computational complexity of the SWTA problem, much of the lit-
erature focuses on heuristic algorithms. The very large scale neighborhood (VLSN) search
metaheuristic was used to improve upon informed feasible solutions (Lee 2010). Xin et al.
(2010) solved the DWTA problem using virtual permutation (VP), tabu search, GA, and ant
colony optimization. In a subsequent work, they developed a rule-based heuristic method
(Xin et al. 2011). The DWTA problem with the objectives of minimizing the operational
cost and maximizing the expected damage to hostile targets was studied in Li et al. (2015).
Leboucher et al. (2013) adopted a Hungarian Algorithm and a GA-PSO hybrid algorithm
to determine the firing order of the assignments. A more recent review of WTA models and
algorithms can be found in Kline et al. (2019).

2.3 Uncertain optimization

In addition to satisfying several conflicting objectives, many real-world applications are char-
acterized by a host of uncertainties induced by incomplete, unobtainable, and unquantifiable
information. That is also the case for the stochastic resource allocation problem. Most exist-
ing research models stochastic resource allocation problems as deterministic optimization
problems with fixed parameters. However, since uncertainties widely exist in practice, uncer-
tain stochastic resource allocation problems are much more practical. Uncertainties come in
different forms, such as stochastic, fuzzy, rough, and compound ones (Liu 2009). In this
paper, uncertainties are introduced by assuming the probability of the completion of each

123
Annals of Operations Research

activity is stochastic with certain probability distribution. During the past decades, handling
uncertainties has been a hot topic, and there are several ways to tackle uncertainties in the
literature. To our knowledge, existing approaches for solving uncertain problems can be
grouped into the following three categories.
(1) Using multi-objective approaches It means that we can define an additional objective
to describe uncertainties. For example, the mean-variance model (Dehghan Hardoroudi
et al. 2017), the mean-variance-skewness model (Li et al. 2010), and the mean-entropy
model (Sulieman et al. 2010) are commonly used approaches. However, this kind of
methods will increase the number of objectives, and thus increase the complexity of the
problem to be handled.
(2) Designing It means that we can design different uncertainty-tolerant algorithms or embed
uncertainty-handling components in existing algorithms. Although metaheuristics are
known to be inherently robust to low-level uncertainties due to their distributed nature and
nonreliance on gradient information, uncertainty-handling components are still needed
to reduce detrimental effects of high-level uncertainties. For instance, Buche et al. (2002)
proposed the noise tolerant strength Pareto evolutionary algorithm (NTSPEA) with an
improved robust performance against noise. Teich (2001) and Hughes (2001) both intro-
duced a probabilistic Pareto ranking scheme to account for the presence of uncertainties.
(3) Converting It means converting uncertain functions into their deterministic counter-
parts. The uncertainty theory founded by Liu (2009) is a branch of mathematics based
on normality, duality, subadditivity, and product axioms. It is a common way to trans-
form uncertain functions into deterministic ones. Based on the uncertainty theory, the
chance-constrained programming and the dependent-chance programming have been
applied to deal with practical problems (Wang et al. 2014). Additionally, mean and
robust approaches are commonly used strategies for handling uncertainties. For exam-
ple, an evolutionary algorithm based on a mean operator for multi-objective flow-shop
scheduling problems with uncertainties was suggested in Liefooghe et al. (2007). Actu-
ally, the mean operator is inappropriate when the distributions of uncertain functions are
far from normal. A robust approach was adopted in Li et al. (2016a) and Gomes de Mattos
et al. (2018). The robust approach is a pessimistic approach with high risk aversion, and
it may be too conservative and restricting. In Krokhmal et al. (2004), the percentile risk
measure CVaR Pavlikov and Uryasev (2018) was adopted in stochastic programming
with poorly defined distributions.
There are very few related work which has studied multi-objective and uncertain aspects of
the RAP and the UMWTA problem simultaneously. Thus, this paper suggests to investigate
the bi-objective uncertain stochastic resource allocation problems in detail and use the CVaR
to measure the risk of failure of completing activities.

3 Mathematical formulations of the uncertain stochastic resource

allocation problem

3.1 Mathematical formulations of the RAP

In general, redundancy strategies are generally grouped into two main categories, namely
active and standby strategies. In an active redundancy strategy, it is assumed that all redundant
components are implemented at the same time. In a standby redundancy strategy, a sequential
order is used for implementing the redundant components and these components can be added

123
 Annals of Operations Research

Fig. 1 The series-parallel system

for RAPs

to the system at component failure time (Zhu and Kuo 2014). Besides, standby redundant
systems can be broadly classified as having unrepairable or repairable elements. We focus
on the unrepairable standby redundancy system here. A series-parallel system is basically
characterized through a predefined number of sub-systems which are connected serially (see
Fig. 1). A parallel subsystem works when at least one of its components works, and a series
system fails when at least one of its subsystems fails. The unrepairable series-parallel standby
redundancy system is taken as an example in this paper, and the following assumptions are
used:

(1) Each component has only two possible states: functioning or failed;
(2) The states of all components are statistically independent;
(3) All the components in a subsystem are identical.

Under the above-mentioned assumptions, the risk of failure of the series-parallel system
with a confidence level α and the cost of the series-parallel system are defined as follows:

m 
ni 
 xi j
f sr (X , ξ , α) = C V a Rα 1 − ri j (ξ ) (1)
i=1 j=1

m 
ni
f sc (X ) = ci j · xi j (2)
i=1 j=1

where α represents the confidence level and m is the number of sub-systems. xi j is the
decision variable which represents the quantity of component j used in sub-system i. n i is
the number of available component choices for sub-system i. ri j (ξ ) represents the uncertain
reliability of component j in sub-system i and depends on a random parameter ξ . Different
distributions of the reliability value ri j (ξ ) can be available through expert knowledge before
the system design. ci j is the cost of component j in sub-system i.
Besides, there is a constraint on the maximum number of components for each sub-system.
That is, for each sub-system i, the maximum number of components which can be parallelized
is set as n max,i . This constraint can be formulated as following:


ni
1≤ xi j ≤ n max,i , i = 1, . . . , m. (3)
j=1

Thus, the bi-objective uncertain RAP is modeled as: min [ f sr (X , ξ , α), f sc (X )], s.t. (3).

123
Annals of Operations Research

3.2 Mathematical formulations of the MWTA problem

Models of MWTA problems depend on many factors, e.g., defense strategies and features
of targets and weapons. The scenario considered in this paper is delineated as follows. At
certain time, the defender detects T hostile targets and has W weapons to intercept targets.
Besides, before these offensive targets break through the defense and escape, there are at most
S stages available for the defender to use its own weapons to hit hostile targets (Johnson et al.
2018; Li et al. 2015, 2016a). The above-mentioned combat scenario is very common, e.g.,
in air-defense-oriented naval group combating. Given a set of targets and available weapons,
one must find the optimal assignments of weapons to targets considering both the risk of
missing targets with a confidence level α and the ammunition cost of operations. The above-
mentioned two factors are defined as follows:

T (t)  
S W (t) 
 xi j (s)
f wr (X , ξ , α) = C V a Rα
t
vj · 1 − pi j (s, ξ ) (4)
j=1 s=t i=1


S 
T 
W
f wc (X t ) = ci j (s) · xi j (s) (5)
s=1 j=1 i=1

where f wr (X t , ξ , α) in Eq. (4) is the CVaR value of missing targets at stage t with a confidence
level α. f wc in Eq. (5) is the overall ammunition consumption through all stages. X t =
[X t , X t+1 , . . . , X S ] with X t = [xi j (t)]W ×T is the decision matrix at stage t, and xi j (t) is a
binary decision variable taking a value of one (i.e., xi j (t) = 1) if weapon i is assigned to target
j at stage t, or zero (i.e., xi j (t) = 0) otherwise. W (t) and T (t) represent the remaining number
of the weapons and targets at stage t, respectively (W (1) = W , T (1) = T ). v j means the
threat value of target j. pi j (s, ξ ) denotes the uncertain kill probability that weapon i destroys
target j at stage s. It depends on a random parameter ξ which relates to the battle situation,
weather conditions, and so on. Different distributions of the uncertain kill probability pi j (s, ξ )
can be obtained, for example, by utilizing the historical observations of weapons’ efficiency
in different environments, or using simulated data, experts opinions, etc. Note that different
probability distributions of pi j (s, ξ ) represent different uncertain situations. u i j (s) denotes
the ammunition consumption when weapon i is allocated to target j at stage s. βi represents
the unit economic cost of the ammunition that weapon i consumes. If all weapons are the
same, βi is assumed to be constant (e.g., one unit in this paper).
In addition, there are some practical constraints on the usage of ammunitions as shown in
the following:
W
xi j (t) ≤ m j ∀ j ∈ I j , ∀t ∈ It (6)
i=1
T
xi j (t) ≤ n i ∀i ∈ Ii , ∀t ∈ It (7)
j=1

T 
S
xi j (t) ≤ Ni ∀i ∈ Ii (8)
j=1 t=1
xi j (t) ≤ f i j (t) ∀i ∈ Ii , ∀ j ∈ I j , ∀t ∈ It (9)

Ii = {1, 2, . . . , W }; I j = {1, 2, . . . , T }; It = {1, 2, . . . , S}.

Constraints (6) mean at each stage at most m j ammunitions can be used to destroy target
j, which limits the ammunition cost for each target at each stage. The value of m j usually

123
 Annals of Operations Research

depends on the performance of available weapons and actical preferences of commanders.

Constraints (7) reflect the capability of weapons of firing at multiple targets at the same
time. To be more precise, weapon i can fire at most n i targets at the same time. Actually,
most weapons can fire only one target, while for special cases, e.g., artillery-based defense
systems, the value of n i may be larger than two. In these cases, these weapons can be regarded
as n i independent weapons, so it is assumed that n i = 1, ∀i ∈ Ii . Constraints (8) indicate
the amount of available ammunitions of weapon i. Constraints (9) are engagement feasibility
constraints which are important features of MWTA against SWTA, since the MWTA problem
considers the influence of time windows on the engagement feasibility of weapons. If weapon
i cannot shoot target j at stage s for various reasons (e.g., target j being beyond the range
of weapon i), then f i j (t) = 0; otherwise f i j (t) = 1.
Based on above, the formulation of the bi-objective uncertain MWTA problem is given
as: min [ f wr (X t , ξ , α), f wc (X t )], s.t. (6)–(9).

4 Linearization of the RAP and the MWTA problem

In this section, we linearize the RAP and approximate the MWTA problem with integer
programming problems. Thus, a true Pareto front and a lower bound Pareto front can be
obtained for the RAP and MWTA problem, respectively.

4.1 Linearization of the RAP

Obviously, Eq. (1) can be easily converted into a linear function as described in the following:

m 
ni 
 
f srL (X , ξ , α) = C V a Rα xi j · ln 1 − ri j (ξ ) (10)
i=1 j=1

What’s more, if a decision-maker can express his/her preference by giving a threshold of

the overall cost of a system (denoted as c1 ), the second component of the bi-criteria objective
function can be transformed into a constraint as following:

m 
ni
ci j xi j ≤ c1 (11)
i=1 j=1

Based on above, the original bi-objective RAP can be transformed into a series of single
objective problems by converting the objective regarding to the system cost into an addi-
tional constraint. What’s more, the nonlinear objective regarding to the risk of failure of a
system, i.e., f sr (X t , ξ , α), can be replaced by the linear function f srL (X t , ξ , α). We attempt
to give a true Pareto front of the original nonlinear bi-objective problem efficiently by solv-
ing a series of the following single objective linear problem: min f srL (X t , ξ , α), s.t. (3) and
(11).

4.2 Linear approximation of the MWTA problem

 S W xi j (s)
In Eq. (4), let s j = s=1 i=1 (1 − pi j (s, ξ )) and take logarithms on both sides, then
S W
we can obtain ln(s j ) = s=1 i=1 ln(1 − pi j (s, ξ )) · xi j (s). Let y j = − ln(s j ) and observe
 S W xi j (s)
the fact that e−y j = s=1 i=1 (1 − pi j (s, ξ )) . By introducing the term y j in Eq. (4),

123
Annals of Operations Research

we get the following formulation: f wr (X t , ξ , α) = C V a Rα T −y j (Ahuja et al.

j=1 v j · e
2007).
We consider v j · e−y j at a series of values {y 1j , y 2j , . . . , y j } and draw tangents of v j · e−y j
p

at these values. Let F j ( p, y kj )(k = 1, 2, . . . , p) denote the upper envelope of these tangents.
It is easy to see that the function F j ( p, y kj ) approximates v j · e−y j from below, and F j ( p, y kj )
k

provides a lower bound on v j · e−y j for every y kj (k = 1, 2, . . . , p). Given above, we can
k

know that the function F j ( p, y kj ) gives a lower bound on the optimal objective function value
for the MWTA problem. Specifically, the process of calculating the lower bound function
L (X t , ξ , α) can be summarized as follows:
f wr
Step 1 First we estimate the possible range of y j ( j = 1, 2, . . . , T ), denoted as
[y min
j , yj
max ], according to data of test instances. Then, each range can be divided into p − 1
p−1 p
segments, i.e., y min
j = y 1j < y 2j < · · · < y j < y j = y max
j , where p denotes the number
of division points.
Step 2 The piecewise linear lower bound function can be obtained as following:

T
 S W
 
−y k−1
L (X t , ξ , α)
f wr = C V a Rα v j · max θk · − ln(1 − pi j ) · xi j − y k−1
j +e j
j=1 k=2,..., p s=1 i=1
p−1 p
y min
j = y 1j < y 2j < · · · < yj < yj = j , j = 1, . . . , T
y max (12)
s.t. −y k −y k−1
e j −e j
θk = , k = 2, . . . , p
y j −y k−1
k
j

Similar to the previous subsection, the overall cost of ammunitions can be transformed
into a constraint by using a threshold of the cost (denoted as c2 ), as shown in the following:


S 
T 
W
ci j (s)xi j (s) ≤ c2 (13)
s=1 j=1 i=1

Based on above, the original bi-objective MWTA problem can be transformed into a
series of single objective problems by converting the objective regarding to the ammuni-
tion cost into an additional constraint. What’s more, the nonlinear objective regarding to
the risk of missing targets, i.e., f wr (X t , ξ , α), can be bounded by the linear lower bound
L (X t , ξ , α). Thus we attempt to give a lower bound of the original nonlinear bi-
function f wr
objective problem efficiently by solving a series of following linear lower bound problems:
L (X t , ξ , α), s.t. (6)–(9), and (13).
min f wr

5 Improved decomposition-based multi-objective evolutionary

algorithms

Among various heuristics algorithms, the decomposition-based multi-objective evolutionary

algorithms have gained much attention. This paper adopts two state-of-the-art decomposition-
based multi-objective evolutionary algorithms (i.e., MOEA/D-AWA and DMOEA-εC) to deal
with the RAP and the MWTA problem. This section presents a brief description of MOEA/D-
AWA and DMOEA-εC at first and then proposes two matching schemes for MOEA/D-AWA
in order to have a fair comparison with DMOEA-εC.

123
 Annals of Operations Research

Algorithm 1 Framework of MOEA/D-AWA

1: Input: An MOP and related parameters.
2: Output: An external archive population E P.
3: Initialize N weight vectors by applying the WS-transformation on the original evenly spread weight vectors
in MOEA/D; randomly initialize the evolving population P = {x1 , . . . , xN } and set FVi = F(xi ); extract
non-dominated individuals from P and denote the set of them as E P; initialize z∗ = (z 1∗ , ..., z m
∗ ) by setting
∗ 1 N −7
z i = min{ f i (x ), ..., f i (x )} − 10 ; set gen = 0, n = N .
4: for i = 1 to N do
5: Set the neighborhood of the ith subproblem B(i).
6: π i = 1.
7: end for
8: while n ≤ N F E do
9: for i ∈ I do
B(i), if rand < δ
10: P=
{1, 2, ..., N }, otherwise
11: Reproduction: select parent individuals from P randomly and apply certain reproduction operator
to generate a new solution y.
12: n = n + 1.
13: Repair: if y is infeasible, repair it.
14: Update the approximated ideal point z∗ .
15: Compare y with neighboring solutions of the subproblem i and update nr neighboring solutions by
using the aggregated objective value of each subproblem.
16: Update the external archive E P and prune it by using the crowding distance-based approach.
17: end for
18: if gen ≤ rate_evol ∗ G max and gen is a multiple of wag then
19: Delete num overcrowded subproblems.
20: Add num new subproblems into the sparse regions.
21: for i = 1 to N do
22: Find the T closest weights to ith subproblem and build new B(i).
23: end for
24: end if
25: gen = gen + 1.
26: end while

5.1 Two decomposition-based multi-objective evolutionary algorithms

Numerous methods including exact methods and intelligent optimization methods have been
applied to solve resource allocation problems. Different exact approaches such as Lagrangian
relaxation and branch-and-bound methods have been developed in the literature to solve less
complicated problems (Ahuja et al. 2007; Xin et al. 2011). Due to the high complexity
induced by multiple objectives1 and uncertainties,2 exact methods cannot be employed to
find optimal solutions for the model at hand in an acceptable time. As a result, two state-of-
the-art decomposition-based multi-objective evolutionary algorithms, including MOEA/D-
AWA (Qi et al. 2014) and DMOEA-εC (Chen et al. 2017), are employed in this paper.
Additionally, MOEA/D-AWA is improved by adding two matching schemes at different
stages of optimization.
Decomposition is an efficient and prevailing strategy for solving multi-objective optimiza-
tion problems (MOPs). Its success was firstly witnessed by the multi-objective evolutionary

1 Since the single objective RAP and MWTA problem are both NP-hard (Chern 1992; Lloyd and Witsenhausen
1986), their multi-objective formulations can only be harder to solve. This implies that bi-objective RAPs and
MWTA problems are also NP-hard.
2 For uncertain multi-objective optimization problem, multiple repeated function evaluations of a solution
usually get different function values under different uncertain scenarios. Thus, it is difficult to definitely
determine the quality of two solutions, which affects the ability of algorithms to find the optimum.

123
Annals of Operations Research

Algorithm 2 Framework of DMOEA-εC

1: Input: An MOP, related parameters.
2: Output: An external archive population E P.
3: Initialize N evenly spread upper bound vectors; randomly initialize the evolving population P =
{x1 , ..., xN } and set FVi = F(xi ); extract nondominated individuals from P and denote the set of them as
E P; initialize z∗ and znad ; set gen = 0, n = N .
4: Use the solution-to-subproblem matching scheme to match solutions with subproblems.
5: for i = 1 to N do
6: Set the neighborhood of the ith subproblem B(i).
7: π i = 1.
8: end for
9: while n ≤ N F E do
10: if gen is a multiple of I Nm then
11: Alternate the main objective.
12: Use the solution-to-subproblem matching scheme to match solutions with subproblems.
13: end if
14: for i ∈ Ido
B(i), if rand < δ
15: P=
{1, 2, ..., N }, otherwise
16: Reproduction: select parent individuals from P randomly and apply certain reproduction operator
to generate a new solution y.
17: n = n + 1.
18: Repair: if y is infeasible, repair it.
19: Update the approximated ideal point z∗ .
20: Use the subproblem-to-solution matching scheme to find a subproblem k for y.
21: Compare y with neighboring solutions of the subproblem k and nr neighboring solutions by using
the feasibility rule.
22: Update the external archive E P and prune it by using the crowding distance-based approach.
23: Update the approximated nadir point znad .
24: end for
25: gen = gen + 1.
26: end while

algorithm based on decomposition (MOEA/D) (Zhang and Li 2007) and its variants.
MOEA/D decomposes an MOP into a set of scalar subproblems by using aggregated func-
tions and uniformly distributed weight vectors and optimizes them concurrently. Commonly
used aggregated functions used in MOEA/D include the weighted sum method, the Cheby-
shev method, and the PBI method. Generally, the uniformity of weight vectors in MOEA/D
can ensure the diversity of the optimal solutions based on the assumption that the Pareto front
(PF) is close to the hyper-plane in the objective space. However, the basic assumption might
be violated in the case that the PF of the target MOP is complex. Therefore, some studies
have been done to refine weight vectors in MOEA/D (Jiang et al. 2011; Ma et al. 2014; Qi
et al. 2014). MOEA/D-AWA Qi et al. (2014) is one of such research, in which an adaptive
weight vector adjustment (AWA) strategy is introduced to obtain the uniformly distributed
PF of the target MOP. It is natural to design an AWA strategy to regulate the distribution
of weight vectors of subproblems periodically by removing subproblems from the crowded
regions and adding new ones into the sparse regions, obtaining uniformly distributed non-
dominated solutions consequently. Firstly, the AWA strategy removes subproblems located in
the crowded regions whose crowded degrees are measured by the vicinity distance. Next, the
elite population is deployed as a guidance to add new subproblems into the real sparse regions
of the complex PF rather than the discontinuous parts which are pseudo sparse regions. If an
elite individual is located in a sparse region of the evolving population, it will be reused in the
evolving population and a new weight vector will be generated and added to the subproblem
set.

123
 Annals of Operations Research

Table 1 Summary of notations used in the description of MOEA/D-AWA and DMOEA-εC

m The number of objective

N The population size
δ Probability of selecting mate solutions from its neighborhood
T Neighborhood size
nr Maximum number of replacement
N FE Maximum number of function evaluations
G max Maximum number of generations
rate_evol The ratio of iteration times to evolve with only MOEA/D
wag The iteration interval of utilizing the adaptive weight vector adjustment strategy
num Maximal number of subproblems needed to be adjusted
I Nm The iteration interval of alternating the main objective function
z∗ Ideal point
znad Nadir point
rand A randomly distributed value in the interval [0, 1]

Algorithm 1 gives a brief description of MOEA/D-AWA. The notations used in the

MOEA/D-AWA are given in Table 1. Readers can refer to Zhang and Li (2007) and Qi
et al. (2014) for a detailed description of MOEA/D and MOEA/D-AWA.
Apart from above-mentioned aggregation methods, the ε-constraint method is also a basic
generation method in mathematical programming (Miettinen 1999) and is often used as an
element of more developed methods. DMOEA-εC takes inspiration from the ε-constraint
method and is a newly proposed multi-objective solver in recent research (Chen et al. 2017).
The ε-constraint method selects one of the objectives as the main objective, while transform-
ing the other non-main objectives to constraints and associating each non-main objective
with an upper bound coefficient. DMOEA-εC explicitly decomposes an MOP into a series of
scalar constrained optimization subproblems by selecting one of the objectives as the main
objective function and associating each subproblem with an upper bound vector. These sub-
problems are optimized collaboratively by an evolutionary algorithm based on the feasibility
rule (Deb 2000). Besides, each subproblem is optimized using information only from its
neighboring subproblems.
Under the ε-constraint framework, DMOEA-εC tends to retain feasible solutions for each
subproblem, which will be bad for the optimization of the main objective function. A main
objective alternation strategy is proposed to tackle this problem periodically. After the main
objective alternation strategy is utilized, a solution which is good for the current subproblem
may not perform well since the objective function of this subproblem has been changed.
Thus a solution-to-subproblem matching scheme is designed to place the nearest solution
to each subproblem. It uses the distance value between a solution and a subproblem as the
criterion and is utilized after the main objective alternation strategy. Additionally, when a
new solution is generated, it may perform badly for the current subproblem but perform
well for another subproblem. In order to avoid wasting potentially useful solutions and make
best use of them, the subproblem-to-solution matching scheme which uses the constraint
violation value as the criterion is proposed to find a subproblem with the minimum constraint
violation value for the new solution. The two matching schemes strike a balance between
convergence and diversity. DMOEA-εC has been compared with six state-of-the-art multi-
objective evolutionary algorithms on both continuous and 0/1 knapsack benchmark problems

123
Annals of Operations Research

and has shown its advantages over competitive approaches. Given parameters presented in
Table 1, DMOEA-εC is summarized in Algorithm 2. Readers can refer to Chen et al. (2017)
for a detailed description of DMOEA-εC.
As stated in Chen et al. (2017), the superiority of DMOEA-εC can be partly attributed
to the effectivenesses of two matching schemes which are capable of balancing convergence
and diversity at different stages of evolution. Numerical results on analyzing algorithmic
behaviors of DMOEA-εC have confirmed this statement. Then are the two matching schemes
applicable to MOEA/D-AWA which is also decomposition-based? If so, can two matching
schemes enhance the performance of MOEA/D-AWA? In order to answer these questions,
we design two matching schemes for MOEA/D-AWA and examine their performance.

5.2 Two matching schemes

Although MOEA/D-AWA and DMOEA-εC are different algorithms, they share the similar
concept of decomposition. In MOEA/D-AWA, there are two types of distance, i.e., d1 andd2 .
 ∗ 
(z −F(x))T w
Suppose L is a line passing through the ideal point z∗ with a direction w, d1 = w is
 
∗  ∗ w 
the distance between z and the projection of F(x) on the line L. d2 = F(x) − (z + d1 w )
is the perpendicular distance from F(x) to the line L. d1 is used to evaluate the convergence
of x toward the PF and d2 is a kind of measure for the diversity of a population.
Inspired by DMOEA-εC, firstly d2 can be adopted as the matching criterion for the
solution-to-subproblem matching scheme to find the solution with minimum perpendicu-
lar distance value for each subproblem. The solution-to-subproblem matching scheme is
used periodically and it can place the nearest solution to each subproblem at a large degree,
which is beneficial to diversity. The subproblem-to-solution matching scheme utilizes d1 to
match the subproblem with the smallest d1 value for a newly generated solution in order to
make the following replacement more effective. Additionally, the subproblem-to-solution
matching scheme is adopted after a new solution is generated, which is good for con-
vergence. Two matching schemes are expected to force solutions to stay close to certain
weight vector and explicitly maintain the desired distribution of solutions in the evolution-
ary process, which leads to a balance between convergence and diversity in multi-objective
optimization. MOEA/D-AWA with the above-mentioned two matching schemes is denoted
as MOEA/D-AWA-M and will be compared with MOEA/D-AWA to verify the effectiveness
of two matching schemes.
In addition, the genetic algorithm is adopted as the search engine in MOEA/D-AWA,
MOEA/D-AWA-M, and DMOEA-εC. In this case, two-point crossover, one-point mutation,
and random repair mechanism are used for both bi-objective RAP and MWTA problems.

6 Computational experiments

This section is devoted to the experimental design for investigating the effectiveness of
two matching schemes designed for MOEA/D-AWA and the performance of two multi-
objective solvers on solving uncertain RAP and MWTA instances. First, descriptions of the
test instances of RAP and MWTA are given. Then parameter tunings for both RAP and
MWTA instances are conducted. Finally, experimental results are illustrated.

123
 Annals of Operations Research

Table 2 Data for the RAP benchmark case 1 (RAP1)

Sub-system i Component type j
1 2 3 4 5
R C R C R C R C R C

1 0.94 9 0.91 6 0.89 6 0.75 3 0.72 2

2 0.97 12 0.96 3 0.70 2 0.66 2 – –
3 0.96 10 0.86 6 0.72 4 0.71 4 0.67 2

Table 3 Data for the RAP Sub-system i Component type j

benchmark case 2 (RAP2)
1 2 3 4
R C R C R C R C

1 0.90 1 0.93 1 0.91 2 0.95 2

2 0.95 2 0.94 1 0.93 1 – –
3 0.85 2 0.90 3 0.87 1 0.92 4
4 0.83 3 0.87 4 0.85 5 – –
5 0.94 2 0.93 2 0.95 3 – –
6 0.99 2 0.98 3 0.97 2 0.96 2
7 0.91 4 0.92 4 0.94 5 – –
8 0.81 3 0.90 5 0.91 6 – –
9 0.97 2 0.99 3 0.96 6 – –
10 0.83 4 0.85 4 0.90 5 – –
11 0.94 3 0.95 4 0.96 5 – –
12 0.79 2 0.82 3 0.85 4 0.90 5
13 0.98 2 0.99 3 0.97 2 – –
14 0.90 4 0.92 4 0.95 5 0.99 6

6.1 Test instances

As to RAPs, two well-known benchmark cases which consist of 3 sub-systems with 5

components and 14 sub-systems with 4 components are considered (Taboada et al. 2007;
Khalili-Damghani and Amiri 2012; Li et al. 2009). The two benchmark cases are denoted as
RAP1 and RAP2, respectively. The maximum number of components which can be paral-
leled for each sub-system n max is set as n max =[7 7 7] and n max =[ 6 5 6 6 6 6 5 6 6 6 5 6 6 5]
for RAP1 and RAP2, respectively. Tables 2 and 3 present the information concerning RAP1
and RAP2.
For MWTA problems, since the actual data is difficult to obtain, three different-scaled
instances, i.e. small, medium, and large-scaled instances, are randomly generated. The
numbers of weapons/targets/stages in small, medium, and large-scaled instances are 3/5/3,
20/12/5, and 50/50/8, respectively (Li et al. 2015, 2016a). The value vector of targets
comes from Cai (2010). For each instance, each element of the deterministic kill proba-
bility and ammunition consumption matrices at stage s, namely P(s) = [ pi j (s)]W ×T and
U (s) = [u i j (s)]W ×T , is randomly generated within a given range related to the problem
scale. Parameters in constraints including m i , n i , and Ni are deterministic.

123
Annals of Operations Research

6 0 0

0 0 1

0 2 3 5 1 4 6 3

0 4 0 Genetic locus/ weapon 1 2 3 4 5

1 0 2
Genetic value/ target 1 2 3 4 5 6

(a) (b)
Fig. 2 Examples of the encoding scheme for a the RAP problem (3 sub-systems with 5 components) and b
the MWTA problem (W = 5, T = 6, S = 1)

As to uncertain RAPs and MWTA problems, in order to generate uncertain instances

based on the deterministic instances, a common probability distribution that the uncertain
completion probability may follow can be applied over the deterministic data. Specifically,
each uncertain completion probability, namely pr obi j (ξ ),3 is sampled from the following
uniform distribution:

pr obi j (ξ ) ∼ U ((1 − γ ) · pr obi j , (1 + γ ) · pr obi j ) (14)

where the parameter γ is used to tune the degree of the deviation of the completion probability.
In any case, the central tendency of the distribution always corresponds to a deterministic
completion probability value pr obi j . In the following, γ is set as 0.2. As to CVaR, α stands
for the confidence level and is set as α = 0.9.

6.2 Encoding

An appropriate solution encoding scheme is crucial for an algorithm when solving opti-
mization problems. For both RAPs and MWTA problems, the integer encoding is adopted.
Every solution of the RAP is represented by a matrix, and each element of the matrix is the
number of components used in each sub-system. As to the MWTA problem, each solution is
represented by a vector whose length is the number of weapons. Each weapon is regarded as
a genetic locus to form a chromosome, and the genic value of each genetic locus indicates
the number of the target to which the weapon is assigned. Such an encoding method can
guarantee that every solution satisfies the constraint (7) naturally. As to the other constraints,
it will be checked whether each new solution satisfies these constraints or not. If not, this
solution should be repaired according to a random repair mechanism. Figure 2 illustrates
examples of the encoding scheme for the RAP problem (3 sub-systems with 5 components)
and the MWTA problem (W = 5, T = 6, S = 1).

6.3 Performance metrics

Two commonly used performance metrics, i.e., inverted generational distance (IGD) Zhou
et al. (2005) and hypervolume (HV ) Zitzler and Thiele (1999) are employed to evaluate the
performance of all compared algorithms.

3 pr ob (ξ ) equals to r (ξ ) and p (s, ξ ) for RAPs and MWTA problems, respectively.

ij ij ij

123
 Annals of Operations Research

The IGD metric measures the average distance from a set of uniformly distributed Pareto
optimal points over the PF P ∗ to the approximation set P. It can be formulated as:
d(x ∗ , P)
x ∗ ∈P ∗
I G D(P ∗ , P) =
|P ∗ |
where d(x ∗ , P) is the minimal Euclidean distance between x ∗ and any point in P, and |P ∗ |
is the cardinality of P ∗ . If |P ∗ | is large enough to represent the PF very well, I G D(P ∗ , P)
could measure both diversity and convergence of P in a sense. A smaller IGD value indicates
a better P.
The HV metric measures the size of the objective space dominated by the solutions in P
and bounded by the reference point r. It is defined as:
 

H V (P, r) = V O L [ f 1 (x), r1 ] × · · · × [ f m (x), rm ]
x∈P

where r = (r1 , . . . , rm ) is a reference point in the objective space dominated by any Pareto
optimal point, and V O L(·) is the Lebesgue measure. A larger HV value implies a better P.

6.4 Parameter tuning

Since different levels of the parameters have effects on the quality of solutions obtained
by certain algorithm, the Taguchi procedure Montgomery (2005); Roy (2010) has been fre-
quently used to tune parameters of algorithms. The Taguchi procedure is applied in the field
of design-of-experiments (DOE) and is regarded as an efficient alternative for full factorial
experiments. This procedure uses a special orthogonal table for setting a set of experiments
to investigate a group of parameters. The preferred parameter settings are then determined
through analysis of the signal-to-noise (S N ) ratio where factor levels that maximize the
appropriate S N ratio are optimal. The S N ratio is defined as:
 n 
1
S N = −10 × log yi (15)
n
i=1

where yi and n are the response value and the number of orthogonal arrays in the orthogonal
table, respectively. In MOEAs, two main goals (convergence and diversity) are considered
simultaneously. As mentioned above, both IGD and HV are suitable metrics. However,
Taguchi method only deals with one response function. Therefore, a combination of the
performance measures should be defined. In this study, an integrated metric, defined as
IGD/HV, will act as the response variable of the Taguchi method.
With the purpose of calculating the IGD metric value, the true Pareto front of RAP instances
and the lower bound Pareto front of MWTA instances generated through the linearized
formation described in Sect. 3 will be chosen as P ∗ . The reference points for each instance
used in calculations of the HV metric values are set as 1.1 times the true nadir point based
on P ∗ .
Since the processes of the Taguchi procedure are similar across different approaches, we
only display detailed analyses process of the MOEA/D-AWA. To be specific, the first stage
of the Taguchi method is to determine the factors and their levels. The common parameters
that MOEA/D-AWA, MOEA/D-AWA-M and DMOEA-εC share are the population size (N ),
the number of iterations (N um), the crossover rate (C R), and the mutation rate (M R). For
a fair comparison, the number of function evaluations (NFE = N · N um) is set the same

123
Annals of Operations Research

Table 4 Algorithm parameters and their levels for RAP and MWTA instances
Parameters Factor level
1 2 3

RAP1 (N , N um) (50, 400) (100, 200) (200, 100)

RAP2 (N , N um) (50, 600) (100,300) (300, 100)
Small-scaled (N , N um) (50, 400) (100, 200) (200, 100)
Medium-scaled (N , N um) (80, 500) (100, 400) (200, 200)
Large-scaled (N , N um) (200, 500) (100, 1000) (500, 200)
CR 0.5 0.7 0.9
MR 0.01 0.05 0.1

Table 5 Orthogonal table for RAP and MWTA instances of MOEA/D-AWA

Experiment Factors Response value
number (N , N um) CR MR RAP1 RAP2 Small-scaled Medium-scaled Large-scaled

1 1 1 1 9.1514 3.6937 2.0622 6.6456E−03 1.0213E+02

2 1 2 2 9.4234 4.7038 3.0797 6.1089E−03 1.0848E+02
3 1 3 3 9.6815 3.1249 2.5660 6.3931E−03 1.3519E+02
4 2 1 2 9.2761 3.5207 2.2045 6.1269E−03 9.9797E+01
5 2 2 3 8.4553 3.4335 2.2145 6.1620E−03 9.5280E+01
6 2 3 1 7.9091 3.9401 1.7004 6.1975E−03 6.2556E+01
7 3 1 3 9.6724 2.9148 2.2979 6.7583E−03 1.0998E+02
8 3 2 1 9.1355 3.8365 1.9409 6.3235E−03 1.1252E+02
9 3 3 2 9.5272 4.5699 2.4670 6.4101E−03 1.3952E+02

for each instance. Thus, the factors to be tuned include: the combination of the population
size and the number of iterations (N , N um), the crossover rate C R, and the mutation rate
M R. Different levels of these factors are shown in Table 4. Since three factors with three
levels exist, the proper orthogonal table is L 9 (33 ). The MOEA/D-AWA is applied to all
combinations of factors, and response values are calculated. The orthogonal table of these
designs along with the response values for RAP and MWTA instances of MOEA/D-AWA is
shown in Table 5. Readers can refer to Montgomery (2005); Roy (2010) for more details on
the Taguchi approach.
According to the orthogonal table, main effect plots of S N ratio for RAP and MWTA
instances of MOEA/D-AWA are illustrated in Figs. 3 and 4. Then, we figure out the change
of response values and analyze the significance of the rank of each parameter and obtain the
response table as shown in Table 6. It can be seen that: (N , N um) is the parameter that has
the most significant impact on the algorithm for most RAP and MWTA instances. According
to the response table, the best combinations of the parameter values for each instance are
determined. Similar processes can be applied to MOEA/D-AWA-M and DMOEA-εC. The
best combination of parameters for RAP and MWTA instances of all three approaches are
listed in Table 7.
In addition to these common parameters, the remaining parameters, including the neigh-
borhood size T , the maximal number of replacement nr , the maximal number of adjusted
subproblems num, and the iteration interval of utilizing the dynamic resource allocation strat-

123
 Annals of Operations Research

Fig. 3 Main effect plots for RAP instances of MOEA/D-AWA

egy and performing the solution-to-subproblem matching procedure I Nm , are also shown
in Table 7. Besides, the probability of selecting mate solutions from neighborhood is set as
δ = 0.9, the ratio of the iterations to evolve with only MOEA/D is set as rate_evol = 0.7
Qi et al. (2014), and the size of the external population is set as 2N for all test instances.

6.5 Experimental results

This section performs experiments to examine effects of the two matching schemes proposed
for MOEA/D-AWA and compare performance of two multi-objective approaches on solving
RAP and MWTA instances. For this part of experiments, the above-mentioned performance
metrics, i.e., IGD and HV, are employed to evaluate the performance of compared algorithms.
As mentioned above, since experimental results have confirmed that the performance of
DMOEA-εC is enhanced because of the introduction of two matching schemes, two similar
matching schemes are proposed and embedded in MOEA/D-AWA. Therefore, effects of the
two proposed matching schemes should be examined on all test instances by comparing the
performance of MOEA/D-AWA with MOEA/D-AWA-M. Besides, numerical experiments
are also conducted to demonstrate the performance of DMOEA-εC on solving RAP and
MWTA instances.
The means and standard deviations of IGD and HV metric values over 30 runs of MOEA/D-
AWA, MOEA/D-AWA-M and DMOEA-εC on RAP and MWTA instances are shown in
Tables 8 and 9, respectively. The numbers in parentheses are the standard deviations. Besides,
the mean HV (IGD) values for each instance are sorted in descending (ascending) order, and
the numbers in the square brackets are their ranks. The Wilcoxon’s rank sum test at a 5%
significance level is conducted to test the significance of differences between DMOEA-εC
and the other algorithms. †, §, and ≈ indicate the performance of the comparison algorithm
is better than, worse than, and similar to that of DMOEA-εC according to the Wilcoxon’s
rank sum test, respectively. The bold data in each table are the best mean metric values for
each instance. The last row of each table presents the mean rank value of each algorithm over
all test instances.
As can be seen in Table 8, in terms of IGD metric values, MOEA/D-AWA-M shows obvi-
ous advantages over MOEA/D-AWA on the majority of test instances. Similar results can be
obtained in terms of HV values as shown in Table 9. This observation demonstrates that two
proposed matching schemes are helpful for improving the performance of MOEA/D-AWA on
solving RAP and MWTA instances. Effects of the two matching schemes in MOEA/D-AWA
are similar to that in DMOEA-εC. That is, the solution-to-subproblem matching scheme

123
 Annals of Operations Research

Fig. 4 Main effect plots for MWTA instances of MOEA/D-AWA

123
 Annals of Operations Research

Table 6 Response table for RAP and MWTA instances of MOEA/D-AWA

Level (N , N um) CR MR

RAP1 1 9.419 9.367 8.732

2 8.547 9.005 9.409
3 9.445 9.039 9.270
Delta. (Rank) 0.898 (1) 0.362 (3) 0.677 (2)
RAP2 1 3.204 3.245 3.311
2 3.166 3.243 3.227
3 3.328 3.210 3.161
Delta. (Rank) 0.162 (1) 0.035 (3) 0.150 (2)
Small-scaled 1 2.569 2.188 1.901
2 2.040 2.412 2.584
3 2.235 2.244 2.359
Delta. (Rank) 0.529 (2) 0.224 (3) 0.683 (1)
Medium-scaled 1 6.383E−03 6.510E−03 6.389E−03
2 6.162E−03 6.198E−03 6.215E−03
3 6.497E−03 6.334E−03 6.438E−03
Delta. (Rank) 0.000335 (1) 0.000312 (2) 0.000223 (3)
Large-scaled 1 115.27 103.97 92.40
2 85.88 105.43 115.93
3 120.67 112.42 113.48
Delta. (Rank) 34.80 (1) 8.45 (3) 23.53 (2)

Table 7 The best combination of parameters for RAP and MWTA instances of three algorithms
Instances Approaches (N , N um) CR MR T nr num I Nm

RAP1 MOEA/D-AWA (100,200) 0.7 0.01 5 1 1 –

MOEA/D-AWA-M (100,200) 0.7 0.1 5 1 1 20
DMOEA-εC (100,200) 0.7 0.1 5 1 – 20
RAP2 MOEA/D-AWA (100,300) 0.5 0.05 8 3 3 –
MOEA/D-AWA-M (100,300) 0.7 0.1 8 3 3 30
DMOEA-εC (100,300) 0.9 0.1 8 3 – 30
Small-scaled MOEA/D-AWA (100,200) 0.5 0.01 3 1 1 –
MOEA/D-AWA-M (100,200) 0.5 0.01 3 1 1 40
DMOEA-εC (100,200) 0.5 0.01 3 1 – 40
Medium-scaled MOEA/D-AWA (100,400) 0.7 0.05 10 3 3 –
MOEA/D-AWA-M (100,400) 0.5 0.1 10 3 3 10
DMOEA-εC (100,400) 0.7 0.05 10 3 – 10
Large-scaled MOEA/D-AWA (100,1000) 0.5 0.01 15 5 5 –
MOEA/D-AWA-M (100,1000) 0.5 0.01 15 5 5 20
DMOEA-εC (100,1000) 0.9 0.01 15 5 – 20

123
 Annals of Operations Research

Table 8 Mean IGD metric values of MOEA/D-AWA and DMOEA-εC and their variants about the two matching schemes and the hierarchical comparison strategy over 30
independent runs on RAP and MWTA instances with the noise strength γ = 0.2 and the confidence value α = 0.9
MOEA/D-AWA MOEA/D-AWA-M DMOEA-εC

RAP1 8.8691E−00(1.2312E−02)§ [3] 8.7325E−00(1.1307E−02)≈ [2] 8.6655E−00(3.3665E−02)[1]

RAP2 2.6850E−00(8.8345E−03)§ [3] 2.5753E−00(1.9516E−02)§ [2] 2.4990E−00(2.0992E−02)[1]
Small-scaled 1.4510E−00(4.9607E−01)§ [3] 1.3013E−00(4.8308E−01)≈ [1] 1.3076E−00(4.0791E−01)[2]
Medium-scaled 1.4245E+01(6.8510E−02)§ [2] 1.3230E+01(2.5467E−03)§ [3] 2.8587E−00(6.3086E−02)[1]
Large-scaled 3.7567E+01(1.6531E−01)§ [3] 3.1206E+01(1.9144E−01)§ [2] 2.4253E+01(1.0463E−01)[1]
Mean rank 2.75 2.00 1.25

123
123
Table 9 Mean HV metric values of MOEA/D-AWA and DMOEA-εC and their variants about the two matching schemes and the hierarchical comparison strategy over 30
independent runs on RAP and MWTA instances with the noise strength γ = 0.2 and the confidence value α = 0.9
MOEA/D-AWA MOEA/D-AWA-M DMOEA-εC

RAP1 9.2501E−01(2.3135E−02)§ [3] 9.2311E−01(6.5411E−02)≈ [2] 9.3812E−01(2.5521E−02)[1]

RAP2 7.1106E−01(3.4008E−02)§ [3] 7.7913E−01(3.2662E−02)§ [2] 7.8221E−01(4.9568E−02)[1]
Small-scaled 4.3556E−01(3.0310E−03)§ [3] 4.5783E−01(1.2571E−03)§ [2] 4.7540E−01(7.8115E−04)[1]
Medium-scaled 2.1436E+03(2.3110E−01)§ [3] 2.2579E+03(6.7151E−02)§ [2] 2.5671E+03(2.5275E−01)[1]
Large-scaled 3.3680E−01(1.9591E−02)§ [3] 3.5078E−01(2.3849E−02)§ [2] 3.8771E−01(1.4577E−02)[1]
Mean rank 3.00 2.00 1.00
Annals of Operations Research
Annals of Operations Research

RAP1 RAP2
150 300
True PF True PF
MOEA/D-AWA-M MOEA/D-AWA-M
250

100 200
sc

sc
150
f

f
50 100

50

0 0
0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8

f sr f sr

Fig. 5 Final populations in the objective space with the minimum IGD metric value within 30 runs obtained
by MOEA/D-AWA-M and DMOEA-εC on RAP test instances

using d2 as matching criterion can place the nearest solution to each subproblem at a large
degree, which is beneficial to keep a diverse population. The subproblem-to-solution match-
ing scheme with d1 as the matching criterion is able to avoid wasting potentially useful
solutions and make best use of new solutions, and thus it is good for convergence. Therefore,
two matching schemes strike a balance between diversity and convergence.
As can be seen in Tables 8 and 9, in terms of IGD metric values, DMOEA-εC shows
significant advantage over MOEA/D-AWA-M on all test instances except for RAP1 and
small-scaled MWTA instances on which two algorithms show competitive performance. As
to HV, DMOEA-εC shows significant superiority over MOEA/D-AWA-M on the majority
of test instances. To be specific, DMOEA-εC performs better than MOEA/D-AWA-M on
RAP2, small-scaled, medium-scaled, and large-scaled MWTA instances. Two algorithms
perform similarly on the RAP1 instance. Tables 8 and 9 also present the overall rank of the
three algorithms, that is DMOEA-εC, MOEA/D-AWA-M, and MOEA/D-AWA, according
to the mean rank values.
Figures 5 and 6 show the distribution of the finall population in the objective space with the
minimum IGD value within 30 runs found by MOEA/D-AWA-M and DMOEA-εC on RAP
and MWTA instances, respectively. It can be seen from Figs. 5 and 6 that MOEA/D-AWA-M
and DMOEA-εC exhibit similar performance on RAP2 and the small-scaled MWTA instance.
For the RAP1 instance, MOEA/D-AWA-M and DMOEA-εC omit a small part of the true
PF. As to the medium-scaled and large-scaled MWTA instance, DMOEA-εC achieves better
convergence than MOEA/D-AWA-M. In this case, both MOEA/D-AWA-M and DMOEA-εC
cannot cover the approximated PF well. This phenomenon can be attributed to bad estimations
of the ideal point and the nadir point during the evolutionary process. In summary, Fig. 5
and 6 display that MOEA/D-AWA-M and DMOEA-εC can approximate the PF very well
for the majority of instances and DMOEA-εC exhibits better performance as compared with
MOEA/D-AWA-M.
In conclusion, the experimental results on MWTA and RAP instances indicate that the
superiority of DMOEA-εC is significant on RAP2, medium-scaled, and large-scaled MWTA
test instances, but not significant on RAP1 and small-scaled MWTA test instances. The main
difference between MOEA/D-AWA-M and DMOEA-εC lies in their algorithmic framework
and the superiority of DMOEA-εC against MOEA/D-AWA-M can be ascribed to the ε-
constraint framework.

123
123
Small-Scaled Medium-Scaled Large-Scaled
50 250 600
True PF True PF True PF
45 MOEA/D-AWA-M MOEA/D-AWA-M MOEA/D-AWA-M
500
40 200

35
400
30 150

wc
25 300

f wc
f wc
f
20 100
200
15

10 50
100
5

0 0 0
7.5 8 8.5 9 9.5 10 10.5 11 20 22 24 26 28 30 32 34 36 38 0 5 10 15 20 25 30 35
f f f
wr wr wr

Fig. 6 Final populations in the objective space with the minimum IGD metric value within 30 runs obtained by MOEA/D-AWA-M and DMOEA-εC on MWTA test instances
Annals of Operations Research
Annals of Operations Research

7 Conclusion and future work

The resource allocation problem is a fundamental combinatorial optimization problem stud-

ied in the operations research community. The bi-objective uncertain stochastic resource
allocation problem with the objectives of minimizing the risk of failure of completing activi-
ties and the resulting cost of resources is investigated in this paper. Mathematical formulations
of bi-objective uncertain RAPs and MWTA problems in which the CVaR measure is used
to control the risk induced by uncertainties are proposed. In order to determine referenced
Pareto fronts, a linearized formulation of the RAP and an approximated lower bound formu-
lation of the MWTA problem are presented according to problem-specific characteristics. A
true Pareto front and a lower bound Pareto front can be obtained for the RAP and MWTA
problem, respectively. Two state-of-the-art decomposition-based multi-objective evolution-
ary algorithms (i.e., MOEA/D-AWA and DMOEA-εC) are used to solve the formulated
problems. With the aim of having a fair comparison between MOEA/D-AWA and DMOEA-
εC, two matching schemes with different matching criteria inspired by DMOEA-εC are
proposed and embedded in MOEA/D-AWA.
Computational experiments have been performed on a set of the RAP and MWTA
instances. Numerical experiments have demonstrated that both MOEA/D-AWA-M and
DMOEA-εC are efficient ways of solving the bi-objective uncertain stochastic resource
allocation problem and DMOEA-εC shows significant better performance than MOEA/D-
AWA-M on RAP2, medium-scaled, and large-scaled MWTA test instances. Besidies,
DMOEA-εC and MOEA/D-AWA-M performs similarly on RAP1 and small-scaled MWTA
test instances. The superiority of DMOEA-εC can be ascribed to the ε-constraint framework.
Future research work includes investigating other types of uncertainties, adopting alter-
native methods to handle uncertainties, and embedding problem-specific knowledge in
multi-objective evolutionary algorithms to further improve their performance.

References
Ahuja, R. K., Kumar, A., Jha, K. C., & Orlin, J. B. (2007). Exact and heuristic algorithms for the weapon-target
assignment problem. Operations Research, 55(6), 1136–1146.
Blodgett, D. E., Gendreau, M., & Potvin, J. Y. (2003). A Tabu search heuristic for resource management in
naval warfare. Journal of Heuristics, 9(2), 145–169.
Braford, J. C.: Determination of optimal assignment of a weapon system to several targets,. Tech. rep., Vought
Aeronautics, Dallas, Texas (1961, AEREITM-9).
Buche, D., Stoll, P., Dornberger, R., & Koumoutsakos, P. (2002). Multiobjective evolutionary algorithm for
the optimization of noisy combustion processes. IEEE Transactions on Systems Man and Cybernetics:
Part C, 32(4), 460–473.
Cai, H. P. (2010). Study on firepower optimal distribution of artillery group based on NSGA-II. Ph.D. thesis,
Changsha, Hunan, P. R. China: National University of Defense Technology.
Cai, H., Liu, J., Chen, Y., & Wang, H. (2006). Survey of the research on dynamic weapon-target assignment
problem. Journal of Systems Engineering and Electronics, 17(3), 559–565.
Caserta, M., & Voß, S. (2016). A corridor method based hybrid algorithm for redundancy allocation. Journal
of Heuristics, 22(4), 405–429.
Chen, J., Li, J., & Xin, B. (2017). DMOEA-εC: Decomposition-based multi-objetive evolutionary algorithm
with the ε-constraint framework. IEEE Transactions on Evolutionary Computation, 21(5), 714–730.
Chen, T. C., & You, P. S. (2005). Immune algorithms-based approach for redundant reliability problems with
multiple component choices. Computers in Industry, 56, 195–205.
Chern, M. (1992). On the computational complexity of reliability redundancy allocation in a series system.
Operations Research Letters, 11(5), 309–315.

123
 Annals of Operations Research

Chu, H. Y., Xu, P. P., & Yang, C. C. (2016). Joint relay selection and power control for robust cooperative
multicast in mmWave WPANs. Science China-Information Sciences, 59(8), 082301.
Day, R. H. (1966). Allocating weapons to target complexes by means of nonlinear programming. Operations
Research, 14(6), 992–1013.
Deb, K. (2000). An efficient constraint handling method for genetic algorithms. Computer Methods in Applied
Mechanics and Engineering, 186(2–4), 311–338.
Dehghan Hardoroudi, N., Keshvari, A., Kallio, M., & Korhonen, P. (2017). Solving cardinality constrained
mean-variance portfolio problems via milp. Annals of Operations Research, 254(1), 47–59.
denBroeder, G. G, Jr., Ellison, R. E., & Emerling, L. (1959). On optimum target assignments. Operations
Research, 7(3), 322–326.
Gomes de Mattos, R., Oliveira, F., Leiras, A., Baptista de Paula Filho, A., & Gonçalves, P. (2018). Robust
optimization of the insecticide-treated bed nets procurement and distribution planning under uncertainty
for malaria prevention and control. Annals of Operations Research.
Hosein, P. A., Walton, J. T., & Athans, M. (1988). Dynamic weapon-target assignment problems with vulnerable
C2 nodes. Massachusetts Inst of Tech Cambridge Lab for Information and Decision Systems: Tech. rep.
Huang, C. L. (2015). A particle-based simplified swarm optimization algorithm for reliability redundancy
allocation problems. Reliability Engineering and System Safety, 142, 221–230.
Hughes, E. J. (2001). Evolutionary multi-objective ranking with uncertainty and noise. In Proceedings of IEEE
international conference on evolutionary multi-criterion optimization (pp. 329–343).
Jiang, S. W., Cai, Z. H., Zhang, J., & Ong, Y. S. (2011). Multiobjective optimization by decomposition with
Pareto-adaptive weight vectors Pareto-adaptive weight vectors. In Proceedings of IEEE international
conference on natural computation (pp. 1260–1264).
Johnson, B. L., Porter, A. T., King, J. C., & Newman, A. M. (2018). Optimally configuring a measurement
system to detect diversions from a nuclear fuel cycle. Annals of Operations Research, 275, 393–420.
Khalili-Damghani, K., & Amiri, M. (2012). Solving binary-state multi-objective reliability redundancy allo-
cation series-parallel problem using efficient epsilon-constraint, multi-start partial bound enumeratio
nalgorithm, and DEA. Reliability Engineering and System Safety, 103(4), 35–44.
Kline, A., Ahner, D., & Hill, R. (2019). The weapon-target assignment problem. Computers and Operations
Research, 105, 226–236.
Krokhmal, P., Murphey, R., Pardalos, P., & Uryasev, S. (2004). Use of conditional value-at-risk in stochastic
programs with poorly defined distributions (pp. 225–241). Boston: Springer.
Leboucher, C., Shin, H. S., Siarry, P., Chelouah, R., Menec, S. L., & Tsourdos, A. (2013). A two-step optimi-
sation method for dynamic weapon target assignment problem. IntechOpen: Tech. rep.
Lee, M. Z. (2010). Constrained weapon-target assignment: Enhanced very large scale neighborhood search
algorithm. IEEE Transactions on Systems Man and Cybernetics Part A, 40(1), 198–204.
Lee, C. Y., Gen, M., & Kuo, W. (2002). Reliability optimization design using hybridized genetic algorithm
with a neural network technique. IEICE Transactions on Fundamentals of Electronics, Communications
and Computer Sciences, 84, E627-A–637.
Li, J., Chen, J., Xin, B., & Dou, L. H. (2015). Solving multi-objective multi-stage weapon target assignment
problem via Adaptive NSGA-II and Adaptive MOEA/D: A comparison study. In Proceedings of IEEE
congress on evolutionary computation (pp 3132–3139).
Li, J., Chen, J., Xin, B., Dou, L. H., & Peng, Z. H. (2016). Solving the uncertain multi-objective multi-stage
weapon target assignment problem via MOEA/D-AWA. In Proceedings of IEEE congress on evolutionary
computation (pp 4934–4941).
Li, M. H., Huang, G. M., & Zhou, D. (2016). A yield-enhanced global optimization methodology for analog
circuit based on extreme value theory. Science China-Information Sciences, 59(8), 082401.
Li, X., Qin, Z., & Kar, S. (2010). Mean-variance-skewness model for portfolio selection with fuzzy returns.
European Journal of Operational Research, 202(1), 239–247.
Li, Z. J., Liao, H. T., & Coit, D. W. (2009). A two-stage approach for multi-objective decision making with
applications to system reliability optimization. Reliability Engineering and System Safety, 94(10), 1585–
1592.
Liefooghe, A., Basseur, M., Jourdan, L., & Talbi, E. G. (2007). Combinatorial optimization of stochastic
multi-objective problems: An application to the flow-shop scheduling problem. In Proceedings of IEEE
international conference on evolutionary multi-criterion optimization (pp 457–471).
Liu, B. D. (2009). Theory and practice of uncertain programming. Berlin: Springer.
Lloyd, S. P., & Witsenhausen, H. S. (1986). Weapons allocation is NP-complete. In Proceedings of IEEE
summer conference on simulation (pp. 1054–1058).
Manne, A. S. (1958). A target-assignment problem. Operations Research, 6(3), 346–351.
Ma, X. L., Qi, Y. T., Li, L. L., Liu, F., Jiao, L. C., & Wu, J. S. (2014). MOEA/D with uniform decomposition
measurement for many-objective problems. Soft Computing, 18(12), 1–24.

123
Annals of Operations Research

Miettinen, K. (1999). Nonlinear multiobjective optimization. Boston: Kluwer Academic Publishers.

Montgomery, D. C. (2005). Design and analysis of experiments. Arizona: Wiley.
Nahas, N., & Nourelfath, M. (2005). Ant system for reliability optimization of a series system with multiple-
choice and budget constraints. Reliability Engineering and System Safety, 87, 1–12.
Pavlikov, K., & Uryasev, S. (2018). Cvar distance between univariate probability distributions and approxi-
mation problems. Annals of Operations Research, 262(1), 67–88.
Prasad, V. R., & Kuo, W. (2000). Reliability optimization of coherent systems. IEEE Transactions on Relia-
bility, 49, 323–330.
Qi, Y. T., Ma, X. L., Liu, F., Jiao, L. C., Sun, J. Y., & Wu, J. S. (2014). MOEA/D with adaptive weight
adjustment. Evolutionary Computation, 22(2), 231–264.
Roy, R. K. (2010). A Primer on the Taguchi method. Dearborn: Society of Manufacturing Engineers.
Sulieman, D., Jourdan, L., & Talbi, E. (2010). Using multiobjective metaheuristics to solve VRP with uncertain
demands. In Proceedings of IEEE international conference on evolutionary computation (pp. 1–8).
Sung, C. S., & Cho, Y. K. (2000). Reliability optimization of a series system with multiple-choice and budget
constraints. European Journal of Operational Research, 127, 158–171.
Taboada, H. A., Baheranwala, F., Coit, D. W., & Wattanapongsakorn, N. (2007). Practical solutions for multi-
objective optimization: An application to system reliability design problems. Reliability Engineering and
System Safety, 92(3), 314–332.
Teich, J. (2001). Pareto-front exploration with uncertain objectives. In Proceedings of IEEE international
conference on evolutionary multi-criterion optimization (pp. 314–328).
Tillman, F. A., Hwuang, C. L., & Kuo, W. (1980). Optimization of system reliability. New York: Marcel
Dekker.
Wang, Z. T., Guo, J. S., Zheng, M. F., & Yang, Y. S. (2014). A new approach for uncertain multiobjective
programming problem based on PE principle. Journal of Industrial and Management Optimization,
11(1), 13–26.
Wu, L., Wang, H. Y., Lu, F. X., & Jia, P. F. (2008). An anytime algorithm based on modified GA for dynamic
weapon-target allocation problem. In Proceedings of IEEE congress on computational intelligence (pp.
2020–2025).
Xin, B., Chen, J., Peng, Z. H., Dou, L. H., & Zhang, J. (2011). An efficient rule-based constructive heuristic to
solve dynamic weapon-target assignment problem. IEEE Transactions on Systems Man and Cybernetics:
Part A Systems and Humans, 41(3), 598–606.
Xin, B., Chen, J., Zhang, J., Dou, L. H., & Peng, Z. H. (2010). Efficient decision makings for dynamic weapon-
target assignment by virtual permutation and tabu search heuristics. IEEE Transactions on Systems Man
and Cybernetics: Part C, 40(6), 649–662.
Xu, L., Yang, Y. W., & Li, Y. P. (2014). Resource allocation of limited feedback in clustered wireless mesh
networks. Wireless Personal Communications, 75(2), 901–913.
Zhang, Q., & Li, H. (2007). MOEA/D: A multiobjective evolutionary algorithm based on decomposition.
IEEE Transactions on Evolutionary Computation, 11(6), 712–731.
Zhou, A., Zhang, Q., Jin, Y., Tsang, E., & Okabe, T. (2005). A model-based evolutionary algorithm for
bi-objective optimization. In Proceedings of the IEEE congress on evolutionary computation (pp. 2568–
2575).
Zhu, X., & Kuo, W. (2014). Importance measures in reliability and mathematical programming. Annals of
Operations Research, 212(1), 241–267.
Zitzler, E., & Thiele, L. (1999). Multiobjective evolutionary algorithm: A comparative case study and strength
pareto approach. IEEE Transactions on Evolutionary Computation, 3(4), 257–271.

Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and
institutional affiliations.

Affiliations

Juan Li1 · Bin Xin2,3,4 · Panos M. Pardalos5 · Jie Chen2,3,4

Juan Li
00134476@bit.edu.cn
Panos M. Pardalos
pardalos@ufl.edu

123
 Annals of Operations Research

Jie Chen
chenjie@bit.edu.cn
1 School of Mechatronical Engineering, Beijing Institute of Technology, Beijing 100081,
People’s Republic of China
2 School of Automation, Beijing Institute of Technology, Beijing 100081, People’s Republic of China
3 State Key Laboratory of Intelligent Control and Decision of Complex Systems, Beijing Institute
of Technology, Beijing 100081, People’s Republic of China
4 Beijing Advanced Innovation Center for Intelligent Robots and Systems, Beijing Institute
of Technology, Beijing 100081, People’s Republic of China
5 Department of Industrial and Systems Engineering, University of Florida, Gainesville, USA

123