A new definition of cross entropy for uncertain random variables and its application

Abstract

This paper proposes a new definition of cross entropy for uncertain random variables, and derives a formula. Moreover, this paper introduces generalized cross entropy for uncertain random variables, and discusses its properties. Based on the definition of cross entropy, a cross entropy chance distribution model of degree-constrained minimum spanning tree (DCMST) problem is proposed. An algorithm is designed here to solve the model. Finally, a numerical example is provided to illustrate the effectiveness of the proposed model and algorithm.

Keywords

Cross entropy uncertain random variable minimum spanning tree uncertain random network

1 Introduction

The minimum spanning tree (MST) problem is one of the most important network optimization problems, which was first investigated by Borüvka [4] in 1926. Due to different research fields, there are many limitations on the MST problem in practical application, such as spanning tree degree of each node in the limit, which shall not exceed the prescribed value, this makes the nature of the problem is very different. In order to reduce the vulnerability of node, the DCMST problem was first proposed by Narula and Ho [25] in 1980. In a deterministic network, all the weights are crisp numbers. In the past decades, the DCMST problem of deterministic network has been a hot issue in the field of study, it has been applied in many fields such as transportation, communications and logistics, etc. Many efficient classical algorithms have been used to solve the DCMST problem, such as heuristic algorithm (Narula and Ho [25]), ant colony optimization algorithm (Bau and Ho [5]), evolutionary algorithm (Raidl [26]), and genetic algorithm (Zhou and Gen [33]), etc.

However, real networks are usually in the state of indeterminacy. In order to model indeterminacy network, random network was first introduced by Frank and Hakimi [7] in 1965 for modeling communication network with random capacities. Random network has been widely applied in many fields. In particular, the DCMST problem with random weights was first investigated by Knowles and Corne [14] in 2000. As extensions, Torkestani [31] proposed a learning automata-based algorithm to solve the DCMST problem for a random network in 2012, and Torkestani [32] investigated the min-degree constrained MST problem in a random network in 2013.

A premise of applying random network is that the estimated probability is close enough to the real frequency. However, in practice, the network is inevitably affected by collisions, congestions and interferences. We usually lack of observed data, and instead have to invite some experts to provide their degrees of belief that each event will occur. As a breakthrough, for dealing with lack of historical data of weights, uncertain network was first proposed by Liu [19] for modeling project scheduling problem with uncertain duration times. After that, uncertain network was applied widely and many uncertain network optimization problems have been solved. For example, the inverse MST problem was introduced by Zhang et al. [35], the quadratic MST problem was investigated by Zhou et al. [36], path optimality conditions for the MST problem were investigated by Zhou et al. [37]. Besides, Gao and Jia [9] first introduced the DCMST problem into uncertain network, and proposed three uncertain programming models.

In practice, uncertainty and randomness may simultaneously appear in a complex network. To model this phenomenon, Liu [20] first proposed a concept of uncertain random network in which some weights are random variables and others are uncertain variables. Many uncertain random network optimization problems have been solved, for example, the MST problem studied by Sheng et al. [27], the maximum flow problem studied by Sheng and Gao [28], and the shortest path problem studied by Shi et al. [30]. In addition, the DCMST problem for uncertain random network was first investigated by Gao et al. [10]. They proposed an ideal chance distribution, as well as formulated an uncertain random programming model and an algorithm to solve the DCMST problem in an uncertain random network.

In this paper, we will further investigate the DCMST problem for an uncertain random network. The remainder of this paper is organized as follows. In Section 2, some basic preliminaries in uncertainty theory, chance theory and uncertain random network will be reviewed. A new definition of cross entropy for uncertain random variables is presented in Section 3. Section 4 will introduce a generalized cross entropy for uncertain random variables. An application of cross entropy is presented in Section 5, a cross entropy chance distribution model of the DCMST problem for an uncertain random network is formulated, and an algorithm is proposed here to solve the model. In Section 6, we give a numerical example to illustrate its effectiveness. And in Section 7, we give a brief summary to this paper.

2 Preliminary

This section will review some basic preliminaries in uncertainty theory, chance theory and uncertain random network.

2.1 Uncertainty theory

For modelling belief degree, uncertainty theory was founded by Liu [15] in 2007 and perfected by Liu [17] in 2009 with the normality, duality, subadditivity, and product axiom of uncertain measure. Uncertainty theory has become a branch of mathematics. In theory, uncertain process [16], uncertain differential equation [6] etc. have been established. In practice, uncertain programming [18], uncertain statistics [19], uncertain optimal control [38] etc. have been developed.

In order to rationally deal with belief degrees, Liu [15] defined an uncertain measure by the following three axioms: Axiom 1. (Normality Axiom) M {Γ} =1 for the universal set Γ. Axiom 2. (Duality Axiom) M {Λ} + M {Λ^c} =1 for any event Λ. Axiom 3. (Subadditivity Axiom) For every countable sequence of events Λ₁, Λ₂, ⋯, we have $ℳ {\cup_{i = 1}^{\infty} Λ_{i}} \leq \sum_{i = 1}^{\infty} {Λ_{i}} .$

Furthermore, Liu [17] defined a product uncertain measure by the fourth axiom:

Axiom 4. (Product Axiom) Let (Γ_k, Ł _k, _Mk) be uncertainty spaces for k = 1, 2, ⋯. The product uncertain measure M is an uncertain measure satisfying $ℳ {\prod_{k = 1}^{\infty} Λ_{k}} =_{k = 1}^{\infty} k {Λ_{k}}$ where Λ_k are arbitrarily chosen events form Ł_k for k = 1, 2, ⋯, respectively.

Definition 1. (Liu [15]) Let Γ be a nonempty set, let $ℒ$ be a σ-algebra over Γ. Then the triplet (Γ, $ℒ$ , M) is called an uncertainty space.

Definition 2. (Liu [15]) An uncertain variable is a measurable function ξ from an uncertainty space (Γ, $ℒ$ , M) to the set of real numbers, i.e., for any Borel set B of real numbers, the set ${ξ \in B} = {γ \in Γ ∣ ξ (γ) \in B}$ is an event.

Definition 3.(Liu [15]) The uncertainty distribution Φ of an uncertain variable ξ is defined by $Φ (x) = ℳ {ξ \leq x}$ for any real number x.

For example, linear uncertain variables Ł (a, b) has an uncertainty distribution as shown in Fig. 1, $Φ_{1} (x) = {\begin{matrix} 0, & if x < a \\ (x - a) / (b - a), & if a \leq x \leq b \\ 1, & if x > b \end{matrix}$ and the zigzag uncertain variable $ξ \sim Z (a, b, c)$ has an uncertainty distribution as shown in Fig. 2, $Φ_{2} (x) = {\begin{matrix} 0, & if x \leq a \\ (x - a) / [2 (b - a)], & if a < x \leq b \\ (x + c - 2 b) / [2 (c - b)], & if b < x \leq c \\ 1, & if x > c . \end{matrix}$

Fig.1

Linear uncertainty distribution.

Fig.2

Zigzag uncertainty distribution.

An uncertainty distribution Φ is said to be regular if its inverse function Φ^-1 (α) exists and is unique for each α ∈ (0, 1). It is clear that the linear uncertain variable and zigzag uncertain variable are regular, and their inverse uncertainty distributions are shown as follows,

$Φ_{1}^{- 1} (α) = (1 - α) a + α b,$ $Φ_{2}^{- 1} (α) = {\begin{matrix} a + 2 (b - a) α, & if α \leq 0.5 \\ 2 b - c + 2 (c - b) α, & if α > 0.5 . \end{matrix}$

Definition 4. (Liu [17]) The uncertain variables ξ₁, ξ₂, ⋯, ξ_n are said to be independent if $ℳ {\cap_{i = 1}^{n} {ξ_{i} \in B_{i}}} = \min_{1 \leq i \leq n} ℳ {ξ_{i} \in B_{i}}$ for any Borel sets B₁, B₂, ⋯, B_n of real numbers.

Theorem 1. mon (Liu [19]) Let ξ₁, ξ₂, ⋯, ξ_n be independent uncertain variables with regular uncertainty distributions Φ₁, Φ₂, …, Φ_n, respectively. If f (ξ₁, ξ₂, ⋯, ξ_n) is strictly increasing with respect to ξ₁, ξ₂, ⋯, ξ_m and strictly decreasing with respect to ξ_m+1, ξ_m+2, …, ξ_n, then $ξ = f (ξ_{1}, ξ_{2}, \dots, ξ_{n})$ has an inverse uncertainty distribution $\begin{matrix} Ψ^{- 1} (α) = f (Φ_{1}^{- 1} (α), \dots, Φ_{m}^{- 1} (α), Φ_{m + 1}^{- 1} (1 - α), \\ \dots, Φ_{n}^{- 1} (1 - α)) . \end{matrix}$

Example 1: Let ξ₁, ξ₂, ⋯, ξ_n be independent and positive uncertain variables with regular uncertainty distributions Φ₁, Φ₂, …, Φ_n, respectively. Then the product $ξ = ξ_{1} \times ξ_{2} \times \dots \times ξ_{n}$ has an inverse uncertainty distribution $Ψ^{- 1} (α) = Φ_{1}^{- 1} (α) \times Φ_{2}^{- 1} (α) \times \dots \times Φ_{n}^{- 1} (α) .$

Definition 5. (Gao et al. [11]) Let ξ and η be two uncertain variables with uncertainty distributions Φ and Ψ, respectively. Then the cross-entropy of ξ form η is defined by $D [ξ; η] = \int_{- \infty}^{+ \infty} | Φ (x) - Ψ (x) | d x .$

2.2 Chance theory

Chance theory was pioneered by Liu [21] in 2013 for modelling complex systems with not only uncertainty but also randomness. In theory, the concepts of uncertain random variable, chance measure and chance distribution were proposed by Liu [21] in 2013. In addition, the concepts of expected value and variance of uncertain random variable were also proposed by Liu [21]. In order to measure the uncertainty of uncertain random variable, Sheng et al. [29] introduced the concept of entropy for uncertain random variable. Moreover, Sheng et al. [29] proposed cross entropy for uncertain random variables to measure the divergence between two chance distributions. Ahmadzade et al. [1] proposed partial entropy, Ahmadzade et al. [2] studied partial triangular entropy, and Ahmadzade et al. [3] proposed partial quadratic entropy for uncertain random variables. The operational law of uncertain random variables was presented by Liu [22]. As an extension, a law of large numbers for uncertain random variables was proved by Yao and Gao [34], and convergence in distribution for uncertain random variables was proved by Gao and Ralescu [13]. In practice, uncertain random programming [22], uncertain random process [8], uncertain random logic [24], uncertain random reliability analysis [12], uncertain random risk analysis [23], uncertain random network [20], and uncertain random graph [20] have been established.

Let (Γ, Ł, M) be an uncertainty space and let (Ω, A, Pr) be a probability space. Then the product (Γ, Ł, M) × (Ω, A, Pr) is called a chance space.

Definition 6. (Liu [21]) Let (Γ, Ł, M) × (Ω, A, Pr) be a chance space, and let Θ ∈ Ł × A be an event. Then the chance measure of Θ is defined as $Ch {Θ} = \int_{0}^{1} \Pr {ω \in Ω | {γ \in Γ | (γ, ω) \in Θ} \geq x} d x .$

Theorem 2. (Liu [21]) Let (Γ, Ł, M) × (Ω, A, Pr) be a chance space. then ${Λ \times A} = ℳ {Λ} \times \Pr {A}$ for any Λ∈ Ł and any A ∈ A. Especially, we have $Ch {\emptyset} = 0, Ch {Γ \times Ω} = 1.$

Definition 7. (Liu [21]) An uncertain random variable is a function ξ from a chance space (Γ, Ł, M) × (Ω, A, Pr) to the set of real numbers such that {ξ ∈ B} is an event in Ł × A for any Borel set B of real numbers.

Definition 8. (Liu [21]) Let ξ be an uncertain random variable. Then its chance distribution is defined by $Φ (x) = Ch {ξ \leq x}$ for any $x \in R .$

Theorem 3. theorem (Liu [22]) Let η₁, η₂, ⋯, η_m be independent random variables with probability distributions Ψ₁, Ψ₂, ⋯, Ψ_m, respectively, and let τ₁, τ₂, ⋯, τ_n be uncertain variables. Assume f is a measure function. Then the uncertain random variable $ξ = f (η_{1}, η_{2}, \dots, η_{m}, τ_{1}, τ_{2}, \dots, τ_{n})$ has a chance distribution $\begin{matrix} Φ (x) = \int_{R^{m}} F (x; y_{1}, y_{2}, \dots, y_{m}) Ψ_{1} (y_{1}) Ψ_{2} (y_{2}) \\ \dots Ψ_{m} (y_{m}) \end{matrix}$ where F (x ; y₁, y₂, ⋯, y_m) is the uncertainty distribution of the uncertain variable f (y₁, y₂, ⋯, y_m, τ₁, τ₂, ⋯, τ_n).

Example 2: Let η be a positive random variable with probability distribution Ψ, and let τ be a positive uncertain variable with uncertainty distribution ϒ. Then the uncertain random variable $ξ_{1} = η + τ$ has a chance distribution $Φ_{1} (x) = \int_{- \infty}^{+ \infty} ϒ (x - y) Ψ (y),$ and uncertain random variable $ξ_{1} = η \lor τ$ has a chance distribution $Φ_{2} (x) = Ψ (x) ϒ (x) .$

Definition 9. (Sheng et al. [29]) Let ξ be an uncertain random variable with chance distribution Φ (x). Then its entropy is defined by $H [ξ] = \int_{- \infty}^{+ \infty} S (Φ (x)) x$ where S (t) = - t ln t - (1 - t) ln(1 - t).

Definition 10. (Sheng et al. [29]) Let ξ and η be two uncertain random variables with chance distributions Φ (x) and Ψ (x). Then the cross entropy of ξ from η is defined by $D [ξ, η] = \int_{- \infty}^{+ \infty} C (Φ (x), Ψ (x)) x$ where C (s, t) = s ln(s/t) - (1 - t) ln((1 - s)/(1 - t)), 0 ≤ t ≤ 1.

Example 3: Consider two uncertain random variables ξ₁ = τ₁ + η and ξ₂ = τ₂ + η, where η ∼ U (0, 2) is an uniform random variable, τ₁ ∼ Ł (0, 2) and τ₂ ∼ Ł (0, 2 - ∊) are linear uncertain variables. We can calculate their chance distributions of ξ₁ and ξ₂ as shown in Fig. 3,

Fig.3

A counterexample.

where $Φ (x) = {\begin{matrix} 0, & if x \leq 0 \\ \frac{1}{8} x^{2}, & if 0 \leq x < 2 \\ - \frac{1}{8} x^{2} + x - 1, & if 2 \leq x < 4 \\ 1, & if x \geq 4, \end{matrix}$ and $Ψ (x) = {\begin{matrix} 0, & if x \leq 0 \\ \frac{x^{2}}{8 - 4 ∊}, & if 0 \leq x < 2 - ∊ \\ - \frac{1}{2} x + \frac{1}{4} ∊ - \frac{1}{2}, & if 2 - ∊ \leq x < 2 \\ - \frac{(x - 2)^{2}}{4 (2 - ∊)} + \frac{1}{2} x + \frac{1}{4} ∊ - \frac{1}{2}, & if 2 \leq x < 4 - ∊ \\ 1, & if x \geq 4 . \end{matrix}$ Then we can calculate cross entropy of ξ₁ from ξ₂. According to the meaning of cross-entropy, we should have D [ξ₁ ; ξ₂] →0 as ∊ → 0. But it follows from the definitions of Sheng et al. [29] that $D [ξ_{1}; ξ_{2}] = + \infty .$ Hence the cross-entropy defined by Sheng et al. [29] is not reasonable.

2.3 Uncertain random network

This section will introduce some basic preliminaries of uncertain random network. The term network is a synonym for a weighted graph, where the weights may be understood as cost, distance, time and so on. For modelling the network in which some weights are random variables and others are uncertain variables, Liu [20] first proposed a concept of uncertain random network.

Definition 11. (Liu [20]) Assume N is the collection of nodes, U is the collection of uncertain arcs, R is the collection of random arcs, and W is the collection of uncertain and random weights. Then the quartette (N, U, R, W) is said to be an uncertain random network.

The uncertain random network becomes a random network (Frank and Hakimi [7]) if all weights are random variables; and becomes an uncertain network (Liu [19]) if all weights are uncertain variables. Fig. 4 shows a simple uncertain random network (N, U, R, W) as followed, $\begin{matrix} N = {1, 2, 3, 4}, & U = {(1, 2), (3, 4)}, \\ ℛ = {(1, 4), (2, 3)}, & W = {ω_{12}, ω_{14}, ω_{23}, ω_{34}} . \end{matrix}$

Fig.4

An uncertain random network of 4 nodes.

Theorem 4. ideal(Gao et al. [10]) Let (N, U, R, W) be an uncertain random network. Assume that the uncertain weights are uncertain variables τ_ij for (i, j) ∈ U, and the random weights are random variables ξ_ij with probability distributions Ψ_ij for (i, j) ∈ R, respectively. Setting d_i and b_i are the degree value and degree constraint of node i, respectively. Then the ideal chance distribution of DCMST with respect to the uncertain random network (N, U, R, W) is $\begin{matrix} Φ (x) = \int_{0}^{+ \infty} \dots \int_{0}^{+ \infty} F (x; y_{ij}, (i, j) \in; d_{i} \leq b_{i}) \\ \prod_{(i, j) \in} Ψ_{ij} (y_{ij}) \end{matrix}$ where F (x ; y_ij, (i, j) ∈ R ; d_i ≤ b_i) is the uncertainty distribution of uncertain variable f (τ_ij, (i, j) ∈ U ; y_ij, (i, j) ∈ R ; d_i ≤ b_i).

3 A new definition of cross-entropy for uncertain random variables

We try to give a new definition of cross-entropy of uncertain random variables as follows.

Definition 12. crossentropy Let ξ and η be two uncertain random variables with chance distributions Φ and Ψ, respectively. Then the cross entropy of ξ from η is defined by $D [ξ; η] = \int_{- \infty}^{+ \infty} | Φ (x) - Ψ (x) | x .$

Theorem 5. For any uncertain random variables ξ and η, the cross entropy is symmetric, i.e., $D [ξ; η] = D [η; ξ] .$ It means the divergence between ξ and η is the same as the divergence between η and ξ.

Proof. Assume Φ (x) and Ψ (x) are the chance distributions of ξ and η, respectively. It is clear that $\begin{matrix} D [ξ; η] = \int_{- \infty}^{+ \infty} | Φ (x) - Ψ (x) | x \\ = \int_{- \infty}^{+ \infty} | Ψ (x) - Φ (x) | x \\ = D [η; ξ] . \end{matrix}$ The theorem is verified.

Theorem 6. Let ξ and η be two uncertain random variables with chance distributions Φ and Ψ, respectively. Then D [ξ ; η] ≥0 and the equality holds if and only if Φ (x) = Ψ (x) almost everywhere.

Proof. Since |Φ (x) - Ψ (x) |≥0 for all the points $x \in R$ . Thus we have $D [ξ; η] = \int_{- \infty}^{+ \infty} | Φ (x) - Ψ (x) | x \geq 0 .$ Assuming Φ (x) = Ψ (x) almost everywhere, it is easy to obtain D [ξ ; η] =0. Conversely, assume D [ξ ; η] =0. Then Φ (x) = Ψ (x) almost everywhere. The theorem is proved.

Example 4: Under these assumptions of Example 3, we compute the cross-entropy of ξ₁ from ξ₂ according to Definition 14. $\begin{matrix} D [ξ_{1}; ξ_{2}] \\ = \int_{0}^{2 - ∊} | \frac{1}{8} x^{2} - \frac{1}{8 - 4 ∊} x^{2} | dx \\ + \int_{2 - ∊}^{2} | \frac{1}{8} x^{2} - \frac{1}{2} x - \frac{1}{4} ∊ + \frac{1}{2} | dx \\ + \int_{2}^{4 - ∊} | - \frac{1}{8} x^{2} + \frac{(x - 2)^{2}}{4 (2 - ∊)} - \frac{1}{2} - \frac{∊}{4} | dx \\ + \int_{4 - ∊}^{4} | \frac{1}{8} x^{2} - x + 2 | x = \frac{1}{2} ∊ . \end{matrix}$ It is clear that D [ξ₁ ; ξ₂] →0 as ∊ → 0. If ∊ = 1/2, then we have D [ξ₁ ; ξ₂] =1/4. Therefore Definition 14 of cross-entropy for uncertain random variables is reasonable.

Example 5: Consider two uncertain random variables ξ₁ = τ₁ ∨ η and ξ₂ = τ₂ ∨ η, where η ∼ U (0, 1) is an uniform random variable, τ₁ ∼ Ł (0, 1) and τ₂ ∼ Ł (0, 2) are linear uncertain variables. We can calculate their chance distributions of uncertain random variables ξ₁ and ξ₂ as follows, $Φ (x) = {\begin{matrix} 0, & if x < 0 \\ x, & if 0 \leq x \leq 1 \\ 1, & if x > 1, \end{matrix}$ $Ψ (x) = {\begin{matrix} 0, & if x < 0 \\ \frac{1}{2} x^{2}, & if 0 \leq x \leq 2 \\ 1, & if x > 2 . \end{matrix}$ It follows from Definition 14 that the cross entropy of ξ₁ from ξ₂ is $\begin{matrix} D [ξ_{1}; ξ_{2}] = \int_{0}^{1} | x^{2} - \frac{1}{2} x^{2} | x + \int_{1}^{2} | 1 - \frac{1}{2} x | x \\ = \frac{5}{12} . \end{matrix}$

Theorem 7. useful Let ξ and η be two uncertain random variables with regular chance distributions Φ and Ψ, respectively. Then the cross-entropy of ξ from η is $D [ξ; η] = \int_{0}^{1} | Φ^{- 1} (α) - Ψ^{- 1} (α) | α .$

Proof. Based on the definition of integral, the formula $D [ξ; η] = \int_{- \infty}^{+ \infty} | Φ (x) - Ψ (x) | x$ indicates the area of the two chance distributions as shown in Fig. 5. Without loss of generality, there is a intersection x₀ subject to {Φ (x) ≥ Ψ (x), x ∈ [x₀, + ∞)} and {Φ (x) < Ψ (x), x ∈ (- ∞, x₀)}. It follows from the method of substitution and integration by parts that the cross entropy is $\begin{matrix} \int_{- \infty}^{+ \infty} | Φ (x) - Ψ (x) | x \\ = \int_{- \infty}^{x_{0}} Ψ (x) - Φ (x) x + \int_{x_{0}}^{+ \infty} Φ (x) - Ψ (x) x \\ = \int_{- \infty}^{x_{0}} Ψ (x) x - \int_{- \infty}^{x_{0}} Φ (x) x \\ + \int_{x_{0}}^{+ \infty} Φ (x) x - \int_{x_{0}}^{+ \infty} Ψ (x) x \\ = \int_{0}^{α_{0}} α Ψ^{- 1} (α) - \int_{0}^{α_{0}} α Φ^{- 1} (α) \\ + \int_{α_{0}}^{1} α Φ^{- 1} (α) - \int_{α_{0}}^{1} α Ψ^{- 1} (α) \\ = \int_{0}^{1} | Φ^{- 1} (α) - Ψ^{- 1} (α) | α . \end{matrix}$ Thus the theorem is completed.

Fig.5

Chance distributions of ξ₁ and ξ₂.

Example 6: Under these assumptions of Example 3, it follows from Theorem 7 that the cross-entropy of ξ₁ from ξ₂ is $\begin{matrix} D [ξ_{1}; ξ_{2}] = \int_{0}^{\frac{1}{2} - \frac{1}{4} ∊} | \sqrt{8 α} - \sqrt{(8 - 4 ∊) α} | α \\ + \int_{\frac{1}{2} - \frac{1}{4} ∊}^{\frac{1}{2}} | \sqrt{8 α} - 2 α - 1 + \frac{1}{2} ∊ | α \\ + \int_{\frac{1}{2}}^{\frac{1}{2} + \frac{1}{4} ∊} | 4 - \sqrt{8 (1 - α)} - 2 α - 1 + \frac{1}{2} ∊ | α \\ + \int_{\frac{1}{2} + \frac{1}{4} ∊}^{1} | \sqrt{(1 - α) (8 - 4 ∊)} - \sqrt{8 (1 - α)} + ∊ | α \\ = \frac{1}{2} ∊ . \end{matrix}$ If ∊ = 1/2, then we have D [ξ₁, ξ₂] =1/4.

Example 7: Under these assumptions of Example 5, it follows from Theorem 7 that the cross-entropy of ξ₁ from ξ₂ is $\begin{matrix} D [ξ_{1}; ξ_{2}] = \int_{0}^{\frac{1}{2}} | \sqrt{2 α} - \sqrt{α} | α + \int_{\frac{1}{2}}^{1} | 2 α - \sqrt{α} | α \\ = \frac{5}{12} . \end{matrix}$

4 Generalized cross-entropy for uncertain random variables

In this section first we introduce a generalized definition of cross-entropy for uncertain random variables and then investigate its mathematical properties.

Definition 13. Let ξ and η be two uncertain random variables with chance distributions Φ and Ψ, respectively. Then the generalized cross-entropy of ξ from η is defined by $GD [ξ; η] = {(\int_{- \infty}^{+ \infty} | Φ (x) - Ψ (x) |^{p} x)}^{\frac{1}{p}}$ where 1 ≤ p ≤ ∞.

Based on this definition, we can obtain some properties as follows.

Theorem 8. For any uncertain random variables ξ and η, the generalized cross-entropy is symmetric, i.e., $GD [ξ; η] = GD [η; ξ] .$

Proof. Let Φ (x) and Ψ (x) be the chance distributions of ξ and η, respectively. It is obvious that $\begin{matrix} GD [ξ; η] = {(\int_{- \infty}^{+ \infty} | Φ (x) - Ψ (x) |^{p} x)}^{\frac{1}{p}} \\ = {(\int_{- \infty}^{+ \infty} | Ψ (x) - Φ (x) |^{p} x)}^{\frac{1}{p}} \\ = GD [η; ξ] \end{matrix}$ where 1 ≤ p ≤ ∞. The theorem is proved.

Theorem 9. Let ξ and η be two uncertain random variables with chance distributions Φ and Ψ, respectively. Then we have GD [ξ ; η] ≥0, and the equality holds if and only if Φ (x) = Ψ (x) almost everywhere.

Proof. Since |Φ (x) - Ψ (x) |^p ≥ 0 for all the points $x \in R$ , we have $GD [ξ; η] = {(\int_{- \infty}^{+ \infty} | Φ (x) - Ψ (x) |^{p} x)}^{\frac{1}{p}} \geq 0$ where 1 ≤ p ≤ ∞. If Φ (x) = Ψ (x) almost everywhere, then we can obtain GD [ξ ; η] =0. Conversely, if GD [ξ ; η] =0, then Φ (x) = Ψ (x) almost everywhere. The theorem is proved.

5 Cross entropy application to uncertain random DCMST problem

We discuss undirected networks here, which are finite and connected. In a deterministic undirected network, all the weights of edges are crisp number. A deterministic network is denoted by (N, E, W), where N = {1, 2, …, n} is the collection of noeds, E is the collection of edges, and W = {(ω_ij), (i, j) ∈ E} is the collection of deterministic weights. We denote that d_i (i ∈ N) is the degree value of node i, and b_i (i ∈ N) is a given value of degree constraint of node i. The concept of a spanning tree is a subnetwork that contains all the nodes. The MST problem is to find a spanning tree with least weight. The DCMST problem is to find the MST of a deterministic network, subject to constraints on each node degree. Many efficient classical algorithms, such as branch-and-bound algorithm and genetic algorithm, have been well applied to the DCMST problem for deterministic networks. The weight of edge is denoted by w_ij. It is clear that the weight of the DCMST is a function of the weight w_ij, and the weight is denoted by f ({w_ij| (i, j) ∈ E}) or f (W). Setting $1 = {w_{i j}^{1} | (i, j) \in} 2 = {w_{i j}^{2} | (i, j) \in}$ are two collections of deterministic weights. It is easy to prove that f (_W1) ≤ f (_W2), if $w_{ij}^{1} \leq w_{ij}^{2}$ for each (i, j) ∈ E. Actually, f ({w_ij| (i, j) ∈ E}) is an increasing function with respect to weights w_ij.

In practice, uncertainty and randomness may coexist in complex network, which means some weights have enough statistical data to obtain probability distributions, while others have no historical data and have to invite experts to give uncertainty distributions. Next we consider an connected and undirected uncertain random network, where some weights are uncertain variables, and others are random variables. In an uncertain random network, the weight of DCMST is a function of uncertain random variable, we can obtain the weight of ideal chance distribution by Theorem 4. In paper [10], an uncertain random programming model and an algorithm are proposed to solve the DCMST problem. This paper will propose a new uncertain random programming model and an algorithm to find the DCMST. Firstly, we give some assumptions as follows:

There is a connected and finite uncertain random network;

The weight of each edge (i, j) ∈ U ∪ R is positive and undirected;

The weights of edges (i, j) ∈ U are independent uncertain variables with respect to uncertain measure;

The weights of edges (i, j) ∈ R are independent random variables with respect to probability measure;

All the degree values d_i are less than the given values b_i.

A connected and undirected uncertain random network is denoted by (N, U, R, W), where N = {1, 2, …, n} is the collection of nodes, U is the collection of uncertain edges, R is the collection of random edges, and W = {τ_ij, (i, j) ∈ U ; ξ_ij, (i, j) ∈ R} is the collection of weights. We assume that there is a constraint on each node, and the degree value d_i is less than a given value b_i. We assume that all uncertain weights with independent uncertain variables τ_ij ((i, j) ∈ U) are defined on an uncertainty space (Γ, Ł, M), and all random weights ξ_ij ((i, j) ∈ R) with random variables are defined on a probability space (Ω, A, Pr). Assume {x_ij, (i, j) ∈ W} are decision vectors, where x_ij = 1 means that edge (i, j) is selected in degree-constrained spanning tree (DCST), otherwise x_ij = 0. Then, {x_ij, (i, j) ∈ U ∪ R ; d_i ≤ b_i} is a DCST if and only if ${\begin{matrix} \sum_{(i, j) \in \cup} x_{ij} = n - 1 \\ \sum_{(i, j) \in \cup (S)} x_{ij} \leq ∣ S ∣ - 1, \forall S \subset, \\ 2 \leq ∣ S ∣ \leq n \\ d_{i} \leq b_{i}, \forall i \in \\ x_{ij} \in {0, 1}, \forall (i, j) \in \cup \end{matrix}$ (1) where U ∪ R (S) denotes the collection of edges of S, and S is a subset of N. The weight of a DCST {x_ij, (i, j) ∈ U ∪ R (S) ; d_i ≤ b_i} is $\sum_{(i, j) \in x_{ij} τ_{ij} + \sum_{(i, j) \in (S)} x_{ij} ξ_{ij},}$ then it is an uncertain random variable.

5.1 Cross entropy chance distribution model

In practice, the decision-makers often find the DCMST with the minimum cross entropy between ideal chance distribution and chance distributions of DCST. Next we will give the followingdefinition.

Definition 14. Let (N, U, R, W) be an uncertain random network, and let Φ (x) be its ideal chance distribution of the DCMST problem. Assume that weight of each DCST with chance distribution. A DCST is called the DCMST about cross entropy chance distribution if $\int_{- \infty}^{+ \infty} | Φ (x) - Φ_{T^{'}} (x | x_{i j}, (i, j) \in U \cup ℛ; d_{i} \leq b_{i}) | d x$ is minimum for any real number x.

According to Definition 3, we formulate the following cross entropy chance distribution model of the DCMST problem for an uncertain random network, ${\begin{array}{l} \min_{{x_{i j}, (i, j) \in U \cup ℛ, d_{i} \leq b_{i}}} & \int_{- \infty}^{+ \infty} | Φ (x) - Φ_{T^{'}} (x | x_{i j}, \\ (i, j) \in U \cup ℛ; d_{i} \leq b_{i} | d x \\ subject to : \\ \sum_{(i, j) \in U \cup ℛ} x_{i j} = n - 1 \\ \sum_{(i, j) \in U \cup ℛ} x_{i j} \leq | S | - 1, & \forall S \subset N \\ 2 \leq | S | \leq n \\ \begin{array}{l} d_{i} \leq b_{i}, \forall i \in N \\ x_{i j} \in {0, 1}, \forall (i, j) \in U \cup ℛ . \end{array} \end{array}$ (2) where Φ (x) is the ideal chance distribution of the DCMST and $\begin{array}{l} Φ T^{'} (x |_{i} & x_{i j}, (i, j) \in U \cup ℛ; d_{i} \leq b) \\ = {\sum_{(i, j) \in U} x_{i j} τ_{i j} + \sum_{(i, j) \in ℛ} x_{i j} ξ_{i j},} \end{array}$ is the chance distribution of DCST for an uncertain random network.

Theorem 10. Let (N, U, R, W) be an uncertain random network, and let Φ (x) be its ideal chance distribution of the DCMST problem. Assume that uncertain weights are uncertain variables τ_ij with uncertainty distributions ϒ_ij for (i, j) ∈ U, and random weights are random variables ξ_ij with probability distributions Ψ_ij for (i, j) ∈ R, respectively. Then model (2) is equivalent to the following model: ${\begin{array}{l} \int_{- \infty}^{+ \infty} | Φ (x) - \int_{- \infty}^{+ \infty} ϒ & (x - \sum_{(i, j) \in ℛ} x_{i j} y_{i j}) d Ψ (y) | \\ subject to : \\ \sum_{(i, j) \in U \cup ℛ} x_{i j} = n - 1 \\ \sum_{(i, j) \in U \cup ℛ} x_{i j} \leq | S | - 1, & \forall S \subset N \\ 2 \leq | S | \leq n \\ \begin{array}{l} d_{i} \leq b_{i}, \forall i \in N \\ x_{i j} \in {0, 1}, \forall (i, j) \in U \cup ℛ . \end{array} \end{array}$ (3) where $\begin{matrix} Φ (x) = \int_{0}^{+ \infty} \dots \int_{0}^{+ \infty} F (x; y_{i j}, (i, j) \in ℛ, d_{i} \leq b_{i}) \\ \prod_{(i, j) \in ℛ} d Ψ i j (y_{i j}), \end{matrix}$ $Ψ (y) = \int^{} \sum^{} (i, j) \in x_{i j} y_{i j} \leq y \prod^{} (i, j) \in Ψ_{i j} (x_{i j} y_{i j}),$ and $ϒ (r) = \sup \sum^{} (i, j) \in x_{i j} r_{i j} = r (\min (i, j) \in ϒ_{i j} (x_{i j} r_{i j})) .$

Proof. According to Theorem 3, the weight of ideal chance distribution of the DCMST problem can be obtained by $\begin{matrix} Φ (x) = \int_{0}^{+ \infty} \dots \int_{0}^{+ \infty} F (x; y_{i j}, (i, j) \in ℛ, d_{i} \leq b_{i}) \\ \prod_{(i, j) \in ℛ} d Ψ i j (y_{i j}), \end{matrix}$ Based on Theorem 3, $Ch {\sum_{(i, j) \in U} x_{i j} τ_{i j} + \sum_{(i, j) \in ℛ} x_{i j} ξ_{i j} \leq x}$ is calculated by $\int_{- \infty}^{+ \infty} ϒ (x - \sum^{} (i, j) \in x_{i j} y_{i j}) Ψ (y)$ where $Ψ (y) = \int^{} \sum^{} (i, j) \in x_{i j} y_{i j} \leq y \prod^{} (i, j) \in Ψ_{i j} (x_{i j} y_{i j}),$ and $ϒ (r) = \sup \sum^{} (i, j) \in x_{i j} r_{i j} = r (\min (i, j) \in ϒ_{i j} (x_{i j} r_{i j})) .$ The theorem is completed.

5.2 Algorithm

This paper has proposed a cross entropy chance distribution model with respect to the DCMST problem for an uncertain random network. In general, it is difficult to solve the uncertain random programming model by classical algorithm. Next we propose the following algorithm to solve the DCMST problem for an uncertain random network.

Algorithm

Step 1: Calculate the ideal chance distribution of the DCMST problem for a given uncertain random network. Step 2: Using the genetic algorithm to find all the DCSTs in an uncertain random network, and calculate chance distribution of each DCST. Step 3: Calculate the cross entropy between the ideal chance distribution and chance distribution of each DCST. Step 4: Compare the cross entropy, choose the minimum value, and that corresponds to DCST is the DCMST.

6 Numerical experiment

This section will give an example to illustrate the cross entropy chance distribution model and Algorithm in the above. Assume that there is an uncertain random network (N, U, R, W) as shown in Fig. 6. Assume that the uncertain random network with 6 nodes and 10 edges, and the degree constraint of each node is 3. Assume that the uncertain weights τ₁₂, τ₁₆, τ₂₅, τ₃₄, τ₃₅, τ₃₆ are independent uncertain variables with regular uncertainty distributions ϒ₁₂, ϒ₁₆, ϒ₂₅, ϒ₃₄, ϒ₃₅, ϒ₃₆, and the random weights ξ₂₃, ξ₂₆, ξ₄₅, ξ₅₆ are independent random variables with probability distributions Ψ₂₃, Ψ₂₆, Ψ₄₅, Ψ₅₆, respectively. The values of weights are listed in Table 1, where U is uniformly random variable, Ł is linear uncertain variable, and $Z$ is zigzag uncertain variable. By Theorem 10, we can calculate the ideal chance distribution of the DCMST problem for the uncertain random network (N, U, R, W), that is $\begin{matrix} Φ (x) = \int_{0}^{+ \infty} \int_{0}^{+ \infty} \int_{0}^{+ \infty} \int_{0}^{+ \infty} F (x; y_{23}, y_{26}, y_{45}, \\ y_{56}, d_{i} \leq 3) Ψ_{23} (y_{23}) Ψ_{26} (y_{26}) \\ Ψ_{45} (y_{45}) Ψ_{56} (y_{56}) \end{matrix}$ where F (α ; y₂₃, y₂₆, y₄₅, y₅₆, d_i ≤ 3) is determined by its inverse uncertainty distribution $\begin{matrix} F^{- 1} (α; y_{23}, y_{26}, y_{45}, y_{56}, d_{i} \leq 3) \\ = & f (ϒ_{12}^{- 1} (α), ϒ_{16}^{- 1} (α), ϒ_{25}^{- 1} (α), ϒ_{34}^{- 1} (α), ϒ_{35}^{- 1} (α), \\ ϒ_{36}^{- 1} (α), y_{23}, y_{26}, y_{45}, y_{56}, d_{i} \leq 3), \end{matrix}$ and f can be calculated by the genetic algorithm for each given α.

Fig.6

An uncertain random network.

Table 1

Weights of the given network

edge(i, j)	τ _ij
(1, 2)	Ł(11, 13)
(1, 6)	$Z (11, 15, 19)$
(2, 5)	Ł(12, 16)
(3, 4)	$Z (21, 23, 25)$
(3, 5)	$Z (13, 16, 19)$
(3, 6)	Ł(24, 28)
edge(i, j)	ξ _ij
(2, 3)	U (11, 15)
(2, 6)	U (18, 22)
(4, 5)	U (21, 23)
(5, 6)	U (23, 25)

By Algorithm, we can find the DCMST as shown in Fig. 7.

Fig.7

The DCMST of uncertain random network.

7 Conclusion

This paper first proposed a new definition of cross entropy for uncertain random variables and derived a formula. This paper also introduced a generalized definition of cross entropy for uncertain random variables and discussed its properties. Moreover, this paper proposed a new cross entropy chance distribution model to formulate the DCMST problem for uncertain random network. This paper also proposed an algorithm to solve the cross entropy chance distribution model. Finally, we gave an example for the DCMST problem of an uncertain random network.

Footnotes

Acknowledgments

This work was supported by National Natural Science Foundation of China (Grant No. 61573210) and the Fundamental Research Funds for the Central Universities (No. 2016MS65).

References

Ahmadzade

, Gao

, Dehghan

M.H.

and Sheng

Y.H.

, Partial entropy of uncertain random variables, Journal of Intelligent and Fuzzy Systems 33 (2017), 105–112.

Ahmadzade

, Gao

, Dehghan

M.H.

and Ahmadi

, Partial triangular entropy of uncertain random variables and its application, Journal of Ambient Intelligence and Humanized Computing. DOI: 10.1007/s12652-017-0565-6

Ahmadzade

, Gao

and Zarei

, Partial quadratic entropy of uncertain random variables, Journal of Uncertain Systems 10(4) (2016), 292–301.

Borüvka

, O jistém problému minimálním, ce Mor Přírodovéd Spol v Brně, Pr’a 3 (1926), 37–58.

Bau

Y.T.

, Ho

C.K.

and Eve

H.T.

, Ant colony optimization approaches to the degree-constrained minimum spanning tree problem, Journal of Information Science and Engineering 24(4) (2008), 1081–1094.

Chen

X.W.

and Liu

, Existence and uniqueness theorem for uncertain differential equations, Fuzzy Optimization and Decision Making 9(1) (2010), 69–81.

Frank

and Hakimi

S.L.

, Probabilistic flows through a communication network, IEEE Transactions on Circuit Theory 12 (1965), 413–414.

Gao

J.W.

and Yao

, Some concepts and theorems of uncertain random process, International Journal of Intelligent Systems 30(1) (2015), 52–65.

Gao

and Jia

L.F.

, Degree-constrained minimum spanning tree problem with uncertain edge weights, Applied Soft Computing 56 (2017), 580–588.

10.

Gao

, Jia

L.F.

and Kar

, Degree-constrained minimum spanning tree problem of uncertain random network, of Ambient Intelligence and Humanized Computing, Journal 8(5) (2017), 747–757.

11.

Gao

, Jia

L.F.

and Kar

, A new definition of cross-entropy for uncertain variables, Soft Computing. 10.1007/s00500-017-2534-6

12.

Gao

and Yao

, Importance index of components in uncertain random systems, Knowledge-Based Systems 109 (2016), 208–217.

13.

Gao

and Ralescu

D.A.

, Convergence in distribution for uncertain random variables, IEEE Transactions on Fuzzy Systems. DOI: 10.1109/TFUZZ.2017.2724021

14.

Knowles

and Corne

, A new evolutionary approach to the degree-constrained minimum spanning tree problem, IEEE Transactions on Evolutionary Computation 4 (2000), 125–134.

15.

Liu

Uncertainty Theory, 2nd edn Springer-Verlag, Berlin 2007.

16.

Liu

, Fuzzy process, hybrid process and uncertain process, Journal of Uncertain Systems 2(1) (2008), 3–16.

17.

Liu

, Some research problems in uncertainty theory, Journal of Uncertain Systems 3(1) (2009), 3–10.

18.

Liu

Theory and Practice of Uncertain Programming 2nd ed, Berlin

Springer-Verlag

2009.

19.

Liu

, Uncertainty Theory: A Branch of Mathematics for Modeling Human Uncertainty Springer-Verlag, Berlin, 2010.

20.

Liu

, Uncertain random graph and uncertain random network, Journal of Uncertain Systems 8(1) (2014), 3–12.

21.

Liu

Y.H.

, Uncertain random variables: A mixture of uncertainty and randomness, Soft Computing 17(4) (2013), 625–634.

22.

Liu

Y.H.

, Uncertain random programming with applications, Fuzzy Optimization and Decision Making 12(2) (2013), 153–169.

23.

Liu

Y.H.

and Ralescu

D.A.

, Risk index in uncertain random risk analysis, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 22(4) (2014), 491–504.

24.

Liu

Y.H.

and Yao

, Uncertain random logic and uncertain random entailment, Journal of Ambient Intelligence and Humanized Computing 8 (2017), 695–706.

25.

Narula

S.C.

and Ho

C.A.

, Degree-constrained minimum spanning tree, Computers and Operations Research 7 (1980), 239–249.

26.

Raidl

G.R.

, An efficient evolutionary algorithm for the degreeconstrained minimum spanning tree problem, IEEE Transactions on Evolutionary Computation 1 (2000), 104–111.

27.

Sheng

Y.H.

, Qin

Z.F.

and Shi

, Minimum spanning tree problem of uncertain random network, Journal of Intelligent Manufacturing 28(3) (2017), 565–574.

28.

Sheng

Y.H.

and Gao

J.W.

, Chance distribution of the maximum flow of uncertain random network, Journal of Uncertainty Analysis and Applications 2 (2014), Article 15.

29.

Sheng

Y.H.

, Shi

and Ralescu

D.A.

, Entropy of uncertain random variables with application to minimum spanning tree problem, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 25(4) (2017), 497–514.

30.

Shi

, Sheng

Y.H.

and Cui

, Relative entropy model of uncertain random shortest path, International Journal of e-Navigation and Maritime Economy 2 (2015), 87–100.

31.

Torkestani

J.A.

, Degree-constrained minimum spanning tree problem in stochastic graph, Cybernetics and Systems 43(1) (2012), 1–21.

32.

Torkestani

J.A.

, A learning automata-based algorithm to the stochastic min-degree constrained minimum spanning tree problem, International Journal of Foundations of Computer Science 24(3) (2013), 329–348.

33.

Zhou

G.G.

and Gen

M.S.

, Approach to the drgree-constrained minimum spanning tree problem using genetic algorithm, Engineering Design and Automation 3 (1997), 157–165.

34.

Yao

and Gao

J.W.

, Law of large numbers for uncertain random variables, IEEE Transactions on Fuzzy Systems 24(3) (2016), 615–621.

35.

Zhang

, Wang

and Zhou

, Two uncertain programming models for inverse minimum spanning tree problem, Industrial Engineering and Management Systems 12(1) (2013), 9–15.

36.

Zhou

, He

and Wang

, Uncertain quadratic minimum spanning tree problem, Journal of Communications 9(5) (2014), 385–390.

37.

Zhou

, Chen

and Wang

, Path optimality conditions for minimum spanning tree problem with uncertain edge weights, International Journal of Uncertainty, Fuzziness & Knowledge-Based Systems 23(1) (2015), 49–71.

38.

Zhu

Y.G.

, Uncertain optimal control with application to a portfolio selection model, Cybernetics and Systems 41(7) (2010), 535–547.