面向進制轉換和克隆進化的帝國競爭改進算法

李 斌，黃起彬

1.福建工程學院 機械與汽車工程學院，福州 350118

2.福建工程學院 交通運輸學院，福州 350118

受自然系統啟發的隨機性優化算法被稱作元啟發式算法。根據算法的啟發方式，可被分為三類：進化算法、物理算法和群體智能算法[1]。進化算法指靈感來自于大自然生物進化的元啟發式算法，例如著名的遺傳算法[2]和進化策略算法[3]；物理算法指受物理規則或化學現象啟發創建的元啟發式算法，如Nuclear Reaction Optimization[4]和Flow Regime Algorithm[5]；群體智能算法是模仿動物群體行為或人類社會行為的元啟發式算法，典型的有蟻群算法[6]和粒子群算法[7]等。此外，不同的元啟發式算法之間相互借鑒或融合生成的混合型優化算法，如基于灰狼優化的反向學習粒子群算法[8]和融合貓群算法的動態分組蟻群算法[9]，也是現代優化算法中的重要組成部分。

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

針對上述不足，國內外眾多學者在改進ICA方面進行了大量的工作，改進方向主要可分為完善原有機制和融入新機制兩種。經典ICA中的同化機制是最有改進潛力的部分：裴小兵等[16]將帝國同化信息記錄于概率矩陣模型中，利用區塊挖掘和競爭實現殖民地的同化行為；Bahrami等[17]設計了四種混沌映射來改變殖民地向其殖民國家同化時的運動角度，以增強算法對局部最優陷阱的逃逸能力。

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

盡管以往研究從多個角度改進了ICA的性能，為智能優化算法的改進提供了有益的嘗試，但仍然存在一些可以繼續改進的空間：

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

（2）現有絕大多數研究主要從單個或少數方面進行改進。算法機制的改進可以是多方面、多元化的。對多種優化目的不同的改進機制進行綜合性探討，有望為ICA的改進提供新的思路。

（3）基于ICA本身的運行特性，以同時提高算法勘探和挖掘能力為目的進行改進。ICA是通過帝國內部以及帝國之間的多種互動行為實現優化，其中能直接影響ICA求解能力的個體對象是帝國主義國家[21]。因此，將有利于提高勘探能力或挖掘能力的改進方法作用于帝國主義國家有望產生較好的改進效果。

上述思想正是本文所提改進算法的理論原點。在ICA的基礎上，本文所提的面向進制轉換和克隆進化的帝國競爭改進算法（decimal-binary conversion and clonal evolution oriented improved imperialist competitive algorithm，DCCE-IICA）更加注重利用演化種群中各群體的特性，針對現有問題進行改進，其引入和應用的核心改進機制如下：

（1）引入基于進制編碼轉換的克隆進化策略。DCCEIICA最主要的改進機制是結合二進制基因變異理論[22]與克隆選擇算法[23]的優化思想，引入一種基于二進制與十進制編碼轉換的克隆進化策略。該策略可用于部分解決ICA停滯于局部最優的問題，通過周期性地為演化種群提供一個強大的新發展途徑，提高殖民地群體基因多樣性的同時，利用帝國主義國家對其附屬殖民地的引導能力跳出局部，并通過調整帝國之間的強弱關系來平衡算法資源的流向，延長算法的活力。

（2）將帝國分裂機制[24]融入新算法中。帝國分裂機制在現有研究成果中，有著較好地緩解ICA執行過程中收斂過早結束的能力，并且對改進算法的適用性強，因此將其作為輔助機制融入DCCE-IICA中。

（3）設計了一個較為有效的出界點替換策略。同化機制執行過程中，存在殖民地向其宗主國方向移動后可能超出搜索邊界的問題。DCCE-IICA的替換策略能更好地保證群體的多樣性。

為了系統性地驗證DCCE-IICA的改進有效性與可信性，本文選擇經典函數測試集、CEC2017測試集[25]以及CEC2020測試集[26]進行優化實驗，面向多個維度下不同類型的函數優化問題來測試和檢驗DCCE-IICA的尋優能力。在此基礎上，將DCCE-IICA在CEC系列測試集上的實驗結果，與13個國際前沿算法進行比較，包括2017年進化算法大賽冠軍算法LSHADE-SPACMA的變體，來充分證明本文所提算法求解復雜函數時的求解精度、收斂狀況和魯棒性。

1 帝國競爭算法

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

步驟1初始化帝國。在搜索區域內隨機生成一定數量的國家，勢力最強的Nimp個國家為帝國主義國家，即殖民國家，然后根據成本值大小瓜分其余的Ncol個國家作為它們的附屬殖民地國家，形成最初的帝國格局。

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

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

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

步驟4帝國合并。當兩個帝國過于接近時，更強一方將另一帝國完全吸收，變為自己的殖民地。

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

步驟6帝國統一。算法在多次的迭代中重復執行步驟2至步驟5，帝國將相繼滅亡。當場上只存在一個帝國時，算法結束。

2 面向進制轉換和克隆進化的帝國競爭改進算法

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

2.1 DCCE-IICA算法的核心改進機制

2.1.1 基于進制編碼轉換的克隆進化機制

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

步驟1進制轉換。對帝國主義國家每一個維度上的坐標值，從一個十進制數字轉變為一條長度固定的二進制數字串。本文計算實驗的搜索區域為（-100，100），因此長度為21的二進制數字串基本可以滿足本文實驗需要的所有變異可能性：除開正負號，整數部分變換后的二進制數字串長度為7，等于規定搜索范圍的上限值轉換為二進制后的數字串長度；而小數部分的長度則設定為整數部分的兩倍。如下是某個國家第i維向量上的坐標值二進制化后的數學表達形式：

其中，xi為某一國家第i維向量上的坐標值，xi,1,xi,2,…,xi,21分別對應二進制數字串的21位數字。

步驟2克隆。各帝國主義國家在完成十進制至二進制的編碼轉換后，對其進行克隆。各帝國主義國家克隆體數量的計算公式如下：

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

步驟3變異。對所有克隆體每一維度的數字串，隨機選擇其中1/3的數字，進行0-1變換。

步驟4交叉。將每一個帝國主義國家對應的所有克隆變異個體視為一個變異族群，族群內部進行高頻交叉。高頻交叉的方式如下：

（1）根據族群內部的個體數量，隨機從內部取出n個變異體作為一組。由下式確定：

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

其中，Muti為第i個帝國的變異族群；k為存儲數值的臨時參數；r1,r2,…,rn用以表示組內不同的個體；下標j表示二進制數字串中第j位數字。

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

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

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

2.1.2 帝國分裂機制的應用

帝國分裂機制是郭婉青[24]模擬歷史上帝國內部不斷發展強大的殖民地與殖民國家發生沖突導致帝國分裂的現象，該機制的設計初衷就是為了緩解ICA因過早收斂而陷入局部最優的缺陷。在DCCE-IICA中，帝國分裂機制主要用于維持帝國個數不為一，算法能夠多輪持續進化，故此處簡化了觸發分裂的條件，即在克隆進化機制執行前，帝國數少于2便觸發帝國分裂機制。具體步驟如下：

步驟1找出帝國中勢力最強的殖民地，將其晉升為帝國主義國家。

步驟2根據新帝國與舊帝國成本值的比值，隨機地將舊帝國相應個數的殖民地分配給新帝國。新帝國分走的殖民地個數由下式決定：

其中，Cost()為國家勢力值的求取函數，NCnew表示新帝國擁有的殖民地個數，NCall表示現存殖民地的總數。

2.1.3 出界點的新型替換策略

DCCE-IICA借鑒Lin等于2013年提出的擾動ICA[30]中對超出搜索范圍的坐標值進行策略性替換的思想，在其改進基礎上提出一種新的替換策略，利用出界坐標點與邊界的距離，按比率將出界個體映射回搜索空間內部。公式如下：

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

2.2 算法的設計與實現

DCCE-IICA在實現與執行中遵循如下規則：

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

（2）將最大迭代數(FEsmax)作為算法唯一的結束條件。因為帝國分裂機制的加入，算法收斂的結束與否已不再受到帝國數量的限制。

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

算法1DCCE-IICA

2.3 算法特性分析

2.3.1 時間復雜度分析

計算成本是限制優化算法應用的一個重要因素。假設國家總數為n，帝國主義國家個數為n1，殖民地國家個數為n2，克隆體個數為λn2。在D維搜索空間內，DCCE-IICA各項機制在單次迭代中的時間復雜度如表1所示。

表1 時間復雜度Table 1 Time complexity

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

從表2中可以看出，與類似算法對比，DCCE-IICA的時間計算成本較為合理，具有典型的線性時間復雜度，故當算法面向不同規模的優化問題時，具有較好的可用性、適應性與魯棒性，這對于將DCCE-IICA應用到工程實踐問題中至關重要。

表2 多種典型算法的時間復雜度對比Table 2 Time complexity of several algorithm

2.3.2 局部與全局尋優能力及平衡性分析

經典ICA具有較強的局部尋優能力，而DCCE-IICA是在原算法的基礎上，周期性地對近乎停滯的演化群體執行克隆進化機制，較好地繼承了原算法的局部挖掘能力和求解效率。同時，克隆進化機制也能直接利用較優解群體幫助算法收斂，是DCCE-IICA算法隱含的一個有效收斂模式。

全局尋優側重的是算法的廣度搜索能力，而這正是原始ICA的短板所在。經基于進制轉換的克隆進化機制重置后的殖民地國家能夠盡可能廣泛地遍布搜索空間，并且，克隆進化機制會賦予較弱帝國更強的勢力并引導其開采新的區域，原本較強的帝國會變得弱勢，進而在下一個克隆進化執行時間點被重置，最終所有帝國都會依次完成從局部躍遷至新區域進行探索和開發的行為，實現全局尋優。

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

3 計算實驗與性能評估

3.1 實驗設計

本節的主要目標是通過全面且完整的多個函數測試集來驗證和評判DCCE-IICA的優缺點。因此，選擇了10個經典測試函數及更具有挑戰性的CEC2017和CEC2020三個測試集50個復雜函數進行計算實驗，并通過與多種不同類型的前沿優化算法進行對比，來對其性能進行全面評估。

本文所選的10個經典測試函數（詳情見表3），除Levy函數（F9）外，全為原點最優問題（即在原點處取到理論最優解），是相對較為易解的一類函數問題。本文將展示30、50和100維三個維度下獨立運行100次的實驗結果，及與一種在該測試集上表現優異的改進智能算法進行對比。此外，經典測試函數的搜索范圍將與CEC測試集一致，將其投射至（-100，100），投射公式如下：

表3 經典測試函數Table 3 Classic benchmark functions

其中，l為經典測試函數原本的搜索上界，x和x*分別為映射前后的坐標位置。

CEC相關數據集通過對測試函數的旋轉和偏移將其變為非原點最優問題，大幅提高了求解難度，尤其是在高維情況下。CEC2017測試集中的30個基準測試函數和CEC2020測試集中的10個基準測試函數，都被劃為單峰函數、簡單多峰函數、混合函數、組合函數四類，如表4所示，更加詳細的函數測試集信息請見參考文獻[25]和[26]。CEC2017和CEC2020為DCCE-IICA的性能評估提供了一個全面的框架。

表4 CEC2017和CEC2020的基準測試函數分類情況Table 4 Classification of benchmark functions in CEC2017 and CEC2020

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

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

表5 經典測試函數的求解結果Table 5 Solving results for classic benchmark functions

表6 CEC2017測試函數的求解結果Table 6 Solving results for benchmark functions in CEC2017 test set

表7 CEC2020測試函數的求解結果Table 7 Solving results for benchmark functions in CEC2020 test set

DCCE-IICA具有良好的適應性，對硬件平臺要求較低。所有計算實驗均在同一環境下完成：計算機CPU 2.20 GHz Intel Core i7-10870H、內存16 GB、操作系統為64位Windows 10，編程語言采用Python 3.7。

3.2 DCCE-IICA的參數設置

智能進化算法在解決不同問題時，適當地調整參數是常見且必要的[33]。經過大量實驗驗證，發現DCCEIICA中只有同化系數β具有較強的敏感性。因此面對不同函數問題時，DCCE-IICA需要對同化系數的取值進行適當的調整。DCCE-IICA的常量參數設置情況為：初始帝國數Nimp為15，初始殖民地總數Ncol為130，克隆系數λ為0.8。同化系數β的取值見表8至表10。

表8 經典函數測試集中同化系數β的取值Table 8 Setting of assimilation coefficientβin classic benchmark functions set

表9 CEC2017測試集中同化系數β的取值Table 9 Setting of assimilation coefficientβ in CEC2017 test set

表10 CEC2020測試集中同化系數β的取值Table 10 Setting of assimilation coefficientβ in CEC2020 test set

3.3 基于經典測試函數的算法對比分析

從表5中DCCE-IICA對10個經典測試函數的收斂結果中可以知道，在30維下的收斂精度較為穩定，且大部分函數都能穩定地收斂至全局最優解，但50維和100維下的求解平均值顯示出的收斂精度波動較大。對此，表11統計了DCCE-IICA對這10個經典測試函數的尋優率，即在三個維度下的100次獨立運行中取得全局最優值的比例。

表11 30、50和100維下經典測試函數的尋優率Table 11 Optimization rate for classic benchmark functions in 30D，50D and 100D %

表11顯示，除了F10和100維下的F9外，DCCE-IICA都能夠較好地收斂至全局最優解，且都能將尋優率保持在一個較高水平。為了驗證本文算法是否能有效應對F10，選擇與王貴林等[34]受春秋戰國史實啟發而提出的SAICA進行對比。SAICA在函數F10上的收斂表現勝過了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種現代算法。表12記錄了SAICA與DCCEIICA的對比數據。

表12 SAICA與DCCE-IICA求解F10的實驗結果Table 12 Performances for SAICA and DCCE-IICA on F10

表12顯示，在三個維度下，DCCE-IICA對函數F10的收斂表現都優于SAICA。綜上可知，DCCE-IICA對經典測試函數有著較好的尋優精度和穩定性。

3.4 基于CEC2017測試集的算法對比分析

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

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

表13 8種算法求解30維CEC2017測試集的實驗數據（MeanStd）Table 13 Solving results of 8 algorithms for 30D CEC2017 test set（MeanStd）

表14 8種算法求解50維CEC2017測試集的實驗數據（MeanStd）Table 14 Solving results of 8 algorithms for 50D CEC2017 test set（MeanStd）

表15 8種算法求解100維CEC2017測試集的實驗數據（MeanStd）Table 15 Solving results of 8 algorithms for 100D CEC2017 test set（MeanStd）

為了從實驗數據上獲得算法性能更加直觀的對比結果，這里采用Wilcoxon符號秩檢驗[41]。在優化算法領域，Wilcoxon符號秩檢驗被廣泛用于多測試集下算法間的兩兩比較[42]。利用IBM SPSS Statistics 26軟件，表16統計了置信度α為0.05時DCCE-IICA與其他8個算法的Wilcoxon符號秩檢驗結果。

表16中，“+”表示DCCE-IICA在30個測試函數中強過競爭對手的函數個數；“-”則與“+”相反；“≈”表示兩算法實驗結果相近的函數個數。“R+”與“R-”分別表示優勢函數個數獲得的秩和與劣勢函數個數獲得的秩和；當p值低于置信度時，可認為算法取得了顯著的優勢。表16的數據顯示，30和50維下，DCCE-IICA全面優于其他算法；在100維時，DCCE-IICA僅對LSHADESPACMA和MLS-EDA的優勢不甚顯著。

表16 面向CEC2017測試集的Wilcoxon符號秩檢驗對比結果(α=0.05)Table 16 Comparison results of Wilcoxon signed rank test for CEC2017 test set(α=0.05)

通過上述數據的比對和分析，可以發現DCCE-IICA算法無法全面取得優勢的主要原因，是其對多個組合函數領域的連續優化問題求解效果不佳。為了進一步驗證這一論點，將本文算法對CEC2017中30個測試函數的收斂曲線繪制于圖1，其中橫坐標為迭代數，縱坐標為收斂誤差值的自然對數形式，縱軸值至-20即表示誤差值已低于10-8。圖1中各函數的收斂曲線呈現如下三種趨勢：

圖1 DCCE-IICA求解CEC2017測試集的收斂表現圖Fig.1 Convergence performance graph of DCCE-IICA solving CEC2017 test set

圖1（續）

（1）曲線在較少迭代內快速下降至X軸。多出現在單峰函數F1～F3和低維度的多峰函數上。

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

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

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

總的來說，DCCE-IICA算法擅長于求解絕大多數單峰、簡單多峰和混合類函數問題及部分組合函數問題，但對于具有龐大數量局部最優解的函數問題，容易出現過早陷入局部最優解的現象，因此對該類領域函數問題的適用性還較為有限。

3.5 基于CEC2020測試集的算法對比分析

本節選擇了另外6種先進算法與DCCE-IICA進行對比，分別是CSsin[43]、RASP-SHADE[44]、GADE[45]、MP-EEH[46]、AGSK[47]和IMODE[48]。以上算法實驗數據同樣都來自于已公開發布的文獻，且對比流程與規則都同3.4節一致。表17至表19分別統計了7種典型智能算法求解10、15和20維CEC2020數據集的實驗結果。

表17 7種算法求解10維CEC2020測試集的實驗數據（MeanStd）Table 17 Solving results of 7 algorithms for 10D CEC2020 test set（MeanStd）

表18 7種算法求解15維CEC2020測試集的實驗數據（MeanStd）Table 18 Solving results of 7 algorithms for 15D CEC2020 test set（MeanStd）

表19 7種算法求解20維CEC2020測試集的實驗數據（MeanStd）Table 19 Solving results of 7 algorithms for 20D CEC2020 test set（MeanStd）

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

接著，同樣使用Wilcoxon符號秩檢驗來成對比較DCCE-IICA與另外6個算法兩兩間的性能差異。表20為DCCE-IICA與其他6種算法面向CEC2020測試集的Wilcoxon符號秩檢驗結果。結果顯示，DCCE-IICA在整體上都未能體現出與其他6種典型算法的明顯優越性，進一步指出了DCCE-IICA的局限性。

表20 面向CEC2020測試集的Wilcoxon符號秩檢驗對比結果(α=0.05)Table 20 Comparison results of Wilcoxon signed rank test for CEC2020 testing set(α=0.05)

從上述對比結果中可以發現，DCCE-IICA并沒有因為問題維度的下降而提高對組合函數問題的收斂精度，同時，對函數F2、F6和F7的求解表現也是DCCE-IICA無法在Wilcoxon符號秩檢驗取得優勢的主要原因。根據CEC2020數據集里的描述，F2具有局部最優的數量很大、且全局第二優解與全局最優解相距甚遠的特性，而混合函數F6、F7和組合函數F8～F10的組成成分中皆包含了F2或CEC2017測試集中的F4[26]。這里依舊用各函數的收斂曲線圖作進一步驗證。圖2為DCCE-IICA求解CEC2020測試集的收斂曲線圖。

圖2中展現的DCCE-IICA收斂情況基本符合圖1總結出的特點和趨勢。并且，本節中求解不佳的函數都呈現出3.4節描述的第三種收斂曲線發展趨勢，即收斂過早停滯，陷入早熟。

圖2 DCCE-IICA求解CEC2020測試集的收斂表現圖Fig.2 Convergence performance graph of DCCE-IICA solving CEC2020 test set

從總體看，DCCE-IICA通過基于進制轉換的克隆進化機制對殖民地國家定期重置、對帝國勢力分布周期性地變動，及在算法近乎陷入停滯時將弱勢帝國從局部移至新領域進行開發的措施和策略，確實較好地改善了原算法在全局尋優能力上的不足，使得DCCE-IICA對多數單峰、簡單多峰和混合類型的函數問題，甚至包括部分組合函數問題，有著不亞于多種國際著名現代優化算法的深度挖掘能力。

然而，以整個帝國為載體來拓展算法的勘探能力存在著兩個問題：一是帝國數量稀少，二是帝國內的個體具有集聚、趨同的特性。這就使得DCCE-IICA對局部最優解數量過多、欺騙性高的多峰搜索空間進行的勘探工作不夠全面和細致，進而導致其對搜索空間各區域的探索嘗試不足。最終造成了DCCE-IICA對局部最優解數量巨大的函數及包含了該特性的組合函數的優化能力不足。

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

前述的實驗分析和結論，實際上都是基于DCCE-IICA對各種函數問題的收斂精度得出的。因此，本節將探討DCCE-IICA對各函數問題的收斂效率。表21至表23為DCCE-IICA算法對經典函數測試集、CEC2017測試集和CEC2020測試集中各函數收斂至最優解所花費的迭代數。當求得全局最優解或收斂結果不再更新時便可認為算法已完成收斂，并統計多次獨立運行中完成收斂所花費的迭代數，記錄其算數平均值。

表21 經典函數測試集的收斂迭代數Table 21 Convergent iteration number for classic benchmark function set

表23 CEC2020測試集的收斂迭代數Table 23 Convergent iteration number for CEC2020 test set

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

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

表22 CEC2017測試集的收斂迭代數Table 22 Convergent iteration number for CEC2017 test set

優化算法的相關研究終歸是面向具體的實踐應用，因此從算法的適用領域出發來評價一個優化算法的收斂效率更為合適。基于前面三個不同數據集的計算實驗及與其他14種先進優化算法的收斂精度對比，確定了DCCE-IICA算法在大部分單峰、簡單多峰和混合函數及部分組合函數的求解精度上具有顯著優勢。而本節的統計結果確切地顯示出DCCE-IICA算法對優勢領域有著較好的收斂效率，從另一個側面說明DCCE-IICA對優勢領域有著較好的應用潛力。

4 結束語

本文提出了一種面向進制轉換和克隆進化機制改進、同時輔以帝國分裂機制和出界點替換策略的改進帝國競爭算法DCCE-IICA，從提高算法勘探和挖掘能力、避免過早收斂和維持個體多樣性三個方面改進了經典ICA。DCCE-IICA本質是通過將生物進化機制與社會演變模式進行深度融合，以得出提高群集智能尋優性能的算法設計范式。通過特定維度下經典函數測試集、CEC2017測試集和CEC2020測試集內共50個基準測試函數的實驗數據，及與其他14個前沿算法的對比結果，驗證了DCCE-IICA較為突出的尋優效率和準確性，初步實現了DCCE-IICA的預期設計目標。

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