一種求解線性二層多目標(biāo)規(guī)劃的粒子群優(yōu)化方法

胡 密，毛和水，盧仕峰，劉 偉，呂一兵 (長江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023)

一種求解線性二層多目標(biāo)規(guī)劃的粒子群優(yōu)化方法

胡 密，毛和水，盧仕峰，劉 偉，呂一兵 (長江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023)

粒子群算法是一種新興的優(yōu)化技術(shù)。由于粒子群算法實(shí)現(xiàn)簡單，可調(diào)參數(shù)少，已得到廣泛研究和應(yīng)用。根據(jù)粒子群算法能夠有效獲得不可微多目標(biāo)規(guī)劃Pareto最優(yōu)解的特點(diǎn)，設(shè)計(jì)了線性二層多目標(biāo)規(guī)劃的粒子群算法：采用以下層問題的K-T最優(yōu)性條件代替下層問題的思想，將線性二層多目標(biāo)規(guī)劃轉(zhuǎn)化為帶互補(bǔ)約束的不可微多目標(biāo)規(guī)劃問題，然后對所得到的不可微多目標(biāo)規(guī)劃問題設(shè)計(jì)粒子群算法，從而得到線性二層多目標(biāo)規(guī)劃問題的Pareto最優(yōu)解。數(shù)值結(jié)果表明所設(shè)計(jì)的算法是可行、有效的。

線性二層多目標(biāo)規(guī)劃；K-T條件；粒子群算法；Pareto最優(yōu)解

二層規(guī)劃是二層決策問題的數(shù)學(xué)模型，它是一種具有二層遞階結(jié)構(gòu)的系統(tǒng)優(yōu)化問題。在二層規(guī)劃模型中，上層問題和下層問題都有各自的目標(biāo)函數(shù)和約束條件。上層問題的目標(biāo)函數(shù)和約束條件不僅與上層決策變量有關(guān)，而且還依賴于下層問題的最優(yōu)解，而下層問題的最優(yōu)解又受到上層決策變量的影響。當(dāng)上、下2層或其一含有多個(gè)目標(biāo)函數(shù)時(shí)，相應(yīng)的二層規(guī)劃被稱為二層多目標(biāo)規(guī)劃問題[1]。

線性二層多目標(biāo)規(guī)劃，即目標(biāo)函數(shù)以及約束條件均為線性函數(shù)的一類二層多目標(biāo)規(guī)劃問題，已經(jīng)引起了國內(nèi)外研究者的重視。Nishizaki和Sakawa[2]給出了線性二層多目標(biāo)規(guī)劃3種Stackelberg解的定義，并設(shè)計(jì)了相應(yīng)的求解算法；Ankhili和Mansouri[3]基于下層問題的邊緣函數(shù)，對上層為線性標(biāo)量優(yōu)化問題、下層為線性多目標(biāo)規(guī)劃的一類線性二層多目標(biāo)規(guī)化問題設(shè)計(jì)了精確罰函數(shù)方法；對上層為線性多目標(biāo)規(guī)劃、下層為線性標(biāo)量優(yōu)化問題的一類線性二層多目標(biāo)規(guī)劃，Calvete和Gale[4]分析了其可行域的特征，同時(shí)給出了一些算法框架。值得指出的是，上述有關(guān)線性二層多目標(biāo)規(guī)劃問題求解算法的研究，大部分僅僅給出了算法框架，并沒有給出具體的數(shù)值試驗(yàn)結(jié)果。

下面，筆者采用以下層問題的K-T最優(yōu)性條件代替下層問題的思想，將線性二層多目標(biāo)規(guī)劃轉(zhuǎn)化為帶互補(bǔ)約束的不可微多目標(biāo)規(guī)劃問題，然后對所得到的不可微多目標(biāo)規(guī)劃問題設(shè)計(jì)粒子群算法，從而得到線性二層多目標(biāo)規(guī)劃問題的Pareto最優(yōu)解。

1 線性二層多目標(biāo)規(guī)劃問題

考慮如下線性二層多目標(biāo)規(guī)劃問題：

s.t.A1x+A2y≤b

(1)

其中，x∈Rn,y∈Rm,b∈Rp,A1∈Rp×n,A2∈Rp×m,C∈Rq×n,C′∈Rq×m,D∈Rl×m。

s.t.A1x+A2y≤b

由于對于固定的x∈Πx, 下層問題(Px)為線性多目標(biāo)規(guī)劃問題，因此(Px)可以等價(jià)地轉(zhuǎn)化為如下標(biāo)量優(yōu)化問題：

s.t.A1x+A2y≤b

綜上，線性二層多目標(biāo)規(guī)劃問題(2)可以轉(zhuǎn)化為如下結(jié)構(gòu)較為特殊的線性二層多目標(biāo)規(guī)劃問題：

s.t.A1x+A2y≤b

(2)

對于問題(2)，以下層問題的K-T最優(yōu)性條件代替下層問題得到：

maxCx+C′y

s.t.A1x+A2y+w=b

uTw+vTy=0

x,y,u,v,w≥0

(3)

其中，u∈Rp,v∈Rm為拉格朗日乘子，w為松弛變量。關(guān)于線性二層多目標(biāo)規(guī)劃問題(1)的最優(yōu)解與轉(zhuǎn)化后的問題(3)最優(yōu)解之間的關(guān)系，有如下結(jié)果：

(4)

(5)

定理1建立了原線性二層多目標(biāo)規(guī)劃問題(1)與轉(zhuǎn)化后的多目標(biāo)規(guī)劃問題(3)在局部Pareto最優(yōu)解之間的等價(jià)關(guān)系。通過求解多目標(biāo)規(guī)劃問題(3)，就可以得到原線性二層多目標(biāo)規(guī)劃問題(1)的局部Pareto最優(yōu)解。問題(3)是帶互補(bǔ)約束的不可微多目標(biāo)規(guī)劃問題，常見的約束規(guī)格一般得不到滿足。因此，采用傳統(tǒng)的數(shù)值方法求解問題(3)存在較大的難度。由于粒子群算法在求解相關(guān)優(yōu)化問題時(shí)，不涉及到函數(shù)的可微性，因此筆者考慮采用粒子群算法求解與原問題(1)等價(jià)的不可微多目標(biāo)規(guī)劃問題(3)。

2 多目標(biāo)規(guī)劃的粒子群算法

2.1粒子群優(yōu)化算法

粒子群優(yōu)化算法(Particle Swarm Optimization,PSO)是由James Kennedy和R.C.Eberhart[6-8]提出的基于群智能的優(yōu)化算法。作為一種新興的高效優(yōu)化算法，PSO算法可用于解決大量不可微的復(fù)雜優(yōu)化問題，而且算法程序簡潔，需要調(diào)整的參數(shù)相對較少。PSO算法中每個(gè)粒子都是解空間的一個(gè)解，每個(gè)粒子根據(jù)自己的飛行經(jīng)歷的個(gè)體歷史最優(yōu)值(pi)和同伴的飛行經(jīng)歷的全局最優(yōu)值(pg)來調(diào)整自己的飛行路線,逐步接近最優(yōu)解所在位置。粒子逐步調(diào)整的過程被認(rèn)為是粒子從群體社會中學(xué)習(xí)和改善的過程。

假設(shè)種群的規(guī)模為N, 搜索空間是D維的，粒子群中第i個(gè)粒子的位置表示為第個(gè)粒子的速度表示為xi=(xi1,xi2,…,xiD)，第個(gè)粒子迄今為止搜索的最好位置記為pbesti=(bi1,bi2,…,biD),整個(gè)粒子群迄今為止搜索到的最好位置記為gbestg=(pg1,pg2,…,pgD)。對于每一個(gè)粒子，其第d維(1≤d≤D)根據(jù)如下等式變化：

vid(t+1)=wvid(t)+c1r1(pbestid(t)-xid(t))+c2r2(gbestgd(t)-xid(t))

xid(t+1)=xid(t)+vid(t+1)

其中,c1,c2為常數(shù)，稱為學(xué)習(xí)因子(通常情況下，c1=c2=2)用來調(diào)節(jié)和方向飛行的最大步長表示(0,1)中的隨機(jī)數(shù)；vid∈[-vmax,vmax]，vmax≥0是之前設(shè)定的最大速度。如果vmax太大, 粒子可能會飛過好的解; 太小, 粒子不能在局部好區(qū)間之外進(jìn)行足夠的搜索, 導(dǎo)致陷入局部最優(yōu)；w稱為慣性權(quán)重，它決定了粒子先前速度對當(dāng)前速度的影響程度，從而起到平衡算法全局搜索和局部搜索能力的作用。一般的做法是取wstart=1.4，wend=0.4，w=wstart-[(wstart-wend)×iter]/Max_iter;其中iter是當(dāng)前迭代次數(shù)，Max_iter是最大迭代次數(shù)。

為了更快的搜集性質(zhì)好的粒子，筆者計(jì)算出每次迭代的所有粒子的最大違反程度，并求出每個(gè)粒子的違反程度與最大違反程度的比值記為λ，將比值分為3類：vmax=A*rand*vmax、vmax=B*rand*vmax、vmax=C*rand*vmax。其中A、B、C為常數(shù)，A、B、C應(yīng)當(dāng)與相應(yīng)范圍的一致。

2.2多目標(biāo)規(guī)劃策略

通過K-T條件將二層多目標(biāo)規(guī)劃問題進(jìn)行轉(zhuǎn)化，可以得到一個(gè)多目標(biāo)優(yōu)化問題。因此首先考慮如下多目標(biāo)規(guī)劃問題的粒子群算法：

minf(x)

s.t.gi(x)≤0 (i=1,2,…q)

hj(x)=0 (j=q+1,…m)

1)約束條件處理技術(shù) 用粒子群優(yōu)化算法求解約束優(yōu)化問題時(shí)，處理約束條件是關(guān)鍵。定義約束違反度函數(shù)[9]：

顯然，Φ(x)是所有違反約束的和，將粒子的位置xi=(xi1,xi2,…,xiD)代入約束條件中，計(jì)算粒子違反約束條件值，并且對所有違反約束條件值取絕對值求和，得出粒子的違反程度。

2)外部精英檔案的維護(hù) 通過采用有限的外部精英集保存迭代過程中搜索到的非支配解[10,11]。當(dāng)外部檔案精英集超過時(shí)，必須對外部檔案進(jìn)行維護(hù)，以確定新解能否進(jìn)入檔案中并保證檔案規(guī)模始終不變。對每一代的每個(gè)新產(chǎn)生的非劣解采用如下步驟以維護(hù)精英檔案：①當(dāng)外部檔案大小小于規(guī)定值時(shí)，新產(chǎn)生的非劣解直接進(jìn)入外部檔案；②當(dāng)外部檔案大小等于規(guī)定值時(shí)，若新產(chǎn)生的非支配解支配了外部檔案的部分個(gè)體，則將新解放入外部檔案并移出外部檔案中受新解支配的精英解；若新產(chǎn)生的非支配解不支配外部檔案中的任何解時(shí)，通過比較擁擠距離的大小移出多余的解，即計(jì)算每個(gè)粒子與其余粒子的擁擠距離得到矩陣A，求出每個(gè)粒子的次小距離(最小距離為其與自身的距離)，并將擁擠距離按逆序排列。

3)個(gè)體最優(yōu)pbest和全局最優(yōu)gbest的選取 粒子的更新通過Pareto支配關(guān)系進(jìn)行比較。

3 線性二層多目標(biāo)規(guī)劃的粒子群算法步驟

步1 根據(jù)K-T條件將線性二層多目標(biāo)規(guī)劃問題轉(zhuǎn)化為帶互補(bǔ)約束的不可微多目標(biāo)規(guī)劃問題。

步2初始化種群。隨機(jī)生成規(guī)模為N的粒子群，設(shè)粒子i初始位置為xi(t)，飛行速度為Vi(t)，粒子i局部最優(yōu)位置為pi(t)=xi(t)。

步3計(jì)算粒子違反約束條件值，并且對所有違反約束條件值取絕對值求和，得出粒子的違反程度。粒子群的全局最優(yōu)位置pg(t)根據(jù)違反程度求得(違反程度最小的粒子為最優(yōu)粒子)，令t=0。

步4更新粒子群中每個(gè)粒子iter。①求出所有粒子每迭代一次的最大違反程度，根據(jù)粒子違反程度與最大違反程度的比值來約束粒子的速度。根據(jù)位置與速度更新公式對粒子進(jìn)行更新，并相應(yīng)更新粒子的違反程度。 ②對粒子進(jìn)行篩選。根據(jù)支配關(guān)系更新外部種群, 并更新可行域與精英集。③將粒子群中更新后的非支配解存放精英集中，去除精英集中所有支配解。

步5對粒子的局部最優(yōu)與全局最優(yōu)值進(jìn)行更新。首先比較當(dāng)前粒子與其上一次pbest的違反程度(違反程度小者為優(yōu))。若兩者違反程度相同，則比較兩者之間的支配關(guān)系。更新后的每個(gè)粒子的pbest與gbest進(jìn)行比較，求出gbest(與求pbest方法同)。

步6判斷iter是否達(dá)到最大循環(huán)迭代次數(shù), 若達(dá)到, 則輸出外部種群, 獲得Pareto最優(yōu)集; 否則iter=iter+1, 返回步3繼續(xù)運(yùn)行。

4 數(shù)值試驗(yàn)

為了說明該粒子群算法的具體計(jì)算步驟，同時(shí)驗(yàn)證算法的可行性，采用筆者所設(shè)計(jì)的粒子群算法求解如下線性二層多目標(biāo)規(guī)劃問題[3]：

s.t.-x+3y≤4

s.t.x-y≤0 -x-y≤0

其中，x∈R,y∈R。

minF(x,y)=(-x+2y,2x-4y)

s.t.-x1+3x2≤4

x1-x2+x6=0

-x1-x2+x7=0

x3+x4+x5=0.5

x2x5+x3x6+x4x7=0 (xi≥0,i=1,…,7)

圖1 Pareto最優(yōu)前沿面

取粒子個(gè)數(shù)n=100，最大迭代次數(shù)N=1000，c1=c2=1,wstart=1.4,wend=0.4, 控制速度的因子A=0.15;B=0.3;C=0.8。判定違反約束程度的誤差限e=0.001，精英集的粒子數(shù)為500個(gè)，試驗(yàn)結(jié)果精英集中粒子個(gè)數(shù)仍為500個(gè)，均為Pareto最優(yōu)解，其最優(yōu)前沿面如圖1所示。由于目標(biāo)函數(shù)f2=-2f1，所以該不可微多目標(biāo)規(guī)劃的最優(yōu)前沿面呈直線遞減趨勢。另外，從圖1可以看到Pareto最優(yōu)解分布均勻。因此，通過對精英集采用擁擠距離法更新，避免了粒子陷入局部最優(yōu)，達(dá)到了增加粒子群搜索的多樣性的目的，因此算法所得非劣解集的均勻性較好。

5 結(jié) 語

對線性二層多目標(biāo)規(guī)劃問題，筆者將其轉(zhuǎn)化為非光滑多目標(biāo)規(guī)劃問題，進(jìn)而設(shè)計(jì)了非光滑多目標(biāo)規(guī)劃問題的粒子群算法，從而得到了線性二層多目標(biāo)規(guī)劃問題的Pareto最優(yōu)解。相比于已有數(shù)值方法只能得到問題一個(gè)Pareto最優(yōu)解，筆者的算法可以獲得多個(gè)Pareto最優(yōu)解，從而有助于決策者做出合理的決策。另外，筆者所設(shè)計(jì)的二層多目標(biāo)規(guī)劃問題的粒子群算法可以推廣到不可微多目標(biāo)規(guī)劃問題的求解。

[1]Zhang G, Lu J, Dillon T.Decentralized multi-objective bilevel decision making with fuzzy demands[J].Knowledge-Based Systems, 2007,20:495-507.

[2] Nishizaka I, Sakawa M.Stackelberg solutions to multiobjective two-level linear programming problems[J].Journal of Optimization Theory and Applications, 1999,103(1):161-182.

[3] Ankhili Z, Mansouri A.An exact penalty on bilevel programs with linear vector optimization lower level[J].European Journal of Operations Research, 2009,197:36-41.

[4] Calvete H I, Gale C.Linear bilevel programs with multiple objectives at the upper level[J].Journal of Computational and Applied Mathematics, 2010,234:950-959.

[5] Tang H W, Qin X Z.Pratical Methods of Optimization[M].Dalian：Dalian University of Technology Press, 2004.

[6] Eberhart R C, Kennedy J.A new optimizer using particle swarm theory[A].Proceedings Sixth Symposium on Micro Machine and Human Science, Piscataway[C].N J：IEEE Service Center, 1995.

[7] Kennedy J, Eberhart R.Particle swarm optimization[A].IEEE International Conference on Neural Networks (Perth, Australia)， Piscataway [C].N J：IEEE Service Center, 1995.

[8] Shi Y, Eberhart R.A modified particle swarm optimizer[A].IEEE International Conference on Evolutionary Computation[C].Anchorage, Alaska, 1998.

[9] 高岳林，張會榮.非線性約束優(yōu)化問題的混合粒子群算法[J].計(jì)算數(shù)學(xué), 2010(5):135-146.

[10] 雷德明, 吳智銘.Pareto檔案多目標(biāo)粒子群優(yōu)化[J].模式識別與人工智能, 2006(4):475-480.

[11] 張利彪, 周春光.基于粒子群算法求解多目標(biāo)優(yōu)化問題[J].計(jì)算機(jī)研究與發(fā)展， 2004(7):1286-1291.

2013-07-24

國家自然科學(xué)基金資助項(xiàng)目(11201039；61273179)，湖北省優(yōu)秀中青年項(xiàng)目(Q20121216)；湖北省教育廳重點(diǎn)項(xiàng)目(D20101304)；大學(xué)生創(chuàng)新訓(xùn)練項(xiàng)目(201210489334)。

胡密(1995-)，女，現(xiàn)主要從事數(shù)學(xué)專業(yè)的學(xué)習(xí)。

呂一兵(1979-)，男，博士，副教授，主要從事最優(yōu)化算法、智能計(jì)算等方面的工作；E-mail: Lvyibing_2001@163.com。

O224；TP18

A

1673-1409(2013)28-0006-05

[編輯] 洪云飛