多策略改進(jìn)的混合帝國競爭算法

孟洪潮

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

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.

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

Key words： ICA；ABC；LHS；information feedback

中圖分類號：TP18 文獻(xiàn)標(biāo)識碼：A 文章編號：1006-4311（2018）14-0193-03

0 引言

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

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

仿真試驗(yàn)結(jié)果表明，改進(jìn)的混合混合帝國競爭算法的性能明顯優(yōu)于原始算法，能有效避免算法早熟，達(dá)到提高了算法的尋優(yōu)精度和收斂速度的目的。

1 帝國競爭算法

ICA是對帝國主義國家殖民擴(kuò)張，并逐漸占有優(yōu)勢資源，逐步吞并其他帝國而最終稱霸過程的模擬，在算法中個體為國家，優(yōu)化中以向量或?qū)崝?shù)列表示。

1.2 殖民地向中心國移動

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

1.3 置換位置

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

1.4 帝國之間競爭

總勢力的定義如下：

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

2 混合帝國競爭算法

2.1 拉丁超立方抽樣

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

①試驗(yàn)點(diǎn)均勻地分布于搜索空間；②試驗(yàn)點(diǎn)具有隨機(jī)性；③希望試驗(yàn)點(diǎn)總均值提供一個無偏均值，且方差較?。虎芫哂蟹€(wěn)定性。

拉丁超立方體抽樣方法的上述特點(diǎn)能夠有效地應(yīng)用于ICA算法初始國家形成的過程，因此本文采用拉丁超立方體抽樣方法進(jìn)行國家初始化構(gòu)造。

2.2 改進(jìn)國家初始化構(gòu)造

2.3 后期多樣性改進(jìn)

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

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

2.4 混合ICA執(zhí)行步驟

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

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

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

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

Step5：重復(fù)上述步驟，經(jīng)過數(shù)次迭代，弱小帝國逐漸消亡，算法結(jié)束。流程如圖2所示。

3 仿真實(shí)驗(yàn)結(jié)果與分析

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

上述圖表結(jié)果表明，對比其他2個算法的平均值，本文提出的算法更接近最優(yōu)解，且標(biāo)準(zhǔn)差較小，說明所提算法具有更高的收斂精度，更高的穩(wěn)定性；迭代曲線圖表明能有效的跳出局部區(qū)域，具有更好的全局搜索能力。以上結(jié)果證明改進(jìn)算法在求解連續(xù)優(yōu)化問題上的的有效性。

參考文獻(xiàn)：

[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]郝巖. 基于帝國競爭算法的非概率可靠性分析及優(yōu)化[D]. 吉林大學(xué)， 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ìn)化優(yōu)化[J]. 計(jì)算機(jī)科學(xué)與探索， 2014， 8（4）： 473-482.

[8]翟云峰， 易國偉， 王亦，等.基于改進(jìn)帝國競爭算法的微網(wǎng)動態(tài)經(jīng)濟(jì)調(diào)度[J]. 電力科學(xué)與工程， 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]陳明華，周本達(dá)，任哲.隨機(jī)化均勻設(shè)計(jì)遺傳算法[J].高校應(yīng)用數(shù)學(xué)學(xué)報(bào)，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]劉新亮，郭波. 基于改進(jìn) ESE 算法的多目標(biāo)優(yōu)化試驗(yàn)計(jì)方法[J]. 系統(tǒng)工程與電子技術(shù)，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.