混沌差分進化算法在復(fù)雜優(yōu)化問題中的應(yīng)用研究

肖文顯，許利軍，馬孝琴

差分進化算法［1］(differential evolution，簡稱DE)，是由Storn和Price于1995年共同提出的一種基于群體智能的啟發(fā)式優(yōu)化算法.該算法通過群體內(nèi)不同個體間的合作與競爭指導(dǎo)優(yōu)化搜索，具有控制參數(shù)少、收斂速度快等特點.近年來，DE算法以其計算的魯棒性、穩(wěn)定性被廣泛應(yīng)用于諸多領(lǐng)域［2－4］.然而，差分進化算法在應(yīng)用時隨著進化的不斷深入及群體多樣性下降，極易導(dǎo)致算法陷入局部最優(yōu).混沌優(yōu)化算法(chaos optimization algorithm，簡稱COA)是一種新型的直接搜索優(yōu)化算法，算法搜索過程按照混沌運動的自身特性進行，在搜索時具有遍歷和非重復(fù)的特性，具有較高的搜索效率，因此得到廣泛的應(yīng)用［5－7］.

論文將DE算法和COA算法相耦合，提出了混沌差分進化算法(chaos differential evolution algorithm，簡稱CDEA).該算法利用混沌映射(Logistic映射)產(chǎn)生的序列能不重復(fù)地遍歷一定范圍內(nèi)的所有點的特點，彌補差分進化算法容易陷入局部最優(yōu)的缺陷，從而提高算法的全局搜索性能.最后，通過若干典型函數(shù)和TSP問題對改進算法的優(yōu)化效果進行測試，結(jié)果證明了論文算法的可行性和有效性.

1 標(biāo)準(zhǔn)差分進化算法

差分進化算法是一種基于群體差異的啟發(fā)式隨機搜索算法，通過種群內(nèi)個體間的合作與競爭來實現(xiàn)對優(yōu)化問題的求解.標(biāo)準(zhǔn)DE算法的基本操作包括變異、交叉和選擇3種算子.算法首先在問題的可行解范圍內(nèi)隨機初始化種群，X0= ［X01，X02，…，X0NP］，NP為種群個體數(shù)目，上標(biāo)0表示為初始種群.個體x0i=［x0i，1，x0i，2，…，］表征問題的一個解，i為個體編號，D為解鏈長度.算法通過利用種群個體間的差異性，依次進行變異和交叉操作完成對種群個體的進化，隨后以貪婪選擇的原則進行種群個體的優(yōu)選.

算法的基本思想是:按式(1)對第g代種群中編號為i的個體Xgi進行變異操作，得到變異體Vgi+1;然后按式(2)對變異體進行交叉操作，產(chǎn)生試驗個體Ugi+1;對于最小化問題，基于貪婪思想按式(3)進行選擇操作產(chǎn)生新個體.

其中:r1，r2，r3∈{1，2，…，NP};Xgr1為父代基向量;(Xgr2－Xgr3)為父代差分向量;F為縮放因子;g為迭代代數(shù);CR為范圍在0～1之間的交叉概率;行()為在0～1范圍內(nèi)生成的隨機數(shù);j行為{1，2，…，D}之間隨機選取的隨機量;f(·)為適應(yīng)度函數(shù).

2 混沌差分進化算法

2.1 混沌差分進化算法的思想

由于種群多樣性在進化后期迅速下降，標(biāo)準(zhǔn)DE算法極易陷入局部最優(yōu)而造成“早熟”.而混沌優(yōu)化法具有隨機性和遍歷性的特點，可以較好地彌補DE算法的上述缺陷.因此，有研究者考慮將兩種優(yōu)化方法進行耦合，從而得到一種新的優(yōu)化算法［8－9］.但是，這些耦合算法僅利用混沌映射對解空間進行混沌搜索，即突出全局搜索能力.論文在此基礎(chǔ)上進一步利用混沌算法的隨機性和遍歷性，在進化過程中和進化結(jié)束后分別進行混沌擾動，加強算法的局部尋優(yōu)能力，從而達到平衡全局搜索與局部尋優(yōu)的目的.

論文所提出的CDEA算法包含3個基本點:一是，將混沌映射(Logistic映射)產(chǎn)生的混沌序列映射到待求解問題的解空間中，以這些通過映射轉(zhuǎn)換后的混沌序列作為DE算法的初始解;二是，對每個經(jīng)過變異、交叉和選擇操作所得到的個體進行混沌擾動，得到新的個體;三是，將尋優(yōu)得到的全局最優(yōu)解進行混沌擾動，在該點進行局部深度搜索.

2.2 混沌差分進化算法的設(shè)計

(1)編碼設(shè)計

利用CDEA算法求解復(fù)雜優(yōu)化問題時采用實數(shù)編碼，待求解問題的初始解群體以染色體序列X0=［X01，X02，…，X0NP］的形式表示，其中:個體x0i=［x0i，1，x0i，2，…，x0i，D］表征問題的一種可行解.

(2)混沌映射

采用一維Logistic模型來設(shè)計混沌映射，其迭代方程為

其中:Rgi為混沌變量，表示由混沌方程產(chǎn)生的［0，1］之間的某個數(shù)，且R1i∈［0，1］;g為迭代次數(shù);μ為控制參數(shù)，且0≤ μ ≤4.當(dāng) μ ＞ 3.57，R1i∈［0，1］且 R1i≠ {0.25，0.5，0.75}時，序列將在(0，1)內(nèi)永不重復(fù)地“游蕩”，不向任意點收斂且敏感地依賴于初始點.

(3)初始解生成

隨機生成NP個數(shù)據(jù)點R1i，其中:i=1，2，…，NP.分別以這些數(shù)據(jù)點為初始點按式(4)的混沌映射方式進行迭代，得到NP個混沌序列Ri=［R1i，R2i，…，］，D為問題維數(shù).對于每個Ri按式(5)映射到待求解問題的解空間.由此，得到問題的初始解集X0=［X01，X02，…，X0NP］，其中:個體 x0i=［x0i，1，x0i，2，…，］.

(4)進化過程中的混沌擾動機制

對第g代種群XNP×D進行擾動，操作如式(6)、(7)所示.

其中:YNP×n為D個混沌時間序列構(gòu)成的矩陣;γ為擾動步長;X'NP×D為經(jīng)擾動產(chǎn)生的新種群.

(5)對求得最優(yōu)解的混沌擾動機制

對求得的最優(yōu)解增加一個微小的混沌擾動，進行局部深度搜索.可以通過如下步驟:設(shè)ω為當(dāng)前求得的最優(yōu)解x*=(x*1，x*2，…，x*D)映射到［0，1］區(qū)間后的決策向量，ωk為對ω迭代k次后所得到的向量.通過式(8)進行動態(tài)擾動，便可得到擾動后的新決策向量ω'.

其中:α為(0，1)之間的一個數(shù)值，按式(9)進行動態(tài)取值，在進化早期α較大，可進行全局搜索，進化后期，α較小，重點進行當(dāng)前最優(yōu)解小范圍內(nèi)的深度搜索;k為迭代次數(shù);m為一個正整數(shù)，取2.

(6)算法迭代終止判斷

所設(shè)迭代終止條件如下，滿足其中任意條件即可結(jié)束尋優(yōu)迭代:

(i)連續(xù)若干代最優(yōu)適應(yīng)值不變化;

(ii)迭代次數(shù)達到最大迭代次數(shù).

2.3 求解步驟

混沌差分進化算法求解的計算步驟如下:

步驟1 根據(jù)待求解問題確定決策變量和解的取值空間;

步驟2 參數(shù)設(shè)定:確定種群規(guī)模NP、縮放因子F、交叉概率CR、控制參數(shù)μ、擾動步長γ以及參數(shù)m;

步驟3 隨機選取NP個不同的初值，根據(jù)Logistic模型生成初始混沌序列，并按式(5)將其映射到待求解問題的解空間中;

步驟4 按式(1)～(3)進行變異、交叉和選擇操作;

步驟5 對求得的新種群中的每個個體進行式(6)、(7)所示的擾動操作，比較擾動前后個體的適應(yīng)值，取較優(yōu)者進入新一代種群;

步驟6 判斷種群是否收斂，若未收斂，則返回步驟4;若已收斂，則進入步驟7;

步驟7 對當(dāng)前最優(yōu)解進行如式(8)、(9)所示擾動，取擾動前后適應(yīng)值更優(yōu)者作為最終的全局最優(yōu)解，算法結(jié)束，輸出結(jié)果.

3 計算機模擬仿真

3.1 測試函數(shù)仿真

為驗證改進算法的可行性和有效性，采用如下測試函數(shù)對上述算法進行對比測試:

Schwefel函數(shù)

Rastrigrin函數(shù)

實驗設(shè)置的參數(shù)如下:函數(shù)維數(shù)D=5，種群規(guī)模NP=40，最大迭代次數(shù)為100，縮放因子F=0.65，交叉概率CR=0.6，控制參數(shù)μ=4，擾動步長γ=0.1，參數(shù)m=2;分別采用COA、DE以及CDEA對上述測試函數(shù)進行40次優(yōu)化計算，取優(yōu)化結(jié)果的平均值、最優(yōu)值、標(biāo)準(zhǔn)差和運行時間作為衡量指標(biāo)，結(jié)果如表1所示.

表1 優(yōu)化結(jié)果對比Tab.1 Comparison of optimal result

由表中數(shù)據(jù)可見，與COA和DE相比，CDEA的求解結(jié)果均優(yōu)于前兩者，這正說明CDEA具有較強的全局尋優(yōu)能力.對比不同算法求解結(jié)果的標(biāo)準(zhǔn)差可以發(fā)現(xiàn)，CDEA的標(biāo)準(zhǔn)差最低，這也反映出CDEA算法求解穩(wěn)定性優(yōu)于COA和DE.對比3種算法的運行時間，CDEA略長于另外兩種算法，但相差不大.這是由于CDEA在算法結(jié)構(gòu)上比前兩者更加復(fù)雜、求解耗時相對會有一定增加的緣故.求解時間的略微增加帶來的影響與求解性能的大幅提升相比，基本可以忽略不計.因此，CDEA在尋優(yōu)能力和求解穩(wěn)定性上均優(yōu)于COA和DE.

3.2 TSP 問題

測試函數(shù)可以在一定程度上檢測算法的可行性和高效性，然而付諸實際應(yīng)用，仍需進一步檢驗.因此，對于OliverTSP30個城市(已知最優(yōu)解為423.74)和TSP50個城市(已知最優(yōu)解為427.86)，分別采用DE和CDEA進行求解，參數(shù)設(shè)置與3.1中相同.

表2為TSP問題運算20次的平均結(jié)果.對比可以發(fā)現(xiàn)，CDEA對TSP問題的求解所得的最優(yōu)解精度要高于COA和DE算法，且平均尋優(yōu)能力也強于另外兩個算法.對比TSP30和TSP50兩問題的求解結(jié)果可以發(fā)現(xiàn)，CDEA在求解較為復(fù)雜的問題時，尋優(yōu)效果比COA和DE更加明顯.上述結(jié)論與3.1中測試函數(shù)模擬結(jié)果所反映的情況一致，再次印證了論文所提出的CDEA算法的有效性.

表2 TSP30和TSP50問題20次運行結(jié)果Tab.2 The results of 20 iterations between TSP30 and TSP50

4 結(jié)束語

論文將差分進化算法和混沌優(yōu)化方法耦合，利用混沌序列的遍歷性和內(nèi)部迭代的隨機性，彌補差分進化算法容易陷入局部最優(yōu)的缺陷，從而提高算法的搜索性能，避免算法的早熟收斂.對CDEA的核心思想和基本設(shè)計框架進行了闡述，并從數(shù)學(xué)測試函數(shù)和實際問題兩方面對其求解性能進行驗證.針對典型函數(shù)的測試結(jié)果表明:與DE和COA相比，CDEA算法的全局搜索性能有了顯著提高，能有效避免算法陷入局部最優(yōu).在TSP問題中的應(yīng)用表明，論文提出的CDEA算法在求解實際問題時，依然具有較高的實用性和有效性.CDEA算法求解具有高效性和穩(wěn)定性優(yōu)點，適用于求解復(fù)雜的優(yōu)化問題.

［1］ Rainer S，Kenneth P.Differential evolution a simple and efficient heuristic for global optimization over continuous spaces［J］.Journal of Global Optimization，1997(11):341 －359.

［2］ Kim H，Chong J，Park K.Differential evolution strategy for constrained global optimization and application to practical engineering problems［J］.IEEE Transactions on Magetics，2007，43(4):1565 －1568.

［3］ 方強，陳德釗，俞歡軍，等.基于優(yōu)進策略的差分進化算法及其化工應(yīng)用［J］.化工學(xué)報，2004，55(4):598－602.

［4］ 鄭慧濤，梅亞東，胡挺，等.雙層交互混合差分進化算法在水庫群優(yōu)化調(diào)度中的應(yīng)用［J］.水力發(fā)電學(xué)報，2013，32(1):54－62.

［5］ 李兵，蔣慰孫.混沌優(yōu)化方法及其應(yīng)用［J］.控制理論與應(yīng)用，1997，14(4):613－615.

［6］ 李新杰，胡鐵松，郭旭寧，等.0－1測試方法的徑流時間序列混沌特性應(yīng)用［J］.水科學(xué)進展，2012，23(6):875－882.

［7］ 婁素華，吳耀武，熊信銀.電力系統(tǒng)無功優(yōu)化的變尺度混沌優(yōu)化算法［J］.電網(wǎng)技術(shù)，2005，29(11):20－24.

［8］ 盧有麟，周建中，李英海，等.基于混沌搜索的自適應(yīng)差分進化算法［J］.計算機工程與應(yīng)用，2008，44(10):31－33.

［9］ 譚躍，譚冠政，涂立.一種新的混沌差分進化算法［J］.計算機工程，2009，35(11):216－217.