李美龍代存傑劉昌生
雙層規劃是一種具有二層遞階結構的系統，
上層結構和下層結構都有各自的決策變數、約束條件和目標函式。ｂｌｐｐ研究的是具有兩個層次系統的規劃與管理問題。自適應粒子群優化演算法
不僅具有ｐｓｏ的優勢，如演算法簡潔，引數少，易於實現等，而且平衡了ｐｓｏ演算法的全域性搜尋能力和區域性改善能力，大大提高了ｐｓｏ演算法的收斂性與精度。提出用ａｐｓｏ演算法求解ｂｌｐｐ的問題，借助分層迭代的思想，進而提出了求解雙層規劃模型的通用演算法，最後通過實驗驗證了演算法的有效性。雙層規劃自適應粒子群優化演算法
分層迭代
１引言當前國內外一些學者提出的求解演算法或求解方法，都是針對特定的雙層規劃模型提出的，並且演算法的運
雙層規劃研究的是具有兩個層次系統的規劃與
管理問題。上層決策者只是通過自己的決策去指導下
層決策者，並不直接干涉下層的決策；而下層決策者只需要把上層的決策作為引數，他可以在自己的可能
行效率和收斂精度都不高。本文在分析和借鑑現有的
一些較優秀的演算法思想的基礎上，提出採用自適應
粒子群優化演算法求解雙層規劃模型。實驗研究表明，本文提出的演算法不僅能有效求解雙層規劃模型，可以
獲得高質量的全域性最優解，而且該演算法具有通用性和
範圍內自由決策。這種決策機制使得上層決策者在
選擇策略以優化自己的目標達成時，必須考慮到下層決策者可能採取的策略對自己的不利影響。因此，雙層規劃是一種ｎｐ ｈａｒｄ問題，具有一定的複雜性與現實意義。
普遍性，不依賴於具體的雙層規劃模型。
２雙層規劃模型
雙層規劃模型的基本思想可以用下面的數學模型來描述：
目前對於雙層規劃模型通常採用數值**計算，
以期在合理的時問內獲得模型的近似最優解。但是，
蘭州交通大學機電技術研究所蘭州７３００７０
設上層決策者控制的變數為＝．
圃 ｑ生生釜！塑
下層決策者控制的變數為
上層規劃的數學模型為：
其中ｙ＝ ｆ ）由下層規劃求解。
下層規劃數學的模型為：
ｙ雙層規劃模型是由以上兩個相互關聯的子模型（ｕ）和（ｌ）組成，ｆ是上層規劃所確定的目標函式，ｘ為上層規劃的決策變數，ｇ是對變數的約束；ｆ為下層規劃所確定的目標函式，ｙ為下層規劃的決策變數，
ｇ是對變數ｙ的約束。上層決策者通過設定ｘ的值影響下層決策者，因此限制了下層決策者的可行約束集，而下層決策者的行為反過來又會通過ｙ影響上層
的決策，所以下層決策變數ｙ是上層決策變數ｘ的
函式，即ｙ＝ （ １，這個函式一般稱為反應函式。
一般來說，求解線性雙層規劃問題是非常困難
的，ｊｅｒｏｓｌｏｗ指出線性雙層規劃是乙個ｎｐ—ｈａｒｄ問
題，ｂｅｎ—ａｙｅｄ及ｂａｒｄ對此結論給出了簡短的證明；ｈａｌ１ｓｅｎ對性雙層規劃是強ｎｐ—ｈａｒｄ問題給出了嚴格的證明。後來，ｖｉｃｅｎｔｅ指出，尋找線性雙層規劃的區域性最優解也是ｎｐ～ｈａｒｄ問題，不存在多項式求解算
法。即使雙層規劃上、下層中目標函式和約束函式都
是線性的，它也可能是乙個非凸問題，並且是非處處可微的。非凸性是造成求解線性雙層規劃問題異常複雜的重要原因。
３粒子群優化演算法模型３．１基本粒子群優化演算法
粒子群優化演算法是通過模擬鳥群覓食行為而發展起來的一種基於群體協作的隨機搜尋演算法，在ｐｓｏ
中，每個優化問題的解都是搜尋空間中的乙隻鳥。我
們稱之為「粒子」。所有的粒子都有乙個由被優化的
函式決定的適應值，每個粒子還有乙個速度決定他們飛翔的方向和距離。然後粒子們就追隨當前的最優粒
子在解空間中搜尋。
ｐｓｏ初始化為～群隨機粒子（隨機解），然後通過迭代找到最優解，在每一次疊代中，粒子通過跟蹤
兩個「極值」來更新自己。第乙個就是粒子本身所找
到的最優解，這個解叫做個體極值ｐｂｅｓｔ，另乙個極值是整個種群目前找到的最優解，這個極值是全域性極值ｇｂｅｓｔ。粒子在找到上述兩個極值後，就根據下面兩個公式來更新自己的速度與位置：
一 ）一 ）
＋＝＋＋
其中，為迭代第ｋ步粒子的速度，
為第ｋ步粒子的位置，ｐｂｅｓｔｋ為第ｋ步粒子本身所找到的最優解的位置，ｇｂｅｓｔｋ為第ｋ步整個粒子群當前找到的最優解的位置；ｒａｎｄ是［０，１］之間的隨機數，
ｃ１和ｃ２被稱作學習因子，通常是加權係數，一般取值在０．１－０．９之間。
３．２自適應粒子群優化演算法
為了平衡ｐｓｏ演算法的全域性搜尋能力和區域性改善能力，採用非線性的動態慣性權重係數，公式如下：
ｗ：．』，一
，廠ｗｍ』ｆ≥ 增
其中、ｗｍｉ分別表示ｗ的最大值和最小值，
ｆ表示粒子當前的目標函式值，
和分別表示
當前所有粒子的平均目標值和最小目標值。在上式中，慣性權重隨著粒子的目標函式值而自動改變，因此稱為自適應權重。
當各粒子的目標值趨於一致或者趨於區域性最優
時，慣性權重將增加，而各粒子的目標值比較分散時，
慣性權重將減小，同時對於目標函式優於平均目標值
的粒子，其對於的慣性權重因子較小，從而保護了改
粒子，反之對於目標函式值差於平均目標值的粒子，其對於的慣性權重因子較大，使得該粒子向較好的搜
索區域靠攏。
３．３雙層規劃模型求解方法
雙層規劃問題是乙個多目標優化難題，對於乙個
非線性雙層規劃問題，對其求解會更加複雜。粒子群優化演算法結構簡單，控制引數更少，本文將利用分層
迭代的思想，採用改進的粒子群演算法求解雙層規劃問題。演算法的基本流程如下：
步驟１（初始化）初始化自適應粒子群演算法中的引數；隨機產生下層模型的初始解（需滿足約束條件）。
步驟２（求解上層規劃）將下層模型的解代入上
ｑ！生簋塑困
表１ａｐｓｏ演算法與相關文獻的數值結果的比較
算例例１例２
本文演算法的結果
（ｘ．ｙ）
上層下層
（ｘ，ｙ）
文獻中的結果
上層下層
層模型，利用演算法求解上層模型，獲得上層模型的最
優解。步驟３（求解下層規劃）將上層模型的解代入下
層模型，利用傳統優化方法求解下層模型，獲得下層模型的最優解。
步驟４（判斷）若滿足演算法終止條件（誤差足夠
好或者達到最大迭代條件），則停止，否則轉步驟２。
４算例研究
下面通過幾個雙層規劃模型的數值例子，來驗證
ｐ【本文給出的自適應粒子群演算法求解雙層規劃模型的１ｊ¨．
可行性與有效性，並與參考文獻中的結果做比較。
例１ｍｉｎｘ ＋（ｙ一１ｏ）０ｌ５
ｍｉｎ（ｘ＋２ｙ一３０）
一＋１，≤ｏ
＋一２０ ｏ
ｖ ０例
＋２ｘ２３０
１＋ｘ２２０
ｍｉｎ（ｘ，一 １）＋（一ｙ２）
０ ｙ１ｙ２１０
．在上例中，取離子數為４０，學習因子都取２，最
大慣性權重為０．９，最小慣性權重為０．６，迭代步數取１００，最後得到的結果和文獻比較如表１所示。
從上述的例子結果可以看出，本文演算法的計算結
果和文獻基本相符合，充分可以得出本文演算法的有效
性，另外，由於粒子群演算法的簡單與智慧型化，引數設定比較少，因此，在解決類似問題具有一定的優勢。
５結論採用自適應粒子群演算法求解雙層規劃模型是一
項嶄新的嘗試，通過對算例的數值計算，表明本文提出的演算法是非常有效的。自適應粒子群演算法不僅能夠有效的求解雙層規劃模型，而且具有一定的通用性和普遍性。本研究期望能為以合理的代價用智慧型演算法求解大型複雜模型指明一條新的路徑。
參考文獻：
－【（ｐｅｒｔｈ，
鍆孫會君，高自友．**鏈分銷系統雙層優化模
型［ｊ】．管理科學學報呂振肅，侯志榮．自適應變異的粒子群優化算
法［ｊ］．電子學報
［５］江燕，胡鐵松等．基於粒子群演算法的非線性
二層規劃問題的求解演算法［ｊ】．運籌與管理，
【６】劉佳，秦四平．不確定性決策在配送中心選址ｙ
元素中的應用研究【ｊ】．物流技術
５２—５４．
［７】龔純，王正林．精通ｍａｔｌａｂ最優化設計［ｍ］．
北京：電子工業出版社，２００９．２７卜２９０．
［８］王紅雙，張欣蕾，趙娜．基於雙層規劃模
型的配送中心選址問題研究【ｊ卜科技信
息［作者簡介］李美龍（１９８６年９月一），男，漢族，
陝西省渭南市人，碩士研究生，主要從事物資儲備點選址和智慧型演算法研究。
（收稿日期
經典pso粒子群優化演算法程式
clear all清除所有變數 clc清屏 format long將資料顯示為長整形科學計數 給定初始條條件 n 40初始化群體個數 d 10初始化群體維數 t 100初始化群體最迭代次數 c11 2學習因子1 c21 2學習因子2 c12 1.5 c22 1.5 w 1.2慣性權重 eps 10 ...
非線性規劃的粒子群演算法1
xx大學 智慧型優化演算法課內實驗報告書 非線性規劃問題的粒子群演算法 1.1 背景介紹 1.1.1 非線性規劃簡介 具有非線性約束條件或目標函式的數學規劃，是運籌學的乙個重要的分支，目標函式和約束條件都是線性函式的情形則屬於線性規劃。非線性規劃是20世紀50年代才開始形成的一門新興學科。1951年...
基本粒子群演算法的matlab源程式
主函式源程式 基本粒子群優化演算法 particle swarm optimization 名稱 基本粒子群優化演算法 pso 作用 求解優化問題 說明 全域性性，並行性，高效的群體智慧型演算法 初始格式化 clear all clc format long 給定初始化條件 c1 1.4962 學習...