孟祥飛, 王 瑛, 亓 堯, 呂茂隆, 李 超
(空軍工程大學(xué)裝備管理與安全工程學(xué)院, 陜西 西安 710051)
經(jīng)典的多目標(biāo)規(guī)劃問題(multi-objective programming, MOP)是最優(yōu)化理論的一個(gè)重要分支,在管理學(xué)、軍事學(xué)等領(lǐng)域具有廣泛的應(yīng)用,并且取得了許多重要成果[1-3]。經(jīng)典多目標(biāo)規(guī)劃其主要解決的是確定環(huán)境下的決策問題。然而,在實(shí)際面臨的決策問題中,往往存在大量的不確定因素。例如,在進(jìn)行電廠發(fā)電調(diào)度[4]或飛行流量優(yōu)化時(shí),需要考慮種種不確定因素,在此基礎(chǔ)上建立的調(diào)度模型是一個(gè)不確定多目標(biāo)規(guī)劃模型。如何求解這類不確定多目標(biāo)規(guī)劃問題具有重要的現(xiàn)實(shí)意義。
為解決該問題,學(xué)者們分別從不同角度刻畫這種不確定因素。一部分學(xué)者將這類不確定性因素看作是隨機(jī)因素,認(rèn)為是隨機(jī)造成了不確定,于是針對概率論和統(tǒng)計(jì)學(xué)的研究蓬勃發(fā)展起來[5-6]。然而,其他學(xué)者認(rèn)為隨機(jī)并不是造成不確定現(xiàn)象的唯一原因,現(xiàn)實(shí)世界中還存在一類不同于隨機(jī)性的不確定現(xiàn)象,即專家信度[7-9]。為解決這種帶有專家信度的多目標(biāo)規(guī)劃問題,許多學(xué)者基于模糊集理論[10]和可能性測度[11],將其轉(zhuǎn)化為模糊多目標(biāo)規(guī)劃問題進(jìn)行研究,文獻(xiàn)[12]針對結(jié)構(gòu)力學(xué)問題提出了基于測量數(shù)據(jù)的模糊分析方法。然而,當(dāng)使用模糊變量描述專家信度時(shí),可能會(huì)做出錯(cuò)誤的決策[13-14]。為了更好地刻畫專家信度,文獻(xiàn)[15-17]建立了不確定理論,經(jīng)過十多年的發(fā)展,已經(jīng)形成了一個(gè)較為成熟的數(shù)學(xué)系統(tǒng)。因此,在處理帶有專家信度的實(shí)際多目標(biāo)規(guī)劃問題時(shí),可通過建立不確定多目標(biāo)規(guī)劃(uncertain multi-objective programming problem,UMOP)模型再進(jìn)行求解。通常情況下所建模型中目標(biāo)函數(shù)之間是相互獨(dú)立的不確定多目標(biāo)規(guī)劃(independent-uncertain multi-objective programming problem,I-UMOP)模型。
傳統(tǒng)求解方法往往是先將UMOP問題通過期望準(zhǔn)則轉(zhuǎn)化為確定的MOP問題再進(jìn)行求解,但在轉(zhuǎn)化過程中可能忽略了原問題的不確定性本質(zhì)而且僅用期望準(zhǔn)則難以反映不確定變量的波動(dòng)性。鑒于此,本文首先通過不確定變量之間的序關(guān)系定義UMOP問題的有效解,然后基于序關(guān)系將其轉(zhuǎn)化為不確定單目標(biāo)規(guī)劃問題,再進(jìn)一步引入期望-方差準(zhǔn)則將原問題轉(zhuǎn)化為確定的單目標(biāo)規(guī)劃問題進(jìn)行求解,最后證明求解得到的最優(yōu)解是原UMOP問題的有效解。
I-UMOP是指各個(gè)目標(biāo)函數(shù)獨(dú)立的不確定多目標(biāo)規(guī)劃問題,其模型為
(1)
式中,x∈Rn為決策變量;ξ1,ξ2,…,ξp為定義在不確定空間(Γ,L,M)上的不確定變量且相互獨(dú)立;η1,η2,…,ηm為定義在不確定空間(Γ,L,M)上的不確定變量且相互獨(dú)立。
期望-方差準(zhǔn)則(PEV準(zhǔn)則)[10]ξ和η是相互獨(dú)立的不確定變量,ξp=(p)η當(dāng)且僅當(dāng)E[ξ]≤(<)E[η]且V[ξ]≤(<)V[η]。其中,E[·]和V[·]分別表示不確定變量的期望與方差。
其中至少存在一個(gè)j0,1≤j0≤p,使得
求解UMOP問題首先是利用某種方法(構(gòu)造實(shí)值可測函數(shù)F)將其轉(zhuǎn)化為不確定單目標(biāo)問題,其表達(dá)式為
(2)
文獻(xiàn)[10]已經(jīng)證明U(x,ξ)是一個(gè)不確定變量。在PEV準(zhǔn)則下,將問題(2)轉(zhuǎn)化為確定的單目標(biāo)規(guī)劃問題,其表達(dá)式為
(3)
問題(3)的最優(yōu)解便是問題(1)的Pareto有效解。
為證明問題(3)的最優(yōu)解是問題(1)的Pareto有效解,在PEV準(zhǔn)則下提出以下引理。
引理1ξ和η是分別服從正則不確定分布Φ和Ψ且相互獨(dú)立的不確定變量。若ξp=(p)η,則對于任意正實(shí)數(shù)λ,λξp=(p)λη成立。
證明由于ξp=(p)η,根據(jù)PEV準(zhǔn)則,可得
E[ξ]≤(<)E[η]
(4)
V[ξ]≤(<)V[η]
(5)
根據(jù)不確定變量期望和方差計(jì)算公式,由式(4)、式(5),得
(6)
(7)
對于任意正實(shí)數(shù)λ,有
(8)
(9)
即
(10)
(11)
根據(jù)不確定變量的期望和方差的運(yùn)算法則,有
E(λξ)≤(<)E(λη)
(12)
V(λξ)≤(<)V(λη)
(13)
即λξp=(p)λη成立。
證畢
引理2ξ1,ξ2是分別服從正則不確定分布Φ1,Φ2且相互獨(dú)立的不確定變量,η1,η2是分別服從正則不確定分布Ψ1,Ψ2且相互獨(dú)立的不確定變量。若ξ1p=η1,ξ2pη2或ξ1pη1,ξ2p =η2,則ξ1+ξ2pη1+η2成立。
證明不失一般性,以ξ1p=η1,ξ2pη2為例,根據(jù)PEV準(zhǔn)則,可得
E(ξ1)≤E(η1)
(14)
V(ξ1)≤V(η1)
(15)
E(ξ2) (16) V(ξ2) (17) 根據(jù)不確定變量的期望和方差計(jì)算公式,由式(14)~式(17),可得 (18) (19) (20) (21) 式(18)與式(20)相加,可得 (22) 式(19)與式(21)相加,可得 (23) 根據(jù)不確定變量的期望運(yùn)算法則,有 E[ξ1+ξ2] (24) 因ξ1,ξ2相互獨(dú)立,有 eξ1eξ2-eξ1eξ2-eξ2eξ1+eξ1eξ2=0 (25) 同理 (26) 根據(jù)式(23)、式(25)及式(26),有 (27) 即 (28) (29) V[ξ1+ξ2] (30) 即ξ1+ξ2pη1+η2成立。 證畢 引理3ξ,η是分別服從正則不確定分布Φ和Ψ且相互獨(dú)立的不確定變量,且兩者下界ξ0,η0存在,記t0=min(ξ0,η0),若ξp=(p)η,則(ξ-t0)2p=(p)(η-t0)2成立。 證明由于ξp=(p)η,根據(jù)PEV準(zhǔn)則,可得 E[ξ]≤(<)E[η] (31) 即 (32) 因?yàn)棣?,η0分別是不確定變量ξ,η的下界,即分別是Φ-1(α)和Ψ-1(α)的下界,于是 Φ-1(α)-t0≥0,Ψ-1(α)-t0≥0 根據(jù)式(32),可得 (33) 由于(ξ-t0)2和(η-t0)2分別關(guān)于ξ和η單調(diào)遞增,因此其逆分布分別為(Φ-1(α)-t0)2和(Ψ-1(α)-t0)2,根據(jù)期望計(jì)算公式,有 (34) (35) 故 E[(ξ-t0)2]≤(<)E[(η-t0)2] (36) 根據(jù)運(yùn)算法則,有 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) 根據(jù)式(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 兩者均為關(guān)于α的增函數(shù),則原式化為 V[(η-t0)2]-V[(ξ-t0)2]= (40) 引進(jìn)輔助函數(shù) (41) 對式(41)求導(dǎo),可得 (42) 又G(0)=0,故G(1)≥0,即 V[(η-t0)2]-V[(ξ-t0)2]≥0 (43) 根據(jù)式(36)和式(43),有(ξ-t0)2p=(p)(η-t0)2成立。 證畢 證明由于ξp=(p)η,根據(jù)PEV準(zhǔn)則,可得 E[ξ]≤(<)E[η] (44) 根據(jù)不確定變量的期望的計(jì)算公式,可得 (45) (46) 即 (47) 又 (48) 根據(jù)引理3關(guān)于方差部分的推導(dǎo)過程,有 (49) 證畢 將UMOP問題如式(1)轉(zhuǎn)化為不確定單目標(biāo)規(guī)劃問題如式(2)的過程,通常采用線性加權(quán)法或理想點(diǎn)法。分別就兩種方法證明其解的有效性。 線性加權(quán)法是通過對每個(gè)目標(biāo)函數(shù)賦予相應(yīng)的權(quán)值并線性加權(quán)求和將問題(1)轉(zhuǎn)換得到的等價(jià)的問題模型為 (50) 定理1問題(50)在PEV準(zhǔn)則下求解的最優(yōu)解是問題(1)的PEV—Pareto有效解。 且存在至少一個(gè)i0,1≤i0≤p,使得 (51) (52) 即 (53) 于是 (54) 由定義1可知,x*不是問題(50)的最優(yōu)解。這與假設(shè)矛盾,因此假設(shè)不成立,即x*是問題(1)在PEV準(zhǔn)則下的Pareto有效解。 證畢 理想點(diǎn)法是通過最小化各目標(biāo)函數(shù)與理想點(diǎn)之間的距離之和將問題(1)轉(zhuǎn)化為等價(jià)的問題模型為 (55) 定理2問題(55)在PEV準(zhǔn)則下求解的最優(yōu)解是問題(1)的PEV—Pareto有效解。 且存在至少一個(gè)i0,1≤i0≤p,使得 (56) (57) 即 (58) 當(dāng)i≠i0時(shí),有 (59) 根據(jù)引理2,有 (60) (61) 即 (62) 根據(jù)引理4,有 (63) (64) 即 (65) 于是 (66) 由定義1可知,x*不是問題(55)的最優(yōu)解。這與假設(shè)矛盾,因此假設(shè)不成立,即x*是問題(1)在PEV準(zhǔn)則下的Pareto有效解。 證畢 為驗(yàn)證求解方法的可行性和有效性,設(shè)計(jì)了一個(gè)不確定多目標(biāo)規(guī)劃問題如式(67),問題中各目標(biāo)函數(shù)較復(fù)雜且約束條件不規(guī)則。其中x1,x2是連續(xù)的非負(fù)決策變量,ξ1,ξ2,ξ3,ξ4,ξ5,ξ6是相互獨(dú)立的不確定變量且分別服從不確定分布L(1,3),L(2,4),L(3,5),L(4,6),L(5,7),L(6,8);η1,η2是相互獨(dú)立的不確定變量且分別服從不確定分布Z(1,2,3),Z(2,3,4)。 (67) 利用線性加權(quán)法將不確定多目標(biāo)規(guī)劃轉(zhuǎn)換成不確定單目標(biāo)規(guī)劃,不妨令λ1=0.3,λ2=0.3,λ3=0.4,當(dāng)權(quán)重變化時(shí),可依然按此法求解。轉(zhuǎn)換結(jié)果如下: 不確定單目標(biāo)規(guī)劃轉(zhuǎn)換成確定的單目標(biāo)規(guī)劃,結(jié)果為 各不確定變量的分布及其逆分布見表1。 表1 各不確定變量的分布及其逆分布 模型進(jìn)一步轉(zhuǎn)化為 其中 (2α-5)(x1+0.5)(cos(2x2)+1)+ (2α-6)(x2+0.5)(sin(2x1)+1)+35 (2α-8)(sin(2x1x2)+1) 考慮轉(zhuǎn)化后的目標(biāo)函數(shù)仍非常復(fù)雜且局部極小點(diǎn)較多,因此采用文獻(xiàn)[18]中的GA-PSO算法進(jìn)行求解。該算法的具體流程見圖1。GA算法以概率的方式進(jìn)行選擇、交叉、變異算子操作,增強(qiáng)了PSO算法的全局尋優(yōu)能力,提高了收斂速度。參數(shù)設(shè)置見表2。 圖1 GA-PSO算法流程圖Fig.1 Sketch map of GA-PSO algorithm 算法參數(shù)取值交叉概率pc0.6變異概率pm0.1學(xué)習(xí)因子c11.495學(xué)習(xí)因子c21.495進(jìn)化次數(shù)maxgen1000種群規(guī)模popsize30粒子更新速度Vmax1粒子更新速度Vmin-1 解得x1=0.538 9,x2=2.599 4函數(shù)目標(biāo)值為3.479 3。其收斂速度見圖2。從圖2中可以看出,大約在第850代時(shí),迭代收斂。 圖2 線性加權(quán)模型求解收斂曲線Fig.2 Convergence curve of linear weighted method 線性加權(quán)法中各個(gè)目標(biāo)函數(shù)的權(quán)重反映了決策者對各目標(biāo)函數(shù)的偏重程度。當(dāng)各權(quán)重發(fā)生變化時(shí),期望和方差均會(huì)變化,導(dǎo)致轉(zhuǎn)化得到的單目標(biāo)函數(shù)會(huì)變化,從而對結(jié)果產(chǎn)生一定的影響。當(dāng)目標(biāo)函數(shù)的權(quán)重發(fā)生變化時(shí),可按照算例1中的步驟計(jì)算。 采用理想點(diǎn)法求解時(shí),根據(jù)各目標(biāo)函數(shù)關(guān)于其相關(guān)不確定變量的單調(diào)性,在可行域內(nèi)分別計(jì)算出3個(gè)目標(biāo)函數(shù)的下界:1.336 1,-4.738 7,-10.357 6,采用GA-PSO算法求解計(jì)算結(jié)果為x1=0.536 5,x2=2.562 7,目標(biāo)函數(shù)值為2.938 6。收斂效果見圖3。從圖3中可以明顯看出,大約在第900代時(shí),迭代收斂。 圖3 理想點(diǎn)模型求解收斂曲線Fig.3 Convergence curve of ideal point method 傳統(tǒng)求解方法是先將不確定多目標(biāo)規(guī)劃問題通過期望準(zhǔn)則轉(zhuǎn)化為確定的多目標(biāo)規(guī)劃問題再進(jìn)行求解。采用理想點(diǎn)法求解,計(jì)算3個(gè)確定目標(biāo)函數(shù)的最小值,結(jié)果分別為2.297 3,2.580 9,-7.994 4.采用GA-PSO算法進(jìn)行求解,并與本文提出的方法對比,見表3。 表3 兩種求解方法結(jié)果比較 如表3所示,傳統(tǒng)方法與本文的方法在求解I-UMOP問題時(shí)結(jié)果不太相同。其主要原因在于:一是本文提出的方法在求解時(shí)首先計(jì)算每個(gè)不確定目標(biāo)的函數(shù)的最小值,在一定程度上保持了原問題的不確定性本質(zhì),傳統(tǒng)方法則首先計(jì)算轉(zhuǎn)化后確定的目標(biāo)函數(shù)的最小值,更加注重原問題的多目標(biāo)本質(zhì),而沒有考慮其不確定的本質(zhì);二是本文的方法是在期望-方差準(zhǔn)則下求解,考慮了不確定變量的波動(dòng)性,而傳統(tǒng)方法是在期望準(zhǔn)則下求解,沒有考慮不確定變量的波動(dòng)性。因此,雖然兩種方法都可以對I-UMOP問題進(jìn)行求解,且運(yùn)算量相差不大,但是本文的方法更加注重保持問題的不確定本質(zhì)和不確定變量的波動(dòng)性。 (68) 采用理想點(diǎn)法將問題(68)轉(zhuǎn)化為單目標(biāo)問題,并利用文獻(xiàn)[19]的二進(jìn)制狼群算法進(jìn)行求解,其算法流程見文獻(xiàn)[19],參數(shù)設(shè)置見表4。 表4 二進(jìn)制狼群算法參數(shù)設(shè)置 分別對3個(gè)目標(biāo)函數(shù)進(jìn)行優(yōu)化求解,得到各目標(biāo)價(jià)值的最優(yōu)解如表5所示。 表5 各個(gè)目標(biāo)價(jià)值的單目標(biāo)最優(yōu)解上限值 表5中,最優(yōu)解向量分別為 采用二進(jìn)制狼群算法求解,其收斂效果如圖4所示。從圖4中可以看出,算法在第162代左右收斂,并且收斂于0.895,求解得到最優(yōu)解為IB。 圖4 二進(jìn)制狼群算法求解不確定背包問題收斂圖Fig.4 Convergence of uncertain knapsack problem solving by binary wolf pack algorithm 具體求解結(jié)果見表6,表中給出了各個(gè)目標(biāo)函數(shù)的最優(yōu)解、本文方法計(jì)算得到的最優(yōu)解和傳統(tǒng)方法計(jì)算得到的最優(yōu)解。經(jīng)過對比,本文方法計(jì)算的最優(yōu)解綜合考慮了各個(gè)單目標(biāo)價(jià)值的理想屬性,并且在保持原問題不確定性本質(zhì)的基礎(chǔ)上計(jì)算得到該算例的帕累托最優(yōu)解。 表6 不確定多目標(biāo)背包算例優(yōu)化求解結(jié)果 傳統(tǒng)求解UMOP問題有以下兩點(diǎn)不足:其一,傳統(tǒng)方法容易忽略原問題的不確定性,而且當(dāng)各個(gè)目標(biāo)之間含有相同的不確定變量時(shí),這種方法割裂了各個(gè)不確定目標(biāo)之間的相關(guān)性;其二,傳統(tǒng)方法僅用期望值作為轉(zhuǎn)化準(zhǔn)則難以反映原目標(biāo)函數(shù)作為一個(gè)不確定變量的波動(dòng)性。鑒于此,本文首先通過引入不確定變量之間的序關(guān)系定義了I-UMOP問題的有效解,然后基于序關(guān)系將其轉(zhuǎn)化為不確定單目標(biāo)規(guī)劃解決第一個(gè)問題,進(jìn)一步通過引入期望-方差準(zhǔn)則將原問題轉(zhuǎn)化為確定的單目標(biāo)規(guī)劃解決了第二個(gè)問題,并證明了求解得到的最優(yōu)解解是原問題的有效解。最后,設(shè)計(jì)了兩類數(shù)值算例,并分別利用GA-PSO算法和二進(jìn)制狼群算法進(jìn)行求解,結(jié)果表明本文提出的求解方法是可行且有效的。 [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] 王族統(tǒng).基于不確定理論的多目標(biāo)規(guī)劃方法及其應(yīng)用研究[D]. 西安: 空軍工程大學(xué), 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] 王曉軍, 楊海峰, 邱志平, 等. 基于測量數(shù)據(jù)的不確定性結(jié)構(gòu)分析的模糊理論[J]. 北京航空航天大學(xué)學(xué)報(bào), 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的多目標(biāo)混流裝配線排序問題[J].華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版),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] 吳虎勝, 張鳳鳴, 戰(zhàn)仁軍, 等. 利用改進(jìn)的二進(jìn)制狼群算法求解多維背包問題[J]. 系統(tǒng)工程與電子技術(shù), 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.3 有效解證明
3.1 線性加權(quán)法
3.2 理想點(diǎn)法
4 數(shù)值算例
4.1 算例1
4.2 算例2
5 結(jié) 論