一種求解非線性二層規(guī)劃的粒子群算法

朱智慧，陳 忠 (長(zhǎng)江大學(xué)一年級(jí)教學(xué)工作部，信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023)

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

一種求解非線性二層規(guī)劃的粒子群算法

朱智慧，陳 忠 (長(zhǎng)江大學(xué)一年級(jí)教學(xué)工作部，信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023)

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

基于下層問(wèn)題的K-T最優(yōu)性條件和罰函數(shù)法，結(jié)合粒子群算法提出了一種求解非線性二層規(guī)劃問(wèn)題的粒子群算法。數(shù)值計(jì)算結(jié)果表明，該算法可以有效地求解非線性二層規(guī)劃問(wèn)題。

非線性二層規(guī)劃；K-T條件；罰函數(shù)法;粒子群算法

二層規(guī)劃是一種具有遞階結(jié)構(gòu)的系統(tǒng)優(yōu)化問(wèn)題，其數(shù)學(xué)模型可以表示為：

其中，上層決策變量x∈Rn1，下層決策變量y∈Rn2，F(xiàn)(x,y)與f(x,y)分別表示上層目標(biāo)函數(shù)與下層目標(biāo)函數(shù)。線性二層規(guī)劃的求解是NP難問(wèn)題，對(duì)于非線性規(guī)劃問(wèn)題的求解就更加困難，目前的方法主要是集中在求解具有某種特殊結(jié)構(gòu)的非線性二層規(guī)劃[1]，如分支定界法[2]、下降方法[3]以及信賴(lài)域方法[4]等。

考慮如下形式的二層二次規(guī)劃問(wèn)題：

式中,F(x,y),f(x,y)分別為上層和下層的目標(biāo)函數(shù)，x∈Rn1,y∈Rn2分別為上、下層決策變量；向量c1,c2∈Rn1，d1,d2∈Rn2，b∈Rm；對(duì)稱(chēng)矩陣R，Q∈R(n1+n2)×(n1+n2)，A∈Rm×n1,B∈Rm×n2。筆者提出了一種求解該類(lèi)問(wèn)題的粒子群算法。

1 基本概念

(2)

定義1稱(chēng)集合S={(x,y)|x≥0,y≥0,Ax+By≤b}為二層二次規(guī)劃問(wèn)題的約束域；集合P={x|?y使得(x,y)∈S}是上層決策變量x的可行域。

為了保證問(wèn)題(1)存在最優(yōu)解，假設(shè)S是非空緊的，Q0為負(fù)定矩陣。因此對(duì)每個(gè)給定的上層決策變量x∈P，下層規(guī)劃問(wèn)題存在唯一的解y(x)。

定義2稱(chēng)集合IR={(x,y)|(x,y)∈S,y=y(x)}為二層二次規(guī)劃問(wèn)題(1)的可行域。

2 非線性二層規(guī)劃的粒子群算法

2.1基本粒子群算法

粒子群優(yōu)化(PSO)算法是一種群智能描述方法，目前已成為演化算法中的研究熱點(diǎn)，并廣泛應(yīng)用于其他領(lǐng)域，如神經(jīng)網(wǎng)絡(luò)訓(xùn)練、模糊系統(tǒng)控制等應(yīng)用領(lǐng)域。

PSO算法首先初始化一群隨機(jī)粒子，每一個(gè)粒子都有一個(gè)適應(yīng)度和速度，在每次迭代中，粒子根據(jù)本身目前所找到的最優(yōu)解(個(gè)體極值pbest)和整個(gè)種群目前找到的最優(yōu)解(全局極值gbest)更新自己：

vi(t+1)=ω·vi(t)+c1·rand()·(pbesti-xi)+c2·rand()·(gbest-xi)

(3)

xi(t+1)=xi(t)+vi(t+1)

(4)

式中，vi(t)表示第i個(gè)粒子在第t次迭代時(shí)的速度；xi(t)表示第i個(gè)粒子在第k次迭代時(shí)的位置；rand()是(0,1)之間的隨機(jī)數(shù)；學(xué)習(xí)因子c1和c2取2.0；慣性權(quán)重ω取值在0.4到0.9之間。文獻(xiàn)[5]證明，隨著迭代的進(jìn)行，如果ω從最大慣性權(quán)重ωmax線性減小到最小慣性權(quán)重ωmin，將顯著改善算法的收斂性能。即ω取為：

式中，iter指當(dāng)前的迭代次數(shù)；itermax為算法設(shè)定的最大迭代次數(shù)。

2.2約束的處理

考慮一般的非線性規(guī)劃問(wèn)題：

對(duì)于上述問(wèn)題(5)，傳統(tǒng)方法的處理方式是將約束優(yōu)化問(wèn)題化為無(wú)約束優(yōu)化問(wèn)題，即將約束條件作為罰項(xiàng)加入目標(biāo)函數(shù)，構(gòu)造相應(yīng)的罰問(wèn)題。然而求解罰問(wèn)題主要面臨如下問(wèn)題：當(dāng)懲罰因子過(guò)小時(shí)得到的解不是原問(wèn)題的最優(yōu)解；如果懲罰因子過(guò)大會(huì)造成數(shù)值計(jì)算的困難。為此，筆者基于競(jìng)爭(zhēng)選擇策略，設(shè)計(jì)了特殊的適應(yīng)度函數(shù)來(lái)處理約束，即：

(6)

2.3算法

下面，筆者利用改進(jìn)的粒子群算法求解非線性二層規(guī)劃問(wèn)題，其主要思想為：對(duì)上層規(guī)劃問(wèn)題使用粒子群算法，而利用單純形法求解下層規(guī)劃問(wèn)題。算法的具體步驟如下：

Step 1 隨機(jī)產(chǎn)生初始粒子群P0,每個(gè)粒子的位置表示為zj=(xj,yj)(j=1,2,…,nl)，其中,xj表示上層決策變量;yj表示下層決策變量；vj=(vxj,vyj)(j=1,2,nl)表示粒子的速度。

Step 2 設(shè)置外層循環(huán)次數(shù)t=0。

Step 3 更新下層粒子：

①設(shè)置初始迭代次數(shù)tl=0。

②保持上層決策變量xj不變，更新粒子的位置與速度：

③tl=tl+1。

④如果tl≥Tl轉(zhuǎn)Step 4；否則轉(zhuǎn)①。

Step 4 更新上層粒子:

①設(shè)置初始迭代次數(shù)tu=0。

②保持下層決策變量yj不變，更新粒子的位置與速度：

③tl=tl+1。

④如果tl≥Tl轉(zhuǎn)Step 5；否則轉(zhuǎn)①。

Step 5t=t+1。

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

為了驗(yàn)證所構(gòu)造粒子群算法的可行性和有效性，考慮如下非線性二層規(guī)劃問(wèn)題：

在例1與例2中，取粒子群的規(guī)模分別為10與20，最大迭代次數(shù)都為50,結(jié)果見(jiàn)表1。結(jié)果表明，筆者所構(gòu)造的粒子群算法是有效的。此外，該算法在迭代過(guò)程中通過(guò)步長(zhǎng)控制避免了使用罰函數(shù)處理約束帶來(lái)的困難，并且迭代的過(guò)程中沒(méi)有復(fù)雜的計(jì)算，實(shí)際的程序運(yùn)行效率較高。

表1 粒子群算法與文獻(xiàn)[5-6]結(jié)果比較

4 結(jié) 語(yǔ)

粒子群優(yōu)化算法具有收斂速度快、操作簡(jiǎn)便、需要調(diào)整參數(shù)少，且對(duì)函數(shù)性質(zhì)要求弱的優(yōu)點(diǎn)。針對(duì)上述優(yōu)點(diǎn)，筆者提出了基于下層問(wèn)題K-T最優(yōu)性條件的粒子群算法，以求解非線性二層規(guī)劃問(wèn)題，并且在處理約束時(shí)，基于競(jìng)爭(zhēng)選擇的概念，設(shè)計(jì)了特殊的適應(yīng)度函數(shù)，使得迭代點(diǎn)在選擇壓力下逐漸向可行域靠近，最終靠近最優(yōu)解。最后，數(shù)值試驗(yàn)表明，該算法是可行和有效的。

[1]Deng X. Complexity issues in bilevel linear programming[M].London: Kluwer Academic Publishers, 1998:149-164.

[2]Bard J F. Practical Bilevel Optimization Algorithms and Application[M].London:Kluwer Academic Publishers, 1998.

[3]Vicente L, Savard G, Judice J. Decent approaches for quadratic bilevel programming[J].Journal of Optimization Theory and Applications, 1994,81(2):379-399.

[4]劉國(guó)山，韓繼業(yè)，汪壽陽(yáng). 雙層優(yōu)化問(wèn)題的信賴(lài)域算法[J].科學(xué)通報(bào), 1998,43(4):383-387.

[5] 盛昭翰. 主從遞階決策論——Stackelberg 問(wèn)題[M]. 北京:科學(xué)出版社，1998.

[6] Mahyar A Amouzegar. A global optimization method for nonlinear bilevel programming problems[J]. IEEE Transactions on Systems, Manamp;Cybernetics-Part B: Cybernetics，1999,29(6): 771-777.

[編輯] 洪云飛

10.3969/j.issn.1673-1409(N).2012.04.001

O224

A

1673-1409(2012)04-N001-03

2012-02-26

國(guó)家自然科學(xué)基金項(xiàng)目(10926168)。

朱智慧(1982-)，男，2002年大學(xué)畢業(yè)，講師，碩士生，現(xiàn)主要從事最優(yōu)化理論與算法方面的教學(xué)與研究工作。