吳 軍 嚴(yán)麗娜

1(寧夏大學(xué)新華學(xué)院 寧夏 銀川 750021)2(北方民族大學(xué)醫(yī)學(xué)影像技術(shù)系 寧夏 銀川 750021)

0 引 言

一般的非線性雙層規(guī)劃(Nonlinear Bilevel Programming,NBLP)問題通常是非凸不可微的，文獻(xiàn)[1]證明了即使搜索局部最優(yōu)解，NBLP問題仍是NP難問題。傳統(tǒng)的方法求解NBLP問題主要有以下幾類：關(guān)于線性規(guī)劃的極點(diǎn)法、分支定界算法、下降算法、罰函數(shù)法和信賴域法[2-7]等。當(dāng)NBLP問題變得復(fù)雜時(shí)，這些傳統(tǒng)算法將失去作用，在求解時(shí)很難獲得全局最優(yōu)解，而智能優(yōu)化算法對函數(shù)要求較低且具有較強(qiáng)的全局搜索能力，因此被逐漸用于求解此類問題。

Mathieu等[8]首次提出將遺傳算法應(yīng)用到求解雙層線性規(guī)劃問題，在算法中使用嵌套策略，用線性規(guī)劃和遺傳算法分別求解下層和上層規(guī)劃問題。在解決雙層規(guī)劃問題中嵌套策略是一個(gè)非常受歡迎的方法，然而，當(dāng)遇見大規(guī)模、復(fù)雜問題時(shí)，這種方法將出現(xiàn)耗時(shí)高甚至不能求解的情況。為了改善這個(gè)問題，Sinha等[9]將二次逼近嵌套在進(jìn)化算法中，使下層規(guī)劃問題的解無限接近最優(yōu)解，在有限的計(jì)算量下有效地解決了復(fù)雜的雙層規(guī)劃問題。何勝學(xué)等[10]針對建立的停車設(shè)施選擇和出行路線選擇的雙層規(guī)劃模型，上下層問題通過設(shè)施選擇概率函數(shù)實(shí)現(xiàn)了有效關(guān)聯(lián)，在嵌套策略下設(shè)計(jì)了有效的算法求解模型。劉丹等[11]針對離散交通網(wǎng)絡(luò)設(shè)計(jì)的大規(guī)模雙層規(guī)劃問題，提出一種機(jī)器學(xué)習(xí)-優(yōu)化混合算法，上下層問題利用不同算法分別求解。Wang等[12]針對同樣的問題，利用新的約束處理機(jī)制提高了算法的搜索能力，改善了個(gè)體的質(zhì)量和算法的收斂速度。但這個(gè)方法對于下層問題的非凸性無能為力，為了解決這個(gè)問題，Wang等[13]在算法中融合了傳統(tǒng)的確定性方法求解下層問題，實(shí)驗(yàn)結(jié)果顯示，新的進(jìn)化算法可以求解各種雙層規(guī)劃問題。Han等[14]依據(jù)多層規(guī)劃問題的求解思路，設(shè)計(jì)出層次粒子群算法求解雙層和三層規(guī)劃問題，實(shí)驗(yàn)結(jié)果顯示，層次粒子群算法對于非線性和大規(guī)模多層規(guī)劃問題效果顯著。Kuo等[15]將遺傳算法和粒子群算法融合構(gòu)造混合算法，擁有同樣思路的還有文獻(xiàn)[16]，他們將粒子群算法和差分進(jìn)化算法混合求解實(shí)際定價(jià)和批量決策問題。Li等[17]將一般的雙層規(guī)劃模型轉(zhuǎn)變?yōu)殡p目標(biāo)雙層規(guī)劃模型，他們認(rèn)為在雙目標(biāo)規(guī)劃中，兩個(gè)決策者經(jīng)過“討價(jià)還價(jià)”而達(dá)到雙方都滿意的結(jié)果并不違背雙層規(guī)劃模型的求解理論，反而可以給出一種形象直觀的解幫助決策者在貿(mào)易中找到最好的權(quán)衡。但是區(qū)別于雙目標(biāo)優(yōu)化問題的Pareto最優(yōu)集，雙層規(guī)劃問題只需得到一個(gè)最優(yōu)解，文獻(xiàn)[17]中該問題并沒有得到解決。

綜上所述，智能優(yōu)化算法在復(fù)雜的優(yōu)化問題中得到了成功的應(yīng)用，大多數(shù)文章都利用KT條件轉(zhuǎn)化雙層規(guī)劃為單層規(guī)劃求解，以雙目標(biāo)優(yōu)化思想解決雙層規(guī)劃問題的文獻(xiàn)卻很少見。文獻(xiàn)[17]雖提出了雙目標(biāo)雙層規(guī)劃模型，但對Pareto最優(yōu)集在雙層規(guī)劃問題中的處理并沒有給出合理的解決方案。本文將非線性雙層規(guī)劃問題轉(zhuǎn)換為雙目標(biāo)規(guī)劃問題，在基本的差分進(jìn)化(Differential Evolution,DE)算法框架中融合非負(fù)的最小二乘曲線擬合判定解的可行性，構(gòu)造了基于動(dòng)態(tài)概率偏好的Pareto支配選擇策略。以動(dòng)態(tài)的概率偏好保護(hù)候選解朝最優(yōu)目標(biāo)前進(jìn)的同時(shí)避免了算法陷入局部最優(yōu)，提高全局尋優(yōu)能力，成功地將多目標(biāo)優(yōu)化算法的思想用于求解雙層規(guī)劃問題。

1 雙層規(guī)劃問題的等價(jià)轉(zhuǎn)換

1.1 雙層規(guī)劃模型

考慮如下非線性雙層規(guī)劃問題：

(1)

式中：F,f:Rn×Rm→R，G:Rn×Rm→Rp，g:Rn×Rm→Rq，上層目標(biāo)函數(shù)F(x,y)和約束函數(shù)G(x,y)是非凸不可微的，下層目標(biāo)函數(shù)f(x,y)和約束函數(shù)g(x,y)是凸并且可微的。

x為上層決策變量，y為下層決策變量。X、Y分別代表上層變量和下層變量的搜索空間：

(2)

(3)

雙層規(guī)劃問題最優(yōu)解的相關(guān)概念如下所述：

定義1[18-19]

1) 約束空間：S={(x,y)|G(x,y)≤0,g(x,y)≤0}；

2) 對于固定的x∈X，下層問題的可行域：S(x)={y|g(x,y)≤0}；

3)S在上層決策空間的投影：S(X)={x|?y,(x,y)∈S}；

4) 對每個(gè)x∈S(x)，下層問題的合理反應(yīng)集：M(x)={y|y∈arg min{f(x,y),y∈S(x)}}；

5) 誘導(dǎo)域：IR={(x,y)|(x,y)∈S,y∈M(x)}；

6) 雙層規(guī)劃問題的最優(yōu)解集：OS={(x,y)|(x,y)∈arg minF(x,y),(x,y)∈IR}。

1.2 雙層規(guī)劃模型的等價(jià)形式

對任意x∈S(x)，下層規(guī)劃模型如下：

miny∈Yf(x,y)

(4)

s.t.g(x)≤0

對于固定的x，根據(jù)最優(yōu)性條件可知，式(4)等價(jià)于求解Kuhn-Tucher點(diǎn)問題[20-21]：

(5)

minx,y,UF(x,y)

(6)

s.t.Ek(x,y,U)=0k=1,2,…,m+1

Ir(x,y,U)≤0r=1,2,…,p+q

U≥0

式中：Ek(x,y,U)是式(5)中前兩個(gè)方程左邊的所有函數(shù)；Ir(x,y,U)是G(x,y)和g(x,y)所有的不等式約束的部分。

1.3 雙目標(biāo)優(yōu)化模型

我們將式(6)中Ek(x,y,U)、Ir(x,y,U)和U結(jié)合組成約束違反函數(shù)，建立一個(gè)特殊的優(yōu)化問題——雙目標(biāo)優(yōu)化。根據(jù)兩個(gè)目標(biāo)函數(shù)值，依據(jù)動(dòng)態(tài)概率偏好的Pareto支配策略選取優(yōu)秀個(gè)體。

(7)

式中：k=1,2,…,m+1；r=1,2,…,q；It=max{0,It}；t=1,2,…,p+2q+m+1。當(dāng)It=0時(shí)，表示個(gè)體(x,y)為可行解，否則為不可行解。顯然，對于式(6)，一個(gè)可行解優(yōu)于不可行解；兩個(gè)可行解中，目標(biāo)函數(shù)值小的解更優(yōu)秀；但兩個(gè)不可行解比較時(shí)，就無法確認(rèn)誰好誰壞。因此構(gòu)造如下雙目標(biāo)優(yōu)化問題：

min{F(Q),I(Q)}

(8)

式中：I(Q)=max{0,I1,I2,…,Ip+2q+m+1}，表示約束違反中最大的一個(gè)，記為可行性度量函數(shù)。同時(shí)優(yōu)化目標(biāo)函數(shù)F(Q)和可行性度量函數(shù)I(Q)，使種群朝向可行區(qū)域和全局最優(yōu)解前進(jìn)。

2 雙目標(biāo)優(yōu)化策略的差分進(jìn)化算法

2.1 差分進(jìn)化算法

差分進(jìn)化[22](Differential Evolution,DE)是一種基于種群的啟發(fā)式全局搜索算法，它主要包括變異和交叉操作。

(9)

(10)

式中：rand(0,1)是[0,1]區(qū)間的隨機(jī)數(shù)；CR是交叉概率；jrand是[1,D]區(qū)間內(nèi)隨機(jī)產(chǎn)生的整數(shù)。

2.2 可行性的度量

約束優(yōu)化問題最關(guān)鍵的步驟是判定解的可行性。對于式(6)中的約束部分，很多情況下滿足Ek(x,y,U)=0是極其困難的，而容忍誤差的設(shè)定沒有具體的標(biāo)準(zhǔn)去衡量。本文依據(jù)最小二乘曲線擬合原理，在有限的計(jì)算量中，尋找每個(gè)候選解對應(yīng)的Lagrange算子U′>0，使函數(shù)|Ek(x,y,U′)|的值盡可能小。

對于Ek(x,y,U)=0，將U看作方程中的未知量，將其改寫成方程組形式AU-B=0，其中A是系數(shù)矩陣，B是常數(shù)向量，那么非負(fù)的最小二乘曲線擬合就相當(dāng)于求解如下最小化問題：

(11)

若Ie=0，證明使用最小二乘曲線擬合的程度最高，等式約束的誤差為零，得到了精確的候選解；Ie的值越大，說明擬合程度越低，約束違反值越大。

2.3 動(dòng)態(tài)概率偏好的Pareto支配選擇

定義2

(1) Pareto支配：對于解Q1和Q2滿足F(Q1)≤F(Q2)和I(Q1)≤I(Q2)時(shí)，且至少存在F(Q1)

(2) Pareto最優(yōu)：設(shè)Ω是一解集，如果解Q1是當(dāng)前Ω集合中Pareto最優(yōu)的，當(dāng)且僅當(dāng)不存在解Q∈Ω，使得解Q支配Q1；

(3) Pareto最優(yōu)集：設(shè)Ω是算法目前為止所有解的集合，那么關(guān)于Ω中所有Pareto最優(yōu)解被稱為Pareto最優(yōu)集。

在通常情況下，雙層規(guī)劃問題的求解理論并不等同于雙目標(biāo)優(yōu)化問題，因此它不能直接轉(zhuǎn)換為雙目標(biāo)優(yōu)化問題(上下兩層的目標(biāo)函數(shù)作為平行的兩個(gè)目標(biāo)函數(shù))，也就是說，雙層規(guī)劃問題的最優(yōu)解不能等同于雙目標(biāo)優(yōu)化問題的Pareto最優(yōu)解。

根據(jù)以上定義，對于雙目標(biāo)優(yōu)化問題(式(8))，如果解Q1支配Q2，那么解Q1優(yōu)于Q2。如果解Q1和Q2互不支配，那將依概率選擇目標(biāo)函數(shù)或可行性度量值較大的解。本文中的雙目優(yōu)化問題(式(8))等價(jià)于單層規(guī)劃問題(式(6))，因此式(8)的Pareto最優(yōu)解是式(6)的最優(yōu)解，也就是式(1)的解，具體內(nèi)容可參照文獻(xiàn)[12]中定理1。

設(shè)置如下的動(dòng)態(tài)概率Pareto支配選擇(DpPa)方案：

(1) 兩個(gè)都是可行解或者兩個(gè)不可行解。按照Pareto支配選擇一個(gè)解進(jìn)入下一代種群。

(2) 可行解支配不可行解。P、NewP分別代表兩代種群，I、NewI分別代表兩代解的可行性度量值，F(xiàn)、NewF分別代表兩代解的目標(biāo)函數(shù)值，randp代表[0,1]的隨機(jī)數(shù)，pd∈[pl,pu]代表動(dòng)態(tài)概率值，它的取值隨著迭代次數(shù)的增加而減小。pd的計(jì)算公式如下：

具體的偽代碼如下所示：

if I=0 & New I≠0 & F

if rand p

Next P←P

else

Next P←NewP

end

end

通過這種選擇策略，一個(gè)可行解支配一個(gè)不可行解，我們以較大概率選擇可行解。隨著迭代的進(jìn)行，種群趨于集中，選擇可行解的概率逐漸減小到最低下限值pl。相反以較小的概率選擇不可行解，隨著迭代的增加選擇不可行解的概率逐漸增大，最大概率限定為pu-pl。以大概率保護(hù)優(yōu)秀可行解進(jìn)入下一代種群，以小概率保留不可行解進(jìn)入下一代種群，增加種群的多樣性以及全局搜索能力。

(4) 兩個(gè)不可行解互不支配。以大概率選擇可行性度量值小的，使種群快速朝著可行區(qū)域進(jìn)化，本文設(shè)置定值pd=0.7。

2.4 基于Pareto支配的雙目標(biāo)差分進(jìn)化算法

基于Pareto支配的雙目標(biāo)差分進(jìn)化算法(DPDE)求解非線性雙層規(guī)劃問題，具體的算法流程如下：

步驟1設(shè)置初始參數(shù)，種群規(guī)模ps，交叉概率cr，動(dòng)態(tài)概率上限和下限pu、pl，當(dāng)前迭代次數(shù)in，縮放因子F，最大迭代次數(shù)inmax。

步驟2初始化種群，在變量范圍內(nèi)隨機(jī)產(chǎn)生初始種群P={Qi|i=1,2,…,ps}，計(jì)算每個(gè)個(gè)體的目標(biāo)函數(shù)值F(Q)和約束違反值I(Q)。

步驟3依據(jù)約束違反值I(Q)判斷個(gè)體的可行性，將可行解中目標(biāo)函數(shù)值F(Q)最小的個(gè)體作為最好個(gè)體Qbest，如果不存在可行解，那么將不可行解中約束違反值I(Q)最小的個(gè)體作為最好個(gè)體Qbest。

步驟4隨機(jī)選擇4個(gè)個(gè)體Qr1、Qr2、Qr3和Qr4，根據(jù)式(9)進(jìn)行變異操作，產(chǎn)生變異個(gè)體Vi，根據(jù)式(10)進(jìn)行交叉操作，產(chǎn)生子代候選個(gè)體Si，計(jì)算Si目標(biāo)函數(shù)值F(Si)和可行性度量值I(Si)，依據(jù)DaPa策略比較Qi與Si的目標(biāo)函數(shù)值和可行性度量值，選擇較好個(gè)體。

步驟5更新種群，判斷算法終止條件，如果in

3 實(shí)驗(yàn)結(jié)果及分析

表1 測試函數(shù)及其相關(guān)來源

(1) 最優(yōu)解(x*,y*)；

(2) 上層目標(biāo)函數(shù)F(x,y)的最優(yōu)值、最差值、均值、方差；

(3) 下層目標(biāo)函數(shù)f(x,y)的最優(yōu)值、最差值、均值、方差；

(4) 算法50次獨(dú)立運(yùn)行適應(yīng)度函數(shù)的平均計(jì)算次數(shù)(MNI)和平均CPU運(yùn)行時(shí)間(CPU)。

表2記錄了DPDE算法的最好解數(shù)值及與文獻(xiàn)[12]和文獻(xiàn)[14]的比較，可以看出，DPDE算法在大多數(shù)問題中可以得到與算法NEA和BL-PSO基本一致的結(jié)果，而測試函數(shù)6的結(jié)果和其他兩種算法有較大不同。由于小數(shù)位的限制，我們也不能比較誰好誰壞。

表3和表4統(tǒng)計(jì)了DPDE算法的最好解的上層和下層函數(shù)值及與文獻(xiàn)[12]和文獻(xiàn)[14]的比較，對比文獻(xiàn)[14]可以看出，DPDE算法對于函數(shù)3、函數(shù)5、函數(shù)11和函數(shù)12的解絕對優(yōu)于算法NEA[12]，其他函數(shù)的解在精度允許范圍內(nèi)也和其相等；對比文獻(xiàn)[14]可以看出，DPDE算法對于函數(shù)5和函數(shù)8得到的解絕對優(yōu)于算法BL-PSO[14]。對于函數(shù)10，算法BL-PSO得到了(F,f)=(1,0)，從數(shù)值上看明顯優(yōu)于DPDE算法，但是經(jīng)過驗(yàn)證，當(dāng)x=1時(shí)，下層目標(biāo)函數(shù)最小值應(yīng)該為f(x,y)=-101 250。因此，算法BL-PSO得到的解(x,y)=(1,0)不是全局最優(yōu)解。剩余函數(shù)中，除過函數(shù)12本文算法稍顯劣勢外，其他函數(shù)都與BL-PSO算法得到的函數(shù)值相等。

表3 最好解F(x*,y*)函數(shù)值的比較

表4 最好解f(x*,y*)函數(shù)值的比較

續(xù)表4

特別說明的是，函數(shù)6的上層函數(shù)中x的系數(shù)為0，即上層目標(biāo)函數(shù)只是關(guān)于變量y的函數(shù)，在要求下層目標(biāo)最小的情況下，DPDE算法計(jì)算出x=(61.306,25.768)，比較下層函數(shù)值可以看出解(x,y)=(61.306,25.768,2.999,2.999)明顯優(yōu)于算法NEA[12]和BL-PSO[14]的解。

表5和表6分別顯示了DPDE算法的計(jì)算結(jié)果在上層和下層函數(shù)的最好值、最差值、平均值和標(biāo)準(zhǔn)差，函數(shù)6的均值和方差出現(xiàn)較大變化，具體原因已解釋過。其他函數(shù)的均值都非常接近最優(yōu)值，方差都不超過10-6數(shù)量級，最小的方差值如函數(shù)3和函數(shù)14的0，表明算法DPDE具有極強(qiáng)的抗變換性。

表5 上層函數(shù)的最好值、最差值、平均值、標(biāo)準(zhǔn)差

表6 下層函數(shù)的最好值、最差值、平均值、標(biāo)準(zhǔn)差

表7顯示了算法的CPU平均運(yùn)行時(shí)間和適應(yīng)度函數(shù)的平均計(jì)算次數(shù)MNI。從各個(gè)函數(shù)的平均CPU時(shí)間上看，本文算法DPDE大多數(shù)超過了NEA算法，但每個(gè)問題的平均CPU耗時(shí)相差不多，而算法NEA則具有較強(qiáng)的波動(dòng)，15個(gè)函數(shù)的CPU時(shí)間的平均值顯示DPDE算法優(yōu)于NEA算法，表明本文算法具有較強(qiáng)的穩(wěn)定性，同樣MNI值也低于NEA算法。

表7 CPU時(shí)間和計(jì)算次數(shù)

續(xù)表7

4 結(jié) 語

本文首先將雙層規(guī)劃問題等價(jià)轉(zhuǎn)化為雙目標(biāo)規(guī)劃問題，采用了非負(fù)的最小二乘曲線擬合，利用擬合結(jié)果判斷候選街的可行性，基于動(dòng)態(tài)概率的Pareto支配選擇策略挑選下一代個(gè)體，解決了NBLP問題容易陷入局部最優(yōu)的缺陷，提高了算法的搜索性能，改善全局尋優(yōu)能力。15個(gè)標(biāo)準(zhǔn)測試函數(shù)的實(shí)驗(yàn)數(shù)據(jù)表明，DPDE算法在求解NBLP問題具有較好的全局尋優(yōu)能力，較低的計(jì)算復(fù)雜度，較強(qiáng)的穩(wěn)定性和適用性，可以獲得全局最優(yōu)解。雙目標(biāo)和雙層規(guī)劃問題深層結(jié)合，自適應(yīng)的Pareto支配選擇策略是下一步探索的問題。