基于PEV準則的I-UMOP問題求解方法

孟祥飛, 王 瑛, 亓 堯, 呂茂隆, 李 超

(空軍工程大學裝備管理與安全工程學院, 陜西 西安 710051)

0 引 言

經典的多目標規劃問題(multi-objective programming, MOP)是最優化理論的一個重要分支,在管理學、軍事學等領域具有廣泛的應用,并且取得了許多重要成果[1-3]。經典多目標規劃其主要解決的是確定環境下的決策問題。然而,在實際面臨的決策問題中,往往存在大量的不確定因素。例如,在進行電廠發電調度[4]或飛行流量優化時,需要考慮種種不確定因素,在此基礎上建立的調度模型是一個不確定多目標規劃模型。如何求解這類不確定多目標規劃問題具有重要的現實意義。

為解決該問題,學者們分別從不同角度刻畫這種不確定因素。一部分學者將這類不確定性因素看作是隨機因素,認為是隨機造成了不確定,于是針對概率論和統計學的研究蓬勃發展起來[5-6]。然而,其他學者認為隨機并不是造成不確定現象的唯一原因,現實世界中還存在一類不同于隨機性的不確定現象,即專家信度[7-9]。為解決這種帶有專家信度的多目標規劃問題,許多學者基于模糊集理論[10]和可能性測度[11],將其轉化為模糊多目標規劃問題進行研究,文獻[12]針對結構力學問題提出了基于測量數據的模糊分析方法。然而,當使用模糊變量描述專家信度時,可能會做出錯誤的決策[13-14]。為了更好地刻畫專家信度,文獻[15-17]建立了不確定理論,經過十多年的發展,已經形成了一個較為成熟的數學系統。因此,在處理帶有專家信度的實際多目標規劃問題時,可通過建立不確定多目標規劃(uncertain multi-objective programming problem,UMOP)模型再進行求解。通常情況下所建模型中目標函數之間是相互獨立的不確定多目標規劃(independent-uncertain multi-objective programming problem,I-UMOP)模型。

傳統求解方法往往是先將UMOP問題通過期望準則轉化為確定的MOP問題再進行求解,但在轉化過程中可能忽略了原問題的不確定性本質而且僅用期望準則難以反映不確定變量的波動性。鑒于此,本文首先通過不確定變量之間的序關系定義UMOP問題的有效解,然后基于序關系將其轉化為不確定單目標規劃問題,再進一步引入期望-方差準則將原問題轉化為確定的單目標規劃問題進行求解,最后證明求解得到的最優解是原UMOP問題的有效解。

1 求解方法基本框架

I-UMOP是指各個目標函數獨立的不確定多目標規劃問題,其模型為

(1)

式中,x∈Rn為決策變量;ξ1,ξ2,…,ξp為定義在不確定空間(Γ,L,M)上的不確定變量且相互獨立;η1,η2,…,ηm為定義在不確定空間(Γ,L,M)上的不確定變量且相互獨立。

期望-方差準則(PEV準則)[10]ξ和η是相互獨立的不確定變量,ξp=(p)η當且僅當E[ξ]≤(<)E[η]且V[ξ]≤(<)V[η]。其中,E[·]和V[·]分別表示不確定變量的期望與方差。

其中至少存在一個j0,1≤j0≤p,使得

求解UMOP問題首先是利用某種方法(構造實值可測函數F)將其轉化為不確定單目標問題,其表達式為

(2)

文獻[10]已經證明U(x,ξ)是一個不確定變量。在PEV準則下,將問題(2)轉化為確定的單目標規劃問題,其表達式為

(3)

問題(3)的最優解便是問題(1)的Pareto有效解。

2 相關引理證明

為證明問題(3)的最優解是問題(1)的Pareto有效解,在PEV準則下提出以下引理。

引理1ξ和η是分別服從正則不確定分布Φ和Ψ且相互獨立的不確定變量。若ξp=(p)η,則對于任意正實數λ,λξp=(p)λη成立。

證明由于ξp=(p)η,根據PEV準則,可得

E[ξ]≤(<)E[η]

(4)

V[ξ]≤(<)V[η]

(5)

根據不確定變量期望和方差計算公式,由式(4)、式(5),得

(6)

(7)

對于任意正實數λ,有

(8)

(9)

即

(10)

(11)

根據不確定變量的期望和方差的運算法則,有

E(λξ)≤(<)E(λη)

(12)

V(λξ)≤(<)V(λη)

(13)

即λξp=(p)λη成立。

證畢

引理2ξ1,ξ2是分別服從正則不確定分布Φ1,Φ2且相互獨立的不確定變量,η1,η2是分別服從正則不確定分布Ψ1,Ψ2且相互獨立的不確定變量。若ξ1p=η1,ξ2pη2或ξ1pη1,ξ2p =η2,則ξ1+ξ2pη1+η2成立。

證明不失一般性,以ξ1p=η1,ξ2pη2為例,根據PEV準則,可得

E(ξ1)≤E(η1)

(14)

V(ξ1)≤V(η1)

(15)

E(ξ2)

(16)

V(ξ2)

(17)

根據不確定變量的期望和方差計算公式,由式(14)～式(17),可得

(18)

(19)

(20)

(21)

式(18)與式(20)相加,可得

(22)

式(19)與式(21)相加,可得

(23)

根據不確定變量的期望運算法則,有

E[ξ1+ξ2]

(24)

因ξ1,ξ2相互獨立,有

eξ1eξ2-eξ1eξ2-eξ2eξ1+eξ1eξ2=0

(25)

同理

(26)

根據式(23)、式(25)及式(26),有

(27)

即

(28)

(29)

V[ξ1+ξ2]

(30)

即ξ1+ξ2pη1+η2成立。

證畢

引理3ξ,η是分別服從正則不確定分布Φ和Ψ且相互獨立的不確定變量,且兩者下界ξ0,η0存在,記t0=min(ξ0,η0),若ξp=(p)η,則(ξ-t0)2p=(p)(η-t0)2成立。

證明由于ξp=(p)η,根據PEV準則,可得

E[ξ]≤(<)E[η]

(31)

即

(32)

因為ξ0,η0分別是不確定變量ξ,η的下界,即分別是Φ-1(α)和Ψ-1(α)的下界,于是

Φ-1(α)-t0≥0,Ψ-1(α)-t0≥0

根據式(32),可得

(33)

由于(ξ-t0)2和(η-t0)2分別關于ξ和η單調遞增,因此其逆分布分別為(Φ-1(α)-t0)2和(Ψ-1(α)-t0)2,根據期望計算公式,有

(34)

(35)

故

E[(ξ-t0)2]≤(<)E[(η-t0)2]

(36)

根據運算法則,有

V[(ξ-t0)2]=E{[(ξ-t0)2-E[(ξ-t0)2]]2}=

E{(ξ-t0)4-2E[(ξ-t0)2](ξ-t0)2+E2[(ξ-t0)2]}=

E[(ξ-t0)4]-2E2[(ξ-t0)2]+E2[(ξ-t0)2]=

E[(ξ-t0)4]-E2[(ξ-t0)2]

(37)

由式(37)可得

V[(η-t0)2]-V[(ξ-t0)2]=

E[(η-t0)4-(ξ-t0)4]-

(E[(η-t0)2]+E[(ξ-t0)2])

(E[(η-t0)2]-E[(ξ-t0)2])

(38)

根據式(38),有

E{[(η-t0)2+(ξ-t0)2][(η-t0)2-(ξ-t0)2]}-

E[(η-t0)2+(ξ-t0)2]E[(η-t0)2-(ξ-t0)2]=

[(Ψ-1(α)-t0)2-(Φ-1(1-α)-t0)2]}dα-

(39)

令

f(α)=(Ψ-1(α)-t0)2+(Φ-1(α)-t0)2,

h(α)=(Ψ-1(α)-t0)2-(Φ-1(1-α)-t0)2

兩者均為關于α的增函數,則原式化為

V[(η-t0)2]-V[(ξ-t0)2]=

(40)

引進輔助函數

(41)

對式(41)求導,可得

(42)

又G(0)=0,故G(1)≥0,即

V[(η-t0)2]-V[(ξ-t0)2]≥0

(43)

根據式(36)和式(43),有(ξ-t0)2p=(p)(η-t0)2成立。

證畢

證明由于ξp=(p)η,根據PEV準則,可得

E[ξ]≤(<)E[η]

(44)

根據不確定變量的期望的計算公式,可得

(45)

(46)

即

(47)

又

(48)

根據引理3關于方差部分的推導過程,有

(49)

證畢

3 有效解證明

將UMOP問題如式(1)轉化為不確定單目標規劃問題如式(2)的過程,通常采用線性加權法或理想點法。分別就兩種方法證明其解的有效性。

3.1 線性加權法

線性加權法是通過對每個目標函數賦予相應的權值并線性加權求和將問題(1)轉換得到的等價的問題模型為

(50)

定理1問題(50)在PEV準則下求解的最優解是問題(1)的PEV—Pareto有效解。

且存在至少一個i0,1≤i0≤p,使得

(51)

(52)

即

(53)

于是

(54)

由定義1可知,x*不是問題(50)的最優解。這與假設矛盾,因此假設不成立,即x*是問題(1)在PEV準則下的Pareto有效解。

證畢

3.2 理想點法

理想點法是通過最小化各目標函數與理想點之間的距離之和將問題(1)轉化為等價的問題模型為

(55)

定理2問題(55)在PEV準則下求解的最優解是問題(1)的PEV—Pareto有效解。

且存在至少一個i0,1≤i0≤p,使得

(56)

(57)

即

(58)

當i≠i0時,有

(59)

根據引理2,有

(60)

(61)

即

(62)

根據引理4,有

(63)

(64)

即

(65)

于是

(66)

由定義1可知,x*不是問題(55)的最優解。這與假設矛盾,因此假設不成立,即x*是問題(1)在PEV準則下的Pareto有效解。

證畢

4 數值算例

4.1 算例1

為驗證求解方法的可行性和有效性,設計了一個不確定多目標規劃問題如式(67),問題中各目標函數較復雜且約束條件不規則。其中x1,x2是連續的非負決策變量,ξ1,ξ2,ξ3,ξ4,ξ5,ξ6是相互獨立的不確定變量且分別服從不確定分布L(1,3),L(2,4),L(3,5),L(4,6),L(5,7),L(6,8);η1,η2是相互獨立的不確定變量且分別服從不確定分布Z(1,2,3),Z(2,3,4)。

(67)

利用線性加權法將不確定多目標規劃轉換成不確定單目標規劃,不妨令λ1=0.3,λ2=0.3,λ3=0.4,當權重變化時,可依然按此法求解。轉換結果如下:

不確定單目標規劃轉換成確定的單目標規劃,結果為

各不確定變量的分布及其逆分布見表1。

表1 各不確定變量的分布及其逆分布

模型進一步轉化為

其中

(2α-5)(x1+0.5)(cos(2x2)+1)+

(2α-6)(x2+0.5)(sin(2x1)+1)+35

(2α-8)(sin(2x1x2)+1)

考慮轉化后的目標函數仍非常復雜且局部極小點較多,因此采用文獻[18]中的GA-PSO算法進行求解。該算法的具體流程見圖1。GA算法以概率的方式進行選擇、交叉、變異算子操作,增強了PSO算法的全局尋優能力,提高了收斂速度。參數設置見表2。

圖1 GA-PSO算法流程圖Fig.1 Sketch map of GA-PSO algorithm

算法參數取值交叉概率pc0.6變異概率pm0.1學習因子c11.495學習因子c21.495進化次數maxgen1000種群規模popsize30粒子更新速度Vmax1粒子更新速度Vmin-1

解得x1=0.538 9,x2=2.599 4函數目標值為3.479 3。其收斂速度見圖2。從圖2中可以看出,大約在第850代時,迭代收斂。

圖2 線性加權模型求解收斂曲線Fig.2 Convergence curve of linear weighted method

線性加權法中各個目標函數的權重反映了決策者對各目標函數的偏重程度。當各權重發生變化時,期望和方差均會變化,導致轉化得到的單目標函數會變化,從而對結果產生一定的影響。當目標函數的權重發生變化時,可按照算例1中的步驟計算。

采用理想點法求解時,根據各目標函數關于其相關不確定變量的單調性,在可行域內分別計算出3個目標函數的下界:1.336 1,-4.738 7,-10.357 6,采用GA-PSO算法求解計算結果為x1=0.536 5,x2=2.562 7,目標函數值為2.938 6。收斂效果見圖3。從圖3中可以明顯看出,大約在第900代時,迭代收斂。

圖3 理想點模型求解收斂曲線Fig.3 Convergence curve of ideal point method

傳統求解方法是先將不確定多目標規劃問題通過期望準則轉化為確定的多目標規劃問題再進行求解。采用理想點法求解,計算3個確定目標函數的最小值,結果分別為2.297 3,2.580 9,-7.994 4.采用GA-PSO算法進行求解,并與本文提出的方法對比,見表3。

表3 兩種求解方法結果比較

如表3所示,傳統方法與本文的方法在求解I-UMOP問題時結果不太相同。其主要原因在于:一是本文提出的方法在求解時首先計算每個不確定目標的函數的最小值,在一定程度上保持了原問題的不確定性本質,傳統方法則首先計算轉化后確定的目標函數的最小值,更加注重原問題的多目標本質,而沒有考慮其不確定的本質;二是本文的方法是在期望-方差準則下求解,考慮了不確定變量的波動性,而傳統方法是在期望準則下求解,沒有考慮不確定變量的波動性。因此,雖然兩種方法都可以對I-UMOP問題進行求解,且運算量相差不大,但是本文的方法更加注重保持問題的不確定本質和不確定變量的波動性。

4.2 算例2

(68)

采用理想點法將問題(68)轉化為單目標問題,并利用文獻[19]的二進制狼群算法進行求解,其算法流程見文獻[19],參數設置見表4。

表4 二進制狼群算法參數設置

分別對3個目標函數進行優化求解,得到各目標價值的最優解如表5所示。

表5 各個目標價值的單目標最優解上限值

表5中,最優解向量分別為

采用二進制狼群算法求解,其收斂效果如圖4所示。從圖4中可以看出,算法在第162代左右收斂,并且收斂于0.895，求解得到最優解為IB。

圖4 二進制狼群算法求解不確定背包問題收斂圖Fig.4 Convergence of uncertain knapsack problem solving by binary wolf pack algorithm

具體求解結果見表6,表中給出了各個目標函數的最優解、本文方法計算得到的最優解和傳統方法計算得到的最優解。經過對比,本文方法計算的最優解綜合考慮了各個單目標價值的理想屬性,并且在保持原問題不確定性本質的基礎上計算得到該算例的帕累托最優解。

表6 不確定多目標背包算例優化求解結果

5 結 論

傳統求解UMOP問題有以下兩點不足:其一,傳統方法容易忽略原問題的不確定性,而且當各個目標之間含有相同的不確定變量時,這種方法割裂了各個不確定目標之間的相關性;其二,傳統方法僅用期望值作為轉化準則難以反映原目標函數作為一個不確定變量的波動性。鑒于此,本文首先通過引入不確定變量之間的序關系定義了I-UMOP問題的有效解,然后基于序關系將其轉化為不確定單目標規劃解決第一個問題,進一步通過引入期望-方差準則將原問題轉化為確定的單目標規劃解決了第二個問題,并證明了求解得到的最優解解是原問題的有效解。最后,設計了兩類數值算例,并分別利用GA-PSO算法和二進制狼群算法進行求解,結果表明本文提出的求解方法是可行且有效的。

[1] MIETTINEN K. Nonlinear multiobjective optimization[M]. Dordrecht: Kluwer Academic Press, 1998.

[2] PADHAN S K, NAHAK C. Higher-order symmetric duality in multiobjective programming problems under higher-order invexity[J].Applied Mathematics and Computation, 2011,218(5): 1705-1712.

[3] LAI H C, HO S C. Optimality and duality for nonsmooth multiobjective fractional programming problems involving exponential VV-rr-invexity[J]. Nonlinear Analysis, 2012, 75(6): 3157-3166.

[4] KOU Y N, ZHENG J H, LI Z G. Many-objective optimization for coordinated operation of integrated electricity and gas network[J]. Journal of Modern Power Systems and Clean Energy, 2017, 5(3): 350-363.

[5] PAVAN K Y V, BHIMASINGU R. Renewable energy based microgrid system sizing and energy management for green buil-dings[J]. Journal of Modern Power Systems and Clean Energy, 2015, 3(1): 1-13.

[6] STANCU-MINASIAN I M. Stochastic programming with multiple objective functions[J]. Mathematical Reports, 1984, 27(1): 49-67.

[7] WANG Z T, GUO J S, ZHENG M F, et al. A new approach for uncertain multi-objective programming problem based on PE principle[J]. Journal of Industrial and Management Optimization, 2015, 11(1): 13-26.

[8] XIE G H, ZHANG J S, LIU R G. Application of matrix-based system reliability method in complex slopes[J]. Journal of Central South University, 2013, 20(3): 812-820.

[9] LIU B D. Why is there a need for uncertainty theory[J]. Journal of Uncertain Systems, 2012, 6(1): 3-10.

[10] 王族統.基于不確定理論的多目標規劃方法及其應用研究[D]. 西安: 空軍工程大學, 2015.

WANG Z T. Research on multi-objective programming and apply based on uncertainty theory[D]. Xi’an: Air Force Engineering University, 2015.

[11] LIU B D. Uncertainty distribution and independence of uncertain processes[J]. Fuzzy Optimization and Decision Making, 2014, 8(1): 3-12.

[12] ZHAO J S, QIU X Y, MA J M, et al. Multi-objective optimization method of microgrid based on fuzzy clustering analysis and model recognition[J].Power System Technology, 2016, 40(8): 2316-2323.

[13] ZADEH L A. Fuzzy sets as a basis for a theory of possibility[J]. Fuzzy Sets and Systems, 1978, 1(1): 3-28.

[14] 王曉軍, 楊海峰, 邱志平, 等. 基于測量數據的不確定性結構分析的模糊理論[J]. 北京航空航天大學學報, 2010, 36(8): 887-891.

WANG X J, YANG H F, QIU Z P, et al. Fuzzy theory for uncertain structural analysis based on measurement data[J]. Journal of Beijing University of Aeronautics and Astronautics, 2010, 36(8): 887-891.

[15] WANG Z T, GUO J S, ZHENG M F, et al. Uncertain multi-objective travelling salesman problem[J]. European Journal of Operational Research, 2015, 241(2): 478-479.

[16] LIU B D, YAO K. Uncertain multilevel programming: algorithm and applications[J]. Computers & Industrial Engineering, 2015, 89: 235-240.

[17] LIU B D. Uncertainty theory[M]. 5th ed. Berlin: Springer-Verlag, 2016.

[18] 劉瓊,劉煒琪,張超勇.基于GA-PSO的多目標混流裝配線排序問題[J].華中科技大學學報(自然科學版),2011,39(10):1-5.

LIU Q, LIU W Q, ZHANG C Y. Hybrid GA-PSO algorithm for sequencing multi objective mixed-model assembly lines[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2011, 39(10):1-5.

[19] 吳虎勝, 張鳳鳴, 戰仁軍, 等. 利用改進的二進制狼群算法求解多維背包問題[J]. 系統工程與電子技術, 2015, 37(5): 1084-1091.

WU H S, ZHANG F M, ZHAN R J, et al. Improved binary wolf pack algorithm for solving multidimensional knapsack problem[J].System Engineering and Electronics,2015,37(5):1084-1091.