肖文顯，許利軍，馬孝琴

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

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

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

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

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

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

2 混沌差分進(jìn)化算法

2.1 混沌差分進(jìn)化算法的思想

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

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

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

(1)編碼設(shè)計(jì)

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

(2)混沌映射

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

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

(3)初始解生成

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

(4)進(jìn)化過(guò)程中的混沌擾動(dòng)機(jī)制

對(duì)第g代種群XNP×D進(jìn)行擾動(dòng)，操作如式(6)、(7)所示.

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

(5)對(duì)求得最優(yōu)解的混沌擾動(dòng)機(jī)制

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

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

(6)算法迭代終止判斷

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

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

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

2.3 求解步驟

混沌差分進(jìn)化算法求解的計(jì)算步驟如下:

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

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

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

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

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

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

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

3 計(jì)算機(jī)模擬仿真

3.1 測(cè)試函數(shù)仿真

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

Schwefel函數(shù)

Rastrigrin函數(shù)

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

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

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

3.2 TSP 問(wèn)題

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

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

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

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

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

［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］ 方強(qiáng)，陳德釗，俞歡軍，等.基于優(yōu)進(jìn)策略的差分進(jìn)化算法及其化工應(yīng)用［J］.化工學(xué)報(bào)，2004，55(4):598－602.

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

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

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

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

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

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