一種求解二層單目標(biāo)規(guī)劃問(wèn)題的基于KKT背離度量方程的粒子群優(yōu)化算法

張鈺,張濤

(長(zhǎng)江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023)

二層規(guī)劃是一種具有遞階結(jié)構(gòu)的系統(tǒng)優(yōu)化問(wèn)題。在二層規(guī)劃模型中，一般可分為上、下2層，上層是一個(gè)含有下層最優(yōu)決策變量(或最優(yōu)目標(biāo)函數(shù)值)的復(fù)合最優(yōu)化問(wèn)題，下層則是一個(gè)以上層決策變量為參數(shù)的參數(shù)規(guī)劃[1～3]。二層規(guī)劃的嵌套結(jié)構(gòu)使得該模型的求解具有一定的復(fù)雜性，其復(fù)雜性表現(xiàn)在上層目標(biāo)函數(shù)決定于下層規(guī)劃問(wèn)題的解函數(shù)，通常這個(gè)解函數(shù)非凸且不可微；二層規(guī)劃約束的嵌套特性使其可行域一般不再具備凸性和閉性，并且在有包含下層決策變量的上層約束時(shí)還可能不連通，甚至是空集。

目前，求解二層規(guī)劃問(wèn)題的傳統(tǒng)算法可以分為4類：Karus-Kuhn-Tucker方法[4～7]、分支定界法[8]、罰函數(shù)法[9～12]以及下降法[13，14]，這些傳統(tǒng)算法均要求目標(biāo)函數(shù)具有可微性和連續(xù)性。然而，二層規(guī)劃問(wèn)題的目標(biāo)函數(shù)通常不具備上述屬性且非凸。粒子群優(yōu)化算法[15]作為近來(lái)提出的一種智能算法，其算法特點(diǎn)與二層規(guī)劃問(wèn)題的結(jié)構(gòu)特征具有優(yōu)良的匹配性：該算法對(duì)模型結(jié)構(gòu)以及目標(biāo)函數(shù)和約束函數(shù)的性態(tài)要求更為寬松，且該算法以種群為操作單元且實(shí)數(shù)編碼，可以與二層規(guī)劃問(wèn)題的下層問(wèn)題的多解特征建立映射關(guān)系。因此，利用粒子群算法求解二層規(guī)劃問(wèn)題是一條有效途徑。2006年，Li等[16]提出了求解二層規(guī)劃問(wèn)題的分層粒子群算法；2009年，Kuo與Huang[17]提出了求解線性二層規(guī)劃問(wèn)題的粒子群算法；2011年，Gao等[18]利用粒子群算法求解了供應(yīng)鏈中的二層規(guī)劃模型；隨后，Zhang等[19]利用粒子群優(yōu)化技術(shù)求解了電力市場(chǎng)中的競(jìng)爭(zhēng)性招標(biāo)策略的二層規(guī)劃模型；2013年，Jiang等[20]提出了基于CHKS光滑方程的粒子群算法求解非線性二層規(guī)劃問(wèn)題。上述二層規(guī)劃模型的決策變量維數(shù)較低且模型相對(duì)較為簡(jiǎn)單。對(duì)于維數(shù)較高且函數(shù)性態(tài)(可微性、連續(xù)性及多模態(tài)性)較為復(fù)雜的二層規(guī)劃模型，利用上述算法進(jìn)行求解時(shí)，將會(huì)花費(fèi)巨大的計(jì)算代價(jià)且收斂性得不到保障。針對(duì)復(fù)雜的二層規(guī)劃模型，利用粒子群算法求解的核心是確保下層規(guī)劃問(wèn)題的最優(yōu)解的精確性，如果所求下層問(wèn)題的最優(yōu)解具有非精確性或欺騙性，則整個(gè)問(wèn)題求解將會(huì)花費(fèi)巨大計(jì)算代價(jià)甚至求解失敗。為此，筆者基于單目標(biāo)規(guī)劃問(wèn)題的KKT條件，引入KKT背離度量方程，利用該度量方程控制下層問(wèn)題的最優(yōu)解精度，然后以下層問(wèn)題最優(yōu)解精度控制值為終止條件，設(shè)計(jì)求解二層規(guī)劃問(wèn)題的粒子群算法。

1 模型與基本概念

假設(shè)x∈Rn1,y∈Rn2,F,f:Rn1×Rn2→R，G，g:Rn1×Rn2→R，樂(lè)觀二層單目標(biāo)規(guī)劃可表述為:

(1)

式中，x∈Rn1和y∈Rn2分別為上層決策變量和下層決策變量；F(x,y)和f(x,y)分別表示上層目標(biāo)函數(shù)和下層目標(biāo)函數(shù)；G(x,y)和g(x,y)分別表示上層約束函數(shù)和下層約束函數(shù)。

記：

約束域S={(x,y)|G(x,y)≤0,g(x,y)≤0}

對(duì)于給定x∈Rn1,下層問(wèn)題的可行域S(x)={y|g(x,y)≤0}

約束域S在上層問(wèn)題決策空間的投影S(X)={x|?y,G(x,y)≤0,g(x,y)≤0}

對(duì)于x∈S(X)，下層問(wèn)題的合理反應(yīng)集P(x)={y|y∈arg min[f(x,y):y∈S(x)]}

二層單目標(biāo)規(guī)劃問(wèn)題的誘導(dǎo)域IR={(x,y)|(x,y)∈S,y∈P(x)}

定義1 如果點(diǎn)(x,y)∈IR，則稱點(diǎn)(x,y)為問(wèn)題(1)的可行點(diǎn)。

定義3 如果(xo,yo)成為問(wèn)題(1)的樂(lè)觀最優(yōu)解, 則 (xo,yo)滿足如下方程:

2 算法設(shè)計(jì)

利用粒子群優(yōu)化算法求解二層規(guī)劃問(wèn)題的基本工作流程如圖1所示：給定上層決策變量，執(zhí)行下層優(yōu)化問(wèn)題；然后將下層問(wèn)題的近似最優(yōu)解作為最優(yōu)響應(yīng)反饋給上層，從而得到整個(gè)問(wèn)題的近似最優(yōu)解；通過(guò)預(yù)設(shè)迭代次數(shù)，使整個(gè)問(wèn)題的近似最優(yōu)解任意精度逼近精確解。具體步驟如下：

Step1 初始化上層種群Pu，種群規(guī)模為Nu，初始化上層循環(huán)變量tu=0。

Step2 對(duì)于上層決策變量xi(i=1,2,…,N), 初始化下層種群Pl，種群規(guī)模為Nl，初始化下層迭代次數(shù)tl=0。

Step3 執(zhí)行下層優(yōu)化問(wèn)題。更新下層粒子的速度和位置：

Step6 上層問(wèn)題的終止條件檢查，如果α(tu)≥α-predefined，轉(zhuǎn)Step7，否則輸出上層問(wèn)題的最優(yōu)解。

Step7 按如下方程更新上層決策變量：

Step8 對(duì)于更新的上層決策變量，轉(zhuǎn)Step2。

如果yj

如果pbestj(y)

如果yj與pbestj(y)相等，則從兩者之中隨機(jī)挑選一個(gè)作為新的pbestj(y)。

Step7中的pbestj(y)按同樣的方式選取。

在Step4中，下層規(guī)劃問(wèn)題基于KKT背離度量方程的終止條件為：

(2)

(3)

(4)

圖1 二層規(guī)劃問(wèn)題的粒子群算法的基本工作流程

3 數(shù)值仿真與結(jié)果分析

粒子群優(yōu)化算法的相關(guān)參數(shù)設(shè)置如下:r1，r2∈random(0,1),慣性權(quán)重w=0.7298，社會(huì)系數(shù)和認(rèn)知系數(shù)c1=c2=1.49618，上層問(wèn)題和下層問(wèn)題的粒子規(guī)模Nu=Nl=50。下層問(wèn)題的終止精度為1×10-4，計(jì)算機(jī)運(yùn)行條件CPU:AMDPhenon(tm)ⅡX6 1055T2.80GHz;RAM:3.25GB，利用C#編程進(jìn)行求解。

以下分別為仿真試驗(yàn)算例。

問(wèn)題1：

問(wèn)題2：

問(wèn)題3：

問(wèn)題4：

問(wèn)題5：

問(wèn)題6：

其中，問(wèn)題1～問(wèn)題5參數(shù)設(shè)置p=5,q=5，r=2；問(wèn)題6的參數(shù)設(shè)置p=5,q=3,r=2，s=2。

將上述算例執(zhí)行11次并與參考文獻(xiàn)[21]中的結(jié)果做比較，表1給出了上層問(wèn)題和下層問(wèn)題的方程評(píng)價(jià)次數(shù)的比較結(jié)果，表2給出了上層問(wèn)題和下層問(wèn)題精度的比較結(jié)果。

表1 上層問(wèn)題和下層問(wèn)題方程評(píng)價(jià)次數(shù)的比較結(jié)果

表2 上層問(wèn)題和下層問(wèn)題最優(yōu)解的精度比較結(jié)果

表1中，第5列與第6列分別表示下層問(wèn)題和上層問(wèn)題的方程評(píng)價(jià)次數(shù)的中位數(shù)。括號(hào)中的數(shù)值表示文獻(xiàn)[21]中的算法所需方程評(píng)價(jià)次數(shù)的中位數(shù)與筆者設(shè)計(jì)算法所需方程評(píng)價(jià)次數(shù)中位數(shù)的比率。從比較結(jié)果來(lái)看，2種方法都能成功求解所有問(wèn)題，但從上層問(wèn)題方程評(píng)價(jià)次數(shù)的中位數(shù)來(lái)看，文獻(xiàn)[21]中的算法所需次數(shù)是筆者設(shè)計(jì)算法所需次數(shù)的1.19～3.03倍，從下層問(wèn)題方程評(píng)價(jià)次數(shù)的中位數(shù)來(lái)看，文獻(xiàn)[21]中的算法所需的次數(shù)是筆者設(shè)計(jì)算法所需次數(shù)的2.31～6.01倍。

從表2中可以看出，在獲得問(wèn)題的幾乎相同的精度解時(shí)，文獻(xiàn)[21]中的方法所執(zhí)行的下層優(yōu)化問(wèn)題的次數(shù)約為筆者設(shè)計(jì)算法的1.5倍，且每執(zhí)行一次下層優(yōu)化問(wèn)題文獻(xiàn)[21]中的方法所需的方程評(píng)價(jià)次數(shù)約為筆者設(shè)計(jì)算法所需方程評(píng)價(jià)次數(shù)的1.6倍。

4 結(jié)語(yǔ)

提出了一種基于KKT背離度量方程的粒子群算法用于求解二層規(guī)劃問(wèn)題的樂(lè)觀解，用6組模型進(jìn)行仿真試驗(yàn)并與經(jīng)典文獻(xiàn)中的計(jì)算結(jié)果做了比較，結(jié)果表明KKT背離度量方程能夠有效的保證下層問(wèn)題最優(yōu)解的真實(shí)性，從而較大幅度的減少了計(jì)算量并在一定程度上改善了算法的收斂速度。在未來(lái)的研究中，將進(jìn)一步考慮在維數(shù)迅速膨脹的情況下如何設(shè)計(jì)該問(wèn)題的并行粒子群算法。

[1]Bard J F, Falk J E. An explicit solution to the multilevel programming problem [J]. Computers and Operations Research, 1982, 9(1): 77～100.

[2]Demple S. Foundation of Bilevel Programming [M]. London: Kluwer Academic, 2002.

[3]藤春賢，李智慧. 二層規(guī)劃理論與應(yīng)用 [M]. 北京:科學(xué)出版社，2002.

[4] Bard J.An algorithm for solving the general bilevel programming problem[J]. Mathematics of Operations Research, 1983,8:260～272.

[5] Edmunds T, Bard J.Algorithm for nonlinear bilevel mathematical programs[J]. IEEE Transactions on Systems,1991,21:83～89.

[6] Amouzegar M.A global optimization method for nonlinear bilevel programming problems[J]. IEEE Transactions on Systems, 1999,29:771～777.

[7] Etoa J.Solving quadratic convex bilevel programming problems using a smoothing method[J]. Applied Mathematics and Computation,2011,217:6680～6690.

[8] Bard J, Falk J.An explicit solution to the multi-level programming problem[J]. Computers & Operations Research,1982，9:77～100.

[9] Ishizuka Y, Aiyoshi E.A new computational method for Stackelberg and min-max problems by use of a penalty method[J]. IEEE Transactions on Automatic Control,1981,26:460～466.

[10] Aiyoshi E, Shimuzu K.A solution method for the static constrained Stackelberg problem via penalty method[J]. IEEE Transactions on Automatic Control, 1984,29:1112～1114.

[11] Ishizuka Y, Aiyoshi E.Double penalty method for bilevel optimization problems[J]. Annals of Operations Research,1992,34:73～88.

[12] Lv Y, Hu T, Wang G,et al. A penalty function method based on Kuhn-Tucker condition for solving linear bilevel programming[J].Applied Mathematics and Computation,2007,188:808～813.

[13] Savard G, Gauvin J.The steepest descent direction for the nonlinear bilevel programming problem[J].Operations Research Letters,1994,15:265～272.

[14] Falk J, Liu J.On bilevel programming, Part I: general nonlinear cases[J].Mathematical Programming,1995,70:47～72.

[15]Kennedy J, Eberhart R C. Particle swarm optimization[A]. Proceedings of IEEE International Conference on Neural Networks [C]. 1995:1942～1948.

[16] Li X, Tian P, Min X.Hierarchical Particle Swarm Optimization for Solving Bilevel Programming Problems[A]. Lecture Notes in Computer Science[C]. 2006:1169～1178.

[17] Kuo R, Huang C.Application of particle swarm optimization algorithm for solving bilevel linear programming problem[J].Computer and Mathematics with Application,2009，58:678～685.

[18] Gao Y, Zhang G, Lu J, et al.Particle swarm optimization for bi-level pricing problems in supply chains[J].Journal of Global Optimization,2011， 51:245～254.

[19] Zhang G, Zhang G, Gao Y, et al.Competitive strategic bidding optimization in electricity markets using bi-level programming and swarm technique[J].IEEE Transactions on Industrial Electronics,2011，58: 2138～2146.

[20] Jiang Y, Li X.Application of particle swarm optimization based on CHKS smoothing function for solving nonlinear bilevel programming problem[J].Applied Mathematics and Computation,2013，129:4332～4339.

[21] Sinha A, Malo P, Deb K. Efficient evolutionary algorithm for single-objective bilevel optimization[J].Neural and Evolutionary Computing, 2013,18(3): 403～449.