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

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

?

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

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

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

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

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

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

1 雙層規(guī)劃問題

雙層規(guī)劃問題最初用于描述市場(chǎng)經(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ù)。因?yàn)殡p方可供選擇的策略集是相互依賴的，上層的決策會(huì)影響下層可選的決策和目標(biāo)實(shí)現(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è)上層和下層約束條件個(gè)數(shù)分別為和，則對(duì)于每個(gè)固定的上層決策矢量，下層優(yōu)化問題可等價(jià)于1個(gè)KKT駐點(diǎn)問題：

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

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

3 混合罰函數(shù)法

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

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

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

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

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

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

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

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

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

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

式中：，rand為[0,1]均勻分布的隨機(jī)數(shù)；r(=1，2，3)為隨機(jī)個(gè)體索引；best表示當(dāng)前種群中動(dòng)態(tài)更新的最優(yōu)個(gè)體；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)點(diǎn)。隨著進(jìn)化代數(shù)增加，變異機(jī)制DE/best/1/bin被選擇的概率不斷增加，算法的局部搜索能力逐步增強(qiáng)，加快了收斂速率，同時(shí)也提高了算法精度。

4.2 交叉操作

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

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

4.3 選擇操作

DE算法基于貪婪的選擇方式，對(duì)測(cè)試個(gè)體()以及當(dāng)前個(gè)體()選擇更優(yōu)的個(gè)體進(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，在每個(gè)變量的定義域內(nèi)隨機(jī)初始化每個(gè)個(gè)體，設(shè)置最大迭代次數(shù)，置當(dāng)前迭代計(jì)數(shù)器=0。

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

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

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

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

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

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

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

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

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

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

6.1 測(cè)試函數(shù)

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

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 測(cè)試結(jié)果及分析

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

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

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

表2 NEA[15]與SADDE平均CPU計(jì)算時(shí)間

實(shí)驗(yàn)中，對(duì)于TP3，TP7和TP8，盡管GA[21]和DEBLP[22]取到了更好的上層結(jié)果，但對(duì)于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é)果，但事實(shí)上該最優(yōu)解(0,0,1.5,1.5,1)是1個(gè)不可行解，其違反了雙層規(guī)劃中下層函數(shù)對(duì)上層函數(shù)的約束。同理，對(duì)于TP7和TP8，GA和DEBLP均獲到了更好的上層結(jié)果，但其解也是1個(gè)不可行解，因此，這2種方法在求解該類問題時(shí)不能保證約束滿足。而SADDE不存在此類問題。

此外，為證明自適應(yīng)變異算子的有效性，給出SADDE與DE/rand/1/bin和DE/best/1/bin求解上述8個(gè)測(cè)試問題20次獨(dú)立運(yùn)行求得的平均最優(yōu)適應(yīng)度，如圖1~8所示。由圖1~8可知：對(duì)于測(cè)試問題TP1，TP2，TP5和TP8，SADDE均能較快地找到全局最優(yōu)解；對(duì)于測(cè)試問題TP3，TP4，TP6和TP7，盡管DE/best/1/bin收斂速度很快，但均陷入局部最優(yōu)，而DE/rand/1/bin速度較慢，在迭代次數(shù)較少時(shí)難以收斂到全局最優(yōu)解。因此，SADDE綜合了DE/rand/1/bin和DE/best/1/bin這2種變異機(jī)制的優(yōu)點(diǎn)，既能有效地保持種群的多樣性，又具有較快的全局收斂性能，使算法在全局最優(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) 針對(duì)一類下層函數(shù)可微且凸的非線性雙層規(guī)劃問題，通過KKT條件將雙層規(guī)劃問題轉(zhuǎn)化為非線性約束單層規(guī)劃問題。對(duì)于不等式約束和等式約束，分別采用非固定多段映射罰函數(shù)法和精確罰函數(shù)法對(duì)約束進(jìn)行處理，將原非線性雙層規(guī)劃問題轉(zhuǎn)化為系列無約束單層非線性優(yōu)化問題。

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

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

4) SADDE的自適應(yīng)變異機(jī)制相對(duì)于DE/rand/1和DE/best/1機(jī)制能夠獲得更好的收斂效果，證實(shí)了自適應(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)工程理論與實(shí)踐, 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] 吳亮紅, 王耀南. 動(dòng)態(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)化計(jì)算的理論和方法[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ì)算機(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é)基金資助項(xiàng)目(61203309，51374107，61403134)；湖南省教育廳優(yōu)秀青年基金資助項(xiàng)目(12B043)；湖南省研究生科研創(chuàng)新項(xià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