1、第 1 页帝国竞争算法在组合优化问题上的应用研究综述rajya摘要ICA 是一种由帝国竞争激发的社会启发性的优化算法。它由一个初始化群体开始，并通过同化，位置互换，帝国竞争，以及淘汰来进行优化。它始于一个初始的群体，并且通过几个特定的步骤高效的对搜索范围进行搜索，并收敛到最优解或者接近最优解。ICA 在过程计划方面的优越性可以通过文献中大量的基准方程的测试来体现。关键词 群体智能；启发算法；帝国竞争1、发展背景目前为止，优化算法已经提出了多种，例如 Holland 教授提出的模拟自然界遗传机制和生物进化论而形成的一种并行随机搜索最优化方法，即遗传算法，由 Eberhart 和 Kennedy
2、博士源于对鸟群捕食的行为研究而提出的粒子群优化算法等，其都属于自然启发的计算的一个分支，即生物启发的计算，而帝国竞争优化算法是属于自然启发计算的另一分支，即社会启发的计算，基于帝国主义殖民竞争的机制的新优化算法。ICA 是一种新型的基于群体的优化算法，由 Atashpaz-Gargari 和 Lucas 提出。群体中的每一个都代表一个国家，所有的国家被分为两类：帝国和殖民地。帝国是初始化时最强的几个国家，其余的国家就是帝国的殖民地。殖民地在初始化时被归给初始的帝国。帝国主义者与其殖民地组成一个帝国。每个国家的实力显示了这个国家的适应性。在迭代与优化过程中，帝国们相互竞争来获得更多的殖民地。更强
3、大的帝国将得到更多的殖民地，弱小的帝国则会失去殖民地。当所有的殖民地都归属于同一个帝国时，算法结束。2、帝国竞争模型及流程帝国竞争算法主要分为以下几个部分：1 初始化帝国在搜索空间内随机生成一些向量，这些向量称为国家，这些国家随机的分布在要搜索的空间里，这些国家势力的大小通过一个代价函数来衡量，与代价函数值成反比，即代价函数值越小，国家势力越大。一定数量的势力中较大的国家被选作帝国主义国家，剩下的国家作为殖民地国家。根据帝国主义国家势力的大小，把殖民地国家分配给帝国主义国家。一个帝国主义国家及其分到的殖民地国家组成一个帝国。2 同化政策在现实世界里，帝国主义国家为了更好地控制其殖民地国家，把自
4、己的文化及规则推广到殖民地国家，这个过程称为同化。在 CCA 算法中，即殖民地国家代表的搜索空间中的位置向帝国主义国家所代表的位置靠近，随机移动一定的距离，沿两个位置连线所在的直线，指向帝国主义国家所在的空间位置。殖民地国家所在空间位置移动后，可能是一个更好的位置，因此有可能取代它所属于的帝国主义国家。3 帝国主义国家间的竞争正如社会历史事实，帝国主义国家通过占有别的帝国主义国家所属的殖民地国家来增加自己的势力。在 CCA 算法中这样描述：先计算每个帝国的总势力，即帝国主义国家的势力第 2 页加上其所有殖民地国家势力的平均值的一部分。竞争的结果是把总势力最弱的帝国中最弱的殖民地国家给最有可能占
5、有它的帝国。4 最弱的帝国灭亡当一个帝国主义国家丧失了其所有的殖民地国家时，其所在的帝国覆灭。经过一定的时间之后，所有帝国中最强大的帝国保存下来，而且保存下来的最强大的帝国中只有一个帝国主义国家和殖民地国家，这个帝国主义国家就代表最优解。ICA 的流程如下图所示：ICA 的过程如下所示：步骤 1 初始化 ICA 的参数步骤 2 随机产生 Npop 个国家。选择 Nimp 个作为帝国，并根据其实力来分配殖民地步骤 3 如果终止条件未达到，重复下述步骤步骤 4 同化步骤 5 帝国竞争步骤 6 循环步骤 7 淘汰弱小的帝国3、运用帝国竞争算法研究尚处于起步阶段，它被运用于很多各个领域的最优化问题上。
6、1中作者 V. Kayvanfar 和M. Zandieh通过对比遗传算法以及帝国竞争算法在解决经济批量调度问题的效率后，得出了帝国竞争算法更优的结论。2中作者Ramin Rajabioun, Esmaeil Atashpaz-Gargari, 以及Caro Lucas通过帝国竞争算法来寻找非线性非合作博弈的纳什均衡点，通过与遗传算法的对第 3 页比，证实了其有效性。3中作者通过将帝国竞争算法与支持向量回归（SVR）相结合，运用在新产品开发（NPD）项目的时间估计上。并与一般回归神经网络（GRNN）之间进行比较。实验结果表明，所提出的模型达到高的估计精度，并导致有效的预测。4中作者通过用 IC
7、A 来设计一个最佳的天线阵列，最大限度地减少了错误的概率为二进制相移键控调制，最小误码率（MBER）波束赋形。且与遗传算法相比，帝国竞争算法连贯性更好且成本更低。4、改进思路 将帝国之间的殖民地互换以实现搜索的乱序度 在删减弱国的同时增加一定量的新帝国，以减小陷入局部最小值的可能性 在殖民地向帝国移动的过程中，保留其最优解的位置并加以利用 增加正交分量，使殖民地有更多的搜索的可能性 使帝国之间保证一定的距离，不要搜索的太集中，以减小陷入局部最小值的可能性5、算法实现本文使用 C+实现算法，界面中可以填入变量个数、国家总数、帝国总数、权重参数以及迭代次数等。第 4 页第 5 页参考文献：1 V.
8、 Kayvanfar & M. Zandieh , The economic lot scheduling problem with deteriorating items and shortage:an imperialist competitive algorithm 2Ramin Rajabioun, Esmaeil Atashpaz-Gargari, and Caro Lucas ,Colonial Competitive Algorithm as a Tool for Nash Equilibrium Point Achievement3S. MeysamMousavi, R.Tav
9、akkoli-Moghaddam, BehnamVahdani, H.Hashemi, M.J.Sanjari, A new support vector model-based imperialist competitive algorithm for time estimation in new product development projects4 Arash Khabbazi, Esmaeil Atashpaz-Gargari, Caro Lucas ,Imperialist competitive algorithm for minimum bit error rate beam
10、forming5Siamak Talatahari Ali Kaveh Razi Sheikholeslami,Chaotic imperialist competitive algorithm for optimum design of truss structures6 Nazari-Shirkouhi, S., et al., Solving the integrated product mix-outsourcing problem using the Imperialist Competitive Algorithm. EXPERT SYSTEMS WITH APPLICATIONS
11、, 2010. 37(12): p. 7615-7626.7 Mohammadi-ivatloo, B., et al., Imperialist competitive algorithm for solving non-convex dynamic economic power dispatch. ENERGY, 2012. 第 6 页44(1): p. 228-240.8 Kaveh, A. and S. Talatahari, Optimum design of skeletal structures using imperialist competitive algorithm. C
12、OMPUTERS & STRUCTURES, 2010. 88(21-22): p. 1220-1229.9 Bahrami, H., K. Faez and M. Abdechiri, Imperialist Competitive Algorithm using Chaos Theory for Optimization (CICA). 2010 12TH INTERNATIONAL CONFERENCE ON COMPUTER MODELLING AND SIMULATION (UKSIM), 2010: p. 98-103.10 Atashpaz-Gargari, E. and C.
13、Lucas, Imperialist competitive algorithm: An algorithm for optimization inspired by imperialistic competition. 2007 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1-10, PROCEEDINGS, 2007: p. 4661-4667.11 Coelho, L.D.S., L.D. Afonso and P. Alotto, A Modified Imperialist Competitive Algorithm for Optimization in Electromagnetics. IEEE TRANSACTIONS ON MAGNETICS, 2012. 48(2): p. 579-582.12 Lian, K., et al., Optimization of process planning with various flexibilities using an imperialist competitive algorithm. INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2012. 59(5-8): p. 815-828.
