程紅萍

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

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

1 將二層非線性規(guī)劃利用KKT條件轉(zhuǎn)化為單層非線性規(guī)劃問題

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

利用KKT條件將二層非線性規(guī)劃問題轉(zhuǎn)化為單層規(guī)劃問題.

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

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

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

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

2 創(chuàng)新的粒子群算法

Eberhart和Kennedy提出了粒子群算法，它是一種基于種群的算法，是在一些種群的社會行為規(guī)律的引導下提出來的，把種群稱做粒子群，種群中的個體稱做粒子.設一個群體中有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個粒子目前搜索到的最優(yōu)位置.整個種群目前搜索到的最優(yōu)位置為pg=(pg1，pg2，…，pgn).粒子群算法早期對粒子進行操作采用的是下面的公式：

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

新算法的具體步驟為：

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

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

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

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

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

3 數(shù)值驗證

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

根據(jù)上述創(chuàng)新的粒子群算法，將此非線性二層規(guī)劃轉(zhuǎn)化為下面的單層非線性規(guī)劃問題：

4 結(jié)語

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

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

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

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

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

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

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