創新粒子群算法：求解二層非線性規劃問題的新途徑

程紅萍

(西安歐亞學院基礎部，西安710065)

由于雙層規劃滿足了絕大多數層次決策問題的實際要求，因此在許多層次決策領域中雙層規劃得到了大量的應用，如：資源分配問題、電力價格和計劃問題、信貸的利率問題、運輸網絡的設計問題、軍事指揮等.但雙層規劃問題較難求解，它是一個典型的非凸不可微規劃，所以多年來，在經濟管理、工程設計、決策和最優控制等領域中引起了國內外學者們的廣泛關注.國際上在雙層規劃領域表現突出的著名學者有Bard，Wen Aiyoshi，Shiminzu，Outrala，Yi等.其中Mathieu R1998年在遺傳算法的基礎上，提出了一種求線性二層規劃問題全局最優解的方法，Bard JF提出了一種網格搜索方法求非線性雙層規劃的方法.在國內，多層規劃的研究在20世紀90年代初才引起關注，較早從事研究的單位有東南大學、中科院系統研究所和自動化研究所、湘潭大學、天津大學和西安電子科技大學等，滕春賢、李智慧的著作《二層規劃的理論與應用》研究了二層線性規劃以及多目標二層非線性規劃的基本概念，性質以及最優性條件和應用等問題.但目前對二層非線性規劃理論和算法的研究大多數僅局限于某些特殊的形式和結構，因此本文對一般的二層非線性規劃的求解方法進行了研究.

1 將二層非線性規劃利用KKT條件轉化為單層非線性規劃問題

二層非線性規劃問題一般可表示為：

利用KKT條件將二層非線性規劃問題轉化為單層規劃問題.

可定義：設變量y的可行域為Y，對于固定的x，將(1)的下層約束中對于y*起作用的下標集用I={i|G2i(x，y*)=0}來記.若{▽xG2i(x，y)|i∈I}關于變量y線性無關，則稱(1)滿足約束規格.

利用罰函數方法求解二層非線性規劃問題時，主要思想是先將下層規劃問題用等價的KKT條件做替代，然后把互補條件作為目標函數的罰項，從而可構造出一個新的非線性規劃.

具體操作為：若f，G2在點(x*，y*)處關于y可微，且對于(1)滿足上面所述的約束規格，則(x*，y*)是(1)的解，當且僅當存在l*(l*∈Rn2)使得點(x*，y*，l*)是問題

然后再把(2)中的互補條件作為目標函數的罰項，于是就可以將問題(2)轉化為：

2 創新的粒子群算法

Eberhart和Kennedy提出了粒子群算法，它是一種基于種群的算法，是在一些種群的社會行為規律的引導下提出來的，把種群稱做粒子群，種群中的個體稱做粒子.設一個群體中有M個粒子，其中第i個粒子表示為一個 N維的向量xi=(xi1，xi2，…，xin)，i=1，2，…，M，也就是說用xi表示第i個粒子在N維的搜索空間中的位置，用ui=(ui1，ui2，…，uin)來記第i個粒子的飛行速度(它也是一個N維的向量)，用pi=(pi1，pi2，…，pin)來記第i個粒子目前搜索到的最優位置.整個種群目前搜索到的最優位置為pg=(pg1，pg2，…，pgn).粒子群算法早期對粒子進行操作采用的是下面的公式：

過去傳統的粒子群算法，記錄每個粒子獲得的信息時，只記錄群體的最優位置和其本身的最優位置，而不記錄其它粒子的信息，其它粒子的最優信息對粒子的運動是否有參考價值?鑒于此原因，在這里我們可以把傳統粒子群算法中的速度和位置公式更新為：

新算法的具體步驟為：

Step1：初始化.在初始化范圍內，對種群(即粒子群)進行隨機初始化.

Step2：計算每個粒子的適應度.

Step3：位置更新.對于每個粒子，把它的適應度和以前所經歷過的最好位置的適應度作對比，如果較好，則把目前粒子所在的位置更新為最好位置.

Step4：全局判斷.對粒子群中的每一個粒子(個體)，將其歷史最好位置的適應度和全局經歷的最好位置的適應度作對比，如果較好，則把它記為目前全局的最好位置.

Step5：根據(6)式和(7)式對粒子的位置和速度做比較.若未達到結束條件，則回到步驟Step2.

3 數值驗證

對于上述創新的粒子群算法，是否可行和有效呢?下面通過數值試驗來驗證.

根據上述創新的粒子群算法，將此非線性二層規劃轉化為下面的單層非線性規劃問題：

4 結語

對于二層規劃問題，由于其本質的非凸性和非處處可微性，從而為求解二層非線性規劃問題的全局最優解帶來了非常大的困難，所以本文首先利用KKT條件將二層非線性規劃問題轉化為單層規劃問題，其次用創新的粒子群優化算法求解單層規劃問題，最后運用數值驗證，不但驗證了該方法的有效性和實用性，而且從數值驗證可以看出，創新的粒子群算法不但提高了求得全局最優解的可靠性和有效性，而且算法簡單，可操作性強.

［1］騰春賢，李智慧.二層規劃的理論與應用［M］.北京：科學出版社，2005.

［2］雍龍泉，張建科，張曉清.求解一類隨機問題的粒子群優化算法［J］.武漢大學學報(理學版)，2005，(S2)：51－53.

［3］劉兵兵.一類非線性二層混合整數規劃問題全局最優解的遺傳算法［J］.燕山大學學報，2007，31(6)：554－557.

［4］郭廣寒，王志剛.一種改進的粒子群算法［J］.哈爾濱理工大學學報，2010，15(2)：31－34.

［5］劉兵兵.一類混合整數二層線性規劃問題的等價形式［J］.安慶師范學院學報(自然科學版)，2011，17(1)：42－45.

［6］吳睿，程紅萍.利用改進的粒子群算法求解二層非線性規劃問題［J］.中國證券期貨，2011，(9)：210.