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

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

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

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

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

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

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

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

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

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

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

1 基本概念

(2)

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

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

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

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

2.1基本粒子群算法

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

PSO算法首先初始化一群隨機粒子，每一個粒子都有一個適應度和速度，在每次迭代中，粒子根據(jù)本身目前所找到的最優(yōu)解(個體極值pbest)和整個種群目前找到的最優(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個粒子在第t次迭代時的速度；xi(t)表示第i個粒子在第k次迭代時的位置；rand()是(0,1)之間的隨機數(shù)；學習因子c1和c2取2.0；慣性權(quán)重ω取值在0.4到0.9之間。文獻[5]證明，隨著迭代的進行，如果ω從最大慣性權(quán)重ωmax線性減小到最小慣性權(quán)重ωmin，將顯著改善算法的收斂性能。即ω取為：

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

2.2約束的處理

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

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

(6)

2.3算法

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

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

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

Step 3 更新下層粒子：

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

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

③tl=tl+1。

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

Step 4 更新上層粒子:

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

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

③tl=tl+1。

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

Step 5t=t+1。

3 數(shù)值試驗

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

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

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

4 結(jié) 語

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

[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]劉國山，韓繼業(yè)，汪壽陽. 雙層優(yōu)化問題的信賴域算法[J].科學通報, 1998,43(4):383-387.

[5] 盛昭翰. 主從遞階決策論——Stackelberg 問題[M]. 北京:科學出版社，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

國家自然科學基金項目(10926168)。

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