面向進(jìn)制轉(zhuǎn)換和克隆進(jìn)化的帝國(guó)競(jìng)爭(zhēng)改進(jìn)算法

李 斌，黃起彬

1.福建工程學(xué)院 機(jī)械與汽車工程學(xué)院，福州 350118

2.福建工程學(xué)院 交通運(yùn)輸學(xué)院，福州 350118

受自然系統(tǒng)啟發(fā)的隨機(jī)性優(yōu)化算法被稱作元啟發(fā)式算法。根據(jù)算法的啟發(fā)方式，可被分為三類：進(jìn)化算法、物理算法和群體智能算法[1]。進(jìn)化算法指靈感來(lái)自于大自然生物進(jìn)化的元啟發(fā)式算法，例如著名的遺傳算法[2]和進(jìn)化策略算法[3]；物理算法指受物理規(guī)則或化學(xué)現(xiàn)象啟發(fā)創(chuàng)建的元啟發(fā)式算法，如Nuclear Reaction Optimization[4]和Flow Regime Algorithm[5]；群體智能算法是模仿動(dòng)物群體行為或人類社會(huì)行為的元啟發(fā)式算法，典型的有蟻群算法[6]和粒子群算法[7]等。此外，不同的元啟發(fā)式算法之間相互借鑒或融合生成的混合型優(yōu)化算法，如基于灰狼優(yōu)化的反向?qū)W習(xí)粒子群算法[8]和融合貓群算法的動(dòng)態(tài)分組蟻群算法[9]，也是現(xiàn)代優(yōu)化算法中的重要組成部分。

帝國(guó)競(jìng)爭(zhēng)算法（imperialist competitive algorithm，ICA）是一種受歷史上帝國(guó)殖民主義產(chǎn)生的社會(huì)現(xiàn)象啟發(fā)的群體智能優(yōu)化算法，由Atashpaz-Gargari和Lucas在2007年提出[10]。ICA主要模擬的社會(huì)現(xiàn)象，是帝國(guó)主義國(guó)家對(duì)殖民地社會(huì)文化、政治和經(jīng)濟(jì)發(fā)展的影響和帝國(guó)之間的競(jìng)爭(zhēng)[11]。相比于其他典型優(yōu)化算法，ICA有著出色的收斂速度和局部挖掘能力，現(xiàn)已被廣泛地應(yīng)用于諸多領(lǐng)域的實(shí)際問(wèn)題中，如醫(yī)學(xué)病理[12]、能源傳輸[13]、計(jì)算機(jī)智能[14]、生產(chǎn)調(diào)度[15]等，且都取得了較好的成果。然而，面對(duì)高維度的復(fù)雜問(wèn)題時(shí)，ICA算法極易出現(xiàn)因過(guò)早收斂而陷入局部最優(yōu)的缺陷。

針對(duì)上述不足，國(guó)內(nèi)外眾多學(xué)者在改進(jìn)ICA方面進(jìn)行了大量的工作，改進(jìn)方向主要可分為完善原有機(jī)制和融入新機(jī)制兩種。經(jīng)典ICA中的同化機(jī)制是最有改進(jìn)潛力的部分：裴小兵等[16]將帝國(guó)同化信息記錄于概率矩陣模型中，利用區(qū)塊挖掘和競(jìng)爭(zhēng)實(shí)現(xiàn)殖民地的同化行為；Bahrami等[17]設(shè)計(jì)了四種混沌映射來(lái)改變殖民地向其殖民國(guó)家同化時(shí)的運(yùn)動(dòng)角度，以增強(qiáng)算法對(duì)局部最優(yōu)陷阱的逃逸能力。

通過(guò)融合新機(jī)制來(lái)提高ICA的優(yōu)化性能是近些年更為熱門的改進(jìn)方向，具體探討可分為三類。一是受歷史真實(shí)事件啟發(fā)所延伸出的新互動(dòng)機(jī)制?；跉v史中帝國(guó)發(fā)現(xiàn)新殖民地而引發(fā)的一系列行為，Ardeh等[18]引入探索者和保留策略的概念，使得算法中帝國(guó)有機(jī)會(huì)獲得全新的優(yōu)秀殖民地；Korhan等[19]為算法注入國(guó)際主義思想，提出地區(qū)統(tǒng)治政策，在算法迭代過(guò)程中不斷生成一個(gè)球形區(qū)域，各帝國(guó)對(duì)區(qū)域內(nèi)部的新國(guó)家通過(guò)民主協(xié)商的方式獲得統(tǒng)治權(quán)，以此提高算法的搜索能力。二是直接針對(duì)算法對(duì)象的特性進(jìn)行新機(jī)制的引入。如Xu等[20]發(fā)現(xiàn)隨著算法的執(zhí)行，帝國(guó)主義國(guó)家減少，殖民地也越來(lái)越集中，群體多樣性降低，故引入高斯變異、柯西變異和萊維變異等變異算子來(lái)改變帝國(guó)主義者的行為，避免算法陷入停滯。三是混合其他優(yōu)化算法。Kaveh等[11]將勘探能力較強(qiáng)、但挖掘能力較弱的哈里斯老鷹優(yōu)化器[17]（Harris hawks optimizer，HHO）與局部挖掘能力強(qiáng)、收斂快的ICA結(jié)合，實(shí)現(xiàn)了一種新的混合算法ICHHO。

盡管以往研究從多個(gè)角度改進(jìn)了ICA的性能，為智能優(yōu)化算法的改進(jìn)提供了有益的嘗試，但仍然存在一些可以繼續(xù)改進(jìn)的空間：

（1）可否著眼于算法機(jī)制本身的局限，改進(jìn)算法收斂過(guò)快而陷入停滯的問(wèn)題。在ICA原有機(jī)制下，資源集聚的速度遠(yuǎn)遠(yuǎn)高過(guò)資源分流的速度，這是ICA的優(yōu)勢(shì)所在，也是造成算法收斂過(guò)快的主要原因。僅改變單一對(duì)象的行為或是增加群體生物多樣性是難以打破現(xiàn)有狀況的，這就需要從算法框架本身出發(fā)，找到克服早熟的演化策略。

（2）現(xiàn)有絕大多數(shù)研究主要從單個(gè)或少數(shù)方面進(jìn)行改進(jìn)。算法機(jī)制的改進(jìn)可以是多方面、多元化的。對(duì)多種優(yōu)化目的不同的改進(jìn)機(jī)制進(jìn)行綜合性探討，有望為ICA的改進(jìn)提供新的思路。

（3）基于ICA本身的運(yùn)行特性，以同時(shí)提高算法勘探和挖掘能力為目的進(jìn)行改進(jìn)。ICA是通過(guò)帝國(guó)內(nèi)部以及帝國(guó)之間的多種互動(dòng)行為實(shí)現(xiàn)優(yōu)化，其中能直接影響ICA求解能力的個(gè)體對(duì)象是帝國(guó)主義國(guó)家[21]。因此，將有利于提高勘探能力或挖掘能力的改進(jìn)方法作用于帝國(guó)主義國(guó)家有望產(chǎn)生較好的改進(jìn)效果。

上述思想正是本文所提改進(jìn)算法的理論原點(diǎn)。在ICA的基礎(chǔ)上，本文所提的面向進(jìn)制轉(zhuǎn)換和克隆進(jìn)化的帝國(guó)競(jìng)爭(zhēng)改進(jìn)算法（decimal-binary conversion and clonal evolution oriented improved imperialist competitive algorithm，DCCE-IICA）更加注重利用演化種群中各群體的特性，針對(duì)現(xiàn)有問(wèn)題進(jìn)行改進(jìn)，其引入和應(yīng)用的核心改進(jìn)機(jī)制如下：

（1）引入基于進(jìn)制編碼轉(zhuǎn)換的克隆進(jìn)化策略。DCCEIICA最主要的改進(jìn)機(jī)制是結(jié)合二進(jìn)制基因變異理論[22]與克隆選擇算法[23]的優(yōu)化思想，引入一種基于二進(jìn)制與十進(jìn)制編碼轉(zhuǎn)換的克隆進(jìn)化策略。該策略可用于部分解決ICA停滯于局部最優(yōu)的問(wèn)題，通過(guò)周期性地為演化種群提供一個(gè)強(qiáng)大的新發(fā)展途徑，提高殖民地群體基因多樣性的同時(shí)，利用帝國(guó)主義國(guó)家對(duì)其附屬殖民地的引導(dǎo)能力跳出局部，并通過(guò)調(diào)整帝國(guó)之間的強(qiáng)弱關(guān)系來(lái)平衡算法資源的流向，延長(zhǎng)算法的活力。

（2）將帝國(guó)分裂機(jī)制[24]融入新算法中。帝國(guó)分裂機(jī)制在現(xiàn)有研究成果中，有著較好地緩解ICA執(zhí)行過(guò)程中收斂過(guò)早結(jié)束的能力，并且對(duì)改進(jìn)算法的適用性強(qiáng)，因此將其作為輔助機(jī)制融入DCCE-IICA中。

（3）設(shè)計(jì)了一個(gè)較為有效的出界點(diǎn)替換策略。同化機(jī)制執(zhí)行過(guò)程中，存在殖民地向其宗主國(guó)方向移動(dòng)后可能超出搜索邊界的問(wèn)題。DCCE-IICA的替換策略能更好地保證群體的多樣性。

為了系統(tǒng)性地驗(yàn)證DCCE-IICA的改進(jìn)有效性與可信性，本文選擇經(jīng)典函數(shù)測(cè)試集、CEC2017測(cè)試集[25]以及CEC2020測(cè)試集[26]進(jìn)行優(yōu)化實(shí)驗(yàn)，面向多個(gè)維度下不同類型的函數(shù)優(yōu)化問(wèn)題來(lái)測(cè)試和檢驗(yàn)DCCE-IICA的尋優(yōu)能力。在此基礎(chǔ)上，將DCCE-IICA在CEC系列測(cè)試集上的實(shí)驗(yàn)結(jié)果，與13個(gè)國(guó)際前沿算法進(jìn)行比較，包括2017年進(jìn)化算法大賽冠軍算法LSHADE-SPACMA的變體，來(lái)充分證明本文所提算法求解復(fù)雜函數(shù)時(shí)的求解精度、收斂狀況和魯棒性。

1 帝國(guó)競(jìng)爭(zhēng)算法

ICA將D維搜索空間內(nèi)的任一演化個(gè)體當(dāng)作一個(gè)國(guó)家，每個(gè)個(gè)體的函數(shù)值被稱為國(guó)家的成本值（Cost），成本值越小的國(guó)家勢(shì)力越強(qiáng)。每個(gè)國(guó)家都是對(duì)應(yīng)問(wèn)題的一個(gè)可行解，其位置信息可表示為Country=(x1,x2,…,xD)。ICA的主要執(zhí)行步驟包括初始化帝國(guó)、殖民地同化、殖民地革命、帝國(guó)合并、帝國(guó)競(jìng)爭(zhēng)與帝國(guó)統(tǒng)一[10，24]，相關(guān)描述如下：

步驟1初始化帝國(guó)。在搜索區(qū)域內(nèi)隨機(jī)生成一定數(shù)量的國(guó)家，勢(shì)力最強(qiáng)的Nimp個(gè)國(guó)家為帝國(guó)主義國(guó)家，即殖民國(guó)家，然后根據(jù)成本值大小瓜分其余的Ncol個(gè)國(guó)家作為它們的附屬殖民地國(guó)家，形成最初的帝國(guó)格局。

步驟2殖民地同化。殖民地國(guó)家向其宗主國(guó)所在位置的大致方向靠近。移動(dòng)距離由下式給出：

其中，yi表示殖民地國(guó)家在第i維向量上移動(dòng)的直線距離；U(a,b)為均勻分布函數(shù)；β為同化系數(shù)，取值一般大于1；di代表第i維向量上殖民地與所屬殖民國(guó)家之間的距離。

步驟3殖民地革命。根據(jù)概率，一定數(shù)量的殖民地可以自主地進(jìn)行位置上的更新。在同化和革命行為結(jié)束后，若帝國(guó)主義國(guó)家落后于其所屬帝國(guó)內(nèi)部的某個(gè)殖民地，則該殖民地與殖民國(guó)家地位互換。

步驟4帝國(guó)合并。當(dāng)兩個(gè)帝國(guó)過(guò)于接近時(shí)，更強(qiáng)一方將另一帝國(guó)完全吸收，變?yōu)樽约旱闹趁竦亍?/p>

步驟5帝國(guó)競(jìng)爭(zhēng)。根據(jù)帝國(guó)總成本值TC（total cost），最弱帝國(guó)的最弱殖民地成為其余帝國(guó)搶奪的對(duì)象，勢(shì)力越強(qiáng)的帝國(guó)將其占有的概率越大。若帝國(guó)失去所有殖民地，則該帝國(guó)宣布滅亡，同時(shí)作為新的殖民地附屬于此次競(jìng)爭(zhēng)中奪得殖民地的帝國(guó)。

步驟6帝國(guó)統(tǒng)一。算法在多次的迭代中重復(fù)執(zhí)行步驟2至步驟5，帝國(guó)將相繼滅亡。當(dāng)場(chǎng)上只存在一個(gè)帝國(guó)時(shí)，算法結(jié)束。

2 面向進(jìn)制轉(zhuǎn)換和克隆進(jìn)化的帝國(guó)競(jìng)爭(zhēng)改進(jìn)算法

DCCE-IICA旨在保留原始ICA局部收斂能力的同時(shí)，均衡演化群體的深度挖掘與全面勘探能力，同時(shí)具備避免停滯于局部最優(yōu)解的進(jìn)化機(jī)制，從而提高算法對(duì)復(fù)雜問(wèn)題的適用性。相較于傳統(tǒng)的ICA，DCCE-IICA的關(guān)鍵改進(jìn)主要有三點(diǎn)，分別是基于進(jìn)制編碼轉(zhuǎn)換的克隆進(jìn)化機(jī)制、帝國(guó)分裂機(jī)制和新的出界點(diǎn)替換策略。DCCE-IICA首先引入一種基于進(jìn)制編碼轉(zhuǎn)換的克隆進(jìn)化機(jī)制，周期性地為殖民地國(guó)家和較弱的帝國(guó)主義國(guó)家提供一個(gè)新的上升渠道，重塑殖民地國(guó)家的基因多樣性，同時(shí)帝國(guó)間也會(huì)因?yàn)樾碌膭?shì)力強(qiáng)弱形勢(shì)而改變資源轉(zhuǎn)移方向，維持算法活力，避免因帝國(guó)的快速消亡與資源的快速集聚而導(dǎo)致算法勘探能力的削弱，幫助算法持續(xù)向全局最優(yōu)解逼近；其次，引入帝國(guó)分裂機(jī)制，當(dāng)環(huán)境中只剩一個(gè)帝國(guó)時(shí)分裂出新的帝國(guó)，讓算法持續(xù)運(yùn)行下去；最后，設(shè)計(jì)了一種更有效的出界點(diǎn)替換策略來(lái)彌補(bǔ)經(jīng)典ICA設(shè)計(jì)上的漏洞，更有效地保證算法執(zhí)行過(guò)程中演化種群不會(huì)因?yàn)橐苿?dòng)出搜索區(qū)域而造成個(gè)體多樣性的降低。帝國(guó)分裂機(jī)制和新的出界點(diǎn)替換策略旨在確保個(gè)體多樣性，兩者的引入并不能令算法的收斂能力有很明顯的提高[24，27]，但可以較好地為DCCE-IICA引入的基于進(jìn)制編碼轉(zhuǎn)換的克隆進(jìn)化機(jī)制提供良好的演化環(huán)境。下面對(duì)DCCE-IICA的改進(jìn)進(jìn)行詳細(xì)論述。

2.1 DCCE-IICA算法的核心改進(jìn)機(jī)制

2.1.1 基于進(jìn)制編碼轉(zhuǎn)換的克隆進(jìn)化機(jī)制

基于進(jìn)制編碼轉(zhuǎn)換的克隆進(jìn)化機(jī)制，是先對(duì)被選中的演化個(gè)體二進(jìn)制化，再進(jìn)行包含克隆、變異、交叉、選擇四個(gè)步驟[23]的克隆進(jìn)化。該思想類似于早期的二進(jìn)制基因遺傳算法。有研究表明，模擬二進(jìn)制基因的交叉變異方法具有更顯著的優(yōu)化效果[22]。對(duì)二進(jìn)制基因來(lái)說(shuō)，只需要簡(jiǎn)單的0-1變換便能實(shí)現(xiàn)數(shù)字上的突變，因此二進(jìn)制數(shù)字串的變異粒度相比十進(jìn)制更為精細(xì)，能產(chǎn)生更多樣化的變異個(gè)體[27]。目前，模擬二進(jìn)制基因已在進(jìn)化算法領(lǐng)域得到了廣泛應(yīng)用[28-29]。DCCE-IICA之所以選擇克隆進(jìn)化算子，是因?yàn)榭寺∵M(jìn)化能高效地用數(shù)量較少的帝國(guó)主義國(guó)家變異出足夠多的新個(gè)體。這些變異個(gè)體能在后續(xù)的機(jī)制執(zhí)行中幫助算法提高種群多樣性和平衡計(jì)算資源的分配。該改進(jìn)機(jī)制的具體步驟如下：

步驟1進(jìn)制轉(zhuǎn)換。對(duì)帝國(guó)主義國(guó)家每一個(gè)維度上的坐標(biāo)值，從一個(gè)十進(jìn)制數(shù)字轉(zhuǎn)變?yōu)橐粭l長(zhǎng)度固定的二進(jìn)制數(shù)字串。本文計(jì)算實(shí)驗(yàn)的搜索區(qū)域?yàn)椋?100，100），因此長(zhǎng)度為21的二進(jìn)制數(shù)字串基本可以滿足本文實(shí)驗(yàn)需要的所有變異可能性：除開(kāi)正負(fù)號(hào)，整數(shù)部分變換后的二進(jìn)制數(shù)字串長(zhǎng)度為7，等于規(guī)定搜索范圍的上限值轉(zhuǎn)換為二進(jìn)制后的數(shù)字串長(zhǎng)度；而小數(shù)部分的長(zhǎng)度則設(shè)定為整數(shù)部分的兩倍。如下是某個(gè)國(guó)家第i維向量上的坐標(biāo)值二進(jìn)制化后的數(shù)學(xué)表達(dá)形式：

其中，xi為某一國(guó)家第i維向量上的坐標(biāo)值，xi,1,xi,2,…,xi,21分別對(duì)應(yīng)二進(jìn)制數(shù)字串的21位數(shù)字。

步驟2克隆。各帝國(guó)主義國(guó)家在完成十進(jìn)制至二進(jìn)制的編碼轉(zhuǎn)換后，對(duì)其進(jìn)行克隆。各帝國(guó)主義國(guó)家克隆體數(shù)量的計(jì)算公式如下：

其中，NCi為第i個(gè)帝國(guó)的克隆體數(shù)量；λ為克隆系數(shù)，本文取值0.8；Ncoli為第i個(gè)帝國(guó)所有的殖民地?cái)?shù)量；floor()為向下取整函數(shù)。

步驟3變異。對(duì)所有克隆體每一維度的數(shù)字串，隨機(jī)選擇其中1/3的數(shù)字，進(jìn)行0-1變換。

步驟4交叉。將每一個(gè)帝國(guó)主義國(guó)家對(duì)應(yīng)的所有克隆變異個(gè)體視為一個(gè)變異族群，族群內(nèi)部進(jìn)行高頻交叉。高頻交叉的方式如下：

（1）根據(jù)族群內(nèi)部的個(gè)體數(shù)量，隨機(jī)從內(nèi)部取出n個(gè)變異體作為一組。由下式確定：

（2）每一組按照公式（6）、（7）進(jìn)行交叉，最終得到新的變異體Cro：

其中，Muti為第i個(gè)帝國(guó)的變異族群；k為存儲(chǔ)數(shù)值的臨時(shí)參數(shù)；r1,r2,…,rn用以表示組內(nèi)不同的個(gè)體；下標(biāo)j表示二進(jìn)制數(shù)字串中第j位數(shù)字。

步驟5選擇。先將所有的Mut和Cro合并為一個(gè)克隆變異群體，再逐個(gè)解碼回十進(jìn)制并計(jì)算成本值，隨后進(jìn)行下述兩個(gè)步驟的選擇工作：

（1）若當(dāng)前帝國(guó)數(shù)大于2，則從克隆變異群體中選出兩個(gè)最優(yōu)個(gè)體，替換掉兩個(gè)最弱的帝國(guó)主義國(guó)家；若此時(shí)帝國(guó)個(gè)數(shù)為2，則僅選擇一個(gè)最優(yōu)克隆變異體替換較弱的帝國(guó)主義國(guó)家。ICA算法中的競(jìng)爭(zhēng)機(jī)制令本就發(fā)展落后的帝國(guó)不斷被更強(qiáng)帝國(guó)蠶食資源，使得弱帝國(guó)更難超越強(qiáng)帝國(guó)，算法資源不斷單向匯聚，進(jìn)而陷入局部最優(yōu)。所以，用優(yōu)秀的變異個(gè)體替換較弱帝國(guó)主義國(guó)家能夠調(diào)節(jié)各帝國(guó)之間的勢(shì)力分布，實(shí)現(xiàn)算法資源真正意義上的互相流通，避免算法因資源的快速集聚而過(guò)早地陷于局部最優(yōu)。同時(shí)，此措施也能通過(guò)變動(dòng)較弱帝國(guó)的宗主國(guó)的所在位置，幫助該帝國(guó)全體成員前往開(kāi)發(fā)新的區(qū)域，提高算法全局尋優(yōu)和跳出局部的能力。

（2）克隆變異群體中余下的個(gè)體，與環(huán)境上所有殖民地一起按成本值從小到大排序，從中選出與所有現(xiàn)存殖民地國(guó)家個(gè)數(shù)相等的最優(yōu)個(gè)體，替換掉所有殖民地國(guó)家，并按原先的殖民地分配情況隨機(jī)性地分配給各個(gè)帝國(guó)。因?yàn)橹趁竦貒?guó)家在同化機(jī)制的作用下會(huì)被不斷地匯集至帝國(guó)主義國(guó)家周邊，所以定時(shí)重置殖民地國(guó)家能夠恢復(fù)種群的基因多樣性，重新布局已過(guò)度集中的算法資源。這同樣有助于算法避免早熟、向全局最優(yōu)解逼近。

2.1.2 帝國(guó)分裂機(jī)制的應(yīng)用

帝國(guó)分裂機(jī)制是郭婉青[24]模擬歷史上帝國(guó)內(nèi)部不斷發(fā)展強(qiáng)大的殖民地與殖民國(guó)家發(fā)生沖突導(dǎo)致帝國(guó)分裂的現(xiàn)象，該機(jī)制的設(shè)計(jì)初衷就是為了緩解ICA因過(guò)早收斂而陷入局部最優(yōu)的缺陷。在DCCE-IICA中，帝國(guó)分裂機(jī)制主要用于維持帝國(guó)個(gè)數(shù)不為一，算法能夠多輪持續(xù)進(jìn)化，故此處簡(jiǎn)化了觸發(fā)分裂的條件，即在克隆進(jìn)化機(jī)制執(zhí)行前，帝國(guó)數(shù)少于2便觸發(fā)帝國(guó)分裂機(jī)制。具體步驟如下：

步驟1找出帝國(guó)中勢(shì)力最強(qiáng)的殖民地，將其晉升為帝國(guó)主義國(guó)家。

步驟2根據(jù)新帝國(guó)與舊帝國(guó)成本值的比值，隨機(jī)地將舊帝國(guó)相應(yīng)個(gè)數(shù)的殖民地分配給新帝國(guó)。新帝國(guó)分走的殖民地個(gè)數(shù)由下式?jīng)Q定：

其中，Cost()為國(guó)家勢(shì)力值的求取函數(shù)，NCnew表示新帝國(guó)擁有的殖民地個(gè)數(shù)，NCall表示現(xiàn)存殖民地的總數(shù)。

2.1.3 出界點(diǎn)的新型替換策略

DCCE-IICA借鑒Lin等于2013年提出的擾動(dòng)ICA[30]中對(duì)超出搜索范圍的坐標(biāo)值進(jìn)行策略性替換的思想，在其改進(jìn)基礎(chǔ)上提出一種新的替換策略，利用出界坐標(biāo)點(diǎn)與邊界的距離，按比率將出界個(gè)體映射回搜索空間內(nèi)部。公式如下：

其中，U和L分別是搜索區(qū)域的上下界，M表示搜索范圍的中值，xi是同化后殖民地國(guó)家第i維的坐標(biāo)值，//為取余符號(hào)。

2.2 算法的設(shè)計(jì)與實(shí)現(xiàn)

DCCE-IICA在實(shí)現(xiàn)與執(zhí)行中遵循如下規(guī)則：

（1）以150次迭代為間隔周期，執(zhí)行基于進(jìn)制轉(zhuǎn)換的克隆進(jìn)化機(jī)制。此舉的目的是給更新了帝國(guó)主義國(guó)家位置的帝國(guó)足夠的挖掘時(shí)間，充分發(fā)揮算法的局部收斂能力。

（2）將最大迭代數(shù)(FEsmax)作為算法唯一的結(jié)束條件。因?yàn)榈蹏?guó)分裂機(jī)制的加入，算法收斂的結(jié)束與否已不再受到帝國(guó)數(shù)量的限制。

于是，DCCE-IICA的詳細(xì)流程如算法1所示。

算法1DCCE-IICA

2.3 算法特性分析

2.3.1 時(shí)間復(fù)雜度分析

計(jì)算成本是限制優(yōu)化算法應(yīng)用的一個(gè)重要因素。假設(shè)國(guó)家總數(shù)為n，帝國(guó)主義國(guó)家個(gè)數(shù)為n1，殖民地國(guó)家個(gè)數(shù)為n2，克隆體個(gè)數(shù)為λn2。在D維搜索空間內(nèi)，DCCE-IICA各項(xiàng)機(jī)制在單次迭代中的時(shí)間復(fù)雜度如表1所示。

表1 時(shí)間復(fù)雜度Table 1 Time complexity

本文中λ取值為0.8，且帝國(guó)主義國(guó)家的數(shù)量遠(yuǎn)遠(yuǎn)小于國(guó)家總數(shù)，故DCCE-IICA單次迭代的時(shí)間復(fù)雜度為O(11.5nD)，略大于基本ICA算法的時(shí)間復(fù)雜度O(2nD)，但并無(wú)根本性的增加。表2為多種同類型典型優(yōu)化算法與DCCE-IICA的時(shí)間復(fù)雜度對(duì)比。

從表2中可以看出，與類似算法對(duì)比，DCCE-IICA的時(shí)間計(jì)算成本較為合理，具有典型的線性時(shí)間復(fù)雜度，故當(dāng)算法面向不同規(guī)模的優(yōu)化問(wèn)題時(shí)，具有較好的可用性、適應(yīng)性與魯棒性，這對(duì)于將DCCE-IICA應(yīng)用到工程實(shí)踐問(wèn)題中至關(guān)重要。

表2 多種典型算法的時(shí)間復(fù)雜度對(duì)比Table 2 Time complexity of several algorithm

2.3.2 局部與全局尋優(yōu)能力及平衡性分析

經(jīng)典ICA具有較強(qiáng)的局部尋優(yōu)能力，而DCCE-IICA是在原算法的基礎(chǔ)上，周期性地對(duì)近乎停滯的演化群體執(zhí)行克隆進(jìn)化機(jī)制，較好地繼承了原算法的局部挖掘能力和求解效率。同時(shí)，克隆進(jìn)化機(jī)制也能直接利用較優(yōu)解群體幫助算法收斂，是DCCE-IICA算法隱含的一個(gè)有效收斂模式。

全局尋優(yōu)側(cè)重的是算法的廣度搜索能力，而這正是原始ICA的短板所在。經(jīng)基于進(jìn)制轉(zhuǎn)換的克隆進(jìn)化機(jī)制重置后的殖民地國(guó)家能夠盡可能廣泛地遍布搜索空間，并且，克隆進(jìn)化機(jī)制會(huì)賦予較弱帝國(guó)更強(qiáng)的勢(shì)力并引導(dǎo)其開(kāi)采新的區(qū)域，原本較強(qiáng)的帝國(guó)會(huì)變得弱勢(shì)，進(jìn)而在下一個(gè)克隆進(jìn)化執(zhí)行時(shí)間點(diǎn)被重置，最終所有帝國(guó)都會(huì)依次完成從局部躍遷至新區(qū)域進(jìn)行探索和開(kāi)發(fā)的行為，實(shí)現(xiàn)全局尋優(yōu)。

綜上所述，DCCE-IICA在提高算法深度挖掘能力的同時(shí)，更多地注重修正原始ICA在全局勘探能力上的不足，令局部尋優(yōu)和全局探索二者在改進(jìn)后的算法中的獲得更加合理的平衡與互補(bǔ)，從而使得DCCE-IICA面對(duì)不同類型的解空間時(shí)都具有全面、持續(xù)和高效的尋優(yōu)探索能力。

3 計(jì)算實(shí)驗(yàn)與性能評(píng)估

3.1 實(shí)驗(yàn)設(shè)計(jì)

本節(jié)的主要目標(biāo)是通過(guò)全面且完整的多個(gè)函數(shù)測(cè)試集來(lái)驗(yàn)證和評(píng)判DCCE-IICA的優(yōu)缺點(diǎn)。因此，選擇了10個(gè)經(jīng)典測(cè)試函數(shù)及更具有挑戰(zhàn)性的CEC2017和CEC2020三個(gè)測(cè)試集50個(gè)復(fù)雜函數(shù)進(jìn)行計(jì)算實(shí)驗(yàn)，并通過(guò)與多種不同類型的前沿優(yōu)化算法進(jìn)行對(duì)比，來(lái)對(duì)其性能進(jìn)行全面評(píng)估。

本文所選的10個(gè)經(jīng)典測(cè)試函數(shù)（詳情見(jiàn)表3），除Levy函數(shù)（F9）外，全為原點(diǎn)最優(yōu)問(wèn)題（即在原點(diǎn)處取到理論最優(yōu)解），是相對(duì)較為易解的一類函數(shù)問(wèn)題。本文將展示30、50和100維三個(gè)維度下獨(dú)立運(yùn)行100次的實(shí)驗(yàn)結(jié)果，及與一種在該測(cè)試集上表現(xiàn)優(yōu)異的改進(jìn)智能算法進(jìn)行對(duì)比。此外，經(jīng)典測(cè)試函數(shù)的搜索范圍將與CEC測(cè)試集一致，將其投射至（-100，100），投射公式如下：

表3 經(jīng)典測(cè)試函數(shù)Table 3 Classic benchmark functions

其中，l為經(jīng)典測(cè)試函數(shù)原本的搜索上界，x和x*分別為映射前后的坐標(biāo)位置。

CEC相關(guān)數(shù)據(jù)集通過(guò)對(duì)測(cè)試函數(shù)的旋轉(zhuǎn)和偏移將其變?yōu)榉窃c(diǎn)最優(yōu)問(wèn)題，大幅提高了求解難度，尤其是在高維情況下。CEC2017測(cè)試集中的30個(gè)基準(zhǔn)測(cè)試函數(shù)和CEC2020測(cè)試集中的10個(gè)基準(zhǔn)測(cè)試函數(shù)，都被劃為單峰函數(shù)、簡(jiǎn)單多峰函數(shù)、混合函數(shù)、組合函數(shù)四類，如表4所示，更加詳細(xì)的函數(shù)測(cè)試集信息請(qǐng)見(jiàn)參考文獻(xiàn)[25]和[26]。CEC2017和CEC2020為DCCE-IICA的性能評(píng)估提供了一個(gè)全面的框架。

表4 CEC2017和CEC2020的基準(zhǔn)測(cè)試函數(shù)分類情況Table 4 Classification of benchmark functions in CEC2017 and CEC2020

基于CEC2017測(cè)試集，本節(jié)將展示30、50和100維三個(gè)維度下DCCE-IICA的執(zhí)行結(jié)果（每一個(gè)測(cè)試函數(shù)獨(dú)立計(jì)算51次），并與7種先進(jìn)算法的實(shí)驗(yàn)結(jié)果對(duì)比；基于CEC2020測(cè)試集，計(jì)算實(shí)驗(yàn)與結(jié)果對(duì)比的問(wèn)題維度則為10、15和20維（每一個(gè)測(cè)試函數(shù)獨(dú)立計(jì)算31次），并與其他6種典型算法的實(shí)驗(yàn)結(jié)果對(duì)比。此外，CEC相關(guān)數(shù)據(jù)集中指定每一次獨(dú)立運(yùn)行的最大迭代數(shù)隨著計(jì)算維度的增大而增大，而DCCE-IICA因其收斂速度相對(duì)較快，在較少迭代下便能得到較優(yōu)的收斂精度，故暫將最大迭代數(shù)設(shè)為固定的10 000次。

數(shù)據(jù)統(tǒng)計(jì)部分，經(jīng)典函數(shù)測(cè)試集相關(guān)的實(shí)驗(yàn)數(shù)據(jù)為DCCE-IICA所求的實(shí)際值；而CEC2017與CEC2020測(cè)試集記錄的數(shù)據(jù)為測(cè)試函數(shù)的全局最優(yōu)值與算法所求值之間的誤差值，若誤差值小于10-8，按CEC測(cè)試集的要求可直接將其記錄為0，默認(rèn)此時(shí)已收斂至全局最優(yōu)解（以下各統(tǒng)計(jì)表格均按照上述規(guī)定）。統(tǒng)計(jì)實(shí)驗(yàn)數(shù)據(jù)后得到的最優(yōu)值（Best）、平均值（Mean）和方差（Std）如下所示：DCCE-IICA對(duì)經(jīng)典函數(shù)測(cè)試集的實(shí)驗(yàn)數(shù)據(jù)見(jiàn)表5，對(duì)CEC2017測(cè)試集的實(shí)驗(yàn)數(shù)據(jù)見(jiàn)表6，對(duì)CEC2020測(cè)試集的實(shí)驗(yàn)數(shù)據(jù)見(jiàn)表7。

表5 經(jīng)典測(cè)試函數(shù)的求解結(jié)果Table 5 Solving results for classic benchmark functions

表6 CEC2017測(cè)試函數(shù)的求解結(jié)果Table 6 Solving results for benchmark functions in CEC2017 test set

表7 CEC2020測(cè)試函數(shù)的求解結(jié)果Table 7 Solving results for benchmark functions in CEC2020 test set

DCCE-IICA具有良好的適應(yīng)性，對(duì)硬件平臺(tái)要求較低。所有計(jì)算實(shí)驗(yàn)均在同一環(huán)境下完成：計(jì)算機(jī)CPU 2.20 GHz Intel Core i7-10870H、內(nèi)存16 GB、操作系統(tǒng)為64位Windows 10，編程語(yǔ)言采用Python 3.7。

3.2 DCCE-IICA的參數(shù)設(shè)置

智能進(jìn)化算法在解決不同問(wèn)題時(shí)，適當(dāng)?shù)卣{(diào)整參數(shù)是常見(jiàn)且必要的[33]。經(jīng)過(guò)大量實(shí)驗(yàn)驗(yàn)證，發(fā)現(xiàn)DCCEIICA中只有同化系數(shù)β具有較強(qiáng)的敏感性。因此面對(duì)不同函數(shù)問(wèn)題時(shí)，DCCE-IICA需要對(duì)同化系數(shù)的取值進(jìn)行適當(dāng)?shù)恼{(diào)整。DCCE-IICA的常量參數(shù)設(shè)置情況為：初始帝國(guó)數(shù)Nimp為15，初始殖民地總數(shù)Ncol為130，克隆系數(shù)λ為0.8。同化系數(shù)β的取值見(jiàn)表8至表10。

表8 經(jīng)典函數(shù)測(cè)試集中同化系數(shù)β的取值Table 8 Setting of assimilation coefficientβin classic benchmark functions set

表9 CEC2017測(cè)試集中同化系數(shù)β的取值Table 9 Setting of assimilation coefficientβ in CEC2017 test set

表10 CEC2020測(cè)試集中同化系數(shù)β的取值Table 10 Setting of assimilation coefficientβ in CEC2020 test set

3.3 基于經(jīng)典測(cè)試函數(shù)的算法對(duì)比分析

從表5中DCCE-IICA對(duì)10個(gè)經(jīng)典測(cè)試函數(shù)的收斂結(jié)果中可以知道，在30維下的收斂精度較為穩(wěn)定，且大部分函數(shù)都能穩(wěn)定地收斂至全局最優(yōu)解，但50維和100維下的求解平均值顯示出的收斂精度波動(dòng)較大。對(duì)此，表11統(tǒng)計(jì)了DCCE-IICA對(duì)這10個(gè)經(jīng)典測(cè)試函數(shù)的尋優(yōu)率，即在三個(gè)維度下的100次獨(dú)立運(yùn)行中取得全局最優(yōu)值的比例。

表11 30、50和100維下經(jīng)典測(cè)試函數(shù)的尋優(yōu)率Table 11 Optimization rate for classic benchmark functions in 30D，50D and 100D %

表11顯示，除了F10和100維下的F9外，DCCE-IICA都能夠較好地收斂至全局最優(yōu)解，且都能將尋優(yōu)率保持在一個(gè)較高水平。為了驗(yàn)證本文算法是否能有效應(yīng)對(duì)F10，選擇與王貴林等[34]受春秋戰(zhàn)國(guó)史實(shí)啟發(fā)而提出的SAICA進(jìn)行對(duì)比。SAICA在函數(shù)F10上的收斂表現(xiàn)勝過(guò)了SaDE（differential evolution algorithm with strategy adaptation）、SE（spherical evolution）、COA（coyote optimization algorithm）與HCOAG（hybrid COA with GWO）、DMS-PSO-EL（dynamic multi-swarm particle swarm optimization based on an elite learning strategy），以及EDA-M/D（estimation distribution algorithm based on multiple elites sampling and individuals differential search）這6種現(xiàn)代算法。表12記錄了SAICA與DCCEIICA的對(duì)比數(shù)據(jù)。

表12 SAICA與DCCE-IICA求解F10的實(shí)驗(yàn)結(jié)果Table 12 Performances for SAICA and DCCE-IICA on F10

表12顯示，在三個(gè)維度下，DCCE-IICA對(duì)函數(shù)F10的收斂表現(xiàn)都優(yōu)于SAICA。綜上可知，DCCE-IICA對(duì)經(jīng)典測(cè)試函數(shù)有著較好的尋優(yōu)精度和穩(wěn)定性。

3.4 基于CEC2017測(cè)試集的算法對(duì)比分析

在本節(jié)，著名算法LSHAD的三個(gè)變種LSHADE-RSP[35]、LSHADE-SPACMA[36]和jSO[37]，及MLS-EDA[33]、RB-IPOPCMA-ES[38]、PPSO[39]和D-YYPO[40]共7種改進(jìn)算法，將會(huì)與DCCE-IICA進(jìn)行實(shí)驗(yàn)數(shù)據(jù)對(duì)比。上述算法的實(shí)驗(yàn)數(shù)據(jù)均來(lái)自于已公開(kāi)發(fā)表的文獻(xiàn)，并主要用誤差平均值（Mean）和方差（Std）來(lái)比較不同算法對(duì)同一函數(shù)求解能力的優(yōu)劣。平均值能同時(shí)體現(xiàn)算法對(duì)某一函數(shù)的收斂精度和穩(wěn)定性[33]，所以用平均值作為主要的對(duì)比參數(shù)。表13至表15分別統(tǒng)計(jì)了8種算法在30、50和100維的實(shí)驗(yàn)數(shù)據(jù)。

從表13可知，30維下，DCCE-IICA在22個(gè)函數(shù)上有著眾算法中最小的誤差值，分別是單峰函數(shù)F1、F2和F3，簡(jiǎn)單多峰函數(shù)中的F5、F7、F8、F9和F10，混合函數(shù)中的F11、F13、F14、F16、F17、F18、F19和F20，及組合函數(shù)中的F21、F22、F23、F24、F28和F29；其中，有多種算法對(duì)函數(shù)F1、F2、F3、F9和F22也求得了最優(yōu)值；對(duì)其余8個(gè)函數(shù)，DCCE-IICA的表現(xiàn)不如LSHADE-SPACMA、LSHADE-RSP和MLS-EDA等算法出色。從表14可知，50維下，DCCE-IICA在23個(gè)函數(shù)上取得了9個(gè)算法中最好的成績(jī)，與30維的情況相比，新增了F12、F15和F25，少了F9和F29。但值得注意的是，隨著維度升高，DCCE-IICA在本就劣勢(shì)的F4、F6、F9、F26、和F27上的求解表現(xiàn)與LSHADE-SPACMA和MLS-EDA的差距更大了。并且，表15顯示，在100維下DCCE-IICA的優(yōu)勢(shì)函數(shù)為18個(gè)，和50維的情況相比少了F9、F11、F13和F20。

表13 8種算法求解30維CEC2017測(cè)試集的實(shí)驗(yàn)數(shù)據(jù)（MeanStd）Table 13 Solving results of 8 algorithms for 30D CEC2017 test set（MeanStd）

表14 8種算法求解50維CEC2017測(cè)試集的實(shí)驗(yàn)數(shù)據(jù)（MeanStd）Table 14 Solving results of 8 algorithms for 50D CEC2017 test set（MeanStd）

表15 8種算法求解100維CEC2017測(cè)試集的實(shí)驗(yàn)數(shù)據(jù)（MeanStd）Table 15 Solving results of 8 algorithms for 100D CEC2017 test set（MeanStd）

為了從實(shí)驗(yàn)數(shù)據(jù)上獲得算法性能更加直觀的對(duì)比結(jié)果，這里采用Wilcoxon符號(hào)秩檢驗(yàn)[41]。在優(yōu)化算法領(lǐng)域，Wilcoxon符號(hào)秩檢驗(yàn)被廣泛用于多測(cè)試集下算法間的兩兩比較[42]。利用IBM SPSS Statistics 26軟件，表16統(tǒng)計(jì)了置信度α為0.05時(shí)DCCE-IICA與其他8個(gè)算法的Wilcoxon符號(hào)秩檢驗(yàn)結(jié)果。

表16中，“+”表示DCCE-IICA在30個(gè)測(cè)試函數(shù)中強(qiáng)過(guò)競(jìng)爭(zhēng)對(duì)手的函數(shù)個(gè)數(shù)；“-”則與“+”相反；“≈”表示兩算法實(shí)驗(yàn)結(jié)果相近的函數(shù)個(gè)數(shù)?！癛+”與“R-”分別表示優(yōu)勢(shì)函數(shù)個(gè)數(shù)獲得的秩和與劣勢(shì)函數(shù)個(gè)數(shù)獲得的秩和；當(dāng)p值低于置信度時(shí)，可認(rèn)為算法取得了顯著的優(yōu)勢(shì)。表16的數(shù)據(jù)顯示，30和50維下，DCCE-IICA全面優(yōu)于其他算法；在100維時(shí)，DCCE-IICA僅對(duì)LSHADESPACMA和MLS-EDA的優(yōu)勢(shì)不甚顯著。

表16 面向CEC2017測(cè)試集的Wilcoxon符號(hào)秩檢驗(yàn)對(duì)比結(jié)果(α=0.05)Table 16 Comparison results of Wilcoxon signed rank test for CEC2017 test set(α=0.05)

通過(guò)上述數(shù)據(jù)的比對(duì)和分析，可以發(fā)現(xiàn)DCCE-IICA算法無(wú)法全面取得優(yōu)勢(shì)的主要原因，是其對(duì)多個(gè)組合函數(shù)領(lǐng)域的連續(xù)優(yōu)化問(wèn)題求解效果不佳。為了進(jìn)一步驗(yàn)證這一論點(diǎn)，將本文算法對(duì)CEC2017中30個(gè)測(cè)試函數(shù)的收斂曲線繪制于圖1，其中橫坐標(biāo)為迭代數(shù)，縱坐標(biāo)為收斂誤差值的自然對(duì)數(shù)形式，縱軸值至-20即表示誤差值已低于10-8。圖1中各函數(shù)的收斂曲線呈現(xiàn)如下三種趨勢(shì)：

圖1 DCCE-IICA求解CEC2017測(cè)試集的收斂表現(xiàn)圖Fig.1 Convergence performance graph of DCCE-IICA solving CEC2017 test set

圖1（續(xù)）

（1）曲線在較少迭代內(nèi)快速下降至X軸。多出現(xiàn)在單峰函數(shù)F1～F3和低維度的多峰函數(shù)上。

（2）曲線呈不規(guī)則的階梯狀持續(xù)下降。這印證了新機(jī)制能有效地工作，能幫助算法在收斂停滯時(shí)跳出瓶頸。這一現(xiàn)象多出現(xiàn)在混合函數(shù)和高維的多峰函數(shù)收斂過(guò)程中。

（3）曲線在前期快速下降，隨后便陷入停滯，不再向下探索。組合函數(shù)的收斂過(guò)程基本都符合這一趨勢(shì)。

組合函數(shù)是由多種函數(shù)拼接而成，其每一個(gè)局部最優(yōu)解都被不同特性的搜索區(qū)域圍繞著[25]。在DCCEIICA算法求解表現(xiàn)不及其他算法的組合函數(shù)F25、F26、F27、F29和F30的構(gòu)成中，都包含了本文所提算法同樣求解效果不佳的簡(jiǎn)單多峰函數(shù)F4或F6。F4和F6的特性是局部最優(yōu)解的數(shù)量繁多，十分考驗(yàn)算法的深度挖掘能力，即算法尋得理論最優(yōu)值的能力。從圖1中也可以發(fā)現(xiàn)，50和100維下F4和F6的收斂曲線同樣呈現(xiàn)出上述的第三種趨勢(shì)，說(shuō)明DCCE-IICA在該問(wèn)題領(lǐng)域上沒(méi)能獲得較為理想的優(yōu)化效果。

總的來(lái)說(shuō)，DCCE-IICA算法擅長(zhǎng)于求解絕大多數(shù)單峰、簡(jiǎn)單多峰和混合類函數(shù)問(wèn)題及部分組合函數(shù)問(wèn)題，但對(duì)于具有龐大數(shù)量局部最優(yōu)解的函數(shù)問(wèn)題，容易出現(xiàn)過(guò)早陷入局部最優(yōu)解的現(xiàn)象，因此對(duì)該類領(lǐng)域函數(shù)問(wèn)題的適用性還較為有限。

3.5 基于CEC2020測(cè)試集的算法對(duì)比分析

本節(jié)選擇了另外6種先進(jìn)算法與DCCE-IICA進(jìn)行對(duì)比，分別是CSsin[43]、RASP-SHADE[44]、GADE[45]、MP-EEH[46]、AGSK[47]和IMODE[48]。以上算法實(shí)驗(yàn)數(shù)據(jù)同樣都來(lái)自于已公開(kāi)發(fā)布的文獻(xiàn)，且對(duì)比流程與規(guī)則都同3.4節(jié)一致。表17至表19分別統(tǒng)計(jì)了7種典型智能算法求解10、15和20維CEC2020數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果。

表17 7種算法求解10維CEC2020測(cè)試集的實(shí)驗(yàn)數(shù)據(jù)（MeanStd）Table 17 Solving results of 7 algorithms for 10D CEC2020 test set（MeanStd）

表18 7種算法求解15維CEC2020測(cè)試集的實(shí)驗(yàn)數(shù)據(jù)（MeanStd）Table 18 Solving results of 7 algorithms for 15D CEC2020 test set（MeanStd）

表19 7種算法求解20維CEC2020測(cè)試集的實(shí)驗(yàn)數(shù)據(jù)（MeanStd）Table 19 Solving results of 7 algorithms for 20D CEC2020 test set（MeanStd）

由表17至表19可知，DCCE-IICA在三個(gè)維度下的收斂表現(xiàn)十分相似：DCCE-IICA在單峰函數(shù)F1、簡(jiǎn)單多峰函數(shù)F3、F4和混合函數(shù)F5上取得了眾算法中較為優(yōu)異的收斂精度；然而對(duì)于其余函數(shù)，DCCE-IICA的表現(xiàn)較為一般，且多是差分進(jìn)化（DE）算法的三個(gè)變種RASPSHADE、GADE和IMODE占據(jù)優(yōu)勢(shì)。

接著，同樣使用Wilcoxon符號(hào)秩檢驗(yàn)來(lái)成對(duì)比較DCCE-IICA與另外6個(gè)算法兩兩間的性能差異。表20為DCCE-IICA與其他6種算法面向CEC2020測(cè)試集的Wilcoxon符號(hào)秩檢驗(yàn)結(jié)果。結(jié)果顯示，DCCE-IICA在整體上都未能體現(xiàn)出與其他6種典型算法的明顯優(yōu)越性，進(jìn)一步指出了DCCE-IICA的局限性。

表20 面向CEC2020測(cè)試集的Wilcoxon符號(hào)秩檢驗(yàn)對(duì)比結(jié)果(α=0.05)Table 20 Comparison results of Wilcoxon signed rank test for CEC2020 testing set(α=0.05)

從上述對(duì)比結(jié)果中可以發(fā)現(xiàn)，DCCE-IICA并沒(méi)有因?yàn)閱?wèn)題維度的下降而提高對(duì)組合函數(shù)問(wèn)題的收斂精度，同時(shí)，對(duì)函數(shù)F2、F6和F7的求解表現(xiàn)也是DCCE-IICA無(wú)法在Wilcoxon符號(hào)秩檢驗(yàn)取得優(yōu)勢(shì)的主要原因。根據(jù)CEC2020數(shù)據(jù)集里的描述，F(xiàn)2具有局部最優(yōu)的數(shù)量很大、且全局第二優(yōu)解與全局最優(yōu)解相距甚遠(yuǎn)的特性，而混合函數(shù)F6、F7和組合函數(shù)F8～F10的組成成分中皆包含了F2或CEC2017測(cè)試集中的F4[26]。這里依舊用各函數(shù)的收斂曲線圖作進(jìn)一步驗(yàn)證。圖2為DCCE-IICA求解CEC2020測(cè)試集的收斂曲線圖。

圖2中展現(xiàn)的DCCE-IICA收斂情況基本符合圖1總結(jié)出的特點(diǎn)和趨勢(shì)。并且，本節(jié)中求解不佳的函數(shù)都呈現(xiàn)出3.4節(jié)描述的第三種收斂曲線發(fā)展趨勢(shì)，即收斂過(guò)早停滯，陷入早熟。

圖2 DCCE-IICA求解CEC2020測(cè)試集的收斂表現(xiàn)圖Fig.2 Convergence performance graph of DCCE-IICA solving CEC2020 test set

從總體看，DCCE-IICA通過(guò)基于進(jìn)制轉(zhuǎn)換的克隆進(jìn)化機(jī)制對(duì)殖民地國(guó)家定期重置、對(duì)帝國(guó)勢(shì)力分布周期性地變動(dòng)，及在算法近乎陷入停滯時(shí)將弱勢(shì)帝國(guó)從局部移至新領(lǐng)域進(jìn)行開(kāi)發(fā)的措施和策略，確實(shí)較好地改善了原算法在全局尋優(yōu)能力上的不足，使得DCCE-IICA對(duì)多數(shù)單峰、簡(jiǎn)單多峰和混合類型的函數(shù)問(wèn)題，甚至包括部分組合函數(shù)問(wèn)題，有著不亞于多種國(guó)際著名現(xiàn)代優(yōu)化算法的深度挖掘能力。

然而，以整個(gè)帝國(guó)為載體來(lái)拓展算法的勘探能力存在著兩個(gè)問(wèn)題：一是帝國(guó)數(shù)量稀少，二是帝國(guó)內(nèi)的個(gè)體具有集聚、趨同的特性。這就使得DCCE-IICA對(duì)局部最優(yōu)解數(shù)量過(guò)多、欺騙性高的多峰搜索空間進(jìn)行的勘探工作不夠全面和細(xì)致，進(jìn)而導(dǎo)致其對(duì)搜索空間各區(qū)域的探索嘗試不足。最終造成了DCCE-IICA對(duì)局部最優(yōu)解數(shù)量巨大的函數(shù)及包含了該特性的組合函數(shù)的優(yōu)化能力不足。

3.6 DCCE-IICA算法的收斂效率分析

前述的實(shí)驗(yàn)分析和結(jié)論，實(shí)際上都是基于DCCE-IICA對(duì)各種函數(shù)問(wèn)題的收斂精度得出的。因此，本節(jié)將探討DCCE-IICA對(duì)各函數(shù)問(wèn)題的收斂效率。表21至表23為DCCE-IICA算法對(duì)經(jīng)典函數(shù)測(cè)試集、CEC2017測(cè)試集和CEC2020測(cè)試集中各函數(shù)收斂至最優(yōu)解所花費(fèi)的迭代數(shù)。當(dāng)求得全局最優(yōu)解或收斂結(jié)果不再更新時(shí)便可認(rèn)為算法已完成收斂，并統(tǒng)計(jì)多次獨(dú)立運(yùn)行中完成收斂所花費(fèi)的迭代數(shù)，記錄其算數(shù)平均值。

表21 經(jīng)典函數(shù)測(cè)試集的收斂迭代數(shù)Table 21 Convergent iteration number for classic benchmark function set

表23 CEC2020測(cè)試集的收斂迭代數(shù)Table 23 Convergent iteration number for CEC2020 test set

表21顯示，DCCE-IICA對(duì)于F1～F8在不同維度下花費(fèi)的收斂迭代數(shù)十分相近：30維下的收斂跌代數(shù)基本在區(qū)間（600，800）內(nèi)；50維則為（700，1 000）；100維則為（900，1 300）。與算法所設(shè)最大迭代數(shù)10 000相比，DCCEIICA對(duì)求解效果好的函數(shù)問(wèn)題有著很好的收斂效率。對(duì)于非原點(diǎn)最優(yōu)問(wèn)題F9，算法在30和50維下求至最優(yōu)解所花費(fèi)的迭代數(shù)較F1～F8多，但與最大迭代數(shù)相比，F(xiàn)9的收斂效率也處于一個(gè)較為合適的水平。對(duì)于較難求解的F10和100維下的F9，DCCE-IICA能持續(xù)收斂至接近最大迭代數(shù)，雖說(shuō)明算法對(duì)其的收斂速率慢，但同時(shí)也表示改進(jìn)機(jī)制很好地發(fā)揮出了避免收斂過(guò)早停滯的作用，不斷幫助算法持續(xù)向全局最優(yōu)解逼近。

從表22和表23中可以看出，DCCE-IICA對(duì)30維及30以下維度的函數(shù)求解效率較高。并且，部分DCCEIICA求解效果較好的函數(shù)，如CEC2017測(cè)試集中的3個(gè)單峰函數(shù)和組合函數(shù)F21～F25，在中高維度下也有著明顯較少的收斂迭代數(shù)。但從其他函數(shù)在中高維度下的收斂迭代數(shù)中可以看出，大部分非原點(diǎn)最優(yōu)函數(shù)問(wèn)題的全局最優(yōu)解是較難求得的，因此對(duì)于此類函數(shù)更應(yīng)該考察的是特定迭代數(shù)下的收斂精度，即前述3.3、3.4和3.5節(jié)的內(nèi)容，而本節(jié)中的最大迭代數(shù)也是基于此設(shè)置的。

表22 CEC2017測(cè)試集的收斂迭代數(shù)Table 22 Convergent iteration number for CEC2017 test set

優(yōu)化算法的相關(guān)研究終歸是面向具體的實(shí)踐應(yīng)用，因此從算法的適用領(lǐng)域出發(fā)來(lái)評(píng)價(jià)一個(gè)優(yōu)化算法的收斂效率更為合適。基于前面三個(gè)不同數(shù)據(jù)集的計(jì)算實(shí)驗(yàn)及與其他14種先進(jìn)優(yōu)化算法的收斂精度對(duì)比，確定了DCCE-IICA算法在大部分單峰、簡(jiǎn)單多峰和混合函數(shù)及部分組合函數(shù)的求解精度上具有顯著優(yōu)勢(shì)。而本節(jié)的統(tǒng)計(jì)結(jié)果確切地顯示出DCCE-IICA算法對(duì)優(yōu)勢(shì)領(lǐng)域有著較好的收斂效率，從另一個(gè)側(cè)面說(shuō)明DCCE-IICA對(duì)優(yōu)勢(shì)領(lǐng)域有著較好的應(yīng)用潛力。

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

本文提出了一種面向進(jìn)制轉(zhuǎn)換和克隆進(jìn)化機(jī)制改進(jìn)、同時(shí)輔以帝國(guó)分裂機(jī)制和出界點(diǎn)替換策略的改進(jìn)帝國(guó)競(jìng)爭(zhēng)算法DCCE-IICA，從提高算法勘探和挖掘能力、避免過(guò)早收斂和維持個(gè)體多樣性三個(gè)方面改進(jìn)了經(jīng)典ICA。DCCE-IICA本質(zhì)是通過(guò)將生物進(jìn)化機(jī)制與社會(huì)演變模式進(jìn)行深度融合，以得出提高群集智能尋優(yōu)性能的算法設(shè)計(jì)范式。通過(guò)特定維度下經(jīng)典函數(shù)測(cè)試集、CEC2017測(cè)試集和CEC2020測(cè)試集內(nèi)共50個(gè)基準(zhǔn)測(cè)試函數(shù)的實(shí)驗(yàn)數(shù)據(jù)，及與其他14個(gè)前沿算法的對(duì)比結(jié)果，驗(yàn)證了DCCE-IICA較為突出的尋優(yōu)效率和準(zhǔn)確性，初步實(shí)現(xiàn)了DCCE-IICA的預(yù)期設(shè)計(jì)目標(biāo)。

下一步，DCCE-IICA至少還有兩個(gè)有待深入探討的研究方向。首先，DCCE-IICA中引入的進(jìn)制編碼轉(zhuǎn)換和克隆進(jìn)化機(jī)制組合是一種兼具提高全局勘探和局部挖掘能力的改進(jìn)方法，其也有望應(yīng)用于提高其他群集智能優(yōu)化算法的性能。其次，DCCE-IICA在優(yōu)化部分局部最優(yōu)解數(shù)量極其龐大的函數(shù)問(wèn)題時(shí)所表現(xiàn)的有限的適用性和深度挖掘能力，亟需在未來(lái)的算法改進(jìn)工作中解決。