多策略改进的混合帝国竞争算法

孟洪潮

摘要：为了克服帝国竞争算法初始帝国分布不均及易早熟等缺陷，提出一种多策略改进的混合帝国竞争算法。通过拉丁超立方抽样改善由于随机产生的帝国在搜索空间分布不均的状况，以达到扩大算法搜索范围的目的。针对算法后期竞争过程中帝国多样性降低过快而导致易早熟，引入人工蜂群算法中引领蜂与跟随蜂之间的信息反馈机制，形成混合帝国竞争算法。多个测试函数的验证结果表明，改进算法提高了算法寻优精度和全局搜索效率。

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.