王 浩 ，李 俊 ，周 蓉

1.武漢科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，武漢 430065

2.智能信息處理與實(shí)時工業(yè)系統(tǒng)湖北省重點(diǎn)實(shí)驗(yàn)室，武漢 430065

1 引言

差分進(jìn)化（Differential Evolution，DE）算法[1]是由美國學(xué)者Storn和Price等人于1995年提出的一種基于群體智能理論的優(yōu)化算法。該算法通過模擬自然界“優(yōu)勝劣汰，適者生存”的法則來實(shí)現(xiàn)種群內(nèi)個體的合作與競爭，使得種群能夠智能進(jìn)行優(yōu)化搜索。DE算法采用了變異，交叉和選擇操作來實(shí)現(xiàn)模擬生物進(jìn)化過程中的基因突變行為，將適應(yīng)性最佳的個體保留下來以此尋求最優(yōu)解。由于其易用性、穩(wěn)健性和強(qiáng)大的全局尋優(yōu)能力，在約束優(yōu)化計(jì)算、聚類優(yōu)化計(jì)算、非線性優(yōu)化、控制神經(jīng)網(wǎng)絡(luò)優(yōu)化等方面得到了廣泛的應(yīng)用。但由于差分進(jìn)化是通過父代個體間的差分矢量進(jìn)行變異、交叉和選擇來實(shí)現(xiàn)尋優(yōu)，與常用進(jìn)化算法相類似，也存在易陷于局部最優(yōu)、過早收斂和停滯的問題。

針對這些問題，國內(nèi)外很多學(xué)者對DE算法進(jìn)行了大量的改進(jìn)，在控制參數(shù)和變異策略[2-4]的優(yōu)化方面，Qin等人[5]提出了單一種群參數(shù)自適應(yīng)的jDE（Differential Evolution algorithm withstrategy adaptation，jDE）。Zhang等人[6]提出了參數(shù)自適應(yīng)和“current-to-pbest/1”策略的JADE（Adaptive Differential Evolution，JADE）。Wang等人提出了適合試驗(yàn)向量代數(shù)策略和固定參數(shù)CoDE（Differential Evolutionwith Composite trial vector，CoDE）[7]算法、變異策略和控制參數(shù)集合的EPSDE（Differential Evolutional gorithm with Ensembleof Parameters and mutation Strategies，EPSDE）[8]算法。Brest等人[9]提出了自適應(yīng)DE算法SaDE，其算法根據(jù)歷史經(jīng)驗(yàn)選擇成功率較高的變異策略和參數(shù)。彭虎等人[10]提出了一種新的基于三角的骨架差分進(jìn)化算法（Bare-BonesDifferentialEvolution algorithm based on trigonometry，tBBDE），并使用隨機(jī)泛函理論分析了算法的收斂性。算法采用了三角高斯變異策略以及三元交叉和交叉概率自適應(yīng)策略對個體進(jìn)行更新，并在收斂停滯時進(jìn)行種群擾動。周新宇等人[11]提出了基于精英反向?qū)W習(xí)的差分進(jìn)化算法。廖雄鷹等人[12]提出了基于自適應(yīng)變異算子的差分進(jìn)化算法。錢武文等人[13]提出了基于反射變異策略的自適應(yīng)差分進(jìn)化算法。在研究高效的算法架構(gòu)[14-15]方面，此類優(yōu)化從種群結(jié)構(gòu)進(jìn)行分析，將初始種群分為多個子種群，子種群間根據(jù)拓?fù)浣Y(jié)構(gòu)相互聯(lián)系，并制訂相應(yīng)的個體遷移機(jī)制，形成分布式差分進(jìn)化算法，分布式DE算法成為DE算法研究的重要分支，引起眾多學(xué)者的關(guān)注。Tasoulis等人[16]提出了并行DE（Parallel Differential Evolution，PDE）算法，對算法的遷移策略、遷移頻率、子種群數(shù)目進(jìn)行了研究。王亞輝等[17]將種群分配為三個子種群，每個子種群為一種進(jìn)化策略，然后根據(jù)每種策略動態(tài)地調(diào)整子種群規(guī)模。Kozlov等[18]對分布式DE算法提出了新的遷移機(jī)制，從而加快算法的收斂速度。Singh等[19]對分布式DE算法的參數(shù)、遷移周期以及遷移個體數(shù)目進(jìn)行了詳細(xì)的研究。DeFale等[20]采用了環(huán)形拓?fù)浣Y(jié)構(gòu)代替單向環(huán)的DDE算法。Weber等人[21]提出了一種縮放因子F自適應(yīng)的分布式DE（“F”Adaptive Control Parallel Differential Evolution，F(xiàn)ACPDE）。文獻(xiàn)[22]提出了參數(shù)適應(yīng)性分布式 DE（Adaptive Parameters Distributed Differential Evolution，APDDE）。

在現(xiàn)有研究中，DE算法仍存在收斂速度慢，容易陷入局部最優(yōu)等問題，特別是在算法進(jìn)化后期，種群資源分布不均、個體多樣性差、算法無法跳出局部最優(yōu)，很大程度地限制了DE算法的開采能力和搜索效率。針對以上問題，本文對差分進(jìn)化策略、單種群進(jìn)化模式兩個方面進(jìn)行了改進(jìn)，以及加入了早熟判定，提出了自適應(yīng)合并與分裂的多種群差分進(jìn)化算法（Adaptive Combine and Split Multi-population Differential Evolution Algorithm，ACSMDE）。ACSMDE在進(jìn)化前期很好地維持種群的多樣性，保證了算法的尋優(yōu)能力，同時有效地避免“陷入局部最優(yōu)”，使盡可能地找到全局最優(yōu)解；而在進(jìn)化后期，ACSMDE能在全局最優(yōu)解附近繼續(xù)收斂，提高算法收斂精度。通過與其他6個具有代表性的算法在CEC201730個標(biāo)準(zhǔn)測試函數(shù)的實(shí)驗(yàn)結(jié)果表明，ACSMDE在算法收斂速度以及收斂精度上有較好的提升。

2 基本DE算法

DE算法是一種基于群體的全局自適應(yīng)搜索優(yōu)化算法[23]，進(jìn)化流程與遺傳算法（GA）[24]非常類似，其首先要隨機(jī)初始化種群，然后借助種群個體間的差分信息對個體形成擾動進(jìn)而搜索整個種群空間，最后利用貪婪機(jī)制選擇下一代個體，尋求問題的最優(yōu)解。差分變異、雜交、選擇為DE算法的3個基本操作。最常見的差分變異策略有以下5種：

式中，為變異后的個體；為當(dāng)前種群中隨機(jī)選取的5個不同的個體；為當(dāng)前個體；為當(dāng)前全局最優(yōu)個體；F為縮放因子；g為當(dāng)前進(jìn)化代數(shù)。

交叉作為差分變異搜索策略的一種有效補(bǔ)充，DE采用對于每個目標(biāo)向量和其相應(yīng)的變異向量進(jìn)行均勻交叉，進(jìn)而產(chǎn)生試驗(yàn)向量)，具體定義如下：

其中，Cr為交叉概率；jrand為[1,2,…,D] 的隨機(jī)整數(shù)。

如果循環(huán)代數(shù)G超過了最大迭代次數(shù)或者精度達(dá)到要求則停止搜索，否則繼續(xù)對種群執(zhí)行變異、交叉和選擇等操作。

3 自適應(yīng)合并與分裂的多種群差分進(jìn)化算法

3.1 子種群自適應(yīng)組合與分裂

由于差分進(jìn)化采取啟發(fā)式搜索模式，種群的進(jìn)化很容易被種群最優(yōu)個體所操控，陷入局部最優(yōu)，因此本文采用分布式差分進(jìn)化算法[22，25]（DDE）架構(gòu)，DDE算法開始時將種群劃分為若干個子種群，在進(jìn)化的過程中，每個子種群獨(dú)立進(jìn)化，子種群按照拓?fù)浣Y(jié)構(gòu)排列，使得每一個子種群只能向特定的子種群傳遞信息，同樣，它只能從特定的子種群中接收信息。在滿足給定概率的情況下，子種群間進(jìn)行信息交流。從遷移種群選擇最佳個體，替換掉被遷移子種群中隨機(jī)挑選的一個個體，通過遷移，實(shí)現(xiàn)在子種群間的信息交流，此過程使得算法很好地從不同子種群的多樣性中收益，圖1為環(huán)形拓?fù)浣Y(jié)構(gòu)的遷移過程。

圖1 環(huán)形拓?fù)溥w移過程

DDE算法在算法前期很好地實(shí)現(xiàn)多種群間的信息交流，但是這種某子種群最優(yōu)個體替換另一子種群的隨機(jī)個體的操作，使得最后子種群的最優(yōu)個體趨于統(tǒng)一，種群多樣性降低，大量的種群資源不能得到有效的利用，在算法后期仍然不好解決陷入局部最優(yōu)問題，因此本文提出了子種群自適應(yīng)合并與分裂的策略，其子種群間的具體操作步驟如下：

步驟1設(shè)置一個最大子種群數(shù)pmax和最小子種群數(shù)pmin，在初始化種群過程中，將種群平均分配pmax個子種群，并為每個子種群設(shè)置一個種群優(yōu)劣因子，來表示種群優(yōu)劣性。

步驟2通過計(jì)算各個子種群的個體適應(yīng)度值fit，找到全局最優(yōu)個體及所在的子種群k，通過式（8）、（9）來更新各個子種群的種群優(yōu)劣因子：

在算法迭代過程中，每一個子種群代表著一個小區(qū)域，子種群的優(yōu)劣性會根據(jù)各個子種群中最優(yōu)個體的適應(yīng)度值進(jìn)行比較，但是最優(yōu)子種群的最優(yōu)個體可能為局部最優(yōu)，而全局最優(yōu)個體可能存在另一個子種群所在區(qū)域內(nèi)，只是還未探尋到，但傳統(tǒng)多種群DE算法[26]隨著子種群間的交流迭代最后種群趨于統(tǒng)一，多樣性降低的同時也陷入局部最優(yōu)，本文提出子種群優(yōu)劣因子，在算法迭代過程中，子種群不會立即進(jìn)行子種群間的交流，而是添加了一個閾值，當(dāng)子種群的種群優(yōu)劣因子達(dá)到此閾值時，才進(jìn)行交流，讓每個子種群有一定的時間在自己所屬的區(qū)域內(nèi)進(jìn)行迭代尋優(yōu)，保證個體多樣性的同時也有效防止陷入局部最優(yōu)。

在初始化時設(shè)置各個子種群的種群優(yōu)劣因子為0；step設(shè)置為25；Dr設(shè)置為0.6。從式子可以看出，在每一次迭代更新過程中，只有擁有全局最優(yōu)個體的子種群，其種群優(yōu)劣因子才會增加，其他不包含全局最優(yōu)個體的子種群的種群優(yōu)劣因子會減少，當(dāng)其減少為0或者小于0時則重新設(shè)置為0。

步驟3通過迭代更新后的子種群的種群優(yōu)劣因子來判斷是否進(jìn)行種群間的組合和分裂，如果滿足要求則進(jìn)行組合或分裂操作。在算法迭代初期，為了保證個體盡可能存在于存在的極值點(diǎn)的區(qū)域內(nèi)，需充分發(fā)揮算法的全局搜索能力來保證種群的多樣性和公平競爭性，故采取隨機(jī)平均分配種群個體，并設(shè)置種群數(shù)量相對較大，設(shè)為10。在算法迭代后期，為了盡可能地增強(qiáng)局部尋優(yōu)能力，能夠在當(dāng)前區(qū)域內(nèi)尋求到最優(yōu)解，此時需將更多的個體資源用于提供給較優(yōu)子種群，從而使其在最優(yōu)值附近的小區(qū)域內(nèi)進(jìn)行探索，增強(qiáng)算法的開發(fā)能力，故一些種群優(yōu)劣因子較小的子種群會被淘汰掉，將其種群資源合并到最優(yōu)子種群，此時子種數(shù)會減少，但是為了避免最優(yōu)子種群的最優(yōu)解為局部最優(yōu)解，故最小子種群數(shù)不能設(shè)為1，為了增強(qiáng)算法跳出局部最優(yōu)能力，本算法將最小子種群個數(shù)設(shè)為4。

步驟4更新組合或者分裂后各個子種群的個體及相關(guān)數(shù)據(jù)，子種群交流結(jié)束。

組合就是在所有子種群中選出種群優(yōu)劣因子最小的子種群，將其種群資源全部重新分配給種群優(yōu)劣因子最大的子種群的過程，如圖2，在初始化時設(shè)置所有子種群規(guī)模因子sizek=1，當(dāng)某個子種群的種群優(yōu)劣因子到達(dá)某個閾值T且子種群的數(shù)目不小于最小子種群數(shù)目Pmin時執(zhí)行組合操作，從式（8）可知，只有擁有全局最優(yōu)個體的子種群的種群優(yōu)劣因子才會增加，所以每次執(zhí)行組合操作只會合并最優(yōu)子種群與最劣子種群，子種群個數(shù)P將會減少1，子種群將會被消除，并將其種群資源通過式（10）重新分配給子種群，得到合并的子種群的子種群規(guī)模因子通過式子（公式（11））來更新。

為最佳子種群的最優(yōu)個體，為最佳子種群的兩個隨機(jī)個體。

圖2 子種群組合過程

分裂就是在種群迭代過程中通過判斷子種群的種群優(yōu)劣因子，若其等于0且種群規(guī)模因子sizek>1，則表示此種群占據(jù)太多資源但是不能尋找到更優(yōu)的個體，所以會將其分裂并重新初始化。其分裂過程如圖3所示，根據(jù)此種群的種群規(guī)模因子sizek將其重新平均分配為sizek個子種群，所有種群的個體通過式（12）進(jìn)行初始化。

圖3 種群分裂過程

3.2 精英池學(xué)習(xí)

在每一次迭代過程中，經(jīng)過變異交叉后產(chǎn)生新的個體，根據(jù)適應(yīng)度值進(jìn)行優(yōu)劣比較，獲勝的進(jìn)入下一代進(jìn)行新的迭代，同時該獲勝個體和所對應(yīng)的縮放因子、交叉因子加入到當(dāng)前子種群的精英池中，也就是說精英池用來保存每次迭代獲勝的個體以及所對應(yīng)的縮放因子和交叉因子。在算法進(jìn)化初期，隨著迭代次數(shù)的增加，精英池中存放的個體以及參數(shù)會隨之增加，但由于更早進(jìn)入池內(nèi)的信息會隨著代數(shù)的增加其對種群的價值會減少，針對此問題設(shè)置精英池容量Tank，并根據(jù)先進(jìn)先出原則，當(dāng)加入的信息溢出精英池時算法選擇移除最早加入的精英信息。

個體的多樣性主要由多種群的拓?fù)浣Y(jié)構(gòu)來保證，在每一個子種群內(nèi)部，更多強(qiáng)調(diào)的是到達(dá)極值點(diǎn)的尋優(yōu)能力，精英池只需保存最新產(chǎn)生的較優(yōu)個體即可，而無需保存較早產(chǎn)生的個體，同時為了減少冗余使算法性能更優(yōu)，本文將精英池規(guī)模設(shè)為當(dāng)前子種群的1/2，初始化時精英池為空。若算法在解決復(fù)雜多峰問題時，需要更多的個體信息來增加開采能力，建議適當(dāng)擴(kuò)充精英池的容量甚至可以等同于當(dāng)前種群規(guī)模。

標(biāo)準(zhǔn)差分進(jìn)化算法的變異策略都會從當(dāng)前種群中隨機(jī)選擇個體，以及約定好的縮放因子和交叉因子來進(jìn)行變異和交叉。此算法對變異策略做了改進(jìn)，種群通過在精英池中選擇優(yōu)良個體參與變異策略和更新縮放因子和交叉因子，通過式（13）、（14）進(jìn)行變異策略，在精英池中分別產(chǎn)生服從正態(tài)分布的CRi和服從柯西分布的Fi來更新種群的縮放因子和交叉因子。

為變異后個體；為當(dāng)前個體；Fi為當(dāng)前個體對應(yīng)的縮放因子；為精英池中選擇的個體；為當(dāng)前種群隨機(jī)選擇的個體為在交叉選擇過程中的選擇的第j維；CRi為當(dāng)前個體對應(yīng)的交叉因子；jrand為隨機(jī)選擇的變異維。

3.3 早熟判定及變異策略

在DE算法后期，產(chǎn)生早熟收斂的根本原因是隨著迭代次數(shù)的增加和種群多樣性的快速下降，個體間適應(yīng)性的差異性越來越小，形成了個體聚集，陷入局部最優(yōu)，從而難以收斂到更好的解。針對此問題，ACSMDE提出了早熟判定以及相應(yīng)的變異策略。通過式（15）進(jìn)行種群早熟判定：

其中，ε為早熟檢驗(yàn)閾值，為第g代和第g+P代種群的最優(yōu)個體的適應(yīng)度值，本文中取P=100，ε=1E?6。算法每迭代P次后，進(jìn)行一次早熟判定，若第g代和第g+P代種群的最優(yōu)個體的適應(yīng)度值的差值小于ε，表示算法陷入了局部最優(yōu)或者搜索處于停滯狀態(tài)。因?yàn)镈E算法的本身局限性，在解決多峰問題時就很容易進(jìn)入此狀態(tài)，所以在DE算法中進(jìn)行早熟判定具有很強(qiáng)的普適性[27]，即從迭代開始就進(jìn)行早熟判定。當(dāng)種群滿足式（15）時表示種群陷入局部最優(yōu)，則對最佳個體進(jìn)行個體變異，本文選擇拉格朗日插值法進(jìn)行變異策略，其一般形式運(yùn)用方法為：在平面上有(x0,y0),(x1,y1),…,(xn-1,yn-1)共n個點(diǎn)，xi為自變量的取值，yi為對應(yīng)函數(shù)的取值，任意的兩個xi互不相等，集合Bk是關(guān)于點(diǎn)(x,y)的集合，Bk={0,1,…,n-1}，對于任意的k∈Bk，都有l(wèi)k(x)，Bk={i|i≠k,i∈Dn}使得：

函數(shù)L(x)的圖像經(jīng)過這n個點(diǎn)，也就是說拉格朗日插值法可以給出一個恰好穿過二維平面上n個已知點(diǎn)的n-1次多項(xiàng)式函數(shù)（17），式（18）為n=3時的多項(xiàng)式函數(shù)。

(4)在最佳擋板高度的前提下，調(diào)節(jié)風(fēng)門開度，使得爐排橫向配風(fēng)更均勻，其最佳風(fēng)門開度(從風(fēng)室進(jìn)口到尾部)依次為100%、70%、50%、50%、50%，其配風(fēng)不均勻系數(shù)為7%。

算法的變異策略如下：在當(dāng)前種群的最優(yōu)個體上選取某一維，希望通過拉格朗日插值構(gòu)造出一個多項(xiàng)式函數(shù)，通過多項(xiàng)式函數(shù)來找到在此維度上適應(yīng)度值最大的值。因?yàn)樗惴看沃辉谝粋€維度上的最優(yōu)點(diǎn)進(jìn)行變異，所以只需在此維度上產(chǎn)生兩個臨近值，用這兩個值分別替換掉原來的值后計(jì)算適應(yīng)度，由此又生出了兩個點(diǎn)，將生成的兩點(diǎn)和原來的點(diǎn)代入式（18）產(chǎn)生一個二次項(xiàng)函數(shù)，根據(jù)二項(xiàng)式函數(shù)的函數(shù)性質(zhì)，當(dāng)其最高項(xiàng)的系數(shù)不為零時為一個一元二次函數(shù)，當(dāng)其最高項(xiàng)的系數(shù)為零時為一次函數(shù)，在根據(jù)其幾何性質(zhì)選取變異點(diǎn)。具體過程如下：找到在此當(dāng)前種群最優(yōu)個體為[xbest,1,xbest,2,…,xbest,D]，選取第j維并計(jì)算其兩個鄰近值，其計(jì)算式如下：

其中，Rj為在第j維上搜索范圍，rand（0，1）為（0，1）內(nèi)的隨機(jī)數(shù)，N為種群個體數(shù)目。

將分別用和替換，得到兩個新的個體x1、x2，計(jì)算三個個體的適應(yīng)度值并按從小到大排序，依次記為，對應(yīng)的三個點(diǎn)x0()、)、x2()，將這三個點(diǎn)代入拉格朗日插值公式（18）可得一個關(guān)于x的方程：

由平面幾何知識以及二次函數(shù)極限的定義可知，在一個可導(dǎo)點(diǎn)的兩側(cè)各取一個相對靠近的點(diǎn)，其幾何關(guān)系只能存在圖4中四種情況，分析滿足此條件三個點(diǎn)的幾何意義，如圖4所示。

圖4 參數(shù)a與b不同取值下的

當(dāng)a=0,b=0時，其幾何圖形如圖4中的（1）所示，表示這三個點(diǎn)在一條平行于橫坐標(biāo)的直線上，取xmin～xmax中的任意一點(diǎn)。

當(dāng)a=0，b≠0時，其集合圖形如圖4中的（2）所示，表示這三個點(diǎn)在一條傾斜的直線上，即為在范圍內(nèi)隨機(jī)取的一個點(diǎn)。當(dāng)a>0時，其集合圖形如圖4中的（3）所示，表示這三個點(diǎn)在一開口向上的拋物線上，取值為。

當(dāng)a<0時，其集合圖形如圖4中的（4）所示，表示這三個點(diǎn)在一開口向下的拋物線上，若在對稱軸左側(cè)，即為在xmin～范圍內(nèi)隨機(jī)取的一個點(diǎn)；若在對稱軸右側(cè)即為在～xmax范圍內(nèi)隨機(jī)取的一個點(diǎn)。

將xbest的第j維用替代，得到新的個體[xbest,1,…,…,xbest,D]，計(jì)算x3的適應(yīng)度值fit3通過式（27）進(jìn)行更新種群。

最優(yōu)個體依次從維度1到D進(jìn)行拉格朗日更新，直到找到最優(yōu)個體或者到達(dá)最高維為止。

3.4 算法實(shí)現(xiàn)過程

步驟1設(shè)置參數(shù)和初始化子種群以及初始化子種群優(yōu)劣因子。設(shè)置最大子種群個數(shù)pmax，最小子種群個數(shù)pmin，初始子種群規(guī)模N，子種群合并閥值Tmax和子種群分裂閥值Tmin，子種群交流概率E1，種群更新系數(shù)Up和Dr，子種群規(guī)模因子SIZE，縮放因子最大值Fmax和最小值Fmin，交叉概率因子最大值Crmax和最小值Crmin，變量的上下界xmax與xmin變量維數(shù)D，種群最大進(jìn)化代數(shù)Gmax，早熟控制周期P，早熟檢驗(yàn)閥值ε。用式（12）來初始化各個子種群，計(jì)算出各子種群個體的適應(yīng)度值，找到各個子種群適應(yīng)度最優(yōu)的個體xbest及對應(yīng)的最佳適應(yīng)值fitbest，并將各個子種群的種群優(yōu)劣因子Fitg置為0，進(jìn)化代數(shù)置為0，初始縮放因子和交叉概率因子都置為0.5。

步驟2變異交叉以及選擇操作。本文使用式（13）的差分策略實(shí)現(xiàn)個體變異，式（14）實(shí)現(xiàn)交叉操作，通過比較原始個體與交叉操作后的個體的適應(yīng)度值，選取較佳個體作為下一代的個體實(shí)現(xiàn)選擇操作。

步驟3子種群間的合并與分裂。各個子種群先進(jìn)行個體評價，找到最優(yōu)個體來更新子種群優(yōu)劣因子，通過子種群優(yōu)劣因子來進(jìn)行子種群間的合并與分裂。

步驟4更新精英池。在各個子種群中，將步驟3中尋找到較佳個體添加到精英池，并判斷精英池是否溢出，當(dāng)總個數(shù)超出精英池容量時剔除較早進(jìn)入精英池中的祖代個體，并通過新的精英池來更新縮放因子和交叉變異因子。

步驟5早熟判定。如果判定為早熟則使用拉格朗日插值法進(jìn)行變異策略。

步驟6判斷是否到達(dá)最大迭代代數(shù)，如果是，算法結(jié)束，否則跳回步驟2。

4 函數(shù)仿真與分析

4.1 參數(shù)設(shè)置

ACSMDE算法的各項(xiàng)參數(shù)設(shè)置：在低維D=30情況下種群規(guī)模NP=150，最大演化代數(shù)Gmax=3 000；在高維D=100情況下NP=250，最大演化代數(shù)Gmax=5 000。

為了全面客觀地對ACSMDE算法進(jìn)行評價，本文將其與標(biāo)準(zhǔn)DE[1]算法（DE/rand/1）以及研究人員近些年提出的優(yōu)秀算法JDE[5]、tBBDE[10]、RDE[28]、AM_DEGL[29]、APPDDE[22]在收斂精度，收斂速度以及時間復(fù)雜度上進(jìn)行比較，各算法均獨(dú)立運(yùn)行20次。其他比較算法的參數(shù)設(shè)置均與原文獻(xiàn)一致。實(shí)驗(yàn)環(huán)境為：處理器Intel?Core? i5-7200U CPU@2.5 GHz RAM 4 GB，Win10 64位操作系統(tǒng)，MATLABR2016a。

表1 標(biāo)準(zhǔn)測試函數(shù)

4.2 測試函數(shù)

為了測試本文算法的可行性，選擇CEC2017[30-31]中的30個標(biāo)準(zhǔn)測試函數(shù)，具體定義如表1所示，其中，F(xiàn)1、F2、F3為單峰函數(shù)，F(xiàn)4～F10為簡單多峰函數(shù)，F(xiàn)11～F20為混合函數(shù)，F(xiàn)21～F30為復(fù)合函數(shù)。

4.3 實(shí)驗(yàn)結(jié)果與分析

4.3.1 算法收斂精度分析

在表2、表3的數(shù)據(jù)中存在數(shù)據(jù)相同但并未加粗的情況，是因?yàn)閿?shù)據(jù)在使用科學(xué)計(jì)數(shù)法進(jìn)行數(shù)學(xué)統(tǒng)計(jì)時，四舍五入會使得很鄰近的數(shù)據(jù)最后表示出來為相等數(shù)據(jù)，但實(shí)際上未加粗?jǐn)?shù)據(jù)的真實(shí)值是略大于加粗?jǐn)?shù)的真實(shí)值的，同時，在表2、表3中存在平均值同時加粗的情況，是因?yàn)閷?yīng)算法都能達(dá)到測試函數(shù)的全局最優(yōu)點(diǎn)或局部最優(yōu)點(diǎn)。

表2為各算法在低維(D=30)情況下的平均值，方差的實(shí)驗(yàn)對比結(jié)果，其中最好結(jié)果已加粗標(biāo)出。從平均值指標(biāo)來看，對于F2、F3、F4、F5、F7、F12、F16、F19、F23、F27等9個測試函數(shù)，ACSMDE均達(dá)到了最優(yōu)精度，無論是簡單函數(shù)，多峰函數(shù)，還是復(fù)合函數(shù)，混合函數(shù)都能夠在指定約束條件下達(dá)到最優(yōu)，并且在其他測試函數(shù)F8、F13、F14、F20、F25、F26上仍然具有較好的精度，與對比算法中最優(yōu)結(jié)果相差結(jié)果不大，說明ACSMDE算法具有較強(qiáng)的精度探索能力。并且在測試函數(shù)F2、F3、F4、F12、F19上，ACSMDE均達(dá)到各個測試函數(shù)理想的最優(yōu)解，說明ACSMDE的具有很強(qiáng)的探索開采能力，同時，ACSMDE在測試函數(shù)F2、F3、F4、F17的方差指標(biāo)上也能達(dá)到最小，在算法穩(wěn)定性上也有一定的保證。

表3為D=100的情況下各算法的平均值和方差實(shí)驗(yàn)對比結(jié)果，其中最好數(shù)據(jù)已加粗標(biāo)出。從表中的數(shù)據(jù)可以看出，當(dāng)維度D=100時，從平均指標(biāo)來看，對于F1、F2、F3、F4、F5、F11、F17、F18、F19、F20、F21、F23等12個測試函數(shù)，ACSMDE算法在精度排名上均排名第一。同時ACSMDE算法在測試函數(shù)F7、F11、F13、F26、F29等與最佳算法最優(yōu)值差距不是特別明顯，并且在較少的迭代次數(shù)上能夠穩(wěn)定地收斂到全局最優(yōu)，同時對比表2和表3，隨著問題維度的增加，ACSMDE算法搜索性能的優(yōu)勢進(jìn)一步體現(xiàn)出來，無論是收斂精度還是收斂的穩(wěn)定性在對比算法中有較大優(yōu)勢。綜上所述，無論是在低維D=30還是在高維D=100，ACSMDE算法在與其他6個對比算法中均能取得較明顯的優(yōu)勢，這說明自適應(yīng)合并與分裂的種群結(jié)構(gòu)，精英池學(xué)習(xí)以及早熟判定及變異策略確實(shí)能提高算法的尋優(yōu)能力以及尋優(yōu)精度。

表2 ACSMDE與其他算法的比較(D=30)

表3 ACSMDE與其他算法的比較(D=100)

4.3.2 算法收斂速度分析

為了進(jìn)一步分析ACSMDE算法在不同函數(shù)上的收斂速度，分別進(jìn)行了在不同維度（D=30和D=100）下30個測試函數(shù)與其他幾個DE算法的比較實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明：在其他算法的收斂速度受到高緯度的限制時，ACSMDE算法無論是高維還是低維，在大多數(shù)函數(shù)上的收斂速度較之其他算法更快，都具有較高的收斂性能。圖5給出了D=30和D=100時各算法在測試函數(shù)上的收斂曲線，其中l(wèi)g表示以10為底的對數(shù)（限于篇幅，每種維度只給出具有代表性的3個函數(shù)）。

由圖5可知，當(dāng)D=30時，對應(yīng)圖中的（a）、（b）、（c），函數(shù)F5、F16、F22都能快速收斂，并且在算法后期同其對比實(shí)驗(yàn)算法相比達(dá)到更好的精度。特別是測試函數(shù)F5和F16，在保證算法快速收斂的同時也有高質(zhì)量的解。當(dāng)D=100 時，對應(yīng)圖中的（d）、（e）、（f），對于函數(shù)F1、F11、F17，ACSMDE在收斂性能夠很好地超越其他算法，并能搜索高質(zhì)量的最優(yōu)解，對于F1和F17，算法不僅在前期與其他一些算法相當(dāng)，并且在其他算法都達(dá)到收斂時，仍具有繼續(xù)尋求最優(yōu)解的能力，在能快速收斂的同時也有很好的收斂精度。

圖5 算法的收斂性比較

4.3.3 算法復(fù)雜度分析

通過對算法實(shí)現(xiàn)步驟來分析ACSMDE的時間復(fù)雜度，其中種群規(guī)模為NP，問題維度為D，迭代次數(shù)為T。算法步驟1初始化種群時間復(fù)雜度為O(NP?D)，步驟2變異交叉操作為O(NP?D)，步驟3選擇操作為O(NP)，步驟4合并與分裂子種群更新為O(1)，更新精英池（池子規(guī)模為O(NP)數(shù)量級）操作有從池頂加入新的精英個體以及池底移除祖代精英個體，其時間復(fù)雜度為O(NP?D)，早熟判定為O(1)，綜上所述，ACSMDE算法的總時間復(fù)雜度為O(NP?D?T)，僅與NP、D和T有關(guān)，ACSMDE算法與標(biāo)準(zhǔn)DE算法時間復(fù)雜度一致，對算法的改進(jìn)沒有增加過多的計(jì)算開銷。

總結(jié)以上實(shí)驗(yàn)分析發(fā)現(xiàn)，雖然ACSMDE算法在極少數(shù)函數(shù)的性能不佳，但對于絕大多數(shù)測試函數(shù)而言，基于自適應(yīng)合并與分裂的種群結(jié)構(gòu)，精英池學(xué)習(xí)，早熟判定及變異策略較大地提高了的DE算法收斂速度和收斂精度，同其他6種算法相比，ACSMDE算法的優(yōu)化性能具有很大的優(yōu)勢，且穩(wěn)定性更佳。

5 結(jié)語

本文提出了自適應(yīng)合并與分裂的多種群差分進(jìn)化算法ACSMDE，算法將種群分為多個子種群，在算法迭代初期，子種群個數(shù)較多，子種群間通過種群優(yōu)劣因子來進(jìn)行交流，保證種群多樣性和個體多樣性，有效加強(qiáng)DE算法的全局尋優(yōu)能力和避免陷入局部最優(yōu)能力；在每個子種群內(nèi)部，采取了精英池學(xué)習(xí)的策略來保存較優(yōu)個體和對參數(shù)進(jìn)行動態(tài)更新，使算法在較優(yōu)個體的附近繼續(xù)進(jìn)化，易于求得較好的解，極大地提高了算法的局部尋優(yōu)能力。并設(shè)置了最小子種群數(shù)和種群早熟檢測及變異策略，增強(qiáng)跳出局部最優(yōu)的能力，同時也提高了算法的精度，通過對CEC2017的30個測試函數(shù)與幾個有代表性的DE算法的對比實(shí)驗(yàn)，證明了本算法的適用性、有效性和準(zhǔn)確性。