吳亮紅，徐睿，左詞立，曾照福，段偉濤

?

求解一類雙層規(guī)劃的自適應(yīng)變異動態(tài)差分進(jìn)化算法

吳亮紅，徐睿，左詞立，曾照福，段偉濤

(湖南科技大學(xué)信息與電氣工程學(xué)院，湖南湘潭，411201)

針對一類上層函數(shù)和約束函數(shù)不具有凸性和可微性要求，而下層函數(shù)可微且凸的非線性雙層規(guī)劃問題，首先通過Karush?Kuhn?Tucher(KKT)條件將雙層規(guī)劃問題轉(zhuǎn)換為單層約束非線性規(guī)劃問題，并結(jié)合非固定多段映射罰函數(shù)法和精確罰函數(shù)法對約束條件進(jìn)行無約束化處理，然后提出一種改進(jìn)的動態(tài)差分進(jìn)化算法優(yōu)化對系列無約束優(yōu)化問題進(jìn)行求解。對8個測試實例進(jìn)行數(shù)值計算并與現(xiàn)有算法進(jìn)行比較。測試結(jié)果表明，所提方法是一種求解該類雙層規(guī)劃問題的有效方法。

雙層規(guī)劃；KKT條件；罰函數(shù)法；差分進(jìn)化算法

雙層規(guī)劃問題(BLPP)是一類具有主從遞階結(jié)構(gòu)的系統(tǒng)優(yōu)化問題。由于這種模型更能描述實際系統(tǒng)的階層關(guān)系和更全面地體現(xiàn)決策者的意愿，故在經(jīng)濟(jì)、軍事、交通、電力和工程等眾多領(lǐng)域具有十分重要的理論意義和應(yīng)用背景[1?2]。一般來說，求解雙層規(guī)劃非常困難，這主要包括2方面的原因。一方面，雙層規(guī)劃問題是1個NP-hard問題，HANSEN等[3]證明即使是最簡單的雙層線性規(guī)劃也是強(qiáng)NP-Hard問題。VICENTE等[4]指出甚至尋找雙層線性規(guī)劃問題的局部最優(yōu)解也是1個NP-Hard問題。另一方面，由于上層優(yōu)化問題的目標(biāo)函數(shù)取決于下層優(yōu)化問題的解函數(shù)，而這個解函數(shù)一般是非線性且不可微的，故雙層優(yōu)化問題是1個非凸優(yōu)化問題。雙層優(yōu)化問題本質(zhì)的非凸性以及非處處可微性給其數(shù)值求解帶來極大困難，因此，對于非線性雙層規(guī)劃問題，設(shè)計有效求解算法仍是當(dāng)前的研究熱點。在過去的20 多年中，人們對雙層規(guī)劃問題進(jìn)行了許多研究，并取得了一些理論、數(shù)值和應(yīng)用研究成果，總體來說可分為以下3種類型。1) 基于數(shù)值計算的精確算法。這類算法大多是針對一些具有良好問題特性的雙層規(guī)劃問題，如求解線性和二次雙層規(guī)劃的分枝定界法[3]等。其通用方法是利用KKT(Karush?Kuhn?Tucker)條件代替下層規(guī)劃問題，將雙層規(guī)劃問題轉(zhuǎn)化為1個約束單層規(guī)劃問題，然后用數(shù)值計算方法進(jìn)行求解。2) 精確方法與啟發(fā)式算法的結(jié)合。其做法通常是利用KKT條件將雙層規(guī)劃問題轉(zhuǎn)化為單層規(guī)劃問題，然后用啟發(fā)式算法求解該單層規(guī)劃問題，如求解線性雙層規(guī)劃的GA算法[5]和混合禁忌搜索算法[6]、求解非線性雙層規(guī)劃的進(jìn)化算法[7]等。3) 層次啟發(fā)式算法。該類算法是一種求解雙層規(guī)劃問題的一般算法，對上、下層目標(biāo)函數(shù)和約束沒有任何特殊要求，上、下層優(yōu)化算法均采用啟發(fā)式算法，通常采取嵌套方式集成在一起，如求解雙層規(guī)劃問題的PSO算法[8]、層次遺傳算法[9]、差分進(jìn)化算法[10]等。然而，這類算法由于采取嵌套方式，對于每個上層個體都必須調(diào)用1次下層啟發(fā)式算法求得相應(yīng)的下層最優(yōu)解，其計算代價很大。另一方面，若下層啟發(fā)式算法陷入局部最優(yōu)解，則得不到相應(yīng)的上層全局最優(yōu)解。本文著重研究第2種類型的求解方法。差分進(jìn)化(differential evolution, DE)算法是由STORN 和 PRICE 共同提出的一種啟發(fā)式優(yōu)化算法[11]。DE算法原理簡單，受控參數(shù)少，易于理解和實現(xiàn)，實施隨機(jī)、并行、直接的全局搜索，是當(dāng)前最有效的進(jìn)化算法之一[12]。然而，由于原創(chuàng)DE算法在每一代進(jìn)化過程中種群始終保持不變，直到被下一代種群所替代，因此，從種群更新角度，DE算法本質(zhì)上是一種靜態(tài)結(jié)構(gòu)，它沒有立即跟蹤當(dāng)前種群的進(jìn)展?fàn)顩r，存在一代時延。顯然，靜態(tài)種群更新方式會導(dǎo)致算法收斂速度變慢。針對以上不足，QIN等[13]采用動態(tài)更新種群方式對DE/best/1/bin進(jìn)化機(jī)制進(jìn)行改進(jìn)，提出一種動態(tài)差分進(jìn)化策略(dynamic differential evolution,DDE)。DDE利用最新更新的種群生成試驗矢量，從而加快算法的收斂速率[14]。本文針對一類上層函數(shù)和約束函數(shù)不具有凸性和可微性要求而下層函數(shù)可微且凸的非線性雙層規(guī)劃問題，通過KKT條件[15?16]將雙層規(guī)劃問題轉(zhuǎn)換為單層非線性約束優(yōu)化問題，分別應(yīng)用非固定多段映射罰函數(shù)法對不等式約束以及精確罰函數(shù)法對等式約束進(jìn)行無約束化處理，然后應(yīng)用動態(tài)差分進(jìn)化算法對等價系列無約束優(yōu)化問題進(jìn)行求解。為進(jìn)一步提高算法的收斂性能，結(jié)合DDE的2種不同變異機(jī)制優(yōu)點，采用自適應(yīng)策略平衡算法的全局搜索和局部開發(fā)能力，提出一種改進(jìn)的DDE算法，對8個Benchmarks測試實例進(jìn)行數(shù)值實驗。

1 雙層規(guī)劃問題

雙層規(guī)劃問題最初用于描述市場經(jīng)濟(jì)中的寡頭行為。在雙層規(guī)劃模型中，上、下層決策者控制相應(yīng)的決策變量，并優(yōu)化各自的目標(biāo)函數(shù)。其中，下層優(yōu)化問題的最優(yōu)化解決了上層優(yōu)化問題的可行解空間。下層決策者首先進(jìn)行決策，這樣上層決策者必須考慮下層的可能反應(yīng)。下層決策者根據(jù)上層的決策進(jìn)行響應(yīng)，以優(yōu)化自身目標(biāo)函數(shù)。因為雙方可供選擇的策略集是相互依賴的，上層的決策會影響下層可選的決策和目標(biāo)實現(xiàn)，反之亦然。

設(shè)上層決策矢量為=(1，…，x)∈R，下層決策矢量為=(1，…，y)∈R，BLPP的數(shù)學(xué)模型定義如下：

其中：(,)和(,)分別為雙層規(guī)劃的上層目標(biāo)函數(shù)和約束函數(shù)，而(,)和(,)分別為下層目標(biāo)函數(shù)和約束函數(shù)。若所有函數(shù)均為線性函數(shù)，則該問題為線性雙層規(guī)劃，否則為非線性雙層規(guī)劃(NBLP)。本文主要研究一類(,)和(,)沒有凸性和可微性等特殊要求而(,)和(,)是可微且凸的NBLP問題。

2 問題轉(zhuǎn)化

由于本文研究的是一類下層問題可微且凸的雙層規(guī)劃，設(shè)上層和下層約束條件個數(shù)分別為和，則對于每個固定的上層決策矢量，下層優(yōu)化問題可等價于1個KKT駐點問題：

其中：E(,,)為式(2)中的前2項等式，即(,)和(,)的非線性不等式部分；h(,,)為它們的非線性等式部分；+y?為(,)和(,)的所有線性部分。

盡管KKT條件將該類雙層規(guī)劃問題轉(zhuǎn)化為單層規(guī)劃問題，但相應(yīng)的約束條件有所增加且維數(shù)增多。式(3)中不等式主要由目標(biāo)函數(shù)給出，并且包含拉格朗日算子皆為非負(fù)數(shù)的條件；等式約束來源于式(2)，為的維數(shù)。對于該約束優(yōu)化問題，由于約束條件較多且上層優(yōu)化問題非凸不可微，一般算法難以求解，因此，本文采用混合罰函數(shù)法對約束進(jìn)行處理，其中不等式約束采用非固定罰函數(shù)法而等式約束采用精確罰函數(shù)法。同時，為了求得該問題的全局最優(yōu)解，本文提出一種具有良好收斂性能的自適應(yīng)動態(tài)差分進(jìn)化算法對該問題進(jìn)行求解。

3 混合罰函數(shù)法

一般地，在處理式(3)這類優(yōu)化問題時，罰函數(shù)法是比較常見的無約束處理方法之一。其基本思路是在目標(biāo)函數(shù)中加上1個能反映滿足約束的懲罰項，從而構(gòu)成1個無約束的廣義目標(biāo)函數(shù)；再利用優(yōu)化算法對這個無約束優(yōu)化問題進(jìn)行計算尋優(yōu)，利用懲罰項的作用，使得算法找到問題的最優(yōu)解。

在通常情況下，構(gòu)造的廣義目標(biāo)函數(shù)形式為

()=()+()() (4)

其中：()為原目標(biāo)函數(shù)；()()為懲罰項，()為懲罰力度，()為懲罰因子。若式(4)中的()固定不變，則稱該罰函數(shù)法為精確罰函數(shù)法或固定罰函數(shù)法，否則為非固定罰函數(shù)法。非固定罰函數(shù)法可以克服固定罰函數(shù)法中()難以選取的問題，該值若過大，則會在可行域邊界造成目標(biāo)函數(shù)產(chǎn)生病態(tài)，導(dǎo)致計算困難。反之，若該值過小，則會導(dǎo)致收斂減慢甚至不收斂。在非固定罰函數(shù)法中，()隨迭代次數(shù)的變化而動態(tài)調(diào)節(jié)，可避免()的選取問題。

由于問題(3)包含若干個等式約束，且約束條件較復(fù)雜，在直接使用非固定多段映射罰函數(shù)法對問題(3)進(jìn)行無約束處理的過程中，該方法雖然能保證問題(3)在不等式約束存在的情況下進(jìn)行有效尋優(yōu)，但是對于若干個等式約束的處理存在較大偏差。若將等式直接改寫成2個相應(yīng)的不等式，即h()=0等價為h()≤0且h()≥0，會導(dǎo)致因約束過強(qiáng)而算法難以收斂。鑒于以上實際問題，采用精確罰函數(shù)法與非固定罰函數(shù)法相結(jié)合的策略。其中，對于不等式約束部分，采用非固定多段映射罰函數(shù)法，而對于等式約束部分，采用精確罰函數(shù)法，這樣既可有效將問題(3)無約束化，又可簡化懲罰力度的選取，使得問題得到有效解決。修正后的混合罰函數(shù)法為

其中：(,)為上層目標(biāo)函數(shù)；為迭代次數(shù)；()為所有不等式約束函數(shù)；()為所有等式約束函數(shù)；為精確罰函數(shù)的懲罰力度；1為非固定多段映射罰函數(shù)的懲罰因子；2為精確罰函數(shù)的懲罰因子。式(7)表示不等式約束條件對約束的違背程度，式(8)表示其對應(yīng)的罰函數(shù)的強(qiáng)度，式(9)為多段映射函數(shù)，式(10)為隨變化的懲罰力度。通過以上約束處理方式，可將式(3)約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題。

4 自適應(yīng)動態(tài)差分進(jìn)化算法

動態(tài)差分進(jìn)化(DDE)算法的進(jìn)化算子與原創(chuàng)DE完全相同，兩者的最大區(qū)別在于個體的動態(tài)更新方式不同[14]。對于DDE算法，若1個新生成的試驗矢量比其目標(biāo)矢量具有更優(yōu)的適應(yīng)度，則試驗矢量替代目標(biāo)矢量且立即更新當(dāng)前種群參與其后的進(jìn)化操作。與原創(chuàng)DE算法相比，DDE算法由于總是利用最新更新的種群生成試驗矢量，且無需額外的存儲空間來保存下一代父代種群，因此，具有更快的收斂速率。然而，對于DE/best/1/bin策略，動態(tài)更新種群雖然加快了收斂速率，但更容易使算法陷入局部最優(yōu)點。因此，為了平衡算法的全局搜索和局部開發(fā)能力，本文結(jié)合DE/rand/1/bin全局搜索能力強(qiáng)和DE/best/1/bin局部開發(fā)能力強(qiáng)的優(yōu)勢，提出一種具有良好收斂性能和魯棒性的自適應(yīng)變異機(jī)制動態(tài)差分進(jìn)化算法(SADDE)，求解式(5)所示的優(yōu)化問題。

4.1 自適應(yīng)變異操作

在進(jìn)化的每一代，DDE算法通過變異操作為當(dāng)前種群中的每個個體()=(x1,x2, …,x)生成1個目標(biāo)個體() =(v1,v2, …,v)(其中，為當(dāng)前迭代次數(shù))。目前，DE算法已發(fā)展多種不同方式的變異機(jī)制。其中，基于“rand”變異方式的DDE算法能很好地保持種群多樣性，從而有較強(qiáng)的全局搜索能力，但也存在收斂速率較慢的問題；而基于“best”變異方式的DDE算法以當(dāng)前種群中適應(yīng)度最高的個體作引導(dǎo)，具有較強(qiáng)局部開發(fā)能力和較大收斂速率，但很容易陷入局部收斂。綜合考慮這2種變異機(jī)制的特點，本文提出一種自適應(yīng)變異機(jī)制：

式中：，rand為[0,1]均勻分布的隨機(jī)數(shù)；r(=1，2，3)為隨機(jī)個體索引；best表示當(dāng)前種群中動態(tài)更新的最優(yōu)個體；F和F分別為DE/rand/1/bin和DE/best/1/bin這2種變異機(jī)制的變異常數(shù)；min和max分別為選擇變異機(jī)制DE/rand/1/bin的最小和最大概率；為當(dāng)前進(jìn)化代數(shù)；為最大進(jìn)化代數(shù)。由式(12)可知：在進(jìn)化前期，變異機(jī)制DE/rand/1/bin被更多地采用，有效地保證了種群的多樣性，使算法具有較強(qiáng)的全局搜索能力，從而盡可能多地找到潛在全局最優(yōu)點。隨著進(jìn)化代數(shù)增加，變異機(jī)制DE/best/1/bin被選擇的概率不斷增加，算法的局部搜索能力逐步增強(qiáng)，加快了收斂速率，同時也提高了算法精度。

4.2 交叉操作

DE通過將當(dāng)前個體()對應(yīng)變異個體()進(jìn)行交叉，生成試驗個體() =(u1,u2, …,u)，從而提高種群的多樣性。

其中：=1，2，…，；C為交叉概率常數(shù)。DE/rand/1/bin和DE/best/1/bin這2種變異機(jī)制的交叉概率常數(shù)分別用C和C表示。

4.3 選擇操作

DE算法基于貪婪的選擇方式，對測試個體()以及當(dāng)前個體()選擇更優(yōu)的個體進(jìn)入下一代搜索。以最小化問題為例，其選擇策略為

5 算法流程

綜合以上雙層規(guī)劃問題的單層轉(zhuǎn)化方法和混合罰函數(shù)的約束處理方法，本文提出的自適應(yīng)變異DDE算法求解上述雙層規(guī)劃問題的算法流程如下。

Step 1：將相應(yīng)的雙層規(guī)劃問題按照式(2)轉(zhuǎn)化成式(3)這種單層規(guī)劃問題，列出所有的不等式約束和等式約束。

Step 2：給定DDE種群規(guī)模NP、差分變異矢量收縮因子F和F、交叉概率常數(shù)C和C，在每個變量的定義域內(nèi)隨機(jī)初始化每個個體，設(shè)置最大迭代次數(shù)，置當(dāng)前迭代計數(shù)器=0。

Step 3：按式(8)~(10)計算個體對各個不等式約束的懲罰因子，并確定精確罰函數(shù)的懲罰力度。

Step 4：按照式(6)和(11)得到每個個體對應(yīng)的懲罰因子1和2。

Step 5：按式(5)計算每個個體對應(yīng)的上層規(guī)劃目標(biāo)函數(shù)的適應(yīng)值，求出相對應(yīng)的最優(yōu)適應(yīng)值best和最優(yōu)個體best。

Step 6：判斷1和2是否達(dá)到精度要求或者進(jìn)化代數(shù)是否達(dá)到所設(shè)定的最大進(jìn)化代數(shù)，若是，則終止；否則，執(zhí)行下一步。

Step 7：對種群中的個體()執(zhí)行Step 7~Step 10，生成+1代種群。

Step 8：在種群中隨機(jī)選取3個與()不同的個體，按照式(12)和(13)進(jìn)行變異操作，生成變異個體。

Step 9：按照(14)式進(jìn)行交叉操作，生成實驗個體u()。

Step 10：按照式(15)進(jìn)行選擇操作，生成+1代個體X(+1)。

Step 11：=+1，返回Step 3。

6 數(shù)據(jù)分析

6.1 測試函數(shù)

為了證明算法能有效解決該類雙層規(guī)劃問題，選取8個測試問題進(jìn)行數(shù)值仿真實驗。各測試問題的定義如下。

1) TP1：

subject to

。

2) TP2：

subject to

0≤。

3) TP3：

subject to

4) TP4：

subject to

0≤≤1。

5) TP5：

subject to

6) TP6：

subject to

0≤x，=1，2。

7) TP7：

subject to

0≤。

8) TP8：

subject to

0≤≤8。

6.2 測試結(jié)果及分析

實驗中，SADDE算法的參數(shù)設(shè)置如下：種群規(guī)模N=50，最大進(jìn)化代數(shù)=200，2種變異機(jī)制選擇相同的變異常數(shù)F=F=0.5，自適應(yīng)變異策略中DE/rand/1/bin策略的最小和最大選擇概率min=0.1和max=0.8。對于交叉概率常數(shù)，為了突出DE/rand/1/bin的全局搜索能力，選取較小的C以保持種群的多樣性，設(shè)置C=0.1。為了突出DE/best/1/bin的局部開發(fā)能力，選擇較大的C以提高收斂速率和精度，設(shè)置C=0.9。為了避免隨機(jī)性影響，SADDE對每個測試問題獨立運行20次，取最好值為全局最優(yōu)解，如表1所示[17?21]。為了驗證本文方法的有效性，表1給出了與現(xiàn)有文獻(xiàn)其他算法包括遺傳算法(NEA，GA，BIGA，AGA，SMGA，PFGA)、禁忌搜索算法(TS)以及差分進(jìn)化算法(BIDE，DEBLP)等對所選測試問題的最好計算結(jié)果。表1中，(,)和(,)分別表示上層和下層目標(biāo)函數(shù)值。

表1 測試函數(shù)計算結(jié)果

由表1可知：本文方法能夠求得以上所有問題的全局最優(yōu)解，且所求得解完全滿足約束條件。由于使用KKT條件將雙層問題轉(zhuǎn)化為單層問題，使得維數(shù)變多(增加了算子)，而SADDE的參數(shù)設(shè)置較少，故相對于采用KKT條件的其他算法(包括NEA和BMA等)避免了計算過程中一些參數(shù)的反復(fù)調(diào)試，因此，收斂速度較快且更精確。而相對于BIDE，SADDE由于KKT條件的引入和高效約束處理，在計算復(fù)雜度上要遠(yuǎn)比采取嵌套機(jī)制的BIDE低。此外，種群的動態(tài)更新和自適應(yīng)變異機(jī)制使得SADDE具有更快的收斂速率和更高的收斂精度。表2所示為SADDE與NEA求解問題 P1~P5時所用平均CPU時間比較。由表2可知：SADDE的收斂速度明顯要快于NEA，是一種求解該類雙層規(guī)劃問題時的有效算法。

表2 NEA[15]與SADDE平均CPU計算時間

實驗中，對于TP3，TP7和TP8，盡管GA[21]和DEBLP[22]取到了更好的上層結(jié)果，但對于TP3，按照文獻(xiàn)[21]，若上層變量均取0，則要滿足下層目標(biāo)函數(shù)取最小值，下層變量的取值應(yīng)當(dāng)均為0，而并非文獻(xiàn)[21]中給出的(1.5,1.5,1)；若和均取0，反而得到更差的上層解。因此，盡管文獻(xiàn)[21]中取得了更好的上層結(jié)果，但事實上該最優(yōu)解(0,0,1.5,1.5,1)是1個不可行解，其違反了雙層規(guī)劃中下層函數(shù)對上層函數(shù)的約束。同理，對于TP7和TP8，GA和DEBLP均獲到了更好的上層結(jié)果，但其解也是1個不可行解，因此，這2種方法在求解該類問題時不能保證約束滿足。而SADDE不存在此類問題。

此外，為證明自適應(yīng)變異算子的有效性，給出SADDE與DE/rand/1/bin和DE/best/1/bin求解上述8個測試問題20次獨立運行求得的平均最優(yōu)適應(yīng)度，如圖1~8所示。由圖1~8可知：對于測試問題TP1，TP2，TP5和TP8，SADDE均能較快地找到全局最優(yōu)解；對于測試問題TP3，TP4，TP6和TP7，盡管DE/best/1/bin收斂速度很快，但均陷入局部最優(yōu)，而DE/rand/1/bin速度較慢，在迭代次數(shù)較少時難以收斂到全局最優(yōu)解。因此，SADDE綜合了DE/rand/1/bin和DE/best/1/bin這2種變異機(jī)制的優(yōu)點，既能有效地保持種群的多樣性，又具有較快的全局收斂性能，使算法在全局最優(yōu)解的探索和局部最優(yōu)解的開發(fā)之間達(dá)到很好的平衡，是一種求解復(fù)雜非線性約束優(yōu)化問題的有效方法。

1—SADDE；2—DE/rand/1；3—DE/best/1。

1—SADDE；2—DE/rand/1；3—DE/best/1。

1—SADDE；2—DE/rand/1；3—DE/best/1。

1—SADDE；2—DE/rand/1；3—DE/best/1。

1—SADDE；2—DE/rand/1；3—DE/best/1。

1—SADDE；2—DE/rand/1；3—DE/best/1。

1—SADDE；2—DE/rand/1；3—DE/best/1。

1—SADDE；2—DE/rand/1；3—DE/best/1。

7 結(jié)論

1) 針對一類下層函數(shù)可微且凸的非線性雙層規(guī)劃問題，通過KKT條件將雙層規(guī)劃問題轉(zhuǎn)化為非線性約束單層規(guī)劃問題。對于不等式約束和等式約束，分別采用非固定多段映射罰函數(shù)法和精確罰函數(shù)法對約束進(jìn)行處理，將原非線性雙層規(guī)劃問題轉(zhuǎn)化為系列無約束單層非線性優(yōu)化問題。

2) 提出一種自適應(yīng)變異動態(tài)差分進(jìn)化算法對該問題進(jìn)行求解。動態(tài)差分進(jìn)化算法采用動態(tài)更新種群方式，對于任一目標(biāo)個體，若新生成的試驗矢量比其具有更優(yōu)的適應(yīng)度，則試驗矢量替代目標(biāo)矢量且立即加入當(dāng)前種群并參與其后的進(jìn)化操作，這樣大大提高了算法的收斂速率。自適應(yīng)動態(tài)變異機(jī)制結(jié)合了DE/rand/1/bin全局搜索能力強(qiáng)和DE/best/1/bin局部開發(fā)能力強(qiáng)的優(yōu)勢，提高了算法的收斂性能和魯棒性。

3) 本文所提出的方法能夠求得該類非線性雙層規(guī)劃問題的全局最優(yōu)解，具有良好的收斂性能和魯棒性，且相對于NEA，平均CPU時間大幅度縮短，證明了SADDE的計算高效性。

4) SADDE的自適應(yīng)變異機(jī)制相對于DE/rand/1和DE/best/1機(jī)制能夠獲得更好的收斂效果，證實了自適應(yīng)算子的學(xué)習(xí)能力和平衡算法性能的作用。因此，SADDE是一種求解該類非線性雙層規(guī)劃問題的有效方法。

參考文獻(xiàn)：

[1] VICENTE L N, CALAMAI P H. Bilevel and multilevel programming: a bibliography review[J]. Journal of Global Optimization, 2004, 5(3): 291?306.

[2] COLSON B, MARCOTTE P, SAVARD G. An overview of bilevel optimization[J]. Annals of Operational Research, 2007, 153(1): 235?256.

[3] HANSEN P, JAUMARD B, SAVARD G. New branch and bound rules for linear bilevel programming[J]. SIAM Journal on Science and Statistical Computing, 1992, 13(5): 1194?1217.

[4] VICENTE L, SAVARD G, JUDICE J. Decent approaches for quadratic bilevel programming[J]. Journal of Optimization Theory and Applications, 1994, 81(2): 379?399.

[5] WANG Guangmin, WANG Xianjia, WAN Zhongping, et al. An adaptive genetic algorithm for solving bilevel linear programming problem[J]. Applied Mathematics and Mechanics, 2007, 28: 1605?1612.

[6] RAJESH J, GUPTA K, KUSUMAKAR H, et al. A tabu search based approach for solving a class of bilevel programming problems in chemical engineering[J]. Journal of Heuristics, 2003, 9: 307?319.

[7] WANG Yuping, JIAO Yongchang, LI Hong. An evolutionary algorithm for solving nonlinear bilevel programming based on a new constraint-handling scheme[J]. IEEE Transactions on Systems, Man, and Cybernetics: Part C, 2005, 35: 221?232.

[8] 李昌兵, 杜荗康, 付德強(qiáng). 基于層次粒子群算法的非線性雙層規(guī)劃問題求解策略[J]. 系統(tǒng)工程理論與實踐, 2013, 33(9): 2292?2298. LI Changbing, DU Shukang, FU Deqiang. Solution strategy for bi-level nonlinear programming problem based on hierarchical particle swarm optimization[J]. Systems Engineering: Theory & Practice, 2013, 33(9): 2292?2298.

[9] LI Hecheng, LEI Fang. An evolutionary algorithm for solving bilevel programming problems using duality conditions[J]. Mathematical Problems in Engineering, 2012, 20: 1101?1114.

[10] JAQUELINE S A, EDUARDO K, HELIO J C B. Differential evolution for bilevel programming[C]//2013 IEEE Congress on Evolutionary Computation, 2013: 470?477.

[11] STORN R, PRICE K. Differential evolution:a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization, 1997, 11(4): 341?359.

[12] DAS S, SUGANTHAN P N. Differential evolution:a survey of the state-of-the-art[J]. IEEE Transactions on Evolutionary Computation, 2011, 15(1): 4?31.

[13] QIN A K, HUANG V L, SUGANTHAN P N. Differential evolution algorithm with strategy adaptation for global numerical optimization[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(2): 398?417.

[14] 吳亮紅, 王耀南. 動態(tài)差分進(jìn)化算法及其應(yīng)用[M]. 北京: 科學(xué)出版社, 2014: 81?88. WU Lianghong, WANG Yaonan. Dynamic differential evolution algorithm and its application[M]. Beijing: Science Press, 2014: 81?88.

[15] 王宇平. 進(jìn)化計算的理論和方法[M]. 北京: 科學(xué)出版社, 2011: 169?190. WANG Yuping. The theory and methods of evolutionary computation[M]. Beijing: Science Press, 2011: 169?190.

[16] BARD J F. Pratical bilevel optimization[M]Norwell: Kluwer, 1998: 1?50.

[17] SHIMIZU K, AIYOSHI E. A new computational method for Syackelberg and min-max problems by use of penalty method[J]. IEEE Transactions on Automatic Control, 1981, 26(2): 460?466.

[18] WANG Guangmin, WANG Xianjia, WAN Zhongping, et al. Genetic algorithms for solving linear bilevel programming[C]// Proceedings of the Sixth International Conference on Parallel and Distributed Computing Applications and Technologies. Washington DC, USA: IEEE Computer Society, 2005: 920?924.

[19] ODUGUWA V, ROY R. Bi-level optimization using genetic algorithm[C]//Proceedings of IEEE Int Conf Artificial Intelligence Systems, 2002: 123?128.

[20] 張蕾. 求解一類特殊非線性雙層規(guī)劃問題的進(jìn)化算法[D]. 西安: 西安電子科技大學(xué)計算機(jī)學(xué)院, 2010: 21?29. ZHANG Lei. Evolutionary algorithms for one special class of nonlinear bilevel programing problem[D]. Xi’an: Xi’an Electronic and Science University. School of Computer Science and Technology, 2010: 21?29.

[21] KOH A. Solving transportation bi-level programs with differential evolution[C]//2007 IEEECongress on Evolutionary Computation, 2007: 2243?2250.

(編輯 陳燦華)

A self-adaptive mutation dynamic differential evolution algorithm for a class of bi-level programming problem

WU Lianghong, XU Rui, ZUO Cili, ZEN Zhaofu, DUAN Weitao

(School of Information and Electrical Engineering,Hunan University of Science and Technology, Xiangtan 411201, China)

Considering aclass of nonlinear bi-level programmingproblem withnon-convex and non-differentiable upper-levelfunction and constraints, convex and differentiablelower-level function and constraints was studied. The Karush-Kunh-Tucker (KKT)conditions were firstly used to transform the bi-level programming problem intoa single-leveloptimization problem. Then, the non-fixedmulti-segmentmappingpenalty function andfixedpenalty function methods were combined to deal with theconstraints. Thereafter, an improved dynamicdifferential evolution algorithm was proposed to solvethe sequence non-constraint problems. Eight benchmarks problems were used to test the proposed method. The results show that, the proposed method is veryeffective for solving such class of bi-level programming problem compared with other algorithms.

bi-level programming; KKT conditions; penalty function method; differential evolution algorithm

10.11817/j.issn.1672-7207.2016.10.021

TP18

A

1672?7207(2016)10?3436?09

2015?11?20；

2016?01?15

國家自然科學(xué)基金資助項目(61203309，51374107，61403134)；湖南省教育廳優(yōu)秀青年基金資助項目(12B043)；湖南省研究生科研創(chuàng)新項目(CX2015B488)(Projects(61203309, 51374107, 61403134) supported by the National Natural Science Foundation of China; Project(12B043) supported by Education Department of Outstanding Youth Foundation of Hunan Province; Project(CX2015B488) supported by Innovation Foundation of Hunan Province For Postgraduate)

吳亮紅，博士，副教授，從事智能優(yōu)化算法、多目標(biāo)優(yōu)化、智能控制理論及應(yīng)用研究等；E-mail: lhwu@hnust.edu.cn