Orsc.edu.cn

Bifuzzy Programming and Hybrid Intelligent Algorithms Uncertainty Theory Laboratory, Department of Mathematical Sciences Tsinghua University, Beijing 100084, China Abstract: A bifuzzy variable is a function from a pos- puter and computational intelligence, many new complex sibility space to the set of fuzzy variables. In this pa- optimization problems can be processed by digital com- per, in order to solve the optimization problems with puters. Thus Liu and Iwamura [9][10] and Liu [11] con- bifuzzy information, bifuzzy programming models are structed a generally-theoretical framework of CCP with- presented originally including the bifuzzy expected value out linearity assumption. Furthermore, following the model, bifuzzy chance-constrained programming, and bi- idea of stochastic DCP, Liu [14] provided the DCP the- fuzzy dependent-chance programming. For solving these ory in fuzzy environments. Especially, Liu and Liu [20] models efficiently, some hybrid intelligent algorithms are presented a new concept of expected value operator of designed and illustrated by several numerical examples.
fuzzy variable and provided a spectrum of fuzzy EVM.
Keywords: fuzzy variable, bifuzzy variable, bifuzzy pro- In many cases, fuzziness and randomness simultane- ously appear in decision systems. Fuzzy random pro-gramming is the theory dealing with optimization prob- lems in fuzzy random environments, and has been madein several ways. We have the theoretical framework of Decisions are usually made in uncertain environments.
fuzzy random EVM (Liu and Liu [25]), fuzzy random In order to solve the optimization problems with uncer- CCP (Liu [17]), and fuzzy random DCP (Liu [18]). As tain information, uncertainty theory and uncertain pro- opposed to fuzzy random variable, Liu [19] introduced gramming are demanded. Before discussing bifuzzy op- a random fuzzy variable defined as a function from a timization theory, let us recall stochastic programming.
possibility space to the set of random variables. Ran- With the requirement of considering randomness, ap- dom fuzzy programming includes random fuzzy EVM propriate formulations of stochastic programming have (Liu and Liu [24]), random fuzzy CCP (Liu [19]), and been developed to suit the different purposes of manage- ment. The first type of stochastic programming is the so-called expected value model (EVM), which optimizes the Recently, as an extension of fuzzy variable, Liu [21] expected objective functions subject to some expected initialized a bifuzzy variable as a function from a possi- constraints. The second, chance-constrained program- bility space to the set of fuzzy variables, i.e., a fuzzy set ming (CCP), was pioneered by Charnes and Cooper [4] on the universal set of fuzzy variables. Following that, as a means of handling uncertainty by specifying a confi- Liu [23] and Zhou and Liu [30] discussed the mathemat- dence level at which it is desired that the stochastic con- ical properties of bifuzzy variable in detail.
straint holds. The third type of uncertain programming,dependent-chance programming (DCP), was initiated by In order to model the optimization problems with Liu [8] as a tool of maximizing the chance functions of bifuzzy information, in this paper, we try to build a the- satisfying some events in stochastic environments.
oretic spectrum of bifuzzy programming. The paper is Fuzzy programming offers a powerful means of han- organized as follows. In section 2, some definitions and dling optimization problems with fuzzy factors. Fuzzy results about possibility space and bifuzzy variables are programming has been used in different ways in the recalled. Three types of bifuzzy programming, i.e., bi- past, for example, Buckley [1][2][3], Inuiguichi et al. [5], fuzzy EVM, bifuzzy CCP and bifuzzy DCP are provided Inuiguchi and Ram´ik [6], Ostasiewicz [26], Ram´ik and according to different criteria in Section 3, 4 and 5, re- Rommelfanger [27], Tanaka et al. [28] and Yazenin [29].
spectively. For solving these models more effectively, we However, with the development of more effective com- integrate bifuzzy simulations, neural network (NN) andgenetic algorithm (GA) to produce some hybrid intelli-gent algorithms in Section 6. Finally, Section 7 presented Proceedings of the 2nd International Conference on Informationand Management Sciences, Chengdu, China, August 24-30, pp. 440 three numerical experiments to show the efficiency of the bifuzzy programming and hybrid intelligent algorithms Before discussing the theory of bifuzzy programming, let In this section, we will present three types of bifuzzy us recall some knowledge about possibility space and bi- programming: bifuzzy EVM, bifuzzy CCP and bifuzzy Let Θ be a nonempty set, and P(Θ) be the power set of Θ. For each set A ∈ P(Θ), there is a nonnegative number Pos{A}, called its possibility, such that (i) Pos{∅} = 0, Pos{Θ} = 1; and Suppose that ξ and η are bifuzzy variables. In order to rank ξ and η, the following ranking criteria are suggested kAk} = supk Pos{Ak} for any arbitrary by employing the concepts of the expected value, opti- The triplet (Θ, P(Θ), Pos) is called a possibility space, mistic and pessimistic values, and α-chance of bifuzzy and the function Pos is referred to as a possibility mea- sure. Furthermore, the credibility measure Cr was de-fined by Liu and Liu [20] as Cr{A} = (Pos{A} + 1 − (i) We say ξ > η if and only if E[ξ] > E[η], where E is Pos{Ac})/2. Note that the credibility measure has self the expected value operator of bifuzzy variable.
duality, i.e., Cr{A} + Cr{Ac} = 1.
In order to describe bifuzzy phenomena, Liu [21] pro- (ii) We say ξ > η if and only if, for some predetermined vided the concept of bifzzy variable defined as a function confidence levels γ, δ ∈ (0, 1], we have ξsup(γ, δ) > from a possibility space (Θ, P(Θ), Pos) to the set of fuzzy ηsup(γ, δ), where ξsup(γ, δ) and ηsup(γ, δ) are the variables. Then the expected value E[ξ] is defined by (γ, δ)-optimistic values to ξ and η, respectively.
(iii) We say ξ > η if and only if, for some prede- termined confidence levels γ, δ ∈ (0, 1], we have Cr{θ ∈ Θ | E[ξ(θ)] ≥ r}dr ξinf(γ, δ) > ηinf(γ, δ), where ξinf(γ, δ) and ηinf(γ, δ) are the (γ, δ)-pessimistic values to ξ and η, respec- Cr{θ ∈ Θ | E[ξ(θ)] ≤ r}dr (iv) We say ξ > η if and only if Ch{ξ ≥ r}(γ) > Ch{η ≥ provided that at least one of the two integrals is finite, r}(γ) for some predetermined levels r and γ ∈ (0, 1].
where E[ξ(θ)] is the expected value of fuzzy variable ξ(θ),defined by Liu and Liu [20] as EVM is to optimize some expected objective functions Cr{ξ(θ) ≥ r}dr − Cr{ξ(θ) ≤ r}dr. subject to some expected constraints, for example, mini- mizing expected cost, maximizing expected profit, and so Following that, in order to measure a bifuzzy event ξ ∈ forth. According to the first ranking criterion for bifuzzy B, the primitive chance was proposed in Liu [21], and variables, we may obtain the following single-objective  max E[f (x, ξ)] = sup β Cr θ ∈ Θ Cr {ξ(θ) ∈ B} ≥ β ≥ α . Note that the primitive chance is a function rather than a number. In addition, the α-chance of bifuzzy event j (x, ξ)] ≤ 0, j = 1, 2, · · · , p. ξ ∈ B is defined as the value of primitive chance at α, In practice, a decision maker may want to optimize i.e., Ch{ξ ∈ B}(α) by Zhou and Liu [30].
multiple objectives. Thus we have the following bifuzzy Moreover, Liu [21] defined the (γ, δ)-optimistic value  max [E[f1(x, ξ)], E[f2(x, ξ)], · · · , E[fm(x, ξ)]] r Ch {ξ ≥ r} (γ) ≥ δ , and defined the (γ, δ)-pessimistic value to ξ as E[gj(x, ξ)] ≤ 0, j = 1, 2, · · · , p ξinf(γ, δ) = inf r Ch {ξ ≤ r} (γ) ≥ δ . where fi(x, ξ) are objective functions for i = 1, 2, · · · , m.
When the fourth bifuzzy ranking criterion is em- ployed, we may formulate a bifuzzy DCP as follows, As the second type of uncertain programming, CCP of- fers a powerful means of modeling uncertain decision sys- k(x, ξ) ≤ 0, k = 1, 2, · · · , q} (α) tems with assumption that the uncertain constraints will hold with a confidence level provided as an appropriate safety margin by the decision-maker.
gj(x, ξ) ≤ 0, j = 1, 2, · · · , p By employing the second ranking criterion for bi- fuzzy variables, the objective is to maximize f instead where the event E is characterized by hk(x, ξ) ≤ 0, k = of f (x, ξ) with a chance constraint as follows, 1, 2, · · · , q, and the uncertain environment is describedby the bifuzzy constraints gj(x, ξ) ≤ 0, j = 1, 2, · · · , p.
Ch f (x, ξ) ≥ f (γ) ≥ δ where γ and δ are the predetermined confidence levels,and max f is the (γ, δ)-optimistic value to the return Generally speaking, uncertain programming models are function f (x, ξ). As a result, the following bifuzzy max- difficult to solve by traditional methods. A good way is to design some hybrid intelligent algorithms for solv-ing them (see Iwamura and Liu [7], Liu [8][11][12][13], grate bifuzzy simulations, NN and GA to produce some hybrid intelligent algorithms for solving general bifuzzy Ch f (x, ξ) ≥ f (γ) ≥ δ j (x, ξ) ≤ 0} (αj ) ≥ βj By uncertain functions we mean the functions with bi- j = 1, 2, · · · , p. fuzzy parameters. In order to solve bifuzzy program-ming models, we have to compute the uncertain func- On the other hand, according to the third ranking tions. Due to the complexity, Zhou and Liu [30] designed criterion for bifuzzy variables, we consider minimizing some bifuzzy simulations to calculate them.
the (γ, δ)-pessimistic value min f to the return function f (x, ξ) with the following chance constraint, U1 : x → E[f(x, ξ)] Ch f (x, ξ) ≤ f (γ) ≥ δ. where ξ is an n-dimensional bifuzzy vector on the pos-sibility space (Θ, P(Θ), Pos). In order to compute it, a Hence we have the following bifuzzy minimax CCP bifuzzy simulation was designed by Zhou and Liu [30] as Pos{θk} ≥ ε, k = 1, 2, · · · , N, where ε is a suffi- Ch f (x, ξ) ≤ f (γ) ≥ δ j (x, ξ) ≤ 0} (αj ) ≥ βj Step 3. Compute E[f (x, ξ(θ k = 1, 2, · · · , N , respectively.
j = 1, 2, · · · , p. Step 4. Let a = min1≤k≤N E[f(x, ξ(θk))] and b = max1≤k≤N E[f(x, ξ(θk))].
Step 5. Randomly generate r from [a, b].
In practice, there usually exist multiple events in a com-plex bifuzzy decision system. Sometimes, the decision- maker wishes to maximize the chance functions of these E ← E + Cr{θ ∈ Θ E[f (x, ξ(θ))] ≥ r}, events. In order to model this type of bifuzzy deci-sion systems, we introduce the DCP theory initiated by where fuzzy simulation is used to calculate Cr{θ ∈ Liu [8] into the bifuzzy environments in this section.
Θ|E[f (x, ξ(θ))] ≥ r}.
bifuzzy programming and hybrid intelligent algorithms E ← E − Cr{θ ∈ Θ|E[f (x, ξ(θ))] ≤ r}, Although bifuzzy simulations are able to compute theuncertain functions like Ui, i = 1, 2, 3, however, bifuzzy where fuzzy simulation is used to obtain Cr{θ ∈ simulation is a time-consuming process. As we know, Θ|E[f (x, ξ(θ))] ≤ r}.
an NN is capable of approximating continuous and in-tegrable functions and has a high speed of operations.
Step 8. Repeat the fifth to seventh steps for N times.
Hence, in order to speed up the solution process, we Step 9. E[f (x, ξ)] = a ∨ 0 + b ∧ 0 + E · (b − a)/N .
first generate a training input-output data set for uncer-tain functions by bifuzzy simulations, then we train some feedforward NNs to approximate the uncertain functions.
Finally, the trained NNs are embedded into genetic al- U2 : x → max f Ch{f(x, ξ) ≥ f}(γ) ≥ δ gorithm to produce some hybrid intelligent algorithms.
We summarize the process as follows.
which may be estimated by the following procedure, Step 1. Generate training input-output data for uncer- k from Θ such that Pos{θk} ≥ ε, and tain functions by bifuzzy simulations.
k = Pos{θk}, k = 1, 2, · · · , N , respectively, where ε is a sufficiently small number.
Step 2. Train some neural networks to approximate Step 2. Obtain the maximal value f (θk) such that the uncertain functions according to the generated Cr{f (x, ξ(θk)) ≥ f(θk)} ≥ δ by fuzzy simulation, k = 1, 2, · · · , N , respectively.
Step 3. Initialize pop size chromosomes whose feasibil- Step 3. Find the maximal value r such that L(r) ≥ γ ity may be checked by the trained neural networks.
Step 4. Update the chromosomes by crossover and mu- tation operations in which the feasibility of offspring may be checked by the trained neural networks.
1 − νk f(θk) < r Step 5. Calculate the objective values for all chromo- somes by the trained neural networks.
Step 6. Compute the fitness of each chromosome ac- U3 : x → Ch{hk(x, ξ) ≤ 0, k = 1, 2, · · · , q}(α) Step 7. Select the chromosomes by spinning the which may be estimated by the following bifuzzy simu- Step 8. Repeat the fourth to seventh steps for a given k from Θ such that Pos{θk} ≥ ε, and write νk = Pos{θk}, k = 1, 2, · · · , N, respectively,where ε is a sufficiently small number.
Step 9. Report the best chromosome as the optimal so- Step 2. Compute h(θk) = Cr{hk(x, ξ(θk)) ≤ 0, k = 1, 2, · · · , q} by using fuzzy simulation, 1, 2, · · · , N , respectively.
Step 3. Find the maximal value r such that L(r) ≥ α holds, where L(r) is defined by In order to illustrate the effectiveness of the proposedhybrid intelligent algorithms, in this section, a set of nu- merical examples has been done, and the results are suc- cessful, which are all performed on a personal computer with the following parameters: the population size is 30, the probability of crossover Pc is 0.3, the probability ofmutation Pm is 0.2, and the parameter a in the rank- Example 1: Now we consider the following bifuzzy where F (x) = ξ1x1+ξ2x2+ξ3x3+ξ4x4. Then we train an NN (3 input neurons, 6 hidden neurons, 1 output neuron) to approximate the uncertain function U . Finally, the (x1 − ξ1)2 + (x2 − ξ2)2 + (x3 − ξ3)2 trained NN is embedded into a GA to produce a hybridintelligent algorithm.
A run of the hybrid intelligent algorithm (3000 cycles |x1| + |x2| + |x3| ≤ 1 in bifuzzy simulation, 2000 data in NN, 500 generations in GA) shows that the optimal solution is 1, ξ2 and ξ3 are defined as 1 = (ρ1 − 1, ρ1, ρ1 + 1), with ρ1 = (−2, −1, 0), x∗2 = 0.8933, x∗3 = 1.4846, x∗4 = 3.1632 ξ2 = (ρ2 − 1, ρ2, ρ2 + 1), with ρ2 = (−1, 0, 1), ξ3 = (ρ3 − 1, ρ3, ρ3 + 1), with ρ3 = (0, 1, 2). Example 3: This is a bifuzzy DCP model which maxi- In order to solve this model, we generate input- mizes the chance function subject to a deterministic con- 1 − ξ1)2 + (x2 − ξ2)2 + (x3 − ξ3)2 1x1 + ξ2x2 + ξ3x3 ≥ 5} (0.9) by a bifuzzy simulation. Then we train an NN (3 in-put neurons representing decision variables x 3, 5 hidden neurons, 1 output neuron representing the x1, x2, x3 ≥ 0 expected value function) to approximate the uncertainfunction U . After that, the trained NN is embedded into where ξ1, ξ2 and ξ3 are bifuzzy variables defined as a GA to produce a hybrid intelligent algorithm.
A run of the hybrid intelligent algorithm (3000 cycles (x) = [1 − (x − 1)2] ∨ 0, in bifuzzy simulation, 2000 data in NN, 1000 generations (x) = [1 − (x − 2)2] ∨ 0, in GA) shows that the optimal solution is µξ = exp[−|x − ρ3|], µρ (x) = [1 − (x − 3)2] ∨ 0. x∗2 = 0.0000, x∗3 = 0.4797 In order to solve the model, we generate input-output Example 2: Let us consider the following bifuzzy max- 1x1 + ξ2x2 + ξ3x3 ≥ 5} (0.9) by bifuzzy simulation. Then we train an NN (3 input neurons, 4 hidden neurons, 1 output neuron) to approxi- mate the uncertain function U . Furthermore, the trained NN is embedded into a GA to produce a hybrid intelli- 1x1 + ξ2x2 + ξ3x3 + ξ4x4 ≥ f 1 + x2 + x3 + x4 ≤ 6 A run of the hybrid intelligent algorithm (5000 cycles in bifuzzy simulation, 2000 data in NN, 500 generations 1, x2, x3, x4 ≥ 0 in GA) shows that the optimal solution is where the bifuzzy variables ξ1, ξ2, ξ3 and ξ4 are definedas x∗1 = 0.7462, x∗2 = 1.1493, x∗3 = 1.4568 ξ1 = (ρ1 − 1, ρ1, ρ1 + 1), µρ (x) = [1 − (x − 1)2] ∨ 0, ξ2 = (ρ2 − 2, ρ2, ρ2 + 2), µρ (x) = [1 − (x − 2)2] ∨ 0, 3 = (ρ3 − 3, ρ3, ρ3 + 3), µρ (x) = [1 − (x − 3)2] ∨ 0, ξ4 = (ρ4 − 4, ρ4, ρ4 + 4), µρ (x) = [1 − (x − 4)2] ∨ 0. In this paper, we have contributed to the research area In order to solve the model, we first employ the bi- of bifuzzy optimization theory in the following three as- fuzzy simulation technique to generate input-output data (i) Three types of bifuzzy programming models — EVM,CCP and DCP — were proposed according to different U (x) = max{f Ch F (x) ≥ f (0.95) ≥ 0.90}, bifuzzy programming and hybrid intelligent algorithms (ii) To solve these models efficiently, we integrated bi- [17] Liu, B., Fuzzy random chance-constrained programming, fuzzy simulations, NN and GA to produce some hybrid IEEE Transactons on Fuzzy Systems, Vol. 9, No. 5, 713-720, [18] Liu, B., Fuzzy random dependent-chance programming, IEEE (iii) Three numerical examples were provided to show Transactons on Fuzzy Systems, Vol. 9, No. 5, 721-726, 2001.
the efficiency of the proposed algorithms.
[19] Liu, B., Theory and Practice of Uncertain Programming, [20] Liu, B., and Liu, Y.-K., Expected value of fuzzy variable and fuzzy expected value models, IEEE Transactions on FuzzySystems, Vol. 10, No. 4, 445-450, 2002.
This work was supported by National Natural Science [21] Liu, B., Toward fuzzy optimization without mathematical am- Foundation of China Grant No.69804006, and Sino- biguity, Fuzzy Optimization and Decision Making, Vol. 1, No.
1, 43-63, 2002.
French Joint Laboratory for Research in Computer Sci- [22] Liu, B., Random fuzzy dependent-chance programming and ence, Control and Applied Mathematics(LIAMA).
its hybrid intelligent algorithm, Information Sciences, Vol.
141, No. 3-4, 259-271, 2002.
[23] Liu, B., Uncertainty Theory, Lecture Note, Tsinghua Univer- [24] Liu, Y.-K., and Liu, B., Expected value operator of ran- [1] Buckley, J.J., Possibility and necessity in optimization, Fuzzy dom fuzzy variable and random fuzzy expected value mod- Sets and Systems, Vol. 25, 1-13, 1988.
els, International Journal of Uncertainty, Fuzziness and [2] Buckley, J.J., Stochastic versus possibilistic programming, Knowledge-Based Systems, Vol. 11, No. 2, 195-215, 2003.
Fuzzy Sets and Systems, Vol. 34, 173-177, 1990.
[25] Liu, Y.-K., and Liu, B., A class of fuzzy random optimiztion: [3] Buckley, J.J., Multiobjective possibilistic linear programming, expected value models, Information Sciences, to be published.
Fuzzy Sets and Systems, Vol. 35, 23-28, 1990.
[26] Ostasiewicz, W., A new approach to fuzzy programming, [4] Charnes, A., and Cooper, W.W., Chance-constrained pro- Fuzzy Sets and Systems, Vol. 7, 139-152, 1982.
gramming, Management Science, Vol. 6, No. 1, 73-79, 1959.
[27] Ram´ik, J., and Rommelfanger, H., Fuzzy mathematical pro- [5] Inuiguchi, M., Ichihashi, H., and Kume, Y., Modality con- gramming based on some inequality relations, Fuzzy Sets and strained programming problems: an unified approach to fuzzy Systems, Vol. 81, 77-88, 1996.
mathematical programming problems in the setting of possi- [28] Tanaka, H., Guo, P., and Zimmermann, H.-J., Possibility dis- bility theory, Information Sciences, Vol. 67, 93-126, 1993.
tribution of fuzzy decision variables obtained from possibilistic [6] Inuiguchi, M., and Ram´ik, J., Possibilistic linear program- linear programming problems, Fuzzy Sets and Systems, Vol.
ming: a brief review of fuzzy mathematical programming and a comparison with stochastic programming in portfolio selec- [29] Yazenin, A.V., On the problem of possibilistic optimization, tion problem, Fuzzy Sets and Systems, Vol. 111, No. 1, 3-28, Fuzzy Sets and Systems, Vol. 81, 133-140, 1996.
[30] Zhou, J., and Liu, B., Analysis and algorithms of bifuzzy [7] Iwamura, K., and Liu, B., Chance-constrained integer pro- gramming for capital budgeting in fuzzy environments, Jour-nal of the Operational Research Society, Vol. 49, No. 8, 854-860, 1998.
[8] Liu, B., Dependent-chance programming: a class of stochastic Baoding Liu has been a full Professor at Tsinghua University optimization, Computers and Mathematics with Applications, since 1998. He graduated from the Nankai University in 1986, and received the M.S. and Ph.D. degrees from Chinese Academy of [9] Liu, B., and Iwamura, K., Chance-constrained programming Sciences in 1989 and 1993, respectively. His current research in- with fuzzy parameters, Fuzzy Sets and Systems, Vol. 94, No.
terests include uncertainty theory, stochastic programming, fuzzy programming, rough programming, intelligent systems, and appli- [10] Liu, B., and Iwamura, K., A note on chance-constrained pro- cations in inventory, scheduling, reliability, project management, gramming with fuzzy coefficients, Fuzzy Sets and Systems, and engineering design. He is the author of 5 books, including Theory and Practice of Uncertain Programming (Physica-Verlag, [11] Liu, B., Minimax chance-constrained programming models for 2002), Uncertain Programming (Wiley, 1999), and Decision Cri- fuzzy decision systems, Information Sciences, Vol. 112, Nos.
teria and Optimal Inventory Processes (Kluwer, 1999). Dr. Liu is now serving on the editorial boards of IEEE Transactions on Fuzzy [12] Liu, B., Dependent-chance programming with fuzzy decisions, Systems, Information: An International Journal, Fuzzy Optimiza- IEEE Transactions on Fuzzy Systems, Vol. 7, No. 3, 354-360, tion and Decision Making, Asian Information-Science-Life, and International Journal of Internet and Enterprise Management.
[13] Liu, B., Uncertain Programming, John Wiley and Sons, New [14] Liu, B., Dependent-chance programming in fuzzy environ- Jian Zhou is a Ph.D. student at the Department of Mathemati- ments, Fuzzy Sets and Systems, Vol. 109, No. 1, 97-106, 2000.
cal Sciences, Tsinghua University. She received the B.S. and M.S.
[15] Liu, B., and Iwamura, K., Topological optimization models for degrees from Tsinghua University in 1998 and 2000, respectively.
communication network with multiple reliability goals, Com- Her research interests include Theory of Optimization under Un- puters & Mathematics with Applications, Vol. 39, 59-69, 2000.
certainty, Intelligent Systems, and Facility Location Problem. She [16] Liu, B., and Iwamura, K., Fuzzy programming with fuzzy has published 11 papers in national and international conferences decisions and fuzzy simulation-based genetic algorithm, Fuzzy and journals. For the other information about her, please visit her Sets and Systems, Vol. 122, No. 2, 253-262, 2001.
homepage titled “Qing Wu Ju” at http://orsc.edu.cn/∼zhoujian/.

Source: http://www.orsc.edu.cn/~zhoujian/english/research/files/Bifuzzyprogramming.pdf