多策略改進的混合帝國競爭算法

孟洪潮

摘要：為了克服帝國競爭算法初始帝國分布不均及易早熟等缺陷，提出一種多策略改進的混合帝國競爭算法。通過拉丁超立方抽樣改善由于隨機產生的帝國在搜索空間分布不均的狀況，以達到擴大算法搜索范圍的目的。針對算法后期競爭過程中帝國多樣性降低過快而導致易早熟，引入人工蜂群算法中引領蜂與跟隨蜂之間的信息反饋機制，形成混合帝國競爭算法。多個測試函數的驗證結果表明，改進算法提高了算法尋優精度和全局搜索效率。

Abstract： In order to overcome the defects of the initial Empire distribution and prematurity in Imperial competition algorithm， a multi strategy improved hybrid Empire competition algorithm is proposed. The purpose of expanding the search scope of the algorithm is to be expanded by the Latin hypercube sampling because the random empires are distributed unevenly in the search space. Aiming at the premature decline of the diversity of the Empire in the later stage of the algorithm， the information feedback mechanism between the bee and the bee was introduced into the artificial bee colony algorithm， and the mixed imperialism competition algorithm was formed. The verification results of multiple test functions show that the improved algorithm improves the precision of optimization and the efficiency of global search.

關鍵詞： 帝國競爭算法；人工蜂群算法；拉丁超立方抽樣；信息反饋

Key words： ICA；ABC；LHS；information feedback

中圖分類號：TP18 文獻標識碼：A 文章編號：1006-4311（2018）14-0193-03

0 引言

Atashpaz-Gargari和Lucas[1]于2007年從帝國對殖民地的掠奪和帝國之間的競爭及最終稱霸的過程，提出帝國競爭算法，至今已在多個領域成功應用，如調度問題[2]、可靠性分析[3]和圖像識別[4]等。相較于遺傳算法、粒子群算法等群體智能算法，ICA具有較快的收斂速度及比較優越的全局搜索能力[5]，但是算法缺陷依舊明顯，包括算法初期形成帝國過程中在搜索空間分布不均，后期帝國多樣性降低致使出現“早熟”現象等。

針對上述問題，研究人員提出了多種改進方式，Niknam等[6]在ICA中加入變異因子，提出MICA；郭婉青等[7]提出兩種改進策略：一是應用微分進化改進原始算法，稱為ICADE應用；二是克隆進化改進算法后期帝國競爭過程，增強帝國之間信息交互，稱為ICACE。翟云峰等[8]引入混沌原理和隨機模擬技術改進帝國競爭算法；張鑫龍等人[9]在將ICA離散化，并在算法各個階段提出有效的改進。其他改進：如混合算法，ICA-PSO算法[10]。本文在學習以上研究中有效的改進方法的基礎上，進一步深入研究了該算法的基本原理，針對原始算法初期存種群不均勻，聚集移動階段無自適應性的移動步長，同時算法后期帝國資源過于集中導致種群多樣性等問題，提出一種改進的混合帝國競爭算法：采用拉丁超立方抽樣初始帝國在搜索空間分布不均的狀況；針對算法后期“早熟”，引入人工蜂群算法中引領蜂與跟隨蜂之間的信息反饋機制，達到有效的信息交互，增加帝國的多樣性。

仿真試驗結果表明，改進的混合混合帝國競爭算法的性能明顯優于原始算法，能有效避免算法早熟，達到提高了算法的尋優精度和收斂速度的目的。

1 帝國競爭算法

ICA是對帝國主義國家殖民擴張，并逐漸占有優勢資源，逐步吞并其他帝國而最終稱霸過程的模擬，在算法中個體為國家，優化中以向量或實數列表示。

1.2 殖民地向中心國移動

移動步長是y，是一個隨機數且y～U（0，β×d），其中d是殖民地與中心國間的距離，并設定β>1。引入角度θ，其值服從θ～U（-r，r）使一定數量的殖民地沿著其他方向移動，以增大搜索空間。

1.3 置換位置

上述移動過程中，殖民地在新位置的勢力有可能超過中心國，此時殖民地取代中心國成為該帝國新的中心。

1.4 帝國之間競爭

總勢力的定義如下：

求解高維問題時，算法初期國家初始化過程中，空間形成的國家分布是隨機的，無法有效地均勻分布在搜索空間中，因此為了降低甚至消除因國家（帝國）分布不均對算法搜索范圍造成的不利影響，本文采用拉丁超立方抽樣方法[11]產生初始國家。針對算法后期，帝國多樣性下降過快，采用ABC算法中引導蜂和跟隨蜂之間交流的信息反饋機制，對算法進行改進，形成新的混合帝國競爭算法。

2 混合帝國競爭算法

2.1 拉丁超立方抽樣

Mckay等人[12 ]于1979年提出的一種抽樣技術——拉丁超立方體抽樣方法（LHS）。目標是使試驗中選取的試驗點能夠均勻地散布在空間中，該方法具有以下特點：

①試驗點均勻地分布于搜索空間；②試驗點具有隨機性；③希望試驗點總均值提供一個無偏均值，且方差較小；④具有穩定性。

拉丁超立方體抽樣方法的上述特點能夠有效地應用于ICA算法初始國家形成的過程，因此本文采用拉丁超立方體抽樣方法進行國家初始化構造。

2.2 改進國家初始化構造

2.3 后期多樣性改進

Karaboga提出人工蜂群優化算法[14]，該算法控制參數教少、易于求解，在函數優化問題表現突出。ABC算法模擬了蜂群個體在覓食過程中的分工以及個體間的信息共享機制，蜂群按照分工的不同可以分為引領蜂、跟隨蜂和偵察蜂。引領蜂在食物源附近進行鄰域搜索，并將食物源的信息反饋給跟隨蜂，跟隨蜂根據收到的信息，挑選較優的食物源繼續開采。

本文中主要利用算法中信息反饋機制改進ICA后期競爭階段帝國種類急劇減少，算法易早熟的狀況。ABC算法中引領蜂根據貪婪選擇策略確定新的食物源，并向跟隨蜂傳遞新食物源信息，跟隨蜂根據傳遞的信息通過下列公式選擇食物源：

2.4 混合ICA執行步驟

Step1：國家初始化，采用？準p準則優化拉丁超立方體抽樣方法改造國家初始化，使之能均勻分布在解空間中；

Step2：殖民地向中心國移動；

Step3：殖民地在新位置的勢力可能超過其中心國，此時殖民地取代它；

Step4：帝國競爭，按式（7）計算各帝國總勢力，依據式（9）計算此時殖民地獨立概率，增大后期的帝國多樣性；

Step5：重復上述步驟，經過數次迭代，弱小帝國逐漸消亡，算法結束。流程如圖2所示。

3 仿真實驗結果與分析

為驗證混合算法是否有效，選擇5個標準測試函數測試改進算法的性能。選擇不同類型的標準測試函數（包括單峰和多峰函數），如表1所示。這些函數的最小值均為0，設置測試函數的維度D=100，設計對比試驗，本文混合ICA與ICA以及OICA[15]的求解結果進行對比，相關對比算法的參數參照相關文獻。試驗中所有算法獨立運行50次，記錄最優結果的平均值（Mean）及標準差（Std）。本文QICA控制參數：初始國家個數N=220，宗主國（帝國）數量Nsuz=8，迭代次數MAXIER=2000。相同的試驗環境：Intel core i5-4670K處理器，4.00 GB 內存，window 7 操作系統，MATLAB2015b軟件；算法獨立運行50次所得標準測試函數最優解的平均值及標準差比較結果如表2所示。

上述圖表結果表明，對比其他2個算法的平均值，本文提出的算法更接近最優解，且標準差較小，說明所提算法具有更高的收斂精度，更高的穩定性；迭代曲線圖表明能有效的跳出局部區域，具有更好的全局搜索能力。以上結果證明改進算法在求解連續優化問題上的的有效性。

參考文獻：

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

[2]Behnamian J， Zandieh M. A discrete colonial competitive algorithm for hybrid flowshop scheduling to minimize earliness and quadratic tardiness penalties[J]. Expert Systemswith Application， 2011， 38（12）： 14490-14498.

[3]郝巖. 基于帝國競爭算法的非概率可靠性分析及優化[D]. 吉林大學， 2014.

[4]Haibin Duan， Chunfang Xu， Senqi Liu， Shan Shao. Template matching using chaotic imperialist competitive algorithm[J]. Pattern recognition letters， 2010（31）： 1868-1875.

[5]Atashpaz-Gargari E， Hashemzadeh F， Lucas C. Designing MIMO PID Controller Using Colonial Competitive Algorithm： Applied to Distillation Column Process[C]//Evolutionary Computation， 2008. CEC 2008. （IEEE World Congress on Computational Intelligence）. IEEE Congress on. IEEE， 2008： 1929-1934.

[6]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.

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

[8]翟云峰， 易國偉， 王亦，等.基于改進帝國競爭算法的微網動態經濟調度[J]. 電力科學與工程， 2015， 31（5）： 34-41.

[9]張鑫龍， 陳秀萬， 肖漢，等. 一種求解旅行商問題的新型帝國競爭算法[J]. 控制與決策， 2016， 31（4）： 586-592.

[10]Idoumghar L， Chérin N， Siarry P， et al. Hybrid ICA-PSO Algorithm for Continuous Optimization[J]. App-lied Mathematics and Computation， 2013， 219（24）： 11149-11170.

[11]陳明華，周本達，任哲.隨機化均勻設計遺傳算法[J].高校應用數學學報，2010，25（3）：279-284.

[12]Makay， M.D.， Beckman， R .J. and Conover， W.J.A comparison of three methods for selecting values of input variables in the analysis of out put from a computer code[J].Technometrics，1979（21）：239-245.

[13]劉新亮，郭波. 基于改進 ESE 算法的多目標優化試驗計方法[J]. 系統工程與電子技術，2010，32（2）：410-412.

[14]Karaboga D， Basturk B. A powerful and efficient algorithm for numerical function optimization： artificial bee colony（ABC） algorithm[J]. J of Global Optimization， 2007， 39（3）： 459-471.

[15]Arashpaz-Gargari E. Imperialist competitive algorithm（ICA）[CP/OL]. （2008-11-10） [2012-01-10]. http：//www.mathworks.c-om/matlabcentral/fileexchange/22046-imperi-alist competitive-algorithm-ica.