解決高維INLP和MINLP問題的混沌差分進化算法

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

(湖南城市學院 信息與電子工程學院，湖南 益陽 413000)

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

根據混沌的用途，常見混沌差分進化算法可分為2 類.第1 類是混沌全局搜索算法，它是用混沌序列來替換DE 算法中的一個或多個參數以增強DE 的全局搜索能力[5-8].之所以被稱為混沌全局搜索算法，是因為DE 本身是一種全局搜索算法，用混沌序列替換參數沒有改變它搜索的性質.第2 類是混沌局部搜索算法，它是在每一代的進化過程中，對當前種群的最優解疊加一個混沌序列來產生一組新解.由于這類算法都是基于最優解來搜索新解，因而它被認為是一種局部搜索算法.根據每次搜索過程中最優解向量維數改變的情況，混沌局部搜索算法又可分為單維的混沌局部搜索[9-10]和多維的混沌局部搜索[11-13].本文提出一種用于解決高維的整數非線性規劃(INLP)問題和混合整數非線性(MINLP)規劃問題的混沌差分進化算法，它是將上述2 類混沌差分進化算法融合在一起，再采用一種混沌全局搜索而構成的混合算法.

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

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

1 一種新的混沌差分進化算法

大多數學者只用了第1 類或第2 類混沌差分進化算法來求解某個或某類具體的優化問題.實際上，第1 類混沌差分進化算法能較好地提高DE的全局搜索能力，因為DE 是一種隨機的全局搜索算法；第2 類混沌差分進化算法則能較好地提高DE 的局部搜索能力，因為每次搜索時只基于當前種群的最優解在一個小的搜索范圍內產生一個新解.根據上述2 類混沌差分進化算法的特點可知，一個好的混沌差分進化算法應能同時提高DE的全局和局部搜索能力.

1.1 混沌序列替換DE 的參數

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

當DE 求解高維的INLP 和MINLP 問題時，讓縮放因子F保持固定不變的常數能導致種群的多樣性不足，因而降低DE 的全局搜索能力.為解決這一問題，可用一個變化的參數來替換縮放因子，所以采用混沌序列來實現這一目的.盡管有許多動態系統具有混沌行為，但是Logistic 映射是應用最廣的一種混沌系統，它被定義為

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

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

其中，f為目標函數；為第G+1 代的第i個個體.

1.2 混沌局部搜索

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

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

1.3 混沌全局搜索

在元啟發式算法中混沌映射的2 個主要應用是替換參數和混沌局部搜索.實際上，混沌映射還可以用來執行全局搜索.當每次進行混沌全局搜索時，通過混沌映射方程在整個解空間產生一個新解.在所有的新解產生之后，再從其中選擇出最好的解與當前種群的最優進行比較，如果前者優于后者，則后者被前者替換.混沌全局搜索描述如下：

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

1.4 算法步驟

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

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

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

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

3)對PN個初始個體進行評價，選出目標函數值最好的個體作為當前種群的最優解bs，設進化代數 1g= .

4)根據式(3)和式(4)執行變異操作.

5)通過式(5)執行交叉操作.

6)根據式(6)進行選擇操作，若選擇操作后的個體優于bs，則用前者替換后者.

7)執行1.3 節中的混沌全局搜索后再執行1.2節的混沌局部搜索.

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

1.5 約束條件的處理

當元啟發式算法應用于求解INLP 和MINLP問題時，通常需要對這些問題的約束條件進行處理.處理約束條件最簡單的方法是保留可行解而舍棄不可行解，這里也采用這種簡單策略來處理約束條件.在CGLSDE 算法中，當執行變異、交叉、混沌局部搜索和混沌全局搜索時，若有n維實數和m維整數的一個解變成了另一個(n+m)維的實數解時，則將該解中相應的m維實數通過四舍五入變為m維整數.若通過四舍五入變化之后的解不滿足所有約束條件，則將其舍棄.

2 仿真實驗及分析

2.1 測試問題

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

1)問題P1.P1 屬于高維的INLP 問題，其目標函數及約束條件如下：

P1 的全局最優解為

對應的目標函數最大值fmax(x) = 1 352 439.

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

3)問題P3.P3 也是一個高維的INLP 問題，其目標函數及約束條件如下：

已知的最優解由CLPSO 算法獲得[20]，對應的目標函數最大值fmax(x) = 304 117 194.

4)問題 P4.該測試問題是一個高維的MINLP 問題，目標函數和約束條件函數與P3 相同，但其決策變量中的50 維為整數，50 維為實數，具體如下：

2.2 實驗結果及分析

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

每個問題用上述4 種算法求解50 次，所得到的結果如表1 所示.

由表1 可知，對于P1，CGLSDE 每次都能找到全局最優值，CDE 和CLSDE 有時能找到，但DEMSCLS 都不能找到；當優化P2 時，CGLSDE優于其它3 種算法，而CDE 和CLSDE 優于DEMSCLS；對于P3，CGLSDE 獲得的結果都好于CDE、CLSDE 和DEMSCLS，而CDE 獲得的每個結果都比CLSDE 和DEMSCLS 差；當優化P4 時，CGLSDE 獲得的結果最好，DEMSCLS 次之，CLSDE 最差.總之，CGLSDE 在優化上述4個問題時獲得的結果整體都好于CDE、CLSDE和DEMSCLS.

表1 4 種算法分別對P1～P4 單獨優化50 次的結果

為了對不同算法的平均收斂速度進行直觀地對比，對4 個函數50 次實驗的每一代最優個體目標函數值的平均值進行計算，所得到的結果分別如圖1～圖4 所示.

圖1 P1 的平均收斂速度

圖2 P2 的平均收斂速度

圖3 P3 的平均收斂速度

圖4 P4 的平均收斂速度

從圖1～圖4 的平均收斂速度曲線對比中不難發現，CGLSDE 平均的收斂速度是4 種算法中速度最快的.根據以上比較可看出，CGLSDE 優于CDE、CLSDE 和DEMSCLS.在4 種算法中，CDE只用混沌序列來替換DE 的參數，CLSDE 和DEMSCLS 都能對當前種群的最優解執行多維的混沌局部搜索，而DEMSCLS 還具有單維的混沌局部搜索能力.從本質上來說，CGLSDE 可以視為在CDE 和DEMSCLS 結合的基礎上再通過混沌全局搜索來進一步增強DE 全局搜索能力.因此，CGLSDE 比CDE 和CLSDE 具有更強的局部和全局搜索能力，而比DEMSCLS 具有更強的全局搜索能力.

3 結束語

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