解決高維INLP和MINLP問(wèn)題的混沌差分進(jìn)化算法

譚 躍，趙政春，楊 冰，肖 湘

(湖南城市學(xué)院 信息與電子工程學(xué)院，湖南 益陽(yáng) 413000)

差分進(jìn)化(Differential Evolution，DE)最初是由Storn 和Price 提出的，它是一種基于種群的隨機(jī)搜索算法[1].目前，有許多方法被提出并用于改進(jìn)其搜索能力，在這些方法中，混沌差分進(jìn)化算法是一類非常有效的優(yōu)化算法[2-4].

根據(jù)混沌的用途，常見(jiàn)混沌差分進(jìn)化算法可分為2 類.第1 類是混沌全局搜索算法，它是用混沌序列來(lái)替換DE 算法中的一個(gè)或多個(gè)參數(shù)以增強(qiáng)DE 的全局搜索能力[5-8].之所以被稱為混沌全局搜索算法，是因?yàn)镈E 本身是一種全局搜索算法，用混沌序列替換參數(shù)沒(méi)有改變它搜索的性質(zhì).第2 類是混沌局部搜索算法，它是在每一代的進(jìn)化過(guò)程中，對(duì)當(dāng)前種群的最優(yōu)解疊加一個(gè)混沌序列來(lái)產(chǎn)生一組新解.由于這類算法都是基于最優(yōu)解來(lái)搜索新解，因而它被認(rèn)為是一種局部搜索算法.根據(jù)每次搜索過(guò)程中最優(yōu)解向量維數(shù)改變的情況，混沌局部搜索算法又可分為單維的混沌局部搜索[9-10]和多維的混沌局部搜索[11-13].本文提出一種用于解決高維的整數(shù)非線性規(guī)劃(INLP)問(wèn)題和混合整數(shù)非線性(MINLP)規(guī)劃問(wèn)題的混沌差分進(jìn)化算法，它是將上述2 類混沌差分進(jìn)化算法融合在一起，再采用一種混沌全局搜索而構(gòu)成的混合算法.

INLP 和MINLP 這2 類問(wèn)題的目標(biāo)函數(shù)以及 相應(yīng)的約束條件通常都是由一些非線性的函數(shù)組成.INLP 問(wèn)題決策變量的每一維都是整數(shù)，而MINLP 問(wèn)題決策變量的有些維數(shù)為整數(shù)，其它的維數(shù)則為實(shí)數(shù).與INLP 問(wèn)題相比，MINLP 問(wèn)題更難求解.一個(gè)MINLP 問(wèn)題可以表示為 其中，max or min 表示最大最優(yōu)化或最小最優(yōu)化問(wèn)題；x和y分別是n維的實(shí)數(shù)變量和m維的整數(shù)變量；f(x,y)為目標(biāo)函數(shù)；gi(x,y)和h j(x,y)分別是不等式和等式約束條件；和分別是第k維實(shí)數(shù)變量的下界和第l維整數(shù)變量的下界，和是其對(duì)應(yīng)的上界.

求解INLP 和MINLP 問(wèn)題可以分為確定性算法和啟發(fā)式算法.確定性算法又包括分支定界算法[14]、擴(kuò)展切平面算法[15]和外逼近算法[16]等.啟發(fā)式算法，特別是那些基于種群的元啟發(fā)式算法如差分進(jìn)化[17]、粒子群優(yōu)化算法[18]和遺傳算法[19]等深受很多學(xué)者的青睞.

1 一種新的混沌差分進(jìn)化算法

大多數(shù)學(xué)者只用了第1 類或第2 類混沌差分進(jìn)化算法來(lái)求解某個(gè)或某類具體的優(yōu)化問(wèn)題.實(shí)際上，第1 類混沌差分進(jìn)化算法能較好地提高DE的全局搜索能力，因?yàn)镈E 是一種隨機(jī)的全局搜索算法；第2 類混沌差分進(jìn)化算法則能較好地提高DE 的局部搜索能力，因?yàn)槊看嗡阉鲿r(shí)只基于當(dāng)前種群的最優(yōu)解在一個(gè)小的搜索范圍內(nèi)產(chǎn)生一個(gè)新解.根據(jù)上述2 類混沌差分進(jìn)化算法的特點(diǎn)可知，一個(gè)好的混沌差分進(jìn)化算法應(yīng)能同時(shí)提高DE的全局和局部搜索能力.

1.1 混沌序列替換DE 的參數(shù)

差分進(jìn)化算法包含變異、交叉和選擇這3 種操作，變異操作[1]表示為

當(dāng)DE 求解高維的INLP 和MINLP 問(wèn)題時(shí)，讓縮放因子F保持固定不變的常數(shù)能導(dǎo)致種群的多樣性不足，因而降低DE 的全局搜索能力.為解決這一問(wèn)題，可用一個(gè)變化的參數(shù)來(lái)替換縮放因子，所以采用混沌序列來(lái)實(shí)現(xiàn)這一目的.盡管有許多動(dòng)態(tài)系統(tǒng)具有混沌行為，但是Logistic 映射是應(yīng)用最廣的一種混沌系統(tǒng)，它被定義為

其中，k為迭代次數(shù)；μ是控制參數(shù).當(dāng)μ= 4，z( 1) ∈ (0,1)且z(1) ≠ {0.25,0.5,0.75}時(shí)，式(3)表現(xiàn)出混沌行為.將式(3)zk+1替換式(2)的F時(shí)，則變異操作為

其中，交叉因子CR可以在(0,1)的范圍內(nèi)變化；j∈ {1,2,...,D}中D是求解問(wèn)題的維數(shù)；rand(j)是在(0,1)范圍產(chǎn)生的一個(gè)均勻分布隨機(jī)數(shù)；rnb(j)是[1,D]的一個(gè)隨機(jī)整數(shù).

其中，f為目標(biāo)函數(shù)；為第G+1 代的第i個(gè)個(gè)體.

1.2 混沌局部搜索

在元啟發(fā)式算法中通常是當(dāng)前種群的最優(yōu)解用于局部搜索.根據(jù)每次搜索時(shí)最優(yōu)解向量維數(shù)改變的情況，混沌局部搜索可以進(jìn)一步分為單維和多維的混沌局部搜索.單維混沌局部搜索每次搜索時(shí)只有最優(yōu)解向量的某一維被改變，這種搜索方式實(shí)際上是一種精細(xì)搜索；多維混沌局部搜索在每次搜索時(shí)最優(yōu)解向量的每一維都會(huì)發(fā)生改變，與單維混沌局部搜索相比，它能執(zhí)行范圍更大的局部搜索.一個(gè)同時(shí)具有單維和多維搜索能力的混沌局部搜索算法可以描述為

其中，rand是一個(gè)(0,1)范圍的隨機(jī)數(shù)，且rand≠ {0.25,0.5,0.75}；ML為總的混沌局部搜索次數(shù)；D表示求解問(wèn)題的維數(shù).式(7)中pi,j表示第i次多維混沌局部搜索產(chǎn)生的解向量的第j維；b sj為當(dāng)前種群最優(yōu)解向量bs的第j維；α是一個(gè)控制多維混沌局部搜索步長(zhǎng)的參數(shù)；而randint(1,D)表示在[1,D]產(chǎn)生的一個(gè)隨機(jī)整數(shù)D.式(8)中pi,r表示第i次單維混沌局部搜索產(chǎn)生的解向量的第r維；參數(shù)β用于控制單維混沌局部搜索的步長(zhǎng).式(9)中f是目標(biāo)函數(shù)；a表示混沌局部搜索產(chǎn)生的所有解向量，即p1,p2, …,pk, …,pML中的最大目標(biāo)函數(shù)值.式(10)中pb表示p1,p2, …,pk, …,pML中的最優(yōu)解.

1.3 混沌全局搜索

在元啟發(fā)式算法中混沌映射的2 個(gè)主要應(yīng)用是替換參數(shù)和混沌局部搜索.實(shí)際上，混沌映射還可以用來(lái)執(zhí)行全局搜索.當(dāng)每次進(jìn)行混沌全局搜索時(shí)，通過(guò)混沌映射方程在整個(gè)解空間產(chǎn)生一個(gè)新解.在所有的新解產(chǎn)生之后，再?gòu)钠渲羞x擇出最好的解與當(dāng)前種群的最優(yōu)進(jìn)行比較，如果前者優(yōu)于后者，則后者被前者替換.混沌全局搜索描述如下：

其中，rand是一個(gè)(0,1)范圍的隨機(jī)數(shù)，且rand≠ {0.25,0.5,0.75}；t是迭代次數(shù)；MG是總的混 沌全局搜 索次數(shù). 在式(11) 中，ut,d(d= 1,2,...,D，D是求解問(wèn)題的維數(shù))是第t次混沌全局搜索產(chǎn)生的新解的第d維；Ld和Hd表示相應(yīng)的決策變量第d維的下界和上界.式(12)中f表示目標(biāo)函數(shù)；c是混沌全局搜索產(chǎn)生的所有解向量u1,u2,...,uMG的目標(biāo)函數(shù)最大值.在式(13)中ub表示u1,u2,...,uMG中的最優(yōu)解.

1.4 算法步驟

所提出混沌差分進(jìn)化算法(簡(jiǎn)稱為CGLSDE)的步驟如下：

1)初始化種群大小PN，交叉因子CR，最大進(jìn)化代數(shù) maxG，所有決策變量的上界和下界，總的混沌局部搜索次數(shù)LM，總的混沌全局搜索次數(shù)GM.

2)根據(jù)式(14)和式(15)產(chǎn)生包含n維實(shí)數(shù)和m維整數(shù)的一個(gè)個(gè)體，若該個(gè)體不滿足所有的約束條件，則重復(fù)這一過(guò)程直到產(chǎn)生PN個(gè)滿足所有約束條件的個(gè)體作為初始種群.

其中，η表示在(0,1)的一個(gè)均勻分布隨機(jī)數(shù)；和是相應(yīng)的決策變量下界，和是對(duì)應(yīng)上界；randint()為和間一個(gè)隨機(jī)整數(shù).

3)對(duì)PN個(gè)初始個(gè)體進(jìn)行評(píng)價(jià)，選出目標(biāo)函數(shù)值最好的個(gè)體作為當(dāng)前種群的最優(yōu)解bs，設(shè)進(jìn)化代數(shù) 1g= .

4)根據(jù)式(3)和式(4)執(zhí)行變異操作.

5)通過(guò)式(5)執(zhí)行交叉操作.

6)根據(jù)式(6)進(jìn)行選擇操作，若選擇操作后的個(gè)體優(yōu)于bs，則用前者替換后者.

7)執(zhí)行1.3 節(jié)中的混沌全局搜索后再執(zhí)行1.2節(jié)的混沌局部搜索.

8)g←g+ 1，若g≤Gmax，則轉(zhuǎn)步驟4，否則輸出結(jié)果并結(jié)束程序.

1.5 約束條件的處理

當(dāng)元啟發(fā)式算法應(yīng)用于求解INLP 和MINLP問(wèn)題時(shí)，通常需要對(duì)這些問(wèn)題的約束條件進(jìn)行處理.處理約束條件最簡(jiǎn)單的方法是保留可行解而舍棄不可行解，這里也采用這種簡(jiǎn)單策略來(lái)處理約束條件.在CGLSDE 算法中，當(dāng)執(zhí)行變異、交叉、混沌局部搜索和混沌全局搜索時(shí)，若有n維實(shí)數(shù)和m維整數(shù)的一個(gè)解變成了另一個(gè)(n+m)維的實(shí)數(shù)解時(shí)，則將該解中相應(yīng)的m維實(shí)數(shù)通過(guò)四舍五入變?yōu)閙維整數(shù).若通過(guò)四舍五入變化之后的解不滿足所有約束條件，則將其舍棄.

2 仿真實(shí)驗(yàn)及分析

2.1 測(cè)試問(wèn)題

4 種算法，即本文提出的CGLSDE、文獻(xiàn)[5]中的 CDE、文獻(xiàn)[10]中的 DEMSCLS 以及CLSDE(文獻(xiàn)[13]中提出的混沌局部搜索與本文1.1 節(jié)中差分進(jìn)化算法相結(jié)合的一種混合算法)被用于求解4 個(gè)高維的測(cè)試問(wèn)題.

1)問(wèn)題P1.P1 屬于高維的INLP 問(wèn)題，其目標(biāo)函數(shù)及約束條件如下：

P1 的全局最優(yōu)解為

對(duì)應(yīng)的目標(biāo)函數(shù)最大值fmax(x) = 1 352 439.

2)問(wèn)題P2.P2 是一個(gè)高維MINLP 問(wèn)題，其目標(biāo)函數(shù)和約束條件函數(shù)與問(wèn)題P1 完全相同，但其決策變量中的20 維為整數(shù)，20 維為實(shí)數(shù)，具體如下：

3)問(wèn)題P3.P3 也是一個(gè)高維的INLP 問(wèn)題，其目標(biāo)函數(shù)及約束條件如下：

已知的最優(yōu)解由CLPSO 算法獲得[20]，對(duì)應(yīng)的目標(biāo)函數(shù)最大值fmax(x) = 304 117 194.

4)問(wèn)題 P4.該測(cè)試問(wèn)題是一個(gè)高維的MINLP 問(wèn)題，目標(biāo)函數(shù)和約束條件函數(shù)與P3 相同，但其決策變量中的50 維為整數(shù)，50 維為實(shí)數(shù)，具體如下：

2.2 實(shí)驗(yàn)結(jié)果及分析

CGLSDE 算法參數(shù)設(shè)置如下：種群大小PN為問(wèn)題維數(shù)的3 倍；交叉因子CR為0.5；最大進(jìn)化代數(shù) maxG為400 代；總的混沌全局搜索次數(shù)GM和混沌局部搜索次數(shù)ML分別為NP/6和NP/3；當(dāng)對(duì)當(dāng)前最優(yōu)解向量的m維整數(shù)進(jìn)行混沌搜索時(shí)，參數(shù)α為區(qū)間[-5,5]的一個(gè)隨機(jī)整數(shù)；若對(duì)n維實(shí)數(shù)進(jìn)行混沌搜索時(shí)，α為( - 1)i，其中i為當(dāng)前的搜索次數(shù)；類似地，控制參數(shù)β設(shè)置為[ -2 ,2]的隨機(jī)整數(shù)或0.1( - 1)i；為公平起見(jiàn)，DEMSCLS 算法中總的混沌局部搜索次數(shù)為NP/2.

每個(gè)問(wèn)題用上述4 種算法求解50 次，所得到的結(jié)果如表1 所示.

由表1 可知，對(duì)于P1，CGLSDE 每次都能找到全局最優(yōu)值，CDE 和CLSDE 有時(shí)能找到，但DEMSCLS 都不能找到；當(dāng)優(yōu)化P2 時(shí)，CGLSDE優(yōu)于其它3 種算法，而CDE 和CLSDE 優(yōu)于DEMSCLS；對(duì)于P3，CGLSDE 獲得的結(jié)果都好于CDE、CLSDE 和DEMSCLS，而CDE 獲得的每個(gè)結(jié)果都比CLSDE 和DEMSCLS 差；當(dāng)優(yōu)化P4 時(shí)，CGLSDE 獲得的結(jié)果最好，DEMSCLS 次之，CLSDE 最差.總之，CGLSDE 在優(yōu)化上述4個(gè)問(wèn)題時(shí)獲得的結(jié)果整體都好于CDE、CLSDE和DEMSCLS.

表1 4 種算法分別對(duì)P1～P4 單獨(dú)優(yōu)化50 次的結(jié)果

為了對(duì)不同算法的平均收斂速度進(jìn)行直觀地對(duì)比，對(duì)4 個(gè)函數(shù)50 次實(shí)驗(yàn)的每一代最優(yōu)個(gè)體目標(biāo)函數(shù)值的平均值進(jìn)行計(jì)算，所得到的結(jié)果分別如圖1～圖4 所示.

圖1 P1 的平均收斂速度

圖2 P2 的平均收斂速度

圖3 P3 的平均收斂速度

圖4 P4 的平均收斂速度

從圖1～圖4 的平均收斂速度曲線對(duì)比中不難發(fā)現(xiàn)，CGLSDE 平均的收斂速度是4 種算法中速度最快的.根據(jù)以上比較可看出，CGLSDE 優(yōu)于CDE、CLSDE 和DEMSCLS.在4 種算法中，CDE只用混沌序列來(lái)替換DE 的參數(shù)，CLSDE 和DEMSCLS 都能對(duì)當(dāng)前種群的最優(yōu)解執(zhí)行多維的混沌局部搜索，而DEMSCLS 還具有單維的混沌局部搜索能力.從本質(zhì)上來(lái)說(shuō)，CGLSDE 可以視為在CDE 和DEMSCLS 結(jié)合的基礎(chǔ)上再通過(guò)混沌全局搜索來(lái)進(jìn)一步增強(qiáng)DE 全局搜索能力.因此，CGLSDE 比CDE 和CLSDE 具有更強(qiáng)的局部和全局搜索能力，而比DEMSCLS 具有更強(qiáng)的全局搜索能力.

3 結(jié)束語(yǔ)

為了同時(shí)改進(jìn)DE 算法的局部和全局搜索能力，提出了一種被稱之為CGLSDE 的混沌差分進(jìn)化算法.該算法采用了單維和多維的混沌局部搜索改進(jìn)其局部搜索能力，還利用混沌序列替換縮放因子并采用混沌全局搜索方式來(lái)改進(jìn)其全局搜索能力.對(duì)CGLSDE 與其它3 種混沌差分進(jìn)化算法(CDE、CLSDE 和DEMSCLS)用于解決4 個(gè)高維的INLP 和MINLP 問(wèn)題進(jìn)行了比較，仿真結(jié)果表明CGLSDE 要優(yōu)于其它3 種算法.