學術研討ｌ１２５
非線性雙層規劃具有遞階結構，被證明是ｎｐ難問題。本文研究了一類下層是連續可微的非線性雙層規劃問題。利用ｋｋｔ最優性條件把下層最優化問題轉為上層最優化問
題的一系列約束條件，利用平滑方法處理了約束條件中
的互補鬆弛問題，從而簡化了原問題的求解。在此基礎上針對轉化後的優化問題，設計了改進的粒子群演算法。利用參考文獻中的兩個數值例子對演算法進行了驗證和比較，結果表明演算法是有效的。
一類雙層規艾ｌｊ問題酌
粒子群演算法研究
◇樂山職業技術學院新能源工程系高紅兵
雙層規劃是一種是具有兩個層次系統的規劃與管理問題則稱（，ｙ ）為問題（１）的最優解，ｆ（，ｙ ）為其對應的最優值。
在這個問題中涉及到兩個子優化問題及兩個決策者，上層決策者通過自己的決策去控制下層決策者的決定，但不能直接干涉下層的決策，反之，下層決策者需要把上層的決策作為引數，其可以在自己的可能範圍內自由決策。這種決策機制使得上層決策者在選擇策略以使得達到自己目標的同時，必須考慮到下層決策者可能採取的方案對自己的不利影響。此類問題廣泛應用於資源分配，選址，決策控制，網路規劃等 。
國內外一些學者對雙層規劃進行了大量的研究，如利用導數資訊的條件 ，罰函式法以及不需要導數資訊的啟發式演算法 。。由於雙層規劃的特殊性和複雜性，其被證明是求解非線性雙層規劃問題的一類有效方法 。
１非線性雙層規劃問題
為了更好的定義問題（１），特做以下假設。
假設１：（１非空；
假設２：ｓ非空且緊的。
由於函式為連續可微函式，於是利用ｋａｒｕｓｈ—
優性條件，（１）轉化為以下問題。
．．ｍ ｖ 三
０．（２）
其中是ｌａｇｒａｎｇｅ乘
子。考慮如下雙層規劃問題。
２問題（２）中的引數處理方法在問題（２）中，對於難１
ｌｌ方法處理（３），詳細過程見參考文獻［６】。
於是（３）可由下式近似替代：
（３）的處理不是很容易，本文利用平滑
在（１）中ｘｒｒ
，ｒ，ｆ：ｒ」
ｒ其中ｎ，ｍ，ｐ，ｑ為
，非負整數為連續可微函式。ｘ，ｙ分別稱為上層決策變數和下層決策變數。
對於（１），給出相關定義：
１一廳（）一
於是問題（２）可轉化為以下問題：
＝０，：１．
ｒ－、（ａ）（１）的約束域為
（ｂ）對固定的ｘ，下層決策問題的可行域
≤ｏ｝。
一ｈｊ（ｘ，）一
在後面的演算法設計中，把引數￡作為乙個變數來處理，在
（ｃ）上層決策空間ｘ的投影下層決策問題的合理反應集
其中（ｅ）誘導域在上定義中，ｉｒ實質上是問題（１）的乙個可行域。
給定￡≥０和ｘ情況下，只要通過求解（４）可以得到最優解ｙ。如果（，）滿足（１）中下層決策問題的所有約束條件，則下層可獲得其最優解ｙ，在求得ｙ之後，於是可求解問題（６）來取得上層決策
問題的最優解 ，從而獲得（１）的最優解（ｘ，）。
３改進的粒子群演算法求解（１）３．１粒子群演算法
（６）定義１如果（ｘ，）∈ｉｒ，則稱（，）是問題（１）的可行點。定義２對於（，）∈ｉｒ和對任何（，）∈儂，如果ｆ（，
１２６ｉ南ｉ恤２０１５年．第１０期
對以上問題，分別記廠（，ｙ ）為執行５【１次後得到的最好解，在（，ｙ ）處上層決策問題的目標函式最優值和下層決策問題的目標函式最優值。同樣記分別記
粒子群演算法是一種基於群體的思想上的隨機優化演算法 。在ｐｓｏ中，每個群體稱為群，個體稱為粒子，粒子通過改變其方向和位置來尋得其最佳位置
（最優解）。
為執行５（）次後得到的最差解，在（ｘ，ｙ）
處上層決策問題的目標函式最差值和下層決策問題的目標函式最差值。表１和表２給出了相關結果。
本文演算法所得結果問題ｓ
０ １設在乙個ｄ維的目標搜尋空間有ｉ個粒子組成的群體，其中第ｉ個粒子表示成乙個ｄ維的向量…，
？，其每個粒子就是乙個潛在解。記第ｉ個粒子在在第ｋ次迭代
（對應文獻的結果
的位置為＝（，，…，），速度記為記第ｉ個粒子迄今為止搜尋到的最優位置為
ｙ ）（，ｙ）
（，ｙ）
整個粒子群迄今為止搜尋到的最優位置為
在搜尋最優解的過程中，每個粒子的速度和位置按以下兩個公式進行：
一）＋ｃｒ２（ｇ￣一一 ｋ－『），（７）
ｘｋ＝ｘｋ－＋ｖ
，（８）
在（７）式中，ｗ稱為慣性因子，它的作用在於控制粒子的前一速度對當前速度的影響。
３ ２適應度函式
在（６）中，令 』＝（ｆ．，佔 ，…，），其中ｅ是充分小的非負整數且隨著迭代數的增加趨於零，把ｇ（ｘ，ｙ）０替換為ｇ（ｘ，ｙ）
≤ 』，
令一￡』），０），於是（６）的適應
度函式定義為
其中ｃ為群體中最差可行解的目標函式值，上述ｆ（ｘ，ｙ）的好處是在迭代過程中迫使不可行解可行解靠近。
３．３演算法設計
針對問題（１），我們給出了改進的粒子群演算法。
步驟１：設定群體規模ｍ，最大迭代數ｔ，在解空間ｘ隨機產生乙個初始群體只，令ｔ＝ｌ；
步驟２：對給定的￡ ｏ和ｘ∈ｘ，求解（４），記其解為ｙ；步驟３：對每個ｙ∈ｙ，通過４．１給出的ｐｓｏ演算法求解（６），記
最優解為ｘ，最優值為，。令
步驟４：若，＞ｔ，演算法停止，輸出（，ｙ ）；否則令 ＝ 十１返回步驟２，求得解為（，ｙ』）和目標函式的值為ｆ 如果ｆ』＜ｆ．則令
４數值實驗
為了更好的說明所提出的演算法在求解本文所研究的非線性
規劃問題的有效性，給出了２個數值例子進行驗證。
４ １數值例子
ｍｉ。ｎｆ（ｘ，）＝一一
．十一５ｙ２，
ｙ－＞ｏ．．
ｘ 一２ｘ１＋ｘ；一２ １＋ ２≥一
由文中提供的方法以上問題均可轉化為單層優化問題。
４．２結果分析
對以上問題，在計算過程中令ｗ從０．９到（）．４線性遞減，ｃ＝ｃ：
：２．０，初始位置在搜尋空間隨機產生，初始速度為零，對每個
數值問題獨立執行演算法５０次。演算法執行環境為個人台式電腦，ｗｉｎ７，６４位作業系統。
０．ｏ１
（０，２，２，０）
（ａ）０．０１
（０，０，一１０，一１０）
（０，０，一１ｏ，一１ｏ）
一１ｏ，一１０）（ｏ，ｏ．一１ｏ．一１ｏ）
表１最優解與最差解的比較結果
表２目標函式值的比較結果
從表１和表２可以看出在的情況下，得到的
值比對應的文獻解要好。
５結論本文研究了一類下層是連續可微的非線性雙層規劃，利用
問題的性質和最優性條件通過把下層決策問題轉化為單目標單層的優化問題後，針對上層決策問題設計改進的粒子群演算法求解這類特殊的非線性雙層規劃問題。通過求解兩個數值優化問
題和已有的演算法進行結果分析比較，數值結果表明所設計的算
法是有效的。
【參考文獻】
［１１孫會君，高自友考慮路線安排的物流配送中心選址雙層
規劃模型及求解演算法中國公路學報
自適應粒子群演算法求解雙層規劃模型
李美龍代存傑劉昌生 雙層規劃是一種具有二層遞階結構的系統，上層結構和下層結構都有各自的決策變數 約束條件和目標函式。研究的是具有兩個層次系統的規劃與管理問題。自適應粒子群優化演算法 不僅具有 的優勢，如演算法簡潔，引數少，易於實現等，而且平衡了 演算法的全域性搜尋能力和區域性改善能力，大大提高了 演...
非線性規劃的粒子群演算法1
xx大學 智慧型優化演算法課內實驗報告書 非線性規劃問題的粒子群演算法 1.1 背景介紹 1.1.1 非線性規劃簡介 具有非線性約束條件或目標函式的數學規劃，是運籌學的乙個重要的分支，目標函式和約束條件都是線性函式的情形則屬於線性規劃。非線性規劃是20世紀50年代才開始形成的一門新興學科。1951年...
探索規律中一類求和問題的解法
由規律可以得到n 1個球隊需要進行的比賽場數為s 1 2 3 n 例2 在一條直線上有n個點a1，a2 an 1，an.這n個點一共可以構成多少條線段？解析 點a1和點a2可以構成線段a1a2，點a1和點a3可以構成線段a1a3，點a1和點an可以構成線段a1an，一共是 n 1 條 點a2和點a3...