智能优化算法：帝国主义竞争算法-附代码

摘要：帝国主义竞争算法最初是由 Atashpaz-Gargari and Lucas 于 2007 年在对基于人口数量最优化算法的著作中提出。在算法中， 每一个个体都被定义为一个国家，同时，所有的国家被分类为两类，即帝国主义国家和殖民地。帝国主义国家为最初时人口数量最有优势的国家，而剩下的国家即为殖民地。每个国家的力量被用来指明它的
健康程度。在该算法的反复使用过程中，帝国之间相互竞争以获得尽可能多的殖民地为目的。更有力量的帝国有更高的可能性去占领更多的殖民地，而力量薄弱的帝国将逐渐失去他们的殖民地。当所有的殖民地都被一个帝国占有时，该算法即为结束。在连续函数优化方面帝国主义竞争算法在效率和质量方面超过遗传算法和粒子群优化算法。

1.算法原理

1.1 帝国集团的初始化

在一个$N_{VAR}$NVAR​ 维的最优化问题中，一个国家即为一个 $1*N_{VAR}$1∗NVAR​的矩阵。该矩阵定义如下:
$country = [p_1,p_2,...,p_{N_{var}}]$country=[p1​,p2​,...,pNvar​​]
此处,$P_i$Pi​为被优化的变量。这些在国家属性中的变量为浮点数。国家中的每个变量可以被理解为这个国家的社会政治属性。在算法中几时要求我们寻找到最小的成本值。每个国家的成本由变量所组成的函数$f$f决定：
$cost = f(country)=f(p_1,p_2,...,p_{N_{var}})$cost=f(country)=f(p1​,p2​,...,pNvar​​)
为了开始该最优化算法，必须初始化国家数量 $N_{country}$Ncountry​ . 我们选择 $N _{imp}$Nimp​个最优力量的国家来形成帝国集团。剩下的 $N_{col}$Ncol​个最初国家作为这些帝国集团中的殖民地。
为了形成最初的帝国集团，殖民地依据各帝国的力量情况决定。即：一个帝国集团最初拥有的殖民地数量应直接与其力量所占比例相关。为了能按比例分配殖民地，每个帝国的成本被定义为：
$C_n=c_n-max\{c_i\}$Cn​=cn​−max{ci​}
在这里，$C_n$Cn​ 为第 $n$n个帝国的成本。计算了所有帝国的成本后，帝国的相对力量定义为：
$p_n=|\frac{c_n}{\sum_{i=1}^{Nimp}}c_i|$pn​=∣∑i=1Nimp​cn​​ci​∣
最初的殖民地的分配依赖于其所属的帝国集团的力量。从而最初的殖民地分配为：
$N.C._n=round\{p_n.N_{col}\}$N.C.n​=round{pn​.Ncol​}
在这里，$N.C._n$N.C.n​ 为第 $n$n 个帝国所拥有的殖民地数量。如图 1 所示的初始化帝国集团，越大的帝国集团拥有更多的殖民地数量，同时，弱小的集团拥有较少的殖民地。在该图中，帝国 1 组成最有力量的帝国集团，于是它拥有最多的殖民地数量。

图1.初始化帝国集团：帝国拥有的殖民地越多，它所代表的五角星越大

1.2 帝国集团内部调整

为了实现吸收壮大的目的，帝国试图去吸收它们的殖民地并使其成为帝国的一部分。更准确的说，殖民地沿着坐标轴向着帝国移动。移动过程如图 2 所示。考虑一个二维最优化问题，殖民地在由文化和语言组成的坐标轴中被帝国吸收。殖民地将会不断地向帝国移动，最终将使殖民地完全被帝国吸收。

图2.殖民地向其相关帝国的移动

在图 2 中，$x$x 为一个服从均匀分布的随机数$x\sim U(0, β×d)$x∼U(0,β×d), 在这里 $β $为比 1 大的数，同时$为比1大的数，同时d$为殖民地与帝国的距离。$为殖民地与帝国的距离。b>1$将使殖民地从两边都离帝国更近。帝国对殖民地的吸收并不直接导致殖民地向帝国的移动。即是说，殖民地并不一定依照向量所示方向向帝国移动。为了更好模型化这个事实，引入一个随机的角度作为移动的方向。

革命是指在力量和组织结构的基础方面在相对短时间内发生变化。在 ICA 的术语中，革命使一个国家的社会政治特征突然产生变化。即是说，与帝国的吸收不同，殖民地是随机的在社会政治坐标轴中突然发生位置上的改变。图 2 和图 3 是在文化语言坐标轴中的革命过程。这种革命增加了该算法的搜索过程同时组织了国家形成早期的局部收敛。算法中的革命率显示的是每个殖民地随机改变它们位置的比例。一个较高的革命率会降低算法的搜索效果并降低收敛率。在我们的应用中，我们将革命率设定为 0.3. 即是指帝国集团中有 30% 的殖民地会随机改变它们的位置。

图3 一个国家社会政治特征的突然改变

1.3 交换帝国和殖民地的位置

当殖民地向帝国移动的过程中，殖民地可能会到达一个成本比帝国要低的点。在这种情况下，帝国和殖民地即交换它们的位置。而后，算法将由在新位置的帝国吸收新位置的殖民地过程继续下去。如图 4 所示为帝国和殖民地交换位置的过程。在改图中，最好的殖民地由深色表示，该殖民地比其帝国的成本要小。如图 5 所示为殖民地和帝国交换位置后的状态。

图4 交换殖民地和帝国的位置

图5 交换位置后的帝国和殖民地的状态

在殖民地和帝国向着目标最小值移动的过程中，一些帝国可能会移动到相似的位置，如果两帝国之间的位置要小于初始位置，它们将会合并为一个新的帝国集团。原帝国集团的殖民地将会成为新帝国集团的殖民地，同时新帝国的位置将由原帝国中二者之一的位置所决定。图 6 和图 7显示的合并过程。

图6 合并前的帝国集团

图7 两帝国合并后的状态

1.4 帝国集团竞争

一个帝国集团的总力量主要由它的帝国力量所决定。可是殖民地的力量也对帝国集团的力量有影响。一个帝国集团的总成本由下式所决定：
$T.C.=Cost(imprialist_n)+\xi mean\{Cost(coloniesofempire_n)\}$T.C.=Cost(imprialistn​)+ξmean{Cost(coloniesofempiren​)}
此处，$T.C.$T.C. 为第 $n$n 个帝国集团的总成本。 $ξ$ξ 为一个较小的正数。 $ξ$ξ 越大会使殖民地对帝国集团的影响越大。在大部分的情况下 $ξ$ξ 取 0.1 被认为是最好的。

每个帝国集团都试图占领并控制其他帝国集团的殖民地。帝国竞争过程中，强国将更强，弱国将更弱。帝国竞争一般先选出最弱帝国集团，并使其他帝国集团竞争去占领该集团。图 8显示帝国竞争。在这个过程中，基于各自的力量，每个集团都有占领最弱集团的可能性。从另一个方面来说，最弱国不一定确定被最强国家占领，但是越强的集团占领弱集团的可能性越大。

图8 帝国竞争：帝国越有力量，越有可能占领最弱帝国集团的殖民地

为了开始这个竞争过程，首先最弱的帝国集团的一个殖民地将被选出来，并确定每个国家占领的可能性。占领可能性$P_p$Pp​ 依据帝国集团的总力量所决定：
$N.T.C.n = T.C.n - max\{T.C.i\}$N.T.C.n=T.C.n−max{T.C.i}
此处，$T.C.n$T.C.n 和 $N.C.n$N.C.n 为第 $n$n 个帝国集团的总成本和相对成本。依据相对成本，每个帝国的占领可能性由下式决定：
$P_{pn}=|\frac{N.T.C.n}{\sum_{i=1}^{Nimp}}N.T.C.i|$Ppn​=∣∑i=1Nimp​N.T.C.n​N.T.C.i∣
为了将在帝国集团中将上述的殖民地分类，我们引入如下向量$P$P：
$P=[P_{p1},P_{p2},P_{p3},...,P_{pNimp}]$P=[Pp1​,Pp2​,Pp3​,...,PpNimp​]
向量 $R$R 是与向量 $P$P 具有相同规格的向量，其元素服从均匀分布：
$R=[r_1,r_2,...,r_{Nimp}],r1,r2,...,r_{Nimp}\sim U(0,1)$R=[r1​,r2​,...,rNimp​],r1,r2,...,rNimp​∼U(0,1)
向量 $D$D 由向量 $P$P 减去向量 $R$R 所得：
$D = P-R = [p_{p1}-r1,...,p_{p_{Nimp}}-r_{Nimp}]$D=P−R=[pp1​−r1,...,ppNimp​​−rNimp​]
向量 $D$D 中元素值最大的对应帝国集团即会占领上述的殖民地。这样选择帝国集团的过程与遗传算法中选择母类的轮盘赌过程相似。但是这里的选择方法比相关的轮盘赌过程要快。因为这个过程并不需要
计算累积分布函数，并且选择过程仅仅基于可能性的值。因此，帝国集团的选择过程可以完全替换遗传算法中的轮盘赌，并增加执行速度。上述步骤将会持续下去直至实现国家收敛并且达到成本最小的目标。不同标准可用来结束该算法。一种思想是设定最大迭代次数。或者当仅剩一个帝国集团时即结束该算法。

帝国主义算法流程描述如下：
1）初始化帝国主义竞争算法的参数：$N_{pop}$Npop​ , $N_{imp}$Nimp​
2）随机生成 $N_{pop}$Npop​ 作为国家的人口数量。选择$N_{imp}$Nimp​ 最好的国家作为帝国并根据他们的能力规定他们的殖民地数量；

3）如果终止条件未得到满足，则重复下列步骤；
4）内部位置交换；
5）帝国主义竞争；
6）淘汰弱小的帝国；
7）保留最终剩余的帝国，其适应度取值作为
最优解。

流程图如图所示:

2.算法结果

3.参考文献

[1] Esmaeil Atashpaz-Gargari,Caro Lucas.ImperialistCompetitive Algorithm: An Algorithm for OptimizationInspired by Imperialistic Competition 1-4244-1340-0/07_c 2007 IEEE.

[2]陈志楚,李聪,张超勇.基于帝国主义竞争算法的切削参数优化[J].制造业自动化,2012,34(24):10-15.

4.Matlab代码

https://mianbaoduo.com/o/bread/aJiYmJo=