第18章 帝国竞争算法
帝国竞争算法是一种基于社会群体的优化算法，群体中的个体称为“国家”，即为待优化问题的可行解。按照强弱国家分为“帝国”和“殖民地”。殖民地按一定准则分给不同帝国而形成“帝国集团”。操作包括帝国集团内部同化、更新及帝国集团之间的竞争。每次迭代后，较强帝国有更大概率获得殖民地而变得更强，而较弱帝国失去殖民地而变得更弱，当失去所有殖民地时该帝国就被删除。算法不断迭代，当群体中只剩下最后一个帝国时即为最优解。本章介绍帝国竞争算法的原理、数学描述、算法的实现步骤及流程。
18.1 帝国竞争算法的提出
帝国竞争算法（Imperialist Competitive Algorithm，ICA）是2007年由Atashpaz-Gargari等提出的一种基于社会政治进化的全局优化算法[60]，[61]。其设计思想源于对人类社会殖民地竞争过程的一种模拟。ICA把种群个体称为国家，根据国家权力的大小分为殖民地和帝国。每个帝国拥有总的权力包括其帝国自身的权力与所其占有的殖民地平均权力的加权。对于最小化问题，帝国的权力与其目标函数值成反比关系。该算法的核心是基于帝国之间的竞争，在竞争过程中，权力弱小的帝国逐渐灭亡，而由权力较强的帝国占有其殖民地。竞争的最终结果是使殖民地的目标函数收敛至全局最小，仅存在一个帝国，其余殖民地均归属该帝国。
对4种标准测试函数的仿真结果表明，ICA均成功地找到了全局最小解。
18.2 帝国竞争算法的原理
帝国竞争算法是基于国家竞争机制的一种新的优化算法。在该算法的种群中，每一个个体被称为一个国家，它们都是由一个实序列或向量来表示的。把所有国家都分成两类：帝国或殖民地。通过计算每一个国家的目标函数值来衡量每一个国家的势力。
将最初势力比较强大的国家作为帝国，剩余的国家即为殖民地。根据每个国家的势力将殖民地分配给不同的帝国。这样帝国及其所包含的殖民地组成了一个整体。每个帝国的势力都是由帝国势力和殖民地势力共同组成的。一个帝国的总势力等于帝国的势力加上一定比例的该帝国所包含的殖民地的平均势力。当把所有的殖民地分配给帝国后，殖民地开始向其所属的帝国主靠近，即在搜索空间内，殖民地向帝国的位置移动。
为了获得更大的势力，每个帝国都试图占有其他帝国的国家，正如社会历史一样，通过占有其他帝国的殖民地来增强自身的势力。任何一个帝国如果在这场竞争中不能获胜，不能增强自己的势力，必将在竞争中被淘汰。在帝国竞争过程中，强大的帝国势力越来越大，相反，较弱的帝国势力逐渐减弱。因此，较弱的帝国将失去其殖民地，势力变弱，最终走向灭亡。在帝国竞争中，殖民地国家只向其所属的帝国移动。这种占有机制最终只保存下来一个帝国，其余的国家都是这个帝国的殖民地，该帝国即为最优解。
18.3 帝国竞争算法的数学描述
在ICA优化算法中，每一个国家代表一个特定的优化问题的可行解。每一个国家都是由一个实数数组或向量来表示的。对于一个Nvar维优化问题，该数组定义为
一个国家的势力大小需要通过计算一定的目标函数f来得到，变量
的目标函数（代价函数）为
1. 帝国的初始化
在搜索空间中随机产生数量为Npop的初始国家。然后，将势力最强的Nimp个国家选为帝国主义国家，殖民地国家则由剩下的Ncol个国家组成。这些殖民地国家所属于帝国主义国家。
Npop=Nimp+Ncol（18.3）
为了形成最初的帝国集团，依据各个帝国主义国家的势力情况来决定分配给它的殖民地国家的数量。最初，一个帝国集团所拥有的殖民地国家的数量直接与其势力大小相关。为了按照比例将殖民地国家分配给帝国，定义帝国的相对势力为
其中，cn为第n帝国的代价函数值；Cn为第n帝国集团标准化后的代价函数值。标准化后的Cn代表了帝国集团的相对势力。
若优化目标函数为最小化问题，则帝国代价函数值越小，其所拥有的势力越大。第n个帝国主义国家的势力大小定义为
最初决定分配给帝国主义国家的殖民地的数量依赖于帝国主义国家的势力。因此，最初的殖民地分配方法为
N·C·n=round｛pn·Ncol｝（18.6）
其中，N·C·n为第n帝国主义国家所拥有的殖民地国家的数量；Ncol为殖民地国家的总数量。N·C·n个殖民地被随机地选为第n帝国的殖民地。这些殖民地国家和该帝国主义国家共同组成了第n帝国集团。
从殖民地分配的规则中可以看出，势力越大的帝国主义国家所拥有的殖民地国家的数量越多，同时，势力越小的帝国主义国家拥有的殖民地数量就越少。如图18.1所示为帝国集团的初始化情况。在该图中可以看出，帝国1为最有势力的国家而且拥有最多的殖民地。
2. 殖民地向所属帝国移动
当帝国集团形成后，每个帝国集团中的帝国主义国家试图去增加其殖民地的数量。在ICA算法中，殖民地国家沿着指向其所属帝国的方向靠近帝国，移动过程如图18.2所示。殖民地移动的单位为x。x的值是一个均匀分布的随机数
x～U（0，β×d）（18.7）
其中，d为殖民地与帝国之间的距离；β为一个大于1的数。β＞1会使殖民地国家从两个方向向其所属的帝国主义国家移动。
图18.1 帝国集团初始化情况
为了从不同的方向靠近帝国主义国家，引入一个随机的角度θ来作为殖民地国家相对帝国的移动方向。
θ～U（-γ，γ）（18.8）
其中，β和γ的值是任意的。Atashpaz-Gargari建议β的值选为π/4，从而增强帝国达到全局最优的收敛性。
3. 交换帝国和殖民地的位置
一旦一个殖民地国家移动到一个新的位置，它的势力可能会比其所属的帝国更大。在这种情况下，交换殖民地与帝国的位置。之后，这一殖民地就作为新的帝国主义国家进行竞争过程。如图18.3所示为帝国与殖民地交换位置的过程及帝国与殖民地交换位置后的状态。
图18.2 殖民地向其所属帝国的移动
图18.3 帝国与殖民地交换位置的过程
4. 计算帝国集团的总势力
一个帝国集团的总势力包括两部分：一部分为帝国主义国家的势力，另一部分为它所拥有的殖民地国家的势力。在这两部分中，帝国主义国家的势力对总势力有更大的影响。因此，一个帝国的总势力定义为
其中，T·C·n为第n个帝国集团的总代价函数值；wi为帝国集团的殖民地的代价函数值；ξ为一个小于1的正实数。将ξ的值选为0.1～0.5可以解决大多数情况下的问题。
5. 帝国集团的竞争
帝国主义国家的竞争过程发生在帝国集团之间，因为每一个帝国集团都试图占有其他帝国的殖民地并且控制它们。通过竞争使得强大的帝国集团更加强大，弱小的帝国集团更加弱小。在ICA算法中，最弱帝国集团中的最弱的一个殖民地国家将被其他帝国集团通过竞争去占有。这种情况如图18.4所示，在竞争中，每一个帝国集团都有可能占有最弱的国家。这种可能性的大小由下式定义得到
其中，Nimp为帝国主义国家的数量；N·T·C·n为第n帝国集团的相对代价函数值，定义如下：
为了将以上所述的帝国集团中的殖民地国家分类，引入以下向量P
图18.4 帝国竞争
向量R是与向量P相同规格的向量：
向量D由以下方程得到：
在向量D中最大的元素所对应的帝国集团将会占有上述最弱的殖民地国家。
6. 弱势帝国的灭亡
在帝国竞争中，失去势力的帝国集团将会灭亡，而且它所拥有的殖民地将被其他帝国集团瓜分。在建模的破坏机制中，可以定义不同的规则使得一个帝国失去势力。在ICA算法中，假定当一个帝国集团失去了其所有的殖民地国家时视为该帝国灭亡。
7. 算法终止条件
当一个帝国失去所有的殖民地时，该帝国会被从当前群体中删除。除了最强大的帝国之外，所有的帝国都将崩溃，所有的殖民地将在这个独特的帝国的控制之下。在理想情况下当整个群体只剩下一个帝国集团（帝国）时，算法终止。
另外，算法终止也可以采用不同的标准：设定最大迭代次数，当算法达到最大迭代次数时，算法停止；假设群体中剩下不止一个帝国，则选择势力最强的帝国作为最优解输出。
18.4 帝国竞争算法的实现步骤及流程
帝国竞争算法实现的主要步骤的伪码描述如下。
（1）在函数上选择一些随机点并初始化帝国。
（2）将殖民地移向他们相关的帝国主义者（同化）。
（3）如果有一个帝国的殖民地拥有比帝国主义更低的成本，交换殖民地和帝国主义的位置。
（4）计算所有帝国的总成本（与帝国主义及其殖民地的力量有关）。
（5）从最弱的帝国选择最弱的殖民地（们）并把它（它们）给最可能拥有它的帝国（帝国主义竞争）。
（6）消除无能的帝国。
（7）如果只有一个帝国，停止，否则转步骤（2）。
帝国竞争算法的流程如图18.5所示。
图18.5 帝国竞争算法的流程图