王貴林，李 斌

（福建工程學院交通運輸學院，福州 350118）

（*通信作者電子郵箱whutmse2007_lb@126.com）

0 引言

Gargari 等［1］于2007 年提出了帝國競爭算法（Imperialist Competitive Algorithm，ICA），其靈感源于人類社會帝國殖民競爭機制，是一種完全受社會行為啟發(fā)的群體隨機優(yōu)化搜索算法。該算法自提出后，已在不同領域得到廣泛研究應用。例如，Bernal 等［2］探討了ICA 在數(shù)學函數(shù)優(yōu)化中的應用；陳孟輝等［3］、Liu 等［4］、張清勇等［5］分別運用ICA 求解旅行商問題、非線性約束優(yōu)化問題和異構工廠分布式并行機調度問題；Fan等［6］、Khalilnejad 等［7］、顏波等［8］基于ICA，分別對起重機金屬結構、風力/光伏混合電解槽和多產品供應鏈設計過程進行了優(yōu)化；Hasanzade-Inallu 等［9］、劉敬浩等［10］將ICA 與神經網絡結合，分別用于預測混凝土梁的抗剪強度、構造入侵檢測模型；Illias等［11］、李明等［12］使用ICA估算微變壓器參數(shù)、實現(xiàn)高維多目標柔性作業(yè)車間調度。原始ICA 局部搜索能力較強，收斂快，但由于群體多樣性在迭代過程中降低過快、帝國之間缺乏有效的信息交互等問題，容易“早收早斂”，特別是在優(yōu)化高維多模問題時，易陷入局部最優(yōu)。

針對上述問題，國內外已有許多學者對ICA 的性能改進以及實際應用進行了大量的研究，也取得了一定的進展。例如，算法的提出者Gargari［13］給出了改進算法的Mathlab 源代碼，調整了殖民地的權值，增加了殖民地革命和帝國合并機制；郭秀萍等［14］引入變鄰域搜索，增加了種群多樣性，改善了解的質量并提高了算法效率；Bahrami等［15］利用混沌映射來調整殖民地向帝國位置的運動角度；Lin等［16］用人工產生國家取代較弱的帝國主義國家，以此來增強帝國之間的信息交互；Ardeh 等［17］通過引入探索者和保留策略的概念，采用動態(tài)種群機制對原算法進行了改進；Xu 等［18］引入高斯變異、柯西變異和萊維變異等變異算子來改變帝國主義者行為；郭婉青等［19］采用微分進化算子和克隆進化算子增強殖民地之間、帝國之間的信息交互。這些改進方案主要采用調整算法流程、引入隨機因素、融合其他算法等方式實現(xiàn)，雖然在不同程度上提升了算法的尋優(yōu)性能和穩(wěn)定性，但普遍缺乏對核心運行機制的研究改進，難以從根本上解決ICA 存在的問題；沒有加入判斷并跳出局部最優(yōu)的方案，限制了算法對高維多模函數(shù)的適用性；同時，個別復雜因子的引入也在一定程度上降低了算法的運行效率。

本文借鑒中國歷史上春秋戰(zhàn)國時期諸侯國競爭稱霸的行為對ICA 進行改進，命名為受春秋戰(zhàn)國史實啟發(fā)的帝國競爭改進算法（Improved ICA Inspired by Spring and Autumn Period，SAICA），探索解決原始ICA 受初始國家影響大、帝國間缺乏有效信息交互、容易早收早斂等問題。通過在標準函數(shù)和CEC2017 測試函數(shù)上進行實驗對比，驗證了改進算法的全局搜索、穩(wěn)定性及跳出局部最優(yōu)能力。經Kendall相關性分析顯示，改進算法與原始算法具有顯著差異性，且同化過程的改進措施發(fā)揮了關鍵的作用。

1 帝國競爭算法

ICA 的基本流程如圖1 所示，可歸納為國家初始化、殖民地同化、帝國競爭、國家匯聚四個流程。

1.1 國家初始化

定義初始國家為：

與遺傳算法每一個向量代表一個染色體不同的是，數(shù)列中的每一維代表國家的一個特征。

國家的勢力值由所求的函數(shù)值來表示，即：

算法開始時，隨機產生Npop個初始國家，并根據(jù)勢力大小劃分為兩種類型：勢力最大的前Nimp個國家為宗主國，其余的為殖民地國家，按照下列流程，根據(jù)宗主國的勢力來劃分殖民地的歸屬國。

1）根據(jù)各個帝國對應的函數(shù)值cn，計算帝國主義國家的歸一化勢力值Cn：

2）計算歸一化勢力的相對值Pn，以此得出每個帝國占有殖民地的初始數(shù)量NCn：

其中：Ncol表示殖民地國家的數(shù)目；round{}為四舍五入取整函數(shù)。

3）將所有殖民地國家隨機分配到各宗主國，組成初始的Nimp個帝國。

圖1 帝國競爭算法流程Fig.1 Fowchart of ICA

1.2 殖民地同化

宗主國為了便于管轄其擁有的殖民地國家，需要在政治、經濟、文化等各方面進行殖民同化，算法通過殖民地向宗主國移動來表示，其移動過程如圖2所示。

其中：x表示移動距離；d表示殖民地和宗主國間的距離；β為移動參數(shù)，取值大于1 使殖民地國家能從前后方向朝宗主國靠近；為了擴大搜索范圍，加入一個隨機的角度偏移參數(shù)θ，其中γ值一般為π4。

圖2 殖民地移動過程Fig.2 Colony moving process

在同化過程中，如果移動后某個殖民地勢力大于其宗主國，則殖民地和宗主國互換位置，帝國中的其他殖民地向新宗主國的位置移動。這個過程確保了宗主國的位置在尋優(yōu)過程中始終保持相對最優(yōu)。

1.3 帝國競爭

所有宗主國都想要占領其他宗主國的殖民地以增強帝國的勢力，這種競爭機制使強大的帝國更加強大，弱小的帝國將逐漸衰落，直至消亡。原始ICA 選取最弱帝國中的最弱殖民地作為帝國競爭的對象，所有帝國都有機會占有這個殖民地國家，且帝國勢力越大，占有的概率越大。

帝國勢力值TCn的計算方法如下：

其中：Cost(imperialistn) 為宗主國的歸一化勢力值；Cost(colonies)為帝國所轄殖民地的歸一化勢力值；mean{}為均值函數(shù)；ξ表示殖民地占帝國勢力的權重值。可以看出，帝國總勢力值為宗主國及其所轄殖民地的勢力值之和。

1.4 國家匯聚

競爭過程中，勢力較弱的帝國因失去殖民地而越發(fā)弱小，直至所有殖民地被其他帝國所占有，則該帝國滅亡。

經過多次迭代，帝國相繼滅亡，在理想狀態(tài)下，最后僅留存唯一一個統(tǒng)轄所有殖民地的國家。此時，所有國家都匯聚于一點，宗主國和殖民地的勢力值完全相同，算法結束。

2 受春秋戰(zhàn)國史實啟發(fā)的帝國競爭改進算法

2.1 春秋戰(zhàn)國歷史背景

春秋戰(zhàn)國時期（公元前770 年—公元前221 年）又稱東周時期。周朝初期，周王朝把宗室和功臣分封到各個戰(zhàn)略要地或王室周圍，以達到屏藩王室和開疆拓土的職責，從而形成了上千之多的諸侯國。春秋初期，平王東遷洛陽，周室開始衰微，中原各國也因社會經濟條件不同，國家間爭奪霸主的局面逐漸顯現(xiàn)。大國依靠強大的政治軍事力量，不斷侵吞兼并小國，強化勢力范圍；小國也通過變革、合并等方式以期獲得一定的生存空間。經過二三百年，至春秋后期，僅剩下幾十個較大的諸侯國。到戰(zhàn)國時期，形成七雄爭霸的格局，直至秦滅六國，統(tǒng)一天下。

在這段歷史時期，一種奇特的外交策略應運而生——“合縱連橫”。即在國家斗爭過程中，較弱的國家為了生存，互相聯(lián)合借以抵抗強大國家的侵襲。抵抗一經失敗，又紛紛投靠強國以圖自保，形成了“合眾弱以攻一強”的“合縱”策略及“事一強以攻眾弱”的“連橫”策略。

2.2 改進的帝國競爭算法

ICA 模擬帝國競爭機制，通過非最優(yōu)解向較優(yōu)解靠近、較優(yōu)解的位置更新、競爭匯聚等實現(xiàn)尋優(yōu)能力。SAICA 在保留ICA核心思想基礎上，提出了三種改進措施，具體步驟如下：

1）初始化設置，包括初始國家數(shù)量Npop、帝國數(shù)量Nimp、殖民地數(shù)量Ncol、移動參數(shù)值β、迭代次數(shù)。

2）隨機產生初始國家，按照歸一化勢力值區(qū)分強國和弱國，強國直接保留，弱國聯(lián)合產生新的國家。新國家勢力值的大小將決定其取代已有強國或被淘汰，最后留存的國家進入帝國競爭。

3）由勢力最強的Nimp個國家擔任宗主國分別組成帝國，并占有相應比例的殖民地。帝國內部的每個殖民地各特征向量分別向宗主國對應的特征向量移動靠近，移動過程中如果殖民地勢力值大于宗主國，則取而代之，其他殖民地向新的宗主國移動。

4）計算帝國總歸一化勢力值，最弱帝國的最弱殖民地將被其他帝國占有，占有概率與帝國勢力成正比。殖民地為零的帝國將淘汰滅亡。

5）連續(xù)出現(xiàn)相同最優(yōu)值則判斷是否陷入局部最優(yōu)，根據(jù)設定的跳出方案擺脫困境。

6）反復迭代，直至達到設定的最大迭代次數(shù)。

改進算法的流程如圖3所示。

圖3 SAICA流程Fig.3 Flowchart of SAICA

2.2.1 改善初始國家產生機制

根據(jù)ICA 的原理分析，初始國家隨機產生導致難以保證種群的優(yōu)質性和穩(wěn)定性。本文借鑒春秋戰(zhàn)國時期諸侯國競爭淘汰的歷史情況，嘗試一種新的初始國家產生機制，具體流程如圖4所示。

圖4 初始化國家流程Fig.4 Flowchart of country initialization

算法開始時，隨機產生較大數(shù)量的國家，一般為ICA 國家數(shù)量的2～4倍，這樣既能通過競爭篩選保留質量較好的國家，又不會對算法的復雜度及運行效率產生較大影響。其中，一部分勢力較強的國家留用，其余相對弱小國家為避免淘汰，聯(lián)合其他國家增強勢力以圖自保。具體步驟如下：

1）按照一定數(shù)量隨機選擇聯(lián)合的國家。

2）計算各國家的勢力大小，獲得權值。

3）依據(jù)權值取各個國家的位置信息組建合并成新的國家，如果新國家勢力值超過留用國家，則取而代之，否則淘汰出局。

上述競爭篩選過程增強了國家間的信息交流，保留了優(yōu)良的位置信息，形成了較好的算法初始種群。

2.2.2 改進帝國同化方式

ICA 帝國同化過程通過殖民地向宗主國整體移動實現(xiàn)，移動參數(shù)β值取2.0 確保殖民地從前后兩個方向向宗主國靠近。在現(xiàn)實世界中，殖民同化一般伴隨政治、經濟、文化等各層面滲透轉變。借鑒這一思想，將殖民地國家移動過程變更為各特征分量向宗主國對應的特征分量移動過程，如圖5所示。

各特征分量單獨移動，若移動參數(shù)值為β，則其最大的移動距離為：

其中，di(i=1，2，…，n)為殖民地各特征分量與帝國對應特征分量間的距離。為確保從正反兩面向目標靠近，β取值應大于1.0。經反復測實驗證：當β取值由1.0 逐步增大時，求解精度逐漸提升；不同的測試函數(shù)在β值取1.5～1.8 時，能夠獲得最佳的尋優(yōu)精度；β取1.8 之后，求解精度又隨β值增大而逐漸降低。因此，針對不同的目標函數(shù)，將移動參數(shù)β值限定在1.5～1.8 區(qū)間能獲得較好的效果。在實驗或實際應用中，可先進行簡單的代入測試，明確參數(shù)值。

圖5 特征分量單獨移動Fig.5 Feature components moving separately

為便于比較改進算法與原算法移動機制的區(qū)別，圖6 展示了二維平面上兩種算法的搜索范圍差異。ICA 的搜索范圍是以2d為半徑的扇形，改進算法則是以各個分量的最大移動范圍為邊構成的矩形。一方面，各特征分量單獨移動增強了靈活性和隨機性，開發(fā)能力更強；另一方面，矩形搜索范圍相對較小，改善了多個目標靠近時搜索區(qū)域的重疊與覆蓋問題（見圖7），效率更高。

圖6 搜索范圍對比Fig.6 Search scope comparison

2.2.3 增加跳出局部最優(yōu)的策略

針對原ICA 的“早熟”問題，提出了一種跳出局部最優(yōu)的策略：如果連續(xù)多次出現(xiàn)相同的最優(yōu)值，則判定陷入局部最優(yōu)，此時，宗主國按照選定的方案跳出局部最優(yōu)。

跳出局部最優(yōu)的方案有多種，本文給出了三種方案并進行測試：一是取各宗主國的算術平均值作為新的移動目標點，本文記為SAICA-Ⅰ；二是按照各個宗主國的勢力取加權平均值作為新的移動目標點，本文記為SAICA-Ⅱ；三是宗主國自身一定比例的位置信息隨機發(fā)生改變，本文將這一比例設定為10%，記為SAICA-Ⅲ。前兩種方案構建的新移動目標點都包含了其他宗主國的信息，增強了信息交互；第三種方案通過隨機變化跳出局部最優(yōu)，提高了種群多樣性。

圖7 搜索區(qū)域交叉和覆蓋Fig.7 Search area crossing and covering

2.3 改進算法的開發(fā)、勘探能力及二者的平衡性分析

ICA 在平衡開發(fā)和勘探能力方面有所不足，缺乏有效的信息交互，帝國的合并、覆滅使種群多樣性快速降低，高維函數(shù)適用性不強。針對上述問題，SAICA 在初始化國家階段利用競爭淘汰機制增強信息交互，保留優(yōu)勢種群；在多次迭代后種群多樣性大幅降低階段增加跳出局部最優(yōu)的機制，為種群多樣性的恢復提供了一條路徑，二者前后呼應配合。同時，同化機制的改進，增強了搜索的靈活性和效率，在不影響勘探能力的前提下，提升了開發(fā)能力。因此，總體來看，改進算法相較ICA，開發(fā)和勘探能力同時得到增強，且勘探能力提升的措施相對更多，二者的平衡性更趨于合理。

3 基準測試函數(shù)實驗對比

3.1 改進有效性驗證

為了測試SAICA 的性能，本文首先選取8 個經典標準函數(shù)進行實驗，如表1 所示，其中前兩個為單模函數(shù)，其余為多模函數(shù)。

表1 標準測試函數(shù)Tab.1 Benchmark test functions

該實驗對SAICA-Ⅰ、SAICA-Ⅱ、SAICA-Ⅲ與遺傳算法（Genetic Algorithm，GA）、粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法、原始ICA 進行對比分析。各種算法在相同的硬件條件下分別獨立運行50 次，每次運行最大迭代次數(shù)Max_Iter為1 000，統(tǒng)計計算各算法運行結果的最小值、均值及標準差，測試函數(shù)的維度分別取30、50 和100，實驗結果如表2～4所示，其中最優(yōu)結果用粗體標出。由分析可知，在30 維條件下，SAICA 對所有測試函數(shù)的尋優(yōu)能力優(yōu)于GA、PSO 和ICA；隨著維數(shù)的增加，各算法的尋優(yōu)精度均有所下降，但改進算法仍保持一定的精度優(yōu)勢。

各算法在測試函數(shù)上的收斂曲線如圖8 所示，可以看出，SAICA 的曲線陡峭，且陡峭曲線到相對水平的轉折點出現(xiàn)得比較早，說明算法收斂快，與ICA 差別不大，相較GA和PSO算法有較大優(yōu)勢。測試的8 個標準函數(shù)均能在500 次迭代內收斂至相對優(yōu)值，其中5 個能夠在100 次迭代內完成。例如Sphere、Rastrigin函數(shù)，SAICA用50次迭代就能達到GA和PSO算法1 000次迭代得到的最優(yōu)解。另外，SAICA 的收斂曲線呈現(xiàn)或多或少的起伏波動，其中Rastrigin、Michalewicz、Schwefel函數(shù)尤為明顯，這是陷入局部最優(yōu)后，跳出機制發(fā)揮了作用。

從SAICA 三種跳出局部最優(yōu)的方案對比分析可以看出，三者實驗結果差別不大，特別是單模函數(shù)CF1、CF2 由于不存在局部最優(yōu)，跳出機制不影響搜尋精度。對多模函數(shù)CF3～CF6，SAICA-Ⅲ相較前兩種方案，隨機因素的引入有利于提升種群多樣性，勘探能力更強一些，特別在求解高維函數(shù)時，可通過迭代次數(shù)的增加，提高其尋優(yōu)精度。因此，后續(xù)的實驗均采用第三種方案。

圖8 算法收斂曲線Fig.8 Algorithm convergence curves

3.2 改進性能測試

為了驗證改進算法的尋優(yōu)性能和穩(wěn)定性，選擇CEC2017中的6 個測試函數(shù)（表5），與5 個具有代表性的先進算法對比分析，分別為：策略自適應差分進化（Differential Evolution algorithm with Strategy adaptation，SaDE）算法、球形搜索進化（Spherical Evolution，SE）算法、郊狼優(yōu)化算法（Coyote Optimization Algorithm，COA）與 灰 狼 優(yōu) 化（Grey Wolf Optimizer，GWO）算法的混合算法（Hybrid COA with GWO，HCOAG）、基于精英學習策略的動態(tài)多群粒子群優(yōu)化（Dynamic Multi-Swarm Particle Swarm Optimization based on an Elite Learning Strategy，DMS-PSO-EL）算法以及基于多精英采樣和差分搜索的分布估計算法（Estimation Distribution Algorithm based on Multiple elites sampling and individuals Differential Search，EDA-M/D）。其中，SaDE 引入了自適應學習機制，根據(jù)進化的不同階段匹配向量生成策略及其控制參數(shù)；SE 在傳統(tǒng)的超立方體搜索基礎上衍生出一種球形搜索模式，并引入了進化算法；HCOAG 采用正弦交叉策略，將COA和GWO 的兩種改進算法融合運用；DMS-PSO-EL 把進化過程劃分為前后兩個階段，采用動態(tài)多群和學習策略實現(xiàn)勘探和開發(fā)能力的提升；EDA-M/D 借助多精英采樣與差分搜索的自適應協(xié)同提升算法的尋優(yōu)性能和穩(wěn)定性。這些對比算法既包含經典的進化算法、粒子群算法的改進型，又包含郊狼算法、分布估計等新型算法的優(yōu)化，涵蓋了策略調整、自適應學習、算法混合等常用的改進方案，且在仿真測試中都取得了較好的實驗結果，具有較高的代表性。

表5 中f1 為單峰函數(shù)，f4、f9 為簡單多峰函數(shù)，f12、f16 為混合函數(shù)，f29 為復合函數(shù)，所有函數(shù)均經過偏移翻轉。運行迭代次數(shù)設置為1 000，每個測試函數(shù)至少運行50 次，取運行結果與最優(yōu)解差值的算術平均值和均方差進行比較。其中，測試結果的算術平均值可以比較算法的尋優(yōu)能力，標準差可以比較算法的穩(wěn)定性。實驗結果如表6 所示，所有算法計算結果的最優(yōu)值以粗體顯示。其中SaDE、SE 的實驗數(shù)據(jù)來自文獻［20］，HCOAG 的實驗數(shù)據(jù)來自文獻［21］，DMS-PSO-EL的實驗數(shù)據(jù)來自文獻［22］、EDA-M/D 的實驗數(shù)據(jù)來自文獻［23］，符號#表示文獻作者未提供。

分析可知，SAICA 對所有測試函數(shù)的求解均值和標準差都優(yōu)于對比算法，其中，f1、f9 函數(shù)搜尋到最優(yōu)解，顯示本文算法有更好的尋優(yōu)精度和穩(wěn)定性。

表2 SAICA與GA、PSO、ICA性能對比（Max_Iter=1000，D=30）Tab.2 Performance comparison of SAICA and GA，PSO，ICA（Max_Iter=1000，D=30）

表3 SAICA與GA、PSO、ICA性能對比（Max_Iter=1000，D=50）Tab.3 Performance comparison of SAICA and GA，PSO，ICA（Max_Iter=1000，D=50）

表4 SAICA與GA、PSO、ICA性能對比（Max_Iter=1000，D=100）Tab.4 Performance comparison of SAICA and GA，PSO，ICA（Max_Iter=1000，D=100）

表5 CEC2017測試函數(shù)Tab.5 CEC2017 test functions

表6 SAICA與其他先進算法性能對比（D=30）Tab.6 Performance comparison between SAICA and other advanced algorithms（D=30）

3.3 相關性檢驗

為了判斷SAICA 與ICA 在尋優(yōu)性能上是否存在顯著性差異及各種改進措施的貢獻度，采用Kendall相關系數(shù)法對算法的計算結果進行顯著性檢驗。選取16 個經典測試函數(shù)，分別用ICA、SAICA 及SAICA 的三種改進措施（依次表示為SAICAA、SAICA-B、SAICA-C）進行實驗，30次實驗結果的均值如表7所示。

用IBM SPSS Statistics 22.0 版本對以上數(shù)據(jù)進行Kendall相關分析，結果如表8 所示。分析可知：SAICA 和ICA 之間的相關系數(shù)值為0.100，接近于0，且顯著性p值為0.589＞0.05，表明SAICA 和ICA 之間沒有相關關系，即SAICA 和ICA 在求解性能上存在顯著差異性。SAICA 和SAICA-B 之間的相關系數(shù)值為0.783，且呈現(xiàn)接近于0 的顯著性，表明SAICA 和SAICA-B 之間有著顯著的正相關關系，即第二種改進措施發(fā)揮的作用最大。SAICA 和SAICA-A、SAICA-C 之間的相關系數(shù)值分別為0.017、0.126，從分析結果上看沒有相關性，但實驗數(shù)據(jù)顯示SAICA 的求解精度高于僅加入一種改進措施的SAICA-B，表明另外兩種改進措施能發(fā)揮一定的輔助作用。

表7 ICA、SAICA及SAICA三種改進措施的實驗結果Tab.7 Experimental results of ICA，SAICA and three improvement measures of SAICA

表8 Kendall相關分析結果Tab.8 Kendall correlation analysis result

4 結語

本文在ICA 框架上，基于春秋戰(zhàn)國史實，引入“合縱連橫”初始化策略、分量移動同化機制、自更新跳出局部最優(yōu)方案，對原算法進行改進優(yōu)化。8 個國際通用標準函數(shù)和CEC2017測試函數(shù)實驗比較結果表明，本文提出的SAICA 在提高求解精度和求解效率上具備一定優(yōu)勢，且方法簡單、復雜度低，對解決現(xiàn)實尋優(yōu)問題有實際意義。經Kendall 相關系數(shù)分析可知，改進算法與原算法具有顯著差異性。同時，在實驗過程中也發(fā)現(xiàn)，SAICA 存在對個別高維函數(shù)尋優(yōu)準確度提升不高、跳出局部最優(yōu)后仍然無法尋得全局最優(yōu)解等問題。下一步，將在本文研究基礎上，進一步優(yōu)化算法，尋求改進跳出局部最優(yōu)的策略，提升對高維函數(shù)的尋優(yōu)性能和覆蓋面，并在解決實際問題中加以研究應用。