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

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

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

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

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

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

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

非線性二層規劃；K-T條件；罰函數法;粒子群算法

二層規劃是一種具有遞階結構的系統優化問題，其數學模型可以表示為：

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

考慮如下形式的二層二次規劃問題：

式中,F(x,y),f(x,y)分別為上層和下層的目標函數，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}為二層二次規劃問題的約束域；集合P={x|?y使得(x,y)∈S}是上層決策變量x的可行域。

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

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

2 非線性二層規劃的粒子群算法

2.1基本粒子群算法

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

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

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

2.2約束的處理

考慮一般的非線性規劃問題：

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

(6)

2.3算法

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

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

Step 2 設置外層循環次數t=0。

Step 3 更新下層粒子：

①設置初始迭代次數tl=0。

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

③tl=tl+1。

④如果tl≥Tl轉Step 4；否則轉①。

Step 4 更新上層粒子:

①設置初始迭代次數tu=0。

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

③tl=tl+1。

④如果tl≥Tl轉Step 5；否則轉①。

Step 5t=t+1。

3 數值試驗

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

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

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

4 結 語

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

[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]劉國山，韓繼業，汪壽陽. 雙層優化問題的信賴域算法[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年大學畢業，講師，碩士生，現主要從事最優化理論與算法方面的教學與研究工作。