哈喽，小伙伴们好呀~
在之前的推文中，我们学习了优化算法学习|帝国竞争算法原理及代码实现，今天呢我们学习一下帝国竞争算法的应用——改进帝国竞争算法求解柔性流水车间排产问题。
柔性流水车间调度问题(flexible flow-shop scheduling problem, FFSP)是传统流水车间调度问题的扩展，突破了资源唯一性限制，每道工序可在多台不同的机器上加工，从而使作业车间调度问题更加贴合实际生产，所以一直是国内外的研究热点。FFSP已经被证明是一个NP难问题[1]，对FFSP的研究有着非常重要的理论意义和实际工程应用价值。
对柔性流水车间调度问题描述如下：n个待加工的工件在m 道工序上进行加工；第j 道工序中并行工位数为j M ，且每道工序至少有一个工位，并且至少有一道工序存在多个并行工位，同一个工件在同一道工序中任意工位上的加工时间相同。
1.模型参数
2.约束条件
① 每个工件Ji 在每道工序中选择任意一台并行工位进行加工。
② 每个工件Ji 一旦开始加工就不能中断。
③ 每台并行工位同时只能加工一个工件Ji ，每个工件Ji 同时只能被一台并行工位加工。
④ 工件的准备时间和移动时间包含在加工时间内。
⑤ 允许工序之间存在等待，允许工位在工件未到达时闲置。
改进帝国竞争算法
由于标准帝国竞争算法（优化算法学习|帝国竞争算法原理及代码实现）的早熟收敛，且易陷入局部最优解，因此提出了改进帝国竞争算法(Improved Imperialist Competitive Algorithm，IICA)。
1.算法改进
① 相比于传统标准的帝国竞争算法，在帝国内同化部分采用离散型帝国竞争算法中的内容实现，即交叉变异操作。
② 为了提高算法群体的全局搜索能力，在帝国竞争之后，增加殖民地改革操作，即将各个帝国内最弱的殖民地用一个随机解代替。
③ 帝国消除部分为了有利于算法收敛，保留较优个体，即失去所有殖民地的帝国，使得进化过程中能够找到更优解。
2.帝国同化
相对于传统连续型帝国竞争算法来说，离散型帝国竞争算法最大的不同在于帝国内部殖民国家对殖民地的同化过程。同化过程通过借鉴遗传算法中的交叉和变异操作，实现了殖民地向帝国的移动，以及移动过程中的偏移[2]。文献[3]采用如下所示的两点交叉方法。随机的选择两个基因片段并交换它们的位置。
3.交换帝国和殖民地的位置
当殖民地向帝国移动的过程中，它的势力可能会比其所属帝国的势力更大。在这种情况下，交换帝国和殖民地的位置。之后，这一殖民地就作为新的帝国主义国家再进行竞争过程。
交叉过程示意图，如图1 所示。变异过程示意图，如图2所示。
图1 交叉过程
图2 变异过程
4. 殖民地改革
帝国竞争算法的特点是寻优速度快，但同时容易陷入局部最优解，因此要增加算法群体的全局搜索能力，在帝国竞争之后，增加殖民地的改革操作[4]，即将各个帝国内最弱的殖民地用一个随机解代替，为了有效增强个体之间的信息
交换，在此引入编码理论中的汉明距离[5-6]的概念。
5. 帝国消除及算法终止条件
帝国之间的竞争，势力较大的帝国通过占有其他帝国的殖民地变得日益强大，而势力较小的帝国其殖民地个数却不断减少。当一个帝国失去所有的殖民地时，消除该帝国。然而这样就损失了优势个体，不利于算法收敛，由于该帝国个体优于一般殖民地国家，因此保留该个体并将其归属于占有它最后一个殖民地的帝国。保留较优个体，使得进化过程中能够找到更优解。算法不断迭代，当只存在一个帝国或者达到迭代次数时，算法结束。
算法流程IICA算法的流程图，如图3所示。
图3 改进帝国竞争算法流程图
参考文献[1] Alireza K, Fariborz J, Morteza B. Integrating sequence-dependent group scheduling problem and preventive maintenance in flexible flow shops[J]. The International Journal of Advanced Manufacturing Technology, 2015, 77(1-4): 173-185.
[2] LIAN K, ZHANG C, GAO L. A modified colonial competitive algorithm for the mixed- model U-line balancing and sequencing problem[J]. International Journal of Production Research,201 2,50(18): 5117-5131.
[3] Jolaia F, Rabiee M., Asefi H. A novel hybrid meta-heuristic algorithm for a no-wait flexible flow shop scheduling problem with sequence dependent setup times[J]. International Journal of Production Research, 2012, 50(24): 7447-7466.
[4] Shokrolahpour E, Zandieh M, Dorri B. A novel imperialist competitive algorithm for bi-criteria scheduling of the assembly flow-shop problem[J].International Journal of Production Research, 2010, 49(11): 3087-3103.
[5] 张焕炯, 王国胜, 钟义信. 基于汉明距离的文本相似度计算[J]. 计算机工程与应用, 2001, 37(19: 21-22.
[6] Shlomi D, Sergey F, Dan E, et al. Preserving Hamming Distance in Arithmetic and Logical Operations[J]. Journal of Electronic Testing, 2013, 29(6): 903-907.
[7]韩忠华,孙越,史海波,林硕.改进帝国竞争算法求解柔性流水车间排产问题[J].控制工程,2017,24(08):1649-1655.
好啦，今天的学习就到这里啦~想要了解什么方面的问题可以关注公众号“土博在路上”，获取更多精彩内容~
论文撰写投稿、科研软件神器、优化算法学习等精彩内容均可以在公众号找到，快来关注吧~
