改進型帝國競爭模型算法的研究

陳 禹，馮 翔，2，虞慧群

1.華東理工大學 信息科學與工程學院，上海 200237

2.上海交通大學 智慧城市協同創新中心，上海 200240

1 引言

1.1 背景與相關工作

帝國競爭算法（ICA）[1]是Atashpaz-Gargari和Lucas于2007年提出的基于帝國主義競爭機制的進化算法，屬于社會啟發的隨機優化搜索方法。目前，ICA已被成功應用于解決實際的優化問題[2-4]，比如社會行為的研究，機械設計，電磁學，分類問題等。如控制、數據聚類[5]、工業工程[6]、函數優化、旅行商問題[7-9]、人工神經網絡訓練[10-11]。ICA最大的問題就是帝國的數量不斷減少，這樣會導致群體的多樣性降低，對于求解最優化問題極為不利。為了克服這一缺點，相關的學者已經提出了許多改進的ICA算法，每個算法都在ICA的基礎上有了一定的改進并取得了不錯的效果，但是仍有不足。

無論是自然還是社會都有它的存在和進步的法則，人們從社會和自然中汲取靈感和行為思索進行模擬，大致分為三類：第一類是進化算法類似于基因遺傳算法，該類算法沒有能夠及時利用網絡的反饋信息，故算法的搜索速度比較慢，要得到較精確的最優解需要較多的訓練時間；第二類是基于行為的群算法，例如殖民地優化算法和粒子群算法，該類算法缺乏速度的動態調節，容易陷入局部最優，導致收斂精度低和不易收斂；第三類是建立現象的模擬模型的算法，例如根生長和颶風模型算法，該類算法不夠靈活，求得的結果的精度不夠。而本文從這三個方面在帝國競爭算法的基礎上進行了改進。

在智能算法中存在的一個問題就是個體與群體頻繁的交互，這樣會導致兩種結果，容易陷入局部最優，進而導致其他的個體容易陷入局部最優；這種強交互性的算法要求智能算法一步一步的執行，因此需要很長的運算時間，尤其是問題規模非常大的時候，所以改進的算法要能夠保持高效性。

1.2 動機與貢獻

本文的動機如下：

早期的ICA改進算法中并未對搜索的精度進行改進，而本文借鑒了以前搜索克服早熟收斂的思想以及帝國相互融合的元素，增強了樣本多樣性以及帝國之間的交互能力，主要是針對原有的帝國競爭算法（ICA）進行模型上的改進，通過基準函數的測試來檢驗改進算法的有效性和準確性。

本文的主要貢獻如下：

（1）本文建立了改進算法的數學模型來展示算法的進程的優越性。

（2）對新的思想進行了數學建模，制作模型圖，并利用代碼實現并且做了大量的實驗，對算法的有效性和優越性進行了分析。

（3）提供了原算法中缺少的理論證明，為以后的研究提供了一定的理論基礎。

2 改進的帝國競爭模型

小世界理論[12-14]描述的是你和任何一個陌生人之間所間隔的人不會超過6個。以此為基礎可以聯系到每個帝國的殖民地都可以計算出一個參數，然后通過這個參數進行殖民地的同化，保持在一個帝國的國家不只與該帝國相互聯系，還能夠與其他帝國保持交互，加強全球化的進程，增強在整個帝國網絡中的相互關聯。

具體定義如下：

在一個帝國中設置總共4個角色，分為帝國、管理者、普通殖民地和叛逃者，具體功能如下：

定義1（統治者）隨機區域中cost最小的國家。

定義2（管理者）和統治者距離最近的那個國家設置為整個帝國的管理者。

定義3（普通殖民地）特征不明顯的國家。

定義4（叛逃者）距離統治者最遠的國家。

（這里的距離都用歐氏距離來表示）

同化過程是先由管理者向著帝國主義國家移動，然后普通殖民地再向管理者移動。

叛逃者是一個帝國中忠誠度最低的一個殖民地。

該算法模擬了帝國在競爭過程中一些行為，具體行為模型如下：

行為模式1：管理者向統治者移動，由于二者距離比較近，所以移動的不是特別明顯。

行為模式2：殖民地向管理者移動。

前兩種模式的綜合圖，如圖1。

圖1 殖民地移動

行為模型3：叛逃者向統治者移動。

為了增強普通殖民地在移動過程中的目的性，引入了忠誠度的概念。

定義5忠誠度是指每個普通殖民地對他所屬帝國的忠誠的程度，忠誠度越大則表示該國家距離統治者的距離越近，反之則越遠。考慮到如果一個帝國中的殖民地也應該相互的存在競爭否則一個國家無法健康地發展下去，有競爭力的殖民地才能在競爭環境中存在，否則就要被淘汰。

在該模型中，同時應用了競爭和同化的兩個概念，每個普通殖民地在計算忠誠度時同國家的管理者競爭，而殖民地都會和其他帝國的統治者進行比較，然后使本帝國的殖民地同化，忠誠度越小的殖民地下次迭代中移動的距離也就越遠，如圖2所示。

2.1 改進的子模型1：基于忠誠度信息熵的納什均衡模型

圖2 同化與競爭的結合模型圖

通常在每個同化過程中，一個帝國總會有背離其統治的國家，在帝國成立的初期，每個帝國的統治一定是混亂的。上文中提到的叛逃者，就是一個帝國中最混亂的國家。所以在競爭機制中設立了兩種模式：當滿足競爭入口系數的要求時，則按照原算法進行競爭的行為；當不滿足競爭的要求時，就利用該模型進行競爭與博弈的行為[16]，具體解釋如下。

在競爭機制中，每次迭代時一旦發生了競爭和占領的行為都是最弱帝國中的最弱的國家（叛逃者）被其他的強帝國占領，如果不發生占領的行為則在原先基礎上進行博弈。在此忠誠度則表示它不離開這個帝國統治的概率。所以忠誠度越低，它的混亂度（信息熵）也就越高。

每個叛逃者的忠誠度信息熵計算如公式（1）：

每次博弈叛逃者都有兩種策略：

（1）向著本國統治者移動。

（2）成為其他國家的叛逃者，而其他國家的叛逃者必須別的選擇合適的帝國成為其叛逃者。

這兩種策略二選其一，目的是要達到所有帝國的叛逃者在選擇策略之后，使得所有帝國的叛逃者的忠誠度信息熵(H)最小，如公式（2）：

在選擇局部最優策略的組合時利用納什均衡的理論進行選擇。

2.2 改進的子模型2：基于差異因子的同化模型

這個改進的模型目的是要模擬網絡關系中的結點之間的關聯。這個模型是為了改善算法搜索范圍的廣度來避免算法陷入局部最優解。因為一個好的帝國競爭算法不能只通過增加國家的數量來增加搜索范圍，應該盡可能地在少量的群體中找到最優解。

在改進的子模型1中，每個普通的殖民地和管理者的連線與管理者和帝國的連線都有一個夾角，在二維群體或者三維群體中，這個夾角表示一個幾何空間上的夾角，其實對于多維函數（30）來說，這個角度的取值代表多個國家與統治者的連線向量和統治者與管理者向量的線性相關度，如果角度過小表示相關度比較大，如果過大也表示相關度過大（因為如果是180°的話說明是負相關），所以設計思路便是令相關度比較大的數據變的更具有隨機性，這一思想與協同過濾算法計算相似度的公式基本思想保持一致。所以利用公式（3）來計算差異因子：

上述的α和γ是事先設定好的閾值。該函數的圖像大致的曲線走勢，如圖3，具體的α和γ的值會在后面實驗中提到。

圖3 μj(coli)函數示意圖

3 改進的帝國競爭模型算法

設置一個排序矩陣OrderMatrix，把帝國的殖民地的位置存放進來，并且增加兩列，一列用于存放該行殖民地的忠誠度，另一列存放計算出來的忠誠率。

忠誠度計算出來以后把矩陣按照忠誠度進行降序排序，排在第一名的作為管理者，最后一名作為叛逃者；忠誠度的計算如公式（4）：

得出結果后保存到計算維度增加的第一列。這列引入了所有帝國的位置作為函數的入口，用來計算每個殖民地的忠誠率。

忠誠率的計算公式如公式（5）：

得出結果后保存到計算維度增加的第二列。

colonyi(t +1)是新一次的迭代位置，β是忠誠率的矯正系數，μ是下文中計算所得差異因子。

在殖民地的移動過程中，最先移動的是管理者，并且修改了同化系數，這樣一個管理者看起來就更像一個帝國的位置，更加區分了管理者與其他殖民地的地位差別。

然后是普通殖民地的移動，殖民地越多，他們的忠誠率也就越小，因為一個帝國中的普通殖民地的忠誠率的和等于1。所以在把忠誠率引入作為參數的時候給每個忠誠率前面乘以了一個普通殖民地的個數，這樣既可以讓每個殖民地看起來都有不同，又可以保證他們的移動是正確而且多樣性的。

同化機制算法模型：

輸入：一個帝國中殖民地的位置

輸出：迭代后殖民地新的位置

（1）把殖民地位置存儲到OrderMatrix矩陣中。

（2）把OrderMatrix增加兩列。

（3）按照公式（4）計算忠誠度，并存儲到新增加的兩列中的第一列。

（4）按照忠誠度從大到小重新排序這些殖民地。

定義第一位為管理者，最后一位為叛逃者，其余的為普通殖民地。

（5）管理者設定參數向著統治者移動，而普通殖民地則是向管理者移動。

（6）利用公式（5）把忠誠度歸一化存儲到第二列中。

（7）輸出新的殖民地位置矩陣。

3.1 改進的子模型1：基于忠誠度信息熵的納什均衡模型

該模型算法的目的就是利用最大最小公平性來尋找局部最優的納什均衡策略組合。

基于忠誠度信息熵的納什均衡模型算法流程：

輸入：所有帝國中統治者的位置及其叛逃者的位置

輸出：所有帝國中統治者的位置及更新后的叛逃者的歸屬情況和移動位置

（1）計算所有剩余叛逃者的忠誠度信息熵。

（2）選擇信息熵最大的叛逃者進行步驟（3），（4）兩種策略選擇。

（3）叛逃者向帝國統治者移動并計算移動后的忠誠度信息熵。

（4）假定該叛逃者屬于其他的帝國，計算它在其他忠誠度信息熵，并選取出最小的一個。

（5）比較步驟（3）和（4）的大小，選取小的進行決策：若第（3）步的策略小，到第（5）步；若第（4）步的策略小，到第（6）步。

（6）保存叛逃者的新位置，并移除此帝國，其余帝國成為新的輸入。

（7）交換兩個帝國中叛逃者的位置，并移除步驟（2）中叛逃者所屬帝國，其余帝國作為新的輸入。

（8）新的輸入帝國數目若大于1則返回步驟（1）；否則結束該模型算法。

3.2 改進的子模型2：基于差異因子的同化模型

在算法中定義了一個差異因子μ來表示每個向量的差異度，令求得的角度為θ，計算公式如下：

當θ<60°，μ=0。

上述函數是隨著自變量的取值的增大而單調遞增的，但是對于角度函數來說，應該是關于90°對稱的，舉個例子來說80°的差異因子應該和100°的差異因子是一樣的，當θ的取值為90°時得到的差異因子應該是最大的這里設為1。所以上述公式前面變成了乘4。所以有以下公式：

當，（對稱性）。

當θ>120°，μ=0。

上述公式中差異因子大，表示數據的搜索范圍越廣，差異因子越小則認為的更改它的值來實現樣本多樣性。

綜上得到公式（7）：

上述分段函數的圖像如圖4。

圖4 分段函數圖像

算法描述：

增加排序矩陣OrderMatrix的一列用來存放普通殖民地的差異量。

按照上述公式把差異因子歸一化。

求得計算管理者與統治者的向量和普通殖民地與管理者之間的向量。

令 μ=arccos θ，求得θ代入到公式（6）中。

計算下一次的迭代位置。

子模型2算法流程：基于差異因子的同化模型。

（1）把新位置存儲到OrderMatrix矩陣中。

（2）把OrderMatrix再增加一列。

（3）計算管理者與統治者的向量和普通殖民地與管理者之間的向量。

（4）求兩個向量的夾角，并利用公式（7）規范化。

（5）μ=tan(arccos θ)，求得 μ代入到公式（6）中。

4 改進的帝國競爭模型理論分析

4.1 算法收斂性證明

定理設A為n階方陣，則的充要條件為ρ(A)<1。該定理證明略。

定理 對任意初始向量x(0)和右端項g，由迭代式x(k+1)=Mx*+g產生的向量序列{x(k)}收斂的充要條件是 ρ(M )<1，證明略。

在改進的帝國競爭算法中的同化模型的同化公式如下：

由于a1,a2,…,a29,a30是相互獨立的，則

令a=0.99，則由2×ak<1，得K>68時，可以滿足公式（8）：

令a=0.99，則由3×ak<1，得 K>111時，可以滿足公式（8）：

令a=0.99，則由4×ak<1，得 K>137時，可以滿足公式（8）：

這三個公式的不同在于a前面的系數也就是趨緊系數β不同，下面會對這個系數做一些實驗。

上述公式中，對于：

滿足，則該向量收斂于imp。

4.2 利用最大最小公平性求最優策略

為簡單求證，假設還剩下兩個帝國，每個帝國有一個叛逃者，則剩余的策略有兩種組合：一是兩個叛逃者分別向各自統治者移動，另外一個策略就是他們兩個交換位置，這時候只需要計算兩者的忠誠度信息熵的和取最小作值的策略組合為最優策略：

假如還剩三個帝國，則總共有23-1=4種策略可供選擇，按照前文提出的算法步驟，先選擇一個信息熵最高帝國：

這個被選擇的帝國中的叛逃者有三種策略選擇，一是向著自己帝國的統治者移動，其余兩種和其他兩個帝國的統治者交換位置，分別記信息熵的變化量為?move，

若則該叛逃者向著他的統治者移動，其他兩個帝國的叛逃者按照還剩兩個帝國的時候進行決策，這時候的信息熵變成：

根據上式，顯而易見，任何其他的策略得到的H′均小于H。

若存在?exchange_i>?move，則選擇?exchange_i中最大的一個，假設是，那么他和該帝國中的叛逃者交換之后得到的忠誠度信息熵為：

根據上式，顯而易見，任何其他策略得到的H′均小于H。

5 改進的帝國競爭模型的實驗

改進算法可以比原ICA文章中提到的測試函數更快得到最優值。

5.1 比較實驗

實驗主要運用14個函數進行比較，如表1。ICA參數設置，如表2所示。得到的最優值比較如表3（DICA），數據來源于參考文獻[4，15]。隨后反復多次實驗，得到算法的平均值和標準差，如表4。

從表3和表4中以及實驗結果可以看出，該算法對于多模函數（很多極值點）的搜索做得不錯，也就是說對于算法的搜索范圍有了很大的提高，因為別的算法要通過增加國家的總個數來增加搜索廣度，而且根據每個算法的收斂函數圖像來看，大多的收斂都是在1 000次左右，說明算法的穩定性有了很大的提高。對于單模函數來講，效果稍有提升但是不是特別明顯，為接下來的研究工作指明了方向。

表1 函數范圍及最小值

5.2 差異因子參數設置實驗

在計算差異因子的模型中，每個殖民地都可以和管理者與統治者三點形成一個夾角，利用Michalewicz函數反復試驗得到6組隨機數據。

在數據中顯示每一列表示一個帝國中的普通殖民地與管理者和統治者三點之間的夾角。從數據中可以看出，求得的角度都是在60°～120°之內，如圖5所示，所以把這兩個作為模型2的兩個參數。

這樣設置參數有兩個目的：一是糾正不正常的數據，二是讓正常的數據更加隨機化來增加樣本多樣性。

圖5 殖民地夾角示意圖

在算法中，定義了一個差異因子μ來表示每個向量的差異度，令求得的角度為θ，計算公式如式（7）。

5.3 競爭入口系數設置實驗

主要研究了帝國減少（融合吞并）時的時間融合點。帝國融合成為一個統一體以后整個帝國的競爭力的值（cost）就不會再發生變化了。因為在全局最優解的搜索過程中，主要有兩個因素影響最終的結果，一個是前面迭代時候對全局搜索范圍的覆蓋廣度，一個是后面迭代時候對精度的搜索。對于一個好的極值搜索迭代算法，應該在最初的時候能夠遍歷所有的搜索的范圍，但是如果唐突地去增加國家的個數會增加系統運行的負擔，所以在迭代的時候選擇讓算法自主地去選擇一個時間節點去分開廣度搜索和精度的搜索是一個不錯的想法，而帝國融合的過程時間是決定這個時間節點的關鍵因素所以對競爭吞并的迭代做了測試，如表5所示。

實驗分析（算法穩定性）：

（1）從表5中得到一個結論，最后一次的吞并發生的越晚，得到的全局最優值大致越小。但是這個算法的穩定性還不足，因為最后一次的融合的迭代時間10組數值的標準差是除了加粗字體中數值中相對較大的，所以選擇合理的控制算法的收斂時間來達到最優值的求解。

表2 參數設置

表3 函數最優值比較

表4 平均值和標準差比較

表5 帝國融合時間節點

（2）在表5中加粗的數據是標準差最大的兩組數據，并且它們的標準差和最大值減去最小值的值也比較相近，說明算法在這個階段是最不穩定的，所以在同化過程中控制這一個迭代時間段加速算法的收斂和放寬帝國融合的條件，而最后一次融合之前又嚴格了同化的條件。

（3）在實驗分析（2）中減緩了最后一次融合的時間是為了能夠找到更加好的最優值，所以又計算了融合間隔數據來確定時間點：從上述數據來看，隨著迭代次數增加，融合的間隔也就越長，最后選擇倒數第二個和倒數第三個數據作為動態的融合時間節點，也就是平均值的前50到后50的迭代范圍（650～950）來加速融合速度，也就是總迭代進度的在這個時間段內，把吞并融合的概率系數增加到0.15（原算法是0.11），在這個時間段以后又把帝國融合的概率系數減小到0.05。

如圖6，雖然到了第1 500次的時候帝國總數還沒有達到1個，但是全局最優解的結果已經要好過之前靜態的0.11。

圖6 融合概率系數為0.11的收斂圖像

6 總結與展望

本文主要研究了帝國競爭算法的優化算法以及對優化算法的實驗驗證，主要包括：（1）利用忠誠度信息熵來增進殖民地與其他國家的聯系；（2）引入了差異因子來增加搜索的多樣性；（3）設置迭代的動態時間節點控制收斂過程的參數來彌補不同階段迭代的缺陷；（4）補充了原ICA算法中沒有的理論證明；（5）進行了有效性實驗和比較實驗來驗證改進算法的可行性。

該算法屬于社會啟發的隨機優化搜索方法，目前這種算法已經被應用于多個領域，如社會行為的研究及機械設計等，希望這類算法能夠應用到更多的領域，解決更多的相關問題。

[1]Atashpaz-Gargari E，Lucas C.Imperialist competitive algorithm：An algorithm for optimization inspired by imperialistic competition[C]//Proceedings of IEEE Congress on Evolutionary Computation，Singapore，2007：4661-4667.

[2]Forouharfard S，Zandieh M.An imperialist competitive algorithm to schedule of receiving and shipping trucks in cross-docking systems[J].The International Journal of Advanced Manufacturing Technology，2010，51（9/12）：1179-1193.

[3]Bahrami H，Faez K，Abdechiri M.Imperialist competitive algorithm using chaos theory for optimization（CICA）[C]//Proceedings of the 2010 12th International Conference on Computer Modelling and Simulation（UKSim’10），Cambridge，UK，2010.Wanshington，DC，USA：IEEE Computer Society，2010：98-103.

[4]郭婉青，葉東毅.帝國競爭算法的進化優化[J].計算機科學與探索，2014，8（4）：473-482.

[5]Niknam T，Fard E T，Ehrampoosh S，et al.A new hybrid imperialist competitive algorithm on data clustering[J].Sadhana，2011，36（3）：293-315.

[6]Nasab E H，Khezri M，Khodamoradi M S，et al.An application of imperialist competitive algorithm to simulation of energy demand based on economic indicators：Evidence from iran[J].European Journal of Scientific Research，2010，43：495-506.

[7]Feng Xiang，Francis C M L，Gao Daqi.A new bio-inspired approach to the traveling salesman problem[J].Information Sciences，2013，233（6）：87-108.

[8]Yannis M，Magdalene M，Georgios D.Honey bees mating optimization algorithm for the Euclidean traveling salesman problem[J].Information Sciences，2011，181（10）：4684-4698.

[9]Dorigo M，Gambardella L M.Ant colonies for the travelling salesman problem[J].BioSystems，1997，43（2）：73-81.

[10]Taghavifar H，Mardani A，Taghavifar L.A hybridized artificial neural network and imperialist competitive algorithm optimization approach for prediction of soil compaction in soil bin facility[J].Measurement，2013，46（8）：2288-2299.

[11]高海兵，高亮，周馳，等.基于粒子群優化的神經網絡訓練算法研究[J].電子學報，2004，32（9）：1572-1574.

[12]Behnamian J，Zandieh M.A discrete colonial competitive algorithm for hybrid flow shop scheduling to minimize earliness and quadratic tardiness penalties[J].Expert Systems with Application，2011，38：14490-14498.

[13]Iamnitchi A，Ripeanu M，Santos-Neto E，et al.The small world of file sharing[J].IEEE Transactions on Parallel and Distributed Systems，2011，22（7）：1120-1134.

[14]Inaltekin H，Chiang M，Poor H V.Average message delivery time for small-world networks in the continuum limit[J].IEEE Transactions on Information Theory，2010，56（9）：4447-4470.

[15]Bahrami H，Faez K，Abdechiri M.Imperialist competitive algorithm using chaos theory for optimization（CICA）[C]//Proceedings of the 2010 12th International Conference on Computer Modelling and Simulation（UKSim）.Cambridge，UK：IEEE Computer Society Conference Publishing Service，2010：98-103.

[16]魏蛟龍.基于博弈論的網絡資源分配方法研究[D].武漢：華中科技大學，2004.