二層規劃求解的精確罰函數蟻群優化算法

馮力靜，陳麗芳，劉洋

(華北理工大學 理學院，河北 唐山 063210)

優化問題[1]具有重要的實際應用價值，備受研究者關注?，F實生活中大量生產管理系統均具有遞階特征，遞階優化問題亦稱多層優化問題，其求解是NP難題[2]。多層規劃的幾何特性比單層規劃要復雜得多，其中二層規劃具有多層規劃的典型特征，能夠有效代表多層規劃問題，因此，該項目從二層規劃入手，研究其特征及求解方法，為多層規劃求解探索一條研究路徑。二層規劃與單層規劃相比有3點本質的不同：(1)上下層決策變量互相影響制約；(2)結構非凸；(3)非處處可微。這些特征為二層規劃求解帶來了極大困難。即使所有函數均是線性函數，也是NP難問題。趙禮陽等[3]提出了二層線性規劃的極點算法，求解過程通過對上層目標函數值的排序，避免了盲目驗證極點，提高了求解效率；余謙等[4]提出了粒子群和單純形法相結合的一種混合粒子群優化算法解決二層線性規劃問題，通過初始種群可行化，控制步長，淘汰不可行粒子等方法避免了罰函數處理約束的困難，提高了算法性能；范宏等[5,6]分別使用了跟蹤中心軌跡內點法和螢火蟲算法結合的混合算法及原-對偶內點法和森林算法對交直流混合輸電網最優潮流和電力系統無功優化的二層規劃問題進行求解，并為算例進行仿真計算，驗證了這些算法在解決實際問題時的可行性；程林鵬等[7]通過下層K-T條件代替下層問題，將二層規劃問題轉化為單層規劃問題，再采用基于Pareto最優解集的螢火蟲群優化算法對其求解，從而避免了算法過早陷入局部最優，通過實例測試表明了算法可行有效；張濤等[8]提出了基于人工蜂群算法求解二層線性規劃問題，數值試驗表明，算法可在較短時間內得到問題的近似最優解；解麗等[9]提出用博弈思想的討價還價模型將二層線性規劃的最優解進行有效化，以此求得問題的Pareto有效解。學者們把粒子群算法、螢火蟲智能群優化算法應用到二層規劃尋優問題中，對二層規劃的算法做了相應的研究，取得很多研究成果，但未考慮上下層全局優化，因此，該項研究擬從全局優化角度解決問題。

蟻群優化算法(Ant Colony Optimization，ACO)采用選擇、更新、合作等分布式并行計算機制，具有良好的搜索性能和較強的魯棒性，在解決典型組合優化問題時顯示出明顯的優越性，目前對蟻群算法在數學理論、算法改進、實際應用等方面的研究[10-17]是計算智能領域的熱點。

罰函數法[18-20]是解決約束優化問題的一種重要、有效的方法，通過在原有目標函數加上由約束函數組成的懲罰項迫使迭代點逼近可行域，把約束優化問題轉化為一個或一系列的無約束優化問題，通過研究無約束問題來解決約束優化問題。但一般罰函數存在計算上的序貫性缺陷，難以直接應用。

為了更好地解決二層規劃問題，該研究將改進蟻群算法應用于二層規劃全局尋優處理，進而推廣到多層規劃問題中?？紤]到二層規劃系統一般帶有約束條件、加大了求解難度，設計一種新的精確罰函數法處理二層規劃問題的約束條件，并將處理過程嵌入蟻群算法流程，編程仿真二層規劃問題的全局尋優，并通過實際問題驗證該算法的有效性。

1二層規劃(BLP)的描述形式

(1)

其中：F，f：Rn1+n2→R，Rn1+n2→Rm1，g；Rn1+n2→Rm2，X，Y分別是Rn1和Rn2的凸子集。

公式(1)，下層以最優決策反應上層，是二層線性、非線性規劃的理論及算法的研究出發點，該研究以此為對象進行研究。

2優化算法設計

2.1 精確罰函數

在解決非線性約束最優化問題時，一般采用罰函數法，它能夠將非線性約束優化問題轉化為無約束優化問題，使得問題求解更加容易。

在應用經典罰函數時，隨著罰因子的變化會引起Hesse矩陣的病態，給無約束最優化的求解帶來障礙，同時，經典罰函數在計算上的序貫性為研究人員的計算應用帶來了困難。精確罰函數，有效地避免了在計算方面的序貫性，并且使約束最優化問題的解直接"精確"地成為該罰函數的某個極小點，因此簡化了問題的求解過程。

不等式約束問題如公式(2)：

(2)

定義一種新的精確罰函數，公式(3)：

(3)

把有約束問題公式(2)轉化為公式(4)的無約束罰函數優化問題：

(4)

如果對于某一個M，無約束罰函數優化問題的最優解也是原不等式約束優化問題的最優解，那么則稱M為精確罰參數，F(x,M)為精確罰函數。

2.2 改進蟻群算法

蟻群算法具有分布式并行計算機制，在處理離散優化問題時，信息素是以離散的方式存儲的；當求解二層規劃的連續優化問題時，信息素仍然離散地分布到各條路徑上，但對解空間的劃分方式與基本蟻群算法不同，對于連續函數最小優化問題，直接求解；對于連續函數最大優化問題，必須要經過變換，將其轉換成在[0,1]上的函數最小優化問題minf(x)+C，其中x∈[0,1]，加常數C的目的是為了使目標函數值大于0。

具體實施過程如下：

(1)解空間的劃分方式：h為自變量x要求精確的小數點位數，用h個十進制數近似表示自變量x，構造由h×10+2個"結點"組成的路徑圖，分h+2層，第一層和最后一層分別為起、終結點且僅含一個結點，記為0。中間包括h層，分別代表x的十分位、百分位、……，這些結點中，相鄰層之間具有連接通路。螞蟻m需逐層游走，不得跨層，所走過的路徑用式(5)解碼計算得到相應的自變量x(m)。

(5)

每只螞蟻第一步均為T(m,1)=0。(螞蟻m第l步所在的結點用T(m,l)表示)。

(2)設螞蟻總數為M0，螞蟻依次通過第一層，第二層……直至最后一層。螞蟻m當前所在的結點為T(m,l-1)=a，螞蟻根據式(6)來選擇下一個結點。

(6)

(3)根據式(7)計算每個結點被選中的概率，選擇下一結點的概率利用遺傳算法中的轉盤法，生成Sr，其中Sr表示用偽隨機選擇來確定下一步要走的結點。

(7)

其中P(a,b)表示從當前結點a轉移到下一層結點b的概率。這個公式僅允許螞蟻在有上一層結點時才允許其向下一層轉移，這是改進蟻群算法區別與其它蟻群算法之處。所有螞蟻按上面的步驟到達h+1層后，均選擇轉移到最后一個結點0上。

(4)螞蟻在游走過程中要按照式(8)不斷改變經過路徑上的殘余信息素，通過殘余信息素量的大小引導下只螞蟻路徑的選擇，經過多次循環之后，得以確定一條最優路徑。之后進行局部殘留信息素的更新：

(8)

其中ρ表示路徑上殘留信息素減弱的速度，通常取定為[0,1]區間上的一個常數，τ0是信息素的初始值，也是一個常數。

(5)所有螞蟻按式(1)～式(4)完成一次循環，利用式(5)解碼螞蟻 選擇的路徑，并計算出第 只螞蟻經解碼之后對應的自變量取值。算出每只螞蟻所對應的函數值，并由式(9)選出函數值最小的螞蟻：

(9)

(6)對函數值最優的這只螞蟻所經過路徑上的信息素按式(10)全局更新：

(10)

其中：i=T(mmin,l-1)，j=T(mmin,l)，l∈[2，h+2]，a是一個[0,1]上的常數，fbest為最優螞蟻所對應的函數值。

(7)重復式(1)～式(6)，當達到指定的循環次數或得到解的最小值在一定循環次數后沒有改進，說明求得最優解，算法結束。

2.3 優化處理步驟

Step1：依據標準解確定解空間，做歸一化處理，利用精確罰函數公式(4)，通過選擇合適的罰因子M處理上層約束問題。

Step2：應用改進的蟻群算法求解上層決策變量值。

Step3：將每個上層決策變量的值，帶入到下層，下層問題轉換成一元連續函數優化問題，利用公式(4)處理下層約束，嵌入蟻群算法計算下層決策變量。

Step4：將下層最優決策變量反饋到上層進行尋優，達到循環次數程序結束，輸出計算結果。

3仿真實驗

由于算法中的參數選擇尚無嚴格的理論依據，該研究采用一些文獻提供的方法得出參數的一般合理范圍，初始參數范圍為：α=0.2～0.8；ρ=0.4～0.9；P0=0.5～1，在此基礎上進一步優化。算法的各個參數，利用仿真實驗通過不同參數對算法運行結果的影響，討論分析參數值的選擇。

該項研究采用經典的實驗方法，控制一個參數變化、保持其他參數不變，經過反復訓練仿真，最終獲得參數最優組合為：α=0.8，ρ=,0.8，P0=0.8，τ0=0.01，h=7，M0=20，M=2，運行循環次數：1 000，程序采用VC++編程實現。

以下面的二層規劃問題為例：

(11)

將數據輸入后，平均時間小于1，得到運行結果為：上層決策變量x=0.999 999，上層決策變量y=0，最優函數值為22.25。表1所示為不同算法求值比較。

表1為理論最優解與文獻[21]及該項研究算法(P-ACO)進行對比，發現P-ACO算法在相當短的時間內得到明顯優于文獻[21]的求解結果且改進了理論最優解和最優值。

表1 不同算法求值比較

4實際應用

4.1 價格控制問題描述

政府為規范價格變動所采取的各種調節和干預措施即為價格控制問題(Price Control Problem)。一般分為直接干預和間接調節方式。對價格行政管理較多的國家，采取直接干預的措施較多；對價格行政管理較少的國家，采取間接調節的措施較多。

價格控制問題是一類具有鮮明實際背景的二層規劃問題，模型如下：

(12)

其中：a，x，b，y∈Rn，P∈Rm，A，B∈Rn×m，Rn表示示n維實數空間。該模型的幾何意義是：下層決策者的目標函數的價值系數x由上層決策者為了優化其自身的目標函數而確定。決策變量y又由下層決策者決定，上層決策者又根據下層進一步調整價值系數x，以使其目標函數最優。分析稅收、補助金規劃和地區性的廢水廢氣處理，確定最優方案主要利用這個模型。

4.2 模型構建及方案優化

分析上述問題，構造數學模型如下：

(13)

其中y為(x給定時)下層規劃的解。

運用線性二級價格控制問題的單純形法[22]求解，可得(0,4)為問題的最優解，該解的實際意義是：上級部門按產品定價x=0給下級部門，下級部門生產y=4個產品為最優方案。這樣的方案可以使上級部門獲利最大為F=24。而下級部門收益卻為0。這樣的最優方案，很難調動生產部門的積極性，在現實生活中明顯不可取。

利用該研究提出P-ACO算法，處理流程如下：

(1)由于本問題屬于約束最大優化問題，應用本算法時，需先將其轉換為約束最小優化問題。

(2)上層屬于無約束最優化問題，依據標準解確定上層決策變量 的取值范圍為[0,1]。下層變量y做變換y-2，構造F(x,y)=10-x-6(y-2)，應用精確罰函數處理約束。

(3)利用P-ACO算法，運行程序，結果,x=0.999 999，y=0.998 325，F(x,y)=15.0 253。

結果分析：運行結果的含義解釋：x=1，y=3其實際意義為：上級部門按產品定價x=1給下級部門，下級部門生產y=3個產品為最優方案。這個方案雖未能使上級部門獲利最大(15<24)，但在考慮利潤的同時兼顧了下級部門利益，能夠充分調動下級部門員工的生產積極性，比單純形法求得的(0,4)方案更符合實際，用于指導生產決策更加科學合理。

5 結論

(1)提出基于精確罰函數的蟻群優化算法，實現了二層規劃問題的優化求解。設計了一種新的精確罰函數處理約束條件，避免了一般罰函數不可微、不光滑的問題，加快算法的收斂速度。

(2)采用改進的蟻群優化算法進行二層規劃上下層組合求解。

(3)通過數值實驗、實際價格控制問題決策對算法進行驗證，編程對整個優化計算過程進行仿真。該研究成果，為二層規劃決策、多層規劃問題求解提供了一種新的研究思路。