New approach for uncertain random multi-objective programming problems based on CESD criterion

SUN Yun, WANG Ying, MENG Xiangfei, FU Chaoqi, and LUO Chengkun

1. Equipment Management and UAV Engineering College, Air Force Engineering University, Xi’an 710051, China;

2. Air Force Command College, Beijing 100097, China; 3. Beijing Institute of System Engineering, Beijing 100101, China

Abstract: To overcome the defects that the traditional approach for multi-objective programming under uncertain random environment (URMOP) neglects the randomness and uncertainty of the problem and the volatility of the results, a new approach is proposed based on expected value-standard deviation value criterion (CESD criterion). Firstly, the effective solution to the URMOP problem is defined; then, by applying sequence relationship between the uncertain random variables, the URMOP problem is transformed into a single-objective programming (SOP) under uncertain random environment (URSOP),which are transformed into a deterministic counterpart based on the CESD criterion. Then the validity of the new approach is proved that the optimal solution to the SOP problem is also efficient for the URMOP problem; finally, a numerical example and a case application are presented to show the effectiveness of the new approach.

Keywords: chance theory, independent-uncertain random multiobjective programming, expected value-standard derivation value criterion (CESD criterion).

1. Introduction

The multi-objective programming (MOP) problem is a discipline developed from the 1970s, which is applied widely in management science, military science, operations research and so on. For example, in the construction of weapons and equipment systems, it is hoped for the largest combat effectiveness with the lowest cost; in the flight scheduling problem, it is expected for the highest mission safety with the shortest flight time. In these decision problems, the various objectives often contradict each other, which is difficult to find an optimal solution. Then, we may only weigh and compromise among the decision-making objectives, and select the most satisfactory plan [1–3].

Classical MOP mainly solves the problems in deterministic environment. In practice, we have to make decisions under indeterministic environment. How to solve MOP with multiple indeterministic factors has important significance. One of the common indeterministic phenomena is randomness, which can be solved by the probability theory with probability distributions obtained from enough samples. A random multi-objective programming(RMOP) problem is proposed [4–6].

Many events cannot accumulate enough and accurate data through experiments or other means. When dealing with such problems, experts in related fields are usually invited for the belief degree of each event [7]. However,since the expert’s estimate of the event’s belief degree is generally higher than the frequency of event in practice[8,9], if this type of problem is still solved by the probability theory, the conclusions are probably contrary to the facts [10]. Therefore, some scholars believed that the fuzzy theory [11] should be used to deal with the problem of expert belief, based on which, they studied the fuzzy multi-objective programming (FMOP) problem in[12–14]. Although FMOP has been widely used, many studies have shown that human uncertainty is not fuzzy[10], for which, applying the fuzzy theory to deal with uncertainty may lead to unrealistic situations. In order to overcome these defects, the uncertainty theory was established [7] by Liu in 2007 and refined [15] in 2010 to solve problems with experts’ belief degree. At present, the uncertainty theory has grown into an important branch of mathematics dealing with belief degree. In 2009, Liu proposed the uncertain programing (UP) problem [16],which was applied in many areas. Then, the multi-objective programming under uncertain environment (UMOP)was proposed [17].

In reality, randomness and uncertainty often coexist in a complex system. In order to handle the problem, Liu proposed the chance theory, defined the uncertain random variable [18], and proposed the uncertain random programming [19]. Then, the multi-objective programming under uncertain random environment (URMOP)was proposed in 2014 [20], and the traditional solution approach was first proposed in this paper, which transformed URMOP into a counterpart under deterministic environment, which was then solved directly. The traditional approach solved the problem without considering uncertainty and randomness. Zheng et al. [21] presented another approach named linear weighted approach(LWA) under the expected value criterion (CEcriterion),based on which, the URMOP is transformed into a singleobjective programming under uncertain random environment (URSOP), and then transformed into a counterpart under deterministic environment. Qi et al. [22] presented a new ideal point method (IPM) to solve the URMOP problem under the CEcriterion.

The equivalent model based on the CEcriterion reflects the average level that the objective function can reach under the influence of uncertain random factors.Uncertain random objective function, as a complex uncertain random variable, sometimes needs to investigate the degree of deviation from the expected value in practice, in particular, when the degree of deviation between the objective function and its expected value is very large, it is difficult to represent the objective function with the expected value only. It is necessary to describe the objective function together with the average level and the degree of deviation, and thus, the expected valuestandard deviation value criterion (CESDcriterion) is proposed, which can maintain the numerical characteristics of the first moment with the expected value, and reflect the deviation degree between the uncertain random objective function and its expected value.

The rest of this paper is organized in the following manner. In Section 2, some basic definitions are introduced and the basic framework of the new approach is proposed and the concepts such as Pareto efficient solution and CESDcriterion are defined. In Section 3 and Section 4, several lemmas and theorems are proved to illustrate that the optimal solution of the single-objective programming (SOP) problem under the deterministic environment is efficient for the URMOP problem. A numerical example and a case application are presented to illustrate the feasibility of the new approach in Section 5. Finally, a brief summary and future research work are stated in Section 6.

2. Preliminaries

In this section, we will introduce several related definitions and theorems as well as the basic framework of URMOP, which is helpful to prove and understand the following.

2.1 Chance theory

Definition 1[18] Chance space

Uncertainty space and probability space are represented by (Γ,L,M) and (Ω,A,Pr), respectively. The product of them is represented by (Γ,L,M)×(Ω,A,Pr), which is called a chance space.

Definition 2[18] Uncertain random variable

An uncertain random variable is represented by a function ξ, which is mapped from (Γ,L,M)× (Ω,A,Pr) to the set of real numbers.

RemarkAny Borel set of real numbers is denoted byB, then, {ξ∈B} is an event inL×A. A random variable and an uncertain variable are denoted by η and τ, respectively, then, an uncertain random variable is represented by ξ(η,τ) . When ξ does not change with η, it would degenerate to an uncertain variable. When ξ does not change with τ, it would degenerate to a random variable.As a result, a random variable and an uncertain variable are both special cases of uncertain random variables.

Definition 3[18] Chance distribution

An uncertain random variable is denoted by a function ξ. Then, the chance distribution Φ(x) for anyx∈R is denoted by Φ(x)=Ch{ξ≤x}.

Definition 4[18] Expected value of uncertain random variable

An uncertain random variable is denoted by ξ, the expected valueof whichcanbe defined asfollows:

where at least one of the two integrals is finite.

Definition 5[18] Variance value of uncertain random variable

An uncertain random variable is denoted by ξ, the variance value of which is defined as follows:

where the uncertain random variable (ξ-e)2is nonnegative, that is, ( ξ-e)2∈[0,+∞).

Definition 6Standard deviation value of uncertain random variable

An uncertain random variable is denoted by ξ, the standard deviationvalueofwhichis definedas follows:

Theorem 1[18] Uncertain random variables on(Γ,L,M)×(Ω,A,Pr)aredenotedbyξ1,ξ2,···,ξnand a measurablefunctionisdenotedbyf. Then,ξ=f(ξ1,

2.2 Model of URMOP

3. Proof of related lemmas

σ2[ξ]=V[ξ]=E[ξ2]-E[ξ]2

Since , we get

Suppose that

Since bothm(y,α) andn(y,α) are strictly monotonically increasing as α increases, thus, according to Theorem 6, we get

Assume that

Then, we get

SinceG(0)=0 andG′(0)＞0(x∈[0,1] , exceptx=0,α),thenG(1)＞0.

Then, we get

Furthermore, we get

According to the CESDcriterion, we get

Assumethat

Since both (61) and (62) are strictly monotonically increasing as α increases, according to (36)-(38), we get

According to the CESDcriterion, we get

The lemma is proved. □

4. Efficient solution

In this section, we introduce two approachs, which are the LWA and the IPM. These are used to transform the I-URMOP problem into an I-URSOP problem under the CESDcriterion.

4.1 LWA

LWA is appropriate for the conditions where the decision makers can easily distinguish the objectives and their importance. By assigning corresponding weights to each objective function and linearly weighted summation according to the importance of objectives, LWA converts the I-URMCOP problem (9) into an equivalent uncertain single-objective problem as follows:

Theorem 5The optimal solution x* of the problem(65) based on the CESDcriterion must also be a CESDPareto efficient solution to the problem (9).

ProofSuppose that x¯ is the optimal solution of the problem (65) but not the CESD-Pareto efficient solution to the problem (9).

That is,

Obviously, we can arrive at

It can be seen from Definition 8 that x*is not the optimalsolution to theproblem(65), soitiscontrarytothe assumption. Thus,theassumption isnot true,andx*isa CESD-Pareto efficient solution to the problem (9). The theorem is proved.

4.2 IPM

IPM is appropriate for the condition where decision makers can easily know the optimal choice for each objective. By minimizing the distance between each objective function and the ideal point which is obtained without considering the influence of other objective functions, the IPM converts the I-URMOP problem (9) into the IURSOP problem according to the distance functions.

wherefi0standsforthelowerboundofsingle objectivefi(x,ξi)(i=1,2,···,q)on the feasibleset.

It can be seen from Definition 8 thatx*is not the optimal solution to the problem (72), so it is contrary to the assumption. Thus, the assumption is not true, andx*is a CESD-Pareto efficient solution to the problem (9). The theorem is proved. □

5. Example applications

In this section, the LWA and the IPM are introduced to transform the I-URMOP problem into the I-URSOP problem. The influences of weights and the conversion criterion are discussed.

5.1 Numerical example

Assume thatx1,x2,x3are nonnegative decision variables,η1,η2,η3are independent random variables with distributionsU(1,3),E(0.8),N(3,5); τ1,τ2,τ3are independent uncertain variables with distributionZ(0.8,1.3,1.8),L(1.5,12),L(5,10). The I-URMOP problem involves three objectives.

Obviously,f1(x,η1,τ1) is strictly decreasing with respect to η1, while strictly increasing with respect to τ1;f2(x,η2,τ2) is strictly decreasing with respect to η2,τ2;f3(x,η3,τ3) is strictly increasing with respect to η3,τ3.The I-URMOP problem can be converted to an I-URSOP problem through LWM with λ1,λ2,λ3(λ1+λ2+λ3=1).

Then we convert the I-URSOP problem into a deterministic counterpart under the CESDcriterion.

The I-URMOP problem can be converted to the IURSOP problem through IPM.

Then we convert the I-URSOP problem into a deterministic counterpart under the CESDcriterion.

In general, the deterministic counterpart converted from the I-URMOP problem has a high complexity and a lot of local minima, the constraints of which may be also complex. Thus, we apply the beetle antennae search(BAS) algorithm [23], which has a strong robustness and a low time complexity. Parameter settings adopted in the BAS algorithm are shown in Table 1.

Table 1 Parameter settings adopted in BAS algorithm

We solve each problem for 20 times, and then use the average values as the final results, which is shown in Table 2. Expected values and standard deviation values change with λ1,λ2,λ3changing.

Table 2 Results by LWA with different weights

The values of the objective function with various weights are evenly distributed in a relatively concentrated interval. For the proposed approach, the value ofx1,x2,x3are in (0.35, 0.46), (2.01, 2.98), (3.18, 3.90), respectively and the values of objective 1, objective 2, objective 3 are in (2.60, 3.79), (6.10, 7.10), (-5.60, -2.89),respectively. For the traditional approach, the values ofx1,x2,x3are in (0.37, 0.43), (2.10, 2.90), (3.16, 3.60), respectively, and the values of objective 1, objective 2, objective 3 are in (2.80, 4.10), (6.30, 7.90), (-5.30, -2.10),respectively.

Because the traditional approach and the new one are different in the order of dealing with uncertainty and randomness, the results are different, which are all Pareto efficient solutions based on the CESDcriterion. However,since the new LWA takes into account the inherent uncertainty and randomness of the problem, it makes the result overall better than the traditional one. This also shows that in practical problems, the solutions generated by uncertain random approaches are more in line with the decision-making preferences of most people.

IPM is appropriate for the condition where decision makers can easily know the optimal choice for each objective. The traditional approach is to convert the URMOP into a deterministic problem under the CEcriterion.The lower bounds of these objectives are 2.987 6, 5.895 6,-3.225 8. Similarly, we apply the BAS algorithm to solve the problem, and the control parameters are listed in Table 2. The comparison of the two approaches are shown in Table 3.

Table 3 Comparison of the traditional approach and the new approach

Obviously, the results of the new approach are different from those of the traditional approach. The new approach calculates the minimum value of each uncertain random objective function; thus, the uncertainty and randomness of the problem are maintained. However, the traditional approach focuses on the multi-objective part of the problem based on the minimum value of deterministic objective functions.

5.2 Case application

The problem (89) is transformed into a deterministic counterpart under the CESDcriterion:

Take λ1=0.6,λ2=0.4 as an example, we get the results by the traditional approach based on the CESDcriterion (TCESD-Weapon), by the new approach based on the CESDcriterion (CESD-Weapon), and by the new approach under the CEcriterion (CE-Weapon), which are shown in Table 4.

Table 4 Results by LWM for WTA

The problem (89) is transformed into a deterministic counterpart under the CESDcriterion:

The lower bounds of these objectives areWe get the results by the traditional approach based on the CESDcriterion (TCESD-Weapon), by the new approach based on the CESDcriterion (CESDWeapon), and by the new approach based on the CEcriterion (CE-Weapon), which are shown in Table 5.

Table 5 Results by IPM for WTA

6. Conclusions

Under the CESDcriterion, this paper proposes a new approach for Pareto-efficient solutions to the I-URMOP problem. The main contributions are as follows.

Under the CESDcriterion, the new approach considers the uncertainty and randomness of the uncertain random problem and volatility of the results, which is appropriate for the problems.

The proofs of the four lemmas lay foundations for the new approach as well as provide a theoretical basis for properties of uncertain random variables, which enrich the chance theory.

For the LWM, the influence of weights is studied. Obviously, the choices of weights depend on the problem as well as the decision makers’ preferences, which shows that it is appropriate to choose weights by collective decision making. For IPM, the differences between the new approach and the traditional approach are discussed, which illustrates that the new approach is more in line with the decision preference of most people.

The URMOP with dependent variables should be studied in the future. And a new approach based on the CESDcriterion for the uncertain random multi-stage programming problem is an open problem solved.