基于殖民地位置信息的自适应帝国主义竞争算法

刘阿建+梁凤梅

摘 要： 在元启发式算法中，问题优化的质量取决于算法参数的精准设定，而参数的设定通常没有一个确定的标准，重复实验又耗时耗力。偏离角度是帝国主义竞争算法（ICA）中的一个重要参数，盲目选取可能会导致算法陷入局部最优解，出现早熟收敛现象。为了克服该缺陷，提出一种基于殖民地位置信息概率密度函数的自适应帝国主义竞争算法。在帝国主义者同化殖民地过程中，根据殖民地密度函数动态地调整其向帝国主义者运动的偏离角度，提高殖民地脱离局部最优解探寻全局最优解的能力。另一方面，帝国主义者通过及时掠取殖民地位置中的有用信息降低自己的成本函数，延伸了原算法中殖民地与帝国主义者位置互换的步骤，加快了算法的收敛速度。在一系列的基准函数测试中，所提算法在收敛速度和优化性能上均优于原ICA和另外几种经典的遗传算法。

关键词： 帝国主义竞争算法； 同化政策； 概率密度模型； 偏离角度； 殖民地位置； 全局优化

中图分类号： TN911?34； TP391.4 文献标识码： A 文章编号： 1004?373X（2018）02?0124?06

Abstract： In the meta?heuristic algorithm， the quality of problem optimization depends on the setting precision of algorithm parameters， but there is no definitive standard for parameter setting， and repeated trials consume time and strength. Deviation angle is an important parameter in imperialist competitive algorithm （ICA）， and blind selection tends to make the algorithm trapped into local optimal solution， resulting in early convergence. To overcome this defect， an adaptive imperialist competitive algorithm based on the probability density function of colony location information is proposed. In the colony assimilation process of imperialists， the deviation angle that the colony moves to the imperialist is dynamically adjusted according to the density function of the colony so as to improve the colony′s capability of separating from the local optimal solution and seeking for the global optimal solution. The imperialists reduce their cost functions by timely capturing useful colony location information， which extends the procedures of location interchange between colonies and imperialists in the original algorithm， and speeds up the convergence of the algorithm. A series of benchmark function tests were carried out. The results show that the proposed algorithm has advantage in convergence speed and optimization performance in comparison to the original ICA and several other classical genetic algorithms.

Keywords： imperialist competitive algorithm； absorption policy； probability density model； deviation angle； colony location； global optimization

0 引 言

全局优化问题已经在科学、工程、商业等领域广泛存在。目前为止，研究者们已经提出多种进化算法解决全局优化问题。进化算法的灵感来自自然进化，它通过模拟生物种群不断调整适应环境变化的过程来探寻全局最优解，主流的进化算法如下所述。第一次由Holland提出的遗传算法（GA）并由Goldberg研究与推广，然而该算法由于其在解决大规模问题时计算复杂度较高而使用受限。粒子群优化算法（PSO）[1]由Eberhart和Kennedy第一次提出，是一个典型的基于种群的进化算法，灵感来自鸟和鱼捕食的行为，该算法中每个个体代表一个问题的解决方案，并且根据自身的位置和最优同伴的位置不断调整自己的飞行速度，形成群体寻优的正反馈机制，最终寻找到问题的最优解。算法规则简单、收敛速度快使得其在工程上广泛应用，但是容易产生早熟收敛、局部寻优能差。灵感来自蚂蚁爬行的蚁群算法（ACO）是一个概率论法[2]，Mohan和Baskaran研究了蚁群算法在工程领域中的大量应用，取得了理想的效果[3]。Geem等人首先提出的和聲搜索算法（HS）也是一种新的种群优化算法[4]，它模拟音乐寻找更好和谐状态的过程，相比于其他算法不仅计算能力高，而且内存要求小。大规模邻域搜索（VLNS）是基于观察的寻找大规模邻域内高质量的局部最优解，因此全局VLNS得到的结果更好，该算法已经在很多NP优化问题中广泛应用[5]。Atashpaz?Gargari和Lucas首先提出帝国主义竞争算法（ICA）[6]，该算法是由模拟生物进化过渡到模拟社会行为，灵感来自帝国主义者侵占殖民地并相互竞争的行为。它有传统种群优化算法无法比拟的优点，不需要梯度函数、强大的局部搜索能力、允许所有的帝国相互竞争的并行进化机制，已经广泛应用在各个领域的问题优化中[7?9]。但是该算法存在缺陷，第一是同化过程中偏离角度需要人为设定，盲目选择可能会导致算法陷入局部最优；第二是对于高维的问题优化收敛速度慢。针对这两个问题，研究者们已经进行了多种改进，Bahrami等人利用混沌映射理论确定殖民地被同化过程中的偏离角度[10]，提高了原算法的全局搜索能力，有效地避免了算法陷入局部最优解的缺陷，但是需要事先确定混沌映射函数；Zhang等人通过殖民地移动后随机地选择一部分更新他们的位置来避免算法陷入局部最优解[11]；Lin等人提出了一种扰动的ICA算法并用人造的帝国主义者去替代迭代中权利最小的帝国主义者从而提高帝国之间的信息交互[12]。以上算法的改进，在一定程度上提高了原算法全局搜索的能力，但是共同的缺陷是人为干涉算法的进行，AA Khaled等人提出一种模糊自适应帝国主义竞争算法（FAICA）[13?14]，在搜寻过程中使用一个模糊控制器动态地调整偏离角度；Wang Shuaiqun等人提出一种具有交易机制的帝国主义竞争算法[15]，将现实生活中强国与弱国的相互交易、共同进步现象引入到原算法中，实现帝国主义与殖民地之间交易有用信息来相互提升的机制，有效地提高了算法的收敛速度。endprint

本文提出一种基于殖民地位置信息的自适应帝国主义竞争算法。在每次殖民地向其帝国主义者移动过程中，根据其概率密度函数动态地调整偏离角度的大小，平衡局部和全局的寻优能力。其次在原算法中，帝国主义者提升自身权利仅仅通过跟殖民地互换位置来实现，限制了收敛速度，本文外延该步骤，根据殖民地的位置信息及时更新帝国主义者的位置，不只是殖民地成本函数低于帝国主义者时才更新帝国主义者位置，这样可以有效地提高原算法的收敛速度。最后通过对比实验部分论证本文算法在收敛速度和全局寻优能力上的优越性。

1 帝国主义竞争算法

1.1 初始化帝国

帝国主义竞争算法以一个初始随机种群开始，每个个体为一个国家，对于一个维的优化问题，每个国家表示为一个的向量，其中每一维代表国家的一个社会属性，如下：

且每个国家有自己的成本函数，第个帝国主义者的成本函数定义为：

在开始算法之前，先生成一个数量为个国家的局面并计算每个国家的成本函数，其中成本函数与权力成反比，选择最有权利的个国家为帝国主义者，剩下的个国家称为殖民地，按帝国主义者权利大小给他们分配殖民地，标准化帝国主义者的成本函数，如下：

则第个帝国主义者标准化后的权利表示为：

则初始化后给第个帝国主义者分配的殖民地数为：

初始化帝国如图1所示，其中一种颜色代表一个帝国，五角星为帝国的帝国主义者，大小代表权利的大小，一共有8个帝国，红色五角星帝国最大，殖民地数量最多。

1.2 帝国主义者同化过程

初始帝国形成后，殖民地开始向其帝国主义者移动，该过程为帝国主义者同化其殖民地，如图2所示，殖民地沿方向向其殖民地移动，为某一均匀分布上的随机变量，定义为：

式中，为殖民地与其帝国主义者之间的距离。

在同化过程中，引入偏离角度可以提高殖民地向其帝国主义者运动时的全局搜索能力，避免陷入局部最优解，且平衡着算法在空间搜索上的强度和广度，原算法[6]中定义为：

1.3 殖民地革命过程

与GA算法相似，ICA算法也允许殖民地突变自己的社会属性，称为革命过程，该过程可以有效地防止算法在早期迭代中陷入局部最优解，且随着迭代次数的增加，突变率逐渐降低，其中革命率为，下降因子为，突变后的殖民地由新生成的国家代替。

1.4 殖民地与其帝国主义者互换位置

同化和革命后，重新计算每个国家的成本函数，如果有任何殖民地成本函数小于其帝国主义者，则互换其位置。

1.5 计算帝国的总成本函数

帝国的总权利大小与其成本函数成反比，第个帝国总成本函数由帝国主义者和殖民地的成本函数计算，如下：

式中，为殖民地总成本函数均值对其帝国主义成本函数的影响因子，原算法中取值为0.1。

1.6 帝国主义者竞争

ICA中最核心的步骤为帝国主义者的相互竞争，每个帝国主义者都设法侵占其他帝国的殖民地来提升自身的权利，每次迭代中，最弱帝国中的最弱殖民地会被侵占，为了确定侵占原则，根据每个帝国主义者的权利分别计算其侵占该殖民地的概率，首先根据式（9）计算第个帝国标准化后的成本函数，再计算第个帝国主义者的侵占概率，如下：

因为该殖民地最终不一定被侵占概率大的帝国主义者侵占，所以将侵占概率生成一个的向量，定义为：

再生成一个与同型矩阵，定義如下：

则在此选择向量中元素最大值的索引为侵占该殖民地的帝国主义者：

1.7 瓦解没有殖民地的帝国主义者

随着竞争的进行，最终最弱帝国主义者的殖民地会被侵占完，它也沦为其他帝国的殖民地，最后的状态为只有一个帝国主义者存在，其余国家均为其殖民地。该帝国主义者的位置即为算法的最优解，部分过程见图3。

2 自适应帝国主义竞争算法

与其他GA算法一样，ICA在问题搜索空间缺乏一定的全局搜索能力，可能会远离全局最优解而陷入局部最优解，出现早熟收敛现象。本文提出一种基于殖民地位置信息动态平衡殖民能力和搜索能力的自适应帝国主义竞争算法，在原ICA的同化过程中，殖民地向其帝国主义者移动的偏离角度是一个随机变量，一旦确定将不再变化，因此陷入局部最优解时逃脱不出来，这是造成早熟收敛的主要原因。为了解决该问题，定义一个自适应的偏离角度，在同化过程中动态地调整自己的大小，并根据殖民地位置信息及时更新帝国主义者的位置加快收敛速度。

2.1 自适应偏离角度

本文中提取当前殖民地位置的统计信息来自适应调整，具体做法如下：

1） 建立当前殖民地位置信息的高斯概率模型，并由每个国家的边缘概率分布乘积得到联合概率分布，如下：

2） 在每次迭代中，由式（14）计算国家的概率密度，计算值如下：

2.2 更新帝国主义者位置

在原ICA算法中，只有当殖民地成本函数小于其帝国主义者时，通过互换位置来提高帝国主义者的权利，然而现实生活中，虽然弱国的综合实力小，但不一定任何方面都比强国弱，同理，当弱国的综合实力大于强国后，也不一定任何方面都比强国强。基于此，对于一个维的优化问题，应该考虑到每一维，当殖民地成本函数高于帝国主义者时，应该检测是否有哪一维优于帝国主义者，同理，当殖民地恒本函数低于帝国主义者时，应该保留优于殖民地的信息，而不是完全被殖民地代替。所以根据殖民地的当前位置信息及时更新帝国主义者可以加快收敛速度，外延了原算法中的互换位置这一步。根据上述原理，为了将更新殖民地位置融入原算法中，伪代码如下：

1） Input empires；

2） for i = 1 ： numel（empires）

3） for j = 1 ： numel（empires（i）.colonies）endprint

4） for k = 1 ：

5） if cost（empires（i）.imperialist） <

cost（empires（i）.colonies（j））

6） if cost（empires（i）.colonies（j）（k）） <

cost（empires（i）.imperialist（k））

7） empires（i）.imperialist（k） =

empires（i）.colonies（j）（k）；

8） end if

9） else

10） if cost（empires（i）.imperialist（k）） <

cost（empires（i）.colonies（j）（k））

11） empires（i）.colonies（j）（k） =

empires（i）.imperialist（k）；

12） end if

13） end

14） end

15） end

16） end

2.3 自适应帝国主义竞争算法流程

本文算法流程图如图4所示。

3 分析对比实验结果

为了验证本文算法在收敛速度和性能的优越性，采用表1给出4种常用的基准函数来测试，图5为4种基准函数的三维图（其中优化问题的维数为2），可知，每个基准函数都有局部最小值和全局最小值。在问题优化方面，采用中等大小为30的维度来进行实验，且每次实验重复进行10次取基准函数值的平均值，结果如表2所示，算法的停止条件设定为达到最大迭代次数，本文取1 000次。ICA和本文算法参数设置为，，，，PSO算法中，，，种群数为100，突变和交叉率分别为0.3和0.95。

图6为三种算法求4种基准函数的全局最小值，其中行坐标表示迭代次数，纵坐标为成本函数值。

图6a）中，三种算法得到的全局最小值相差不大，但本文算法在迭代340次左右达到全局最小值，收敛速度明显优于另外两种；图6b）中，传统ICA与PSO算法相继陷入局部最小值，虽然传统ICA算法有较强的局部搜索能力，取到优于PSO算法的最优解，但本文通过设置自适应偏离角度的ICA算法在跳出局部最优解方面明显优于另外两种；图6c）中，不仅体现出ICA算法在全局最优解方面优于PSO算法，更能看出本文算法通过及时更新帝国主义者位置在收敛速度方面获得的优势；图6d）中，传统ICA和PSO算法几乎陷进了同一个局部最小值，但本文算法没有陷入该局部最小值且在迭代次数为300和600左右时分别跳出三个局部最小值达到全局最小值。

4 结 语

本文提出一种基于殖民地位置信息的自适应帝国主义竞争算法，首先根据殖民地的概率密度函数动态地调整殖民地向其帝国主义者运动的偏离角度，有效地提高了全局搜索能力，避免了算法陷入局部最小值，其次根据殖民地的当前位置信息及时更新帝国主义者位置，可以加快收敛速度。实验结果表明，本文算法切实可行，但殖民地位置的概率密度函数选取对算法性能的影响将是今后探索的方向。

参考文献

[1] EBERHART R， KENNEDY J. A new optimizer using particle swarm theory [C]// International Symposium on Micro Machine and Human Science. Nagoya： IEEE， 2002： 39?43.

[2] DORIGO M， MANIEZZO V， COLORNI A. Positive feedback as a search strategy [J/OL]. [2017?07?02]. https：//wenku.baidu.com/view/3a6125e881c758f5f61f67b3.html.

[3] MOHAN B C， BASKARAN R. A survey： ant colony optimization based recent research and implementation on several engineering domain [J]. Expert systems with applications， 2012， 39（4）： 4618?4627.

[4] MAHDAVI M， FESANGHARY M， DAMANGIR E. An improved harmony search algorithm for solving optimization problems [J]. Applied mathematics & computation， 2007， 188（2）： 1567?1579.

[5] VADLAMANI S， HOSSEINI S. A novel heuristic approach for solving aircraft landing problem with single runway [J]. Journal of air transport management， 2014， 40： 144?148.

[6] ATASHPAZ?GARGARI E， LUCAS C. Imperialist competitive algorithm： an algorithm for optimization inspired by imperialistic competitive [C]// IEEE Congress on Evolutionary Computation， 2008， 21： 4661?4667.endprint

[7] CHEN C H， CHEN W H. United?based imperialist competitive algorithm for compensatory neural fuzzy systems [J]. IEEE transactions on systems man & cybernetics systems， 2016， 9（46）： 1?10.

[8] TALATAHARI S， RAHBARI N M. Enriched imperialist competitive algorithm for system identification of magneto?rheological dampers [J]. Mechanical systems & signal processing， 2015， 62： 506?516.

[9] MAHMOODABADI Z， ABADEH M S. CADICA： Diagnosis of coronary artery disease using the imperialist competitive algorithm [J]. Journal of computing science & engineering， 2014， 8（2）： 87?93.

[10] BAHRAMI H， FAEZ K， ABDECHIRI M. Imperialist competitive algorithm using chaos theory for optimization （CICA） [C]// Proceedings of International Conference on Computer Modelling and Simulation. Washington： IEEE， 2010： 98?103.

[11] ZHANG Y， WANG Y， PENG C. Improved imperialist competitive algorithm for constrained optimization [C]// Proceedings of International Forum on Computer Science?Technology and Applications. Washington： IEEE， 2009， 1： 204?207.

[12] LIN J L， CHO C W， CHUAN H C. Imperialist competitive algorithms with perturbed moves for global optimization [J]. Applied mechanics & materials， 2013， 284/287： 3135?3139.

[13] KHALED A A， HOSSEINI S. Fuzzy adaptive imperialist competitive algorithm for global optimization [J]. Neural computing & applications， 2015， 26（4）： 813?825.

[14] ARISH S， AMIRI A， NOORI K. FICA： fuzzy imperialist competitive algorithm [J]. Journal of Zhejiang University， 2014， 15（5）： 363?371.

[15] WANG S， AORIGELE， LUO J， et al. Imperialist competitive algorithm with trading mechanism for optimization [C]// Proceedings of International Conference on Computational Intelligence， Networked Systems and Their Applications. [S.l.]： Springer Berlin Heidelberg， 2014， 462： 87?98.endprint