【机器学习】改进猫群算法求解置换流水车间调度问题

团购合买资源类别：文库，文档格式：PDF，文档页数：10，文件大小：3.39MB

第14卷第4期智能系统学报 Vol.14 No.4 2019年7月 CAAI Transactions on Intelligent Systems Jul.2019 D0:10.11992/tis.201804016 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180704.1011.004html 改进猫群算法求解置换流水车间调度问题裴小兵，于秀燕 (天津理工大学管理学院，天津300384) 摘要：标准猫群算法(CSO)在求解最小化最大完工时间的置换流水车间调度问题(PFSP)时收敛速度较慢，同时，当问题规模变大时容易出现“维数灾难”。为加快寻优速度，同时避免“维数灾难”，提出了一种基于分布估计算法的改进猫群算法(EDA-CSO)。以猫群算法为框架，嵌入分布估计算法，在搜寻模式下，利用概率矩阵挖掘解序列中的优秀基因链组合区块，使用猫群算法中的跟踪模式更新猫的速度和位置，从而更新优秀解序列产生子群体。最后，通过对Carlier和Reeves标准例题集的仿真测试和结果比较，验证了该算法良好的鲁棒性和全局搜索能力。关键词：置换流水车间调度；猫群算法：分布估计算法；搜寻模式：概率矩阵：组合区块；跟踪模式：优秀解序列中图分类号：TP18文献标志码：A 文章编号：1673-4785(2019)04-0769-10 中文引用格式：裴小兵，于秀燕.改进猫群算法求解置换流水车间调度问题.智能系统学报，2019,14(4)：769-778，英文引用格式：PEI Xiaobing,YU Xiuyan.Improved cat swarm optimization for permutation flow shop scheduling problemJ. CAAI transactions on intelligent systems,2019,14(4):769-778. Improved cat swarm optimization for permutation flow shop scheduling problem PEI Xiaobing,YU Xiuyan (School of Management,Tianjin University of Technology,Tianjin 300384,China) Abstract:The standard cat swarm optimization(CSO)has a slow convergence rate in solving the permutation flow shop scheduling problem(PFSP)to minimize the maximum completion time.Meanwhile,the "dimension disaster"is prone to occur when the scale of the problem is large.To speed up the optimization and avoid the"dimension disaster,"a CSO al- gorithm based on the estimation of distribution algorithms is proposed in this paper.Based on the cat swarm algorithm, the distribution estimation algorithm is embedded.In the search mode,the probability matrix is used to mine the excel- lent gene chain combination blocks in the solution sequence,and the tracking mode in the cat swarm algorithm is used to update the speed and position of the cat,thus updating the excellent solution sequence to generate a subpopulation.Fi- nally,through the simulation test and comparison result of Carlier and Reeves standard example set,the good robust- ness and global searching ability of the algorithm are verified. Keywords:permutation flow shop scheduling problem;cat swarm optimization;estimation of distribution algorithm; search mode;probability matrix;combination block;tracking mode;excellent solution sequence 置换流水车间调度问题(permutation flow shop al-.time hard,NP)。常见的PFSP求解方法可分为： scheduling problem,PFSP)是智能制造的核心问题精确算法、启发式算法等。启发式算法能够快之一，具有很重要的工程应用价值。研究表明，速求得问题的可行解，但这些算法结构比较复该问题属于NP难题(non-deterministic polynomi- 杂，求解最优解比较困难。收稿日期：2018-04-13.网络出版日期：2018-07-04. 在有限的资源条件下，对PFSP的优化可有效基金项目：国家创新方法工作专项项目(2017IM0I0800) 通信作者：于秀燕.E-mail:Yu xiuyanl026@163.com 增加企业收益，相关人士一直致力于研究和开发

DOI: 10.11992/tis.201804016 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180704.1011.004.html 改进猫群算法求解置换流水车间调度问题裴小兵，于秀燕（天津理工大学管理学院，天津 300384）摘要：标准猫群算法 (CSO) 在求解最小化最大完工时间的置换流水车间调度问题 (PFSP) 时收敛速度较慢，同时，当问题规模变大时容易出现“维数灾难”。为加快寻优速度，同时避免“维数灾难”，提出了一种基于分布估计算法的改进猫群算法 (EDA-CSO)。以猫群算法为框架，嵌入分布估计算法，在搜寻模式下，利用概率矩阵挖掘解序列中的优秀基因链组合区块，使用猫群算法中的跟踪模式更新猫的速度和位置，从而更新优秀解序列产生子群体。最后，通过对 Carlier 和 Reeves 标准例题集的仿真测试和结果比较，验证了该算法良好的鲁棒性和全局搜索能力。关键词：置换流水车间调度；猫群算法；分布估计算法；搜寻模式；概率矩阵；组合区块；跟踪模式；优秀解序列中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2019)04−0769−10 中文引用格式：裴小兵, 于秀燕. 改进猫群算法求解置换流水车间调度问题 [J]. 智能系统学报, 2019, 14(4): 769–778. 英文引用格式：PEI Xiaobing, YU Xiuyan. Improved cat swarm optimization for permutation flow shop scheduling problem[J]. CAAI transactions on intelligent systems, 2019, 14(4): 769–778. Improved cat swarm optimization for permutation flow shop scheduling problem PEI Xiaobing，YU Xiuyan (School of Management, Tianjin University of Technology, Tianjin 300384, China) Abstract: The standard cat swarm optimization (CSO) has a slow convergence rate in solving the permutation flow shop scheduling problem (PFSP) to minimize the maximum completion time. Meanwhile, the "dimension disaster" is prone to occur when the scale of the problem is large. To speed up the optimization and avoid the "dimension disaster," a CSO algorithm based on the estimation of distribution algorithms is proposed in this paper. Based on the cat swarm algorithm, the distribution estimation algorithm is embedded. In the search mode, the probability matrix is used to mine the excellent gene chain combination blocks in the solution sequence, and the tracking mode in the cat swarm algorithm is used to update the speed and position of the cat, thus updating the excellent solution sequence to generate a subpopulation. Finally, through the simulation test and comparison result of Carlier and Reeves standard example set, the good robustness and global searching ability of the algorithm are verified. Keywords: permutation flow shop scheduling problem; cat swarm optimization; estimation of distribution algorithm; search mode; probability matrix; combination block; tracking mode; excellent solution sequence 置换流水车间调度问题 (permutation flow shop scheduling problem，PFSP) 是智能制造的核心问题之一，具有很重要的工程应用价值。研究表明，该问题属于 NP 难题[1] (non-deterministic polynomial-time hard，NP)。常见的 PFSP 求解方法可分为：精确算法、启发式算法[2] 等。启发式算法能够快速求得问题的可行解，但这些算法结构比较复杂，求解最优解比较困难。在有限的资源条件下，对 PFSP 的优化可有效增加企业收益，相关人士一直致力于研究和开发收稿日期：2018−04−13. 网络出版日期：2018−07−04. 基金项目：国家创新方法工作专项项目 (2017IM010800). 通信作者：于秀燕. E-mail：Yu_xiuyan1026@163.com. 第 14 卷第 4 期智能系统学报 Vol.14 No.4 2019 年 7 月 CAAI Transactions on Intelligent Systems Jul. 2019

·770· 智能系统学报第14卷高效的优化技术，希望能够快速找到PFSP的最 (block-based estimation distribution algorithm, 优解。受猫日常行为启发，Chu)在2006年提出 BBEDA)相结合来求解PFSP问题；鉴于EDA良了猫群算法(cat swarm optimization,CSO)。猫群好的收敛速度，本研究将CSO算法与EDA相结算法将猫的行为分为搜寻模式和跟踪模式，这两合，得到高适应度的人工解，同时利用3种变异算种模式通过结合律MR(mixture ratio)进行交互转子对解序列重组以提高解序列的质量和多样性：换。搜寻模式下，通过对个体进行扰动从而使得并通过仿真实例验证EDA-CSO算法的有效性及每个个体向局部最优个体靠近；跟踪模式下，猫良好的鲁棒性。通过一定速度来跟踪目标，从而使得个体向全局 1置换流水车间调度问题数学模型最优靠近。近年来，猫群算法被应用于很多领域，并取得较好效果。在识别领域，Ganapati将 PFSP是许多生产调度问题的简化模型，该问该算法运用到无线脉冲响应(IR)系统识别；Pra- 题主要研究了n个工件W,N2,…,N}在m台机 dhan将猫群算法应用于图像识别：Guo等基于器{M1,M2,·,Mm}上加工，并且每个工件有m道以上研究基础，运用猫群算法对光伏系统进行优加工工序，目标是求使某项生产指标达到最优的化。在数学研究领域，Pappula等将猫群算法用方案。相关约束条件如下：1)所有工件按照相同于函数优化问题，但收敛速度较慢；为提高猫群顺序，即1,2，…，m在机器上加工；2)某一时刻，算法的全局搜索速度，Tsai等8提出了猫群算法任一机器只能加工一个工件；3)某一时刻，任一并行结构，同时验证了在种群规模较小及总迭代工件只能在一台机器上进行加工；4)任何工件在次数较少的情况下，该并行结构能有效提高收敛加工过程中不能中断：5)所有工件在初始时刻都速度。在多目标生产调度方面，Pradhan运用猫可以加工。群算法求解多目标优化问题；刘琼等将该算法若PFSP以最大完工时间为目标，则该问题可运用到混流装配线排序问题。以用n、m、prmu、Cm这几个符号来表示，其中，尽管猫群算法在以上领域取得了一些研究 n代表总工件数，m代表总机器数，pmu代表所有成果，但在单目标置换流水车间调度领域的研究工件在所有机器上的加工顺序相同，Cx代表最较少。Bouzidi等uo针对置换流水车间调度问题大完工时间。利用标准的猫群算法来求解；此外，Bouzidi等上述问题的数学描述如下：令（π，）代表工还将猫群算法与遗传算法中的相关解码操作结件i在机器j上的加工时间，C(π，)代表工件i在合起来对置换流水车间进行求解；马邦雄等四运机器j上的完工时间。T={π1,2，…，πn}代表全部用猫群算法对置换流水车间调度问题进行求解工件的一个加工顺序，Γ代表全部的排序集合。并与其他算法进行比较。针对置换流水车间调具体的PFSP模型可以表示为度问题，尽管上述研究都取得较好效果，但求解 C(π1,1)=t(π1,1) 过程中该算法收敛速度较慢，同时，当问题规模 C(π，1)=C(π-l,1)+t(π，1)i=2,3,…,n 变大时容易出现“维数灾难”。为加快寻优速度， C(π1，)=C(π1，j-1)+(π1，)j=2,3,…,n 同时避免“维数灾难”，本研究提出一种基于分布 C(π，)=max{C(π-，j),C(π，j-l)}+t(π，j) i=2,3,…,j=2,3,…,m 估计算法的改进猫群算法(EDA-CSO)用于解决 Cmax=C(πn,m） PFSP。该问题的目标是得到最优的工件加工顺序目前，分布估计算法(estimation of distribution π'，因而对于其他任意的工件加工顺序π都有： algorithms,EDA)已应用于智能学习、函数优化、 Cns(π）≤Cmx(π)o 图像识别、多目标规划等多个领域。EDA算法利用概率矩阵模型描述解序列在空间的分布，利 2改进的猫群算法用统计学知识分析概率模型，同时，利用概率矩基于以上优化目标及约束条件，改进的猫群阵产生子群体。为得到更好的解，TZENG等算法求解PFSP的流程如下：将蚁群算法与EDA算法相结合，用于求解PFSP: 1)初始化种群； Chang等I将EDA算法与遗传算法相结合来解 2)计算猫的适应度值；决旅行商问题(traveling salesman problem,TSP): 3)改进的猫群算法通过利用混合比率将猫群同时，Chang等l6将区块模型与分布估计算法分为搜寻模式和跟踪模式的2个子群，对不同子

高效的优化技术，希望能够快速找到 PFSP 的最优解。受猫日常行为启发，Chu[3] 在 2006 年提出了猫群算法 (cat swarm optimization，CSO)。猫群算法将猫的行为分为搜寻模式和跟踪模式，这两种模式通过结合律 MR(mixture ratio) 进行交互转换。搜寻模式下，通过对个体进行扰动从而使得每个个体向局部最优个体靠近；跟踪模式下，猫通过一定速度来跟踪目标，从而使得个体向全局最优靠近。近年来，猫群算法被应用于很多领域，并取得较好效果。在识别领域，Ganapati[4] 将该算法运用到无线脉冲响应 (IIR) 系统识别；Pradhan[5] 将猫群算法应用于图像识别；Guo 等 [6] 基于以上研究基础，运用猫群算法对光伏系统进行优化。在数学研究领域，Pappula 等 [7]将猫群算法用于函数优化问题，但收敛速度较慢；为提高猫群算法的全局搜索速度，Tsai 等 [8] 提出了猫群算法并行结构，同时验证了在种群规模较小及总迭代次数较少的情况下，该并行结构能有效提高收敛速度。在多目标生产调度方面，Pradhan[5] 运用猫群算法求解多目标优化问题；刘琼等[9] 将该算法运用到混流装配线排序问题。尽管猫群算法在以上领域取得了一些研究成果，但在单目标置换流水车间调度领域的研究较少。Bouzidi 等 [10] 针对置换流水车间调度问题利用标准的猫群算法来求解；此外，Bouzidi 等 [11] 还将猫群算法与遗传算法中的相关解码操作结合起来对置换流水车间进行求解；马邦雄等[12] 运用猫群算法对置换流水车间调度问题进行求解并与其他算法进行比较。针对置换流水车间调度问题，尽管上述研究都取得较好效果，但求解过程中该算法收敛速度较慢，同时，当问题规模变大时容易出现“维数灾难”。为加快寻优速度，同时避免“维数灾难”，本研究提出一种基于分布估计算法的改进猫群算法 (EDA-CSO) 用于解决 PFSP。目前，分布估计算法 (estimation of distribution algorithms，EDA) 已应用于智能学习、函数优化、图像识别、多目标规划[13] 等多个领域。EDA 算法利用概率矩阵模型描述解序列在空间的分布，利用统计学知识分析概率模型，同时，利用概率矩阵产生子群体。为得到更好的解，TZENG 等 [14] 将蚁群算法与 EDA 算法相结合，用于求解 PFSP； Chang 等 [15] 将 EDA 算法与遗传算法相结合来解决旅行商问题 (traveling salesman problem，TSP)；同时，Chang 等 [16] 将区块模型与分布估计算法 (block-based estimation distribution algorithm， BBEDA) 相结合来求解 PFSP 问题；鉴于 EDA 良好的收敛速度，本研究将 CSO 算法与 EDA 相结合，得到高适应度的人工解，同时利用 3 种变异算子对解序列重组以提高解序列的质量和多样性，并通过仿真实例验证 EDA-CSO 算法的有效性及良好的鲁棒性。 1 置换流水车间调度问题数学模型 {N1 , N2,··· , Nn} {M1 , M2,··· , Mm} PFSP 是许多生产调度问题的简化模型，该问题主要研究了 n 个工件在 m 台机器上加工，并且每个工件有 m 道加工工序，目标是求使某项生产指标达到最优的方案。相关约束条件如下：1) 所有工件按照相同顺序，即 1，2，···，m 在机器上加工；2) 某一时刻，任一机器只能加工一个工件；3) 某一时刻，任一工件只能在一台机器上进行加工；4) 任何工件在加工过程中不能中断；5) 所有工件在初始时刻都可以加工。 Cmax Cmax 若 PFSP 以最大完工时间为目标，则该问题可以用 n、m、prmu、这几个符号来表示，其中， n 代表总工件数，m 代表总机器数，prmu 代表所有工件在所有机器上的加工顺序相同，代表最大完工时间。 πi πi Γξ = {π1, π2,··· , πn} Γ 上述问题的数学描述如下：令 t( ，j) 代表工件 i 在机器 j 上的加工时间，C( ，j) 代表工件 i 在机器 j 上的完工时间。代表全部工件的一个加工顺序，代表全部的排序集合。具体的 PFSP 模型可以表示为 C(π1 ,1) = t(π1 ,1) C(πi ,1) = C(πi−1 ,1)+t(πi ,1) i = 2,3,··· ,n C(π1 , j) = C(π1 , j−1)+(π1 , j) j = 2,3,··· ,n C(πi , j) =max{C(πi−1, j),C(πi , j−1)}+t(πi , j) i = 2,3,··· ,n; j = 2,3,··· ,m Cmax = C(πn ,m) π ∗ π Cmax (π ∗ ) ⩽ Cmax (π) 该问题的目标是得到最优的工件加工顺序，因而对于其他任意的工件加工顺序都有：。 2 改进的猫群算法基于以上优化目标及约束条件，改进的猫群算法求解 PFSP 的流程如下： 1) 初始化种群； 2) 计算猫的适应度值； 3) 改进的猫群算法通过利用混合比率将猫群分为搜寻模式和跟踪模式的 2 个子群，对不同子 ·770· 智能系统学报第 14 卷

第4期裴小兵，等：改进猫群算法求解置换流水车间调度问题 ·771· 群采取不同的方法处理：新概率矩阵1次，挖掘区块n次，区块竞争1次， 4)在搜寻模式下，利用概率模型更新记录可组合人造解1次，解序列重组1次，故搜寻模式行解信息并更新可行解：下的时间复杂度为O(MRN+MR2W2+MeN+MRN+ 5)先后运用区块挖掘及区块竞争来得到适应 MN); 度较高的人工解：步骤7)中执行跟踪模式的猫，每次迭代速度 6)为提高人工解的质量和多样性，运用搜寻更新1次，位置更新1次，解序列更新1次，故跟算子对人工解进行重组：踪模式下的时间复杂度为O(1-Mr)W+N+): )在跟踪模式中利用基于二元竞赛法的速度步骤8)中终止条件判断需要1次操作，故此位移模型对猫的速度、位置更新，直至达到全局步骤的时间复杂度为O1)。最优；由以上可知，该算法的时间复杂度为O(TM+ 8)算法终止条件判断。 5)W+TMWN2),故时间复杂度主要与与初始种群规基于区块的猫群算法求解PFSP的具体流程模、混合比率及迭代次数有关。如图1所示。 2.2初始化种群开始传统的猫群算法通过轮盘赌的方式生成初始种群，由于初始种群个体适应度较低，在一定程利用贪婪准则及随机方式初始化速度和位置度上制约了算法的收敛速度。本研究利用贪婪准计算猫的适应度值则寻及轮盘赌相结合的方式优化初始化种群，以达到加快收敛速度的同时，增加初始解的多样基于线性混合比率的猫行为模式选择性。在利用贪婪准则初始化种群时，随机选取第一个工件i,并将其加入到「={π1，π2，…，π}里，然猫处于搜寻状态 Y N 后在其他未加工的工件中搜索，寻找下一个工搜寻模式跟踪模式件，其在所有未加工工件中加工时间最短，将其更新概率矩阵更新猫的速度加至T={π1，π2，…，πn}里，并将其作为当前加工工组合区块更新猫的位置件，继续搜索并增加下一个加工工件，直至所有工件都加入加工顺序集T={π1，π2，…，πn。运用贪组合人造解二元竞赛法婪准则产生的是初始解序列，因而，需要将初始更新解序列解序列重组解序列转变为一定区间内的位置矢量。具体如式(1)：满足算法终止条件 =+二.6-1+5 n (1) Y j=1,2,…m 结束式中：x代表猫在j维的位置值；5代表初始解图1EDA-CSO流程图序列的第j维工件序号；xmj及xa表示猫在连 Fig.1 The flow chart of EDA-CSO 续空间中位置矢量的上下界值；3代表[0,1]区间 2.1复杂度分析内随机产生的随机数。一般而言，时间复杂度能够度量算法的运行初始位置及速度产生方式为时间及算法的优劣。假设种群规模为N,猫处于 Xi=Xmin+(Xmax -Xmin)r1 (2) 搜寻模式下的概率为MR,迭代次数为T,根据改 Vi=Vmin +(Vmax -Vmin)r2 (3) 进猫群算法的步骤进行时间复杂度分析。式中：X在区间[Xa,Xax]内连续变化；V,在区间步骤1)中种群初始化需要N次操作，所以步 [Vmn,VnaJ内连续变化。骤1)的时间复杂度为OW: 2.3基于混合比率的猫行为模式选择步骤2)中用以计算适应度的时间复杂度为传统的猫群算法不能根据算法的迭代次数合 O(N):; 理分配局部搜索和全局搜索的比重，若在算法迭步骤3)中用以选择猫行为方式的时间复杂代前期采用较大的混合比率的跟踪猫，可以增加度为O: 算法的全局搜索能力，但在算法迭代后期搜寻猫步骤4)6)中执行搜寻模式的猫，每次迭代更所占比率较大，可以提高解精度和收敛性。因

群采取不同的方法处理； 4) 在搜寻模式下，利用概率模型更新记录可行解信息并更新可行解； 5) 先后运用区块挖掘及区块竞争来得到适应度较高的人工解； 6) 为提高人工解的质量和多样性，运用搜寻算子对人工解进行重组； 7) 在跟踪模式中利用基于二元竞赛法的速度− 位移模型对猫的速度、位置更新，直至达到全局最优； 8) 算法终止条件判断。基于区块的猫群算法求解 PFSP 的具体流程如图 1 所示。开始利用贪婪准则及随机方式初始化速度和位置计算猫的适应度值基于线性混合比率的猫行为模式选择 Y Y N N 猫处于搜寻状态满足算法终止条件解序列重组组合人造解结束组合区块更新概率矩阵搜寻模式二元竞赛法更新解序列更新猫的位置更新猫的速度跟踪模式图 1 EDA-CSO 流程图 Fig. 1 The flow chart of EDA-CSO 2.1 复杂度分析一般而言，时间复杂度能够度量算法的运行时间及算法的优劣。假设种群规模为 N，猫处于搜寻模式下的概率为 MR，迭代次数为 T，根据改进猫群算法的步骤进行时间复杂度分析。步骤 1) 中种群初始化需要 N 次操作，所以步骤 1) 的时间复杂度为 O(N)；步骤 2) 中用以计算适应度的时间复杂度为 O(N)；步骤 3) 中用以选择猫行为方式的时间复杂度为 O(N)；步骤 4)~6) 中执行搜寻模式的猫，每次迭代更新概率矩阵 1 次，挖掘区块 n 次，区块竞争 1 次，组合人造解 1 次，解序列重组 1 次，故搜寻模式下的时间复杂度为 O(MRN+MR 2 N 2 +MRN+MRN+ MRN)；步骤 7) 中执行跟踪模式的猫，每次迭代速度更新 1 次，位置更新 1 次，解序列更新 1 次，故跟踪模式下的时间复杂度为 O((1-MR)(N+N+N))；步骤 8) 中终止条件判断需要 1 次操作，故此步骤的时间复杂度为 O(1)。由以上可知，该算法的时间复杂度为 O(T(MR+ 5)N+TMRN 2 )，故时间复杂度主要与与初始种群规模、混合比率及迭代次数有关。 2.2 初始化种群 i Γξ = {π1, π2,··· , πn} Γξ = {π1, π2,··· , πn} Γξ = {π1, π2,··· , πn} 传统的猫群算法通过轮盘赌的方式生成初始种群，由于初始种群个体适应度较低，在一定程度上制约了算法的收敛速度。本研究利用贪婪准则 [16] 寻及轮盘赌相结合的方式优化初始化种群，以达到加快收敛速度的同时，增加初始解的多样性。在利用贪婪准则初始化种群时，随机选取第一个工件，并将其加入到里，然后在其他未加工的工件中搜索，寻找下一个工件，其在所有未加工工件中加工时间最短，将其加至里，并将其作为当前加工工件，继续搜索并增加下一个加工工件，直至所有工件都加入加工顺序集。运用贪婪准则产生的是初始解序列，因而，需要将初始解序列转变为一定区间内的位置矢量。具体如式 (1)： xi, j = xmin, j + xmax, j − xmin, j n ·(si, j −1+r3), j = 1,2,··· ,m (1) xi, j si, j xmin, j xmax, j r3 式中：代表猫在 j 维的位置值；代表初始解序列的第 j 维工件序号；及表示猫在连续空间中位置矢量的上下界值；代表 [0，1] 区间内随机产生的随机数。初始位置及速度产生方式为 Xi = Xmin +(Xmax − Xmin)r1 (2) Vi = Vmin +(Vmax −Vmin)r2 (3) Xi [Xmin,Xmax] Vi [Vmin,Vmax] 式中：在区间内连续变化；在区间内连续变化。 2.3 基于混合比率的猫行为模式选择传统的猫群算法不能根据算法的迭代次数合理分配局部搜索和全局搜索的比重，若在算法迭代前期采用较大的混合比率的跟踪猫，可以增加算法的全局搜索能力，但在算法迭代后期搜寻猫所占比率较大，可以提高解精度和收敛性。因第 4 期裴小兵，等：改进猫群算法求解置换流水车间调度问题 ·771·

·772· 智能系统学报第14卷此，本研究采用文献[9]中的一种猫行为混合比工件相依矩阵D 123456 1 23456 率选择法，具体如图2所示。 1 202 1 -01/52/5025 30 2 /5-01/500 混合比率1 3 000 3/50-1/53/50 M 4 10 4 1/51/525-1/50 1 5 00151/5-1/5 6 100- 61/53/51/500- Ma. 图4相依矩阵更新方式 0 迭代次数 Fig.4 Updating method of dependency matrix 2.4.2组合区块图2混合比率分配 Fig.2 The allocation of mixed ratio 组合区块能够降低种群迭代复杂度，降低解的维度，加快收敛速度。以单个机器10个工件的该线性混合比率的计算公式为排序为例，如图5所示，未组合区块之前母体中的 Mx=Mg+(M&-Mk.)xT (4) 工件{工件1，工件2，…，工件10}为单独的基因， To 式中：T代表迭代次数；T。代表最大迭代次数。此时可产生10！种排列组合，而组合区块后排列组合变为5！种，在很大程度上降低了解的维度。 2.4搜寻模式为找出含有高竞争优势的区块，本研究从区块挖 2.4.1构建概率模型掘与区块竞争两个步骤来组合区块。本研究采用位置矩阵和相依矩阵来记载不同的加工信息，位置矩阵用来表示工件和所处加工工件图工件8 组合工件工件8工件工件I 工件7 区块位置之间的关系，相依矩阵用来表示任意两个工工件4 工件1可工件正件冈工件1可件之间的加工前后顺序。工件2 工件3 工件2工件9工件3工件6 工件9 对初始解的适应度函数值从小到大排序，选工件6 择前s个优秀解组成优秀解集合，0={「1，「2，…，T, 图5种群迭代复杂度比较同时位置矩阵及相依矩阵按以下方式更新： Fig.5 The comparison of iterative complexity of popula- 咸=器流手拉置上 tion (5) 1)区块挖掘 i=1,2,…,nj=1,2,…,mk=1,2,…,s 根据位置矩阵和相依矩阵模型提供的相关信 1,0=7,-0+2统息，进行相应的区块挖掘。以随机的方式选择区 k=1 (6) 块的起始位置，产生一个符合最小长度的空白区 i=1,2,…,n;j=1,2,…,m;k=1,2,…,s 块，设区块的最小长度为3。 =化架赛工作在空白区块中放人最适合的工件，为计算方 (7) i=1,2,…,;1=1,2,…,:k=1,2,…,s 便，将各工件在位置矩阵与相依矩阵中的累计结果转化为概率，同时，将两矩阵的概率整合成一 10=-+2 (8) 个合并概率(combination probability,CP),利用轮 i,l=1,2,…,m:j=1,2,…,m;k=1,2,…,s 盘赌对合并概率进行挑选，其中，起始位置按照具体位置、相依矩阵更新方式如图3、图4所示。依据位置矩阵的概率，以轮盘赌进行选择。选出第1个工件后，以合并概率对第2个、第3个工件位置位置矩阵P 123456 123456 等进行选择。经一系列研究发现，在进化前期前 001121 1001/51/52/51/5 后关系相比位置关系更能影响解序列的适应度高 012200 201/52/52/500 低，相反，在进化中后期位置关系比工件前后关 30 0110E33/500550 4 031001 403/51/5001/5 系更重要，因而在进化的不同阶段，令位置矩阵 2 1 1001 52/51/51/5001/5 的权重随着世代数由0.3增加到0.7，反之，相依 6 000122 60001/52/52/5 矩阵由0.7递减到0.3。合并概率的计算如式图3位置矩阵更新方式 (9)所示，其中，i代表工件编码、y表示i紧前工 Fig.3 Updating method of position matrix 件号码、j表示工件i所在的位置、n表示工件总

此，本研究采用文献 [9] 中的一种猫行为混合比率选择法，具体如图 2 所示。 O MR2 MR1 迭代次数混合比率图 2 混合比率分配 Fig. 2 The allocation of mixed ratio 该线性混合比率的计算公式为 MR = MR1 + ( MR2 − MR1 ) ×T T0 (4) 式中： T 代表迭代次数； T0 代表最大迭代次数。 2.4 搜寻模式 2.4.1 构建概率模型本研究采用位置矩阵和相依矩阵来记载不同的加工信息，位置矩阵用来表示工件和所处加工位置之间的关系，相依矩阵用来表示任意两个工件之间的加工前后顺序。 s ∂ ∂ = {Γ1,Γ2,··· ,Γs} 对初始解的适应度函数值从小到大排序，选择前个优秀解组成优秀解集合，，同时位置矩阵及相依矩阵按以下方式更新： B k i j = { 1, 如果工件i位于j位置上 0, 否则 i = 1,2,··· ,n; j = 1,2,··· ,m; k = 1,2,··· ,s (5) Ti j(t) = Ti j(t−1)+ ∑s k=1 B k i j, i = 1,2,··· ,n; j = 1,2,··· ,m; k = 1,2,··· ,s (6) Y k il = { 1, 如果工件i紧邻l 0, 否则 i = 1,2,··· ,n; l = 1,2,··· ,n; k = 1,2,··· ,s (7) Ti j(t) = Ti j(t−1)+ ∑s k=1 Y k i j, i,l = 1,2,··· ,n; j = 1,2,··· ,m; k = 1,2,··· ,s (8) 具体位置、相依矩阵更新方式如图 3、图 4 所示。位置位置矩阵 P 工件 1 2 2 3 3 4 4 5 5 6 0 0 3 0 2 0 0 1 0 3 1 0 1 2 0 1 1 0 1 2 1 0 0 1 2 0 1 0 0 2 1 0 0 1 1 2 0 0 3/5 0 2/5 0 0 1/5 0 3/5 1/5 0 1/5 2/5 0 1/5 1/5 0 1/5 2/5 1/5 0 0 1/5 2/5 0 1/5 0 0 2/5 1/5 0 0 1/5 1/5 2/5 6 1 1 1 2 3 4 5 6 2 3 4 5 6 图 3 位置矩阵更新方式 Fig. 3 Updating method of position matrix 工件相依矩阵 D 工件 1 2 2 3 3 4 4 5 5 6 − 1 1 1 0 1 0 − 1 1 0 3 1 0 − 2 1 1 2 1 0 − 1 0 0 3 0 1 − 0 2 0 0 0 1 − − 1/5 3/5 1/5 0 1/5 0 − 0 1/5 0 3/5 1/5 0 − 2/5 1/5 1/5 2/5 1/5 1/5 − 1/5 0 0 0 3/5 1/5 − 0 2/5 0 0 0 1/5 − 6 1 1 1 2 3 4 5 6 2 3 4 5 6 图 4 相依矩阵更新方式 Fig. 4 Updating method of dependency matrix 2.4.2 组合区块 ··· 组合区块能够降低种群迭代复杂度，降低解的维度，加快收敛速度。以单个机器 10 个工件的排序为例，如图 5 所示，未组合区块之前母体中的工件{工件 1，工件 2，，工件 10}为单独的基因，此时可产生 10！种排列组合，而组合区块后排列组合变为 5！种，在很大程度上降低了解的维度。为找出含有高竞争优势的区块，本研究从区块挖掘与区块竞争两个步骤来组合区块。组合工件1 区块工件1 工件2 工件3 工件2 工件3 工件4 工件5 工件6 工件7 工件8 工件9 工件10 工件4 工件5 工件6 工件8工件7 工件9 工件10 图 5 种群迭代复杂度比较 Fig. 5 The comparison of iterative complexity of population 1) 区块挖掘根据位置矩阵和相依矩阵模型提供的相关信息，进行相应的区块挖掘。以随机的方式选择区块的起始位置，产生一个符合最小长度的空白区块，设区块的最小长度为 3。 i γ i i n 在空白区块中放入最适合的工件，为计算方便，将各工件在位置矩阵与相依矩阵中的累计结果转化为概率，同时，将两矩阵的概率整合成一个合并概率 (combination probability，CP)，利用轮盘赌对合并概率进行挑选，其中，起始位置按照依据位置矩阵的概率，以轮盘赌进行选择。选出第 1 个工件后，以合并概率对第 2 个、第 3 个工件等进行选择。经一系列研究发现，在进化前期前后关系相比位置关系更能影响解序列的适应度高低 [17] ，相反，在进化中后期位置关系比工件前后关系更重要，因而在进化的不同阶段，令位置矩阵的权重随着世代数由 0.3 增加到 0.7，反之，相依矩阵由 0.7 递减到 0.3。合并概率的计算如式 (9) 所示，其中，代表工件编码、表示紧前工件号码、j 表示工件所在的位置、表示工件总 ·772· 智能系统学报第 14 卷

第4期裴小兵，等：改进猫群算法求解置换流水车间调度问题 ·773· 数、CP,表示工件i的合并概率、Waom与Wap分别 CP:=(Wdom X Pim)+(Wdep x PP) (9) 表示当前位置矩阵与相依矩阵的合并权重值、 i,y=1,2,…,;j=1,2,…,m 计算出所有工件的合并概率，并运用轮盘赌 P为位置矩阵中工件i处于位置j上的概率、选择出区块的第2个工件及第3个工件等，具体 P为相依矩阵中工件j紧前于工件i的概率。如图6所示。位置矩阵相依矩阵位置矩阵相依矩阵 123456 23456 23.456 1001121 001121 01202 位置矩阵“ 2012200 012200 -0130 123456 3300110 00 300110 311-000 100/S32S/S 031001 4112-10 0W32S2300 4031001 0 3/s00/5S0 5200▣ 0 5211001 50011- 0 3/5 L/S 00 L/S 6000122 6 3 0 6000122 613100- 52/s/S1/3001/s 6000232 合并概率合并概率小轮盘赌工件1的合并概率=0.3×1/5)+0.7×(1/5)=0.2 工.件1的合并概率=0.3×(2/5)+0.7×(0/5)=0.12 位置31 置4位置牛3的合并概率=0.3×(1/5)+0.7×(0/5)=0.06 工件4的合并概率=0.3×(0/5)+0.7×(1/5=0.14 工件3的合并概率=0.3×1/5+0.7×1/5=02 块工件5的合并概率=0.3×1/5)+0.7×(3/5)=0.48 工件4的合并概率=0.3×(0/5)+0.7×(1/5=0.14 工件5的合并概率=0.3×(2/5)+0.7×(0/5)=0.12 工件6的合并概率=0.3×2/5+0.7×(15=026 ↓轮盘赌 0轮盘赌位置3位置4位置5 位置3位置4位置5 25 256 图6以合并概率挖掘区块 Fig.6 Mining blocks by combining probability 随着区块长度的增长，总概率逐渐降低，即错式中：h为区块编号；B为第i个区块的第l个工误的概率越大。例如，一个由5个工件{工件1，件；j为B的位置；m1为当前区块长度。工件2，工件3，工件4，工件5}组成的区块，其概具体的区块竞争如图7所示，新产生的2个率分别为0.5、0.8、0.6、04、0.3，此区块的总概率区块{D,D2},区块库包含3个区块{D3,D4,D}, 0.5×0.8×0.6×0.4×0.3=0.0288,若该区块由3个工件新产生的区块D,与区块库中的D,重复出现工件 {工件1，工件2，工件3}组成，则总概率为0.5× 6,此时对D,与D3的平均概率进行比较，D,的平 0.8×0.6=0.24,由此可见，错误概率随着区块长度均概率为0.26，大于D3的平均概率0.23，故D1取的增长而变大。为保证区块的质量不会随着区块代D3进入区块库中，D3被淘汰删除。D2与D,在长度的增加而降低，设计一个阈值用以筛选上述挖掘的区块，阈值随着迭代次数的增加由0.24增位置11重叠，比较与D,的平均D2概率由图可知到0.8。将符合阈值的区块暂存在区块库中，区块 D2高于D4,故淘汰D4。D,未与任何区块发生工库中保留着本次迭代中全部符合阈值的区块。件或位置重复，因此继续保存于区块库中。 2)区块竞争区块区块库区块挖掘完成后，利用区块竞争选择竞争力位置3位置4位置5 位置3位置4置3 较大的区块，每迭代一次，其产生的区块与区块 D,256平均概率 D128 平均概率 0.26 0.24 位置13也置14位置1 平均概率库中的区块进行比较，最终选择其中竞争优势较位置11位置12位置13 D1037 大的区块，更新区块库。区块进行竞争时，如果 D:91114门平均概率 0.30 0.37 位置17置18位置19 D12615平均概率 0.42 几个区块之间工件重复或者区块之间包含的位置出现重复，利用平均概率对这几个区块比较，淘汰概率较小的区块。区块库平均概率的计算方法：区块的第一个工件位位置3位置4位置3 D256 平均概率置矩阵概率加上其余工件的合并概率之和除以区 0.26 位置11位置12位置1 D291114 平均概率块总长度，即可求出该区块的平均概率。平均概 0.37 位置17他置18位置19 率的计算如式(10)所示： D,2615平均概率 0.42 P+CP时 (10) 图7区块竞争 n Fig.7 The competition of blocks

CPi i Wdom Wdep P dom i, j P dep i,γ 数、表示工件的合并概率、与分别表示当前位置矩阵与相依矩阵的合并权重值、为位置矩阵中工件 i 处于位置 j 上的概率、为相依矩阵中工件 j 紧前于工件 i 的概率。 CPi = (Wdom × P dom i, j )+(Wdep × P dep i,γ ) i, γ = 1,2,··· ,n; j = 1,2,··· ,m (9) 计算出所有工件的合并概率，并运用轮盘赌选择出区块的第 2 个工件及第 3 个工件等，具体如图 6 所示。空白区块轮盘赌位置3位置4位置5 2 位置矩阵 1 2 2 3 3 4 4 5 6 5 6 0 0 3/5 0 2/5 0 0 1/5 0 3/5 1/5 0 1/5 2/5 0 1/5 1/5 0 1/5 2/5 1/5 0 0 1/5 2/5 0 1/5 0 0 2/5 1/5 0 0 1/5 1/5 2/5 1 轮盘赌位置3 位置4 位置5 2 5 合并概率位置矩阵相依矩阵工件1的合并概率 = 0.3×(1/5) + 0.7×(1/5) = 0.2 工件3的合并概率 = 0.3×(1/5) + 0.7×(0/5) = 0.06 工件4的合并概率 = 0.3×(0/5) + 0.7×(1/5) = 0.14 工件5的合并概率 = 0.3×(1/5) + 0.7×(3/5) = 0.48 工件5的合并概率 = 0.3×(2/5) + 0.7×(0/5) = 0.12 1 2 3 4 5 6 0 0 3 0 2 0 0 1 0 3 1 0 1 2 0 1 1 0 1 2 1 0 0 1 2 0 1 0 0 2 1 0 0 1 1 2 − 1 1 1 0 1 0 − 1 1 0 3 1 0 − 2 1 1 2 1 0 − 1 0 0 3 0 1 − 0 2 0 0 0 1 − 1 2 3 4 5 6 1 2 3 5 6 4 1 2 3 5 6 4 轮盘赌位置3 位置4 位置5 2 5 6 位置矩阵相依矩阵合并概率工件1的合并概率 = 0.3×(2/5) + 0.7×(0/5) = 0.12 工件3的合并概率 = 0.3×(1/5) + 0.7×(1/5) = 0.2 工件4的合并概率 = 0.3×(0/5) + 0.7×(1/5) = 0.14 工件6的合并概率 = 0.3×(2/5) + 0.7×(1/5) = 0.26 0 0 3 0 2 0 0 1 0 3 1 0 1 2 0 1 1 0 1 2 1 0 0 1 2 0 1 0 0 2 1 0 0 1 1 2 − 1 1 1 0 1 0 − 1 1 0 3 1 0 − 2 1 1 2 1 0 − 1 0 0 3 0 1 − 0 2 0 0 0 1 − 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 5 6 4 1 2 3 5 6 4 图 6 以合并概率挖掘区块 Fig. 6 Mining blocks by combining probability 随着区块长度的增长，总概率逐渐降低，即错误的概率越大。例如，一个由 5 个工件{工件 1，工件 2，工件 3，工件 4，工件 5}组成的区块，其概率分别为 0.5、0.8、0.6、0.4、0.3，此区块的总概率 0.5×0.8×0.6×0.4×0.3=0.028 8，若该区块由 3 个工件 {工件 1，工件 2，工件 3}组成，则总概率为 0.5× 0.8×0.6=0.24，由此可见，错误概率随着区块长度的增长而变大。为保证区块的质量不会随着区块长度的增加而降低，设计一个阈值用以筛选上述挖掘的区块，阈值随着迭代次数的增加由 0.24 增到 0.8。将符合阈值的区块暂存在区块库中，区块库中保留着本次迭代中全部符合阈值的区块。 2) 区块竞争区块挖掘完成后，利用区块竞争选择竞争力较大的区块，每迭代一次，其产生的区块与区块库中的区块进行比较，最终选择其中竞争优势较大的区块，更新区块库。区块进行竞争时，如果几个区块之间工件重复或者区块之间包含的位置出现重复，利用平均概率对这几个区块比较，淘汰概率较小的区块。平均概率的计算方法：区块的第一个工件位置矩阵概率加上其余工件的合并概率之和除以区块总长度，即可求出该区块的平均概率。平均概率的计算如式 (10) 所示： P AVG Bi = P dom B h l + ∑n1 l=2 CPB h l n1 (10) B h l i B h l n1 式中：h 为区块编号；为第个区块的第 l 个工件；j 为的位置；为当前区块长度。具体的区块竞争如图 7 所示，新产生的 2 个区块{D1，D2}，区块库包含 3 个区块{D3，D4，D5}，新产生的区块 D1 与区块库中的 D3 重复出现工件 6，此时对 D1 与 D3 的平均概率进行比较，D1 的平均概率为 0.26，大于 D3 的平均概率 0.23，故 D1 取代 D3 进入区块库中，D3 被淘汰删除。D2 与 D4 在位置 11 重叠，比较与 D4 的平均 D2 概率由图可知 D2 高于 D4，故淘汰 D4。D5 未与任何区块发生工件或位置重复，因此继续保存于区块库中。区块区块库区块库 D1 D2 D1 D2 D3 D4 D5 D5 位置3 位置4 位置5 位置3 位置4 位置5 位置3 位置4 位置5 位置11位置12位置13 位置17位置18位置19 位置13位置14位置15 位置17位置18位置19 位置11位置12位置13 平均概率 0.37 平均概率 0.26 平均概率 0.24 平均概率 0.30 平均概率 0.42 平均概率 0.26 平均概率 0.37 平均概率 0.42 2 5 6 1 2 8 10 3 7 12 6 15 2 5 6 9 11 14 12 6 15 9 11 14 图 7 区块竞争 Fig. 7 The competition of blocks 第 4 期裴小兵，等：改进猫群算法求解置换流水车间调度问题 ·773·

·774· 智能系统学报第14卷 2.4.3组合人工解利用遗传算法中的插入搜寻算子操作，对解序列为提高解序列的质量，在完成区块挖掘后重组，使得两个最短片段形成一个基因片段。若利用区块库中保留的区块组合人工解，具体步骤重组之后的片段不再是最短片段，则对解序列中如下：的最长片段及该片段按照合并概率重组，若区块 1)从人工解的第一个位置开始挖掘，挖掘方库含有以被选择的工件开头的区块，则直接插法与上述区块挖掘相同，第一个位置利用位置矩入，具体如图9和图10所示。阵中概率以轮盘赌的方式选择工件：位置2 位置7 2)其余N-1个位置以轮盘赌的形式对合并概 8 5 7 9 4111261 率进行选择； 3)每选出一个工件，将该工件与所有其他区位置2 位置7 块的起始位置进行比较，若与其他区块的位置及 57941181261 3 工件都相同，则将此区块直接复制到人工解中，然后从下个位置继续进行选择和比较，直至人工图9插入搜寻算子 Fig.9 Insert search operator 解组合完成。具体的操作方式如图8所示。位置1 位置7 工件位于位置1的概率 35794181261 Fm=0.38Fm=0.21 =0.14m=0.42 区块库具位置7 Pm=0.18 9 181261 工件位于位置2的合并概率位置2位置3位置4 D3457 CP,=0.28CP=0.17 CP,=0.31CP,=0.09 位置6位置7位置8位置9位置10 93 81261 8111261 工件位于位置3的合并概率 CP,=0.28CP,=0.11 位置17位置18位置19 934578261 CP=0.29 D6179 图10利用概率重组解序列 Fig.10 Using probability recombination solution sequence 位置1 几，选择最大的优势矩阵概率 2.5跟踪模式 3 猫的跟踪模式是为了使个体靠近全局最优几，选择最大的合并概率位置1 解，在该模式下，猫与群体最优位置进行比较来 34 更新个体速度与位置。跟踪模式可以根据以下位置1 ,与区块数据库中的区块对比两步进行。 345☑ 1)速度的更新。任意时刻，每个猫都有一个速度，第i只猫的位置1 当前速度可表示为V={w,y2,…,y,所有猫的速 3457 9 度按照式(11)进行更新：位置1 公餐辛钙武漆极瑕 V:(n+1)=V(n)×w+cxrand×[Xe(n)-V(n)](1l) 345798111261 w=Wmx-(Wmax -Wmin)x (f/fmax) (12) 式中：'(+1)表示更新后第i只猫的速度；w为惯图8人工解组合过程性权重，w的大小由式(12)决定；1表示迭代信 Fig.8 The combination process of artificial solution 息；1max表示最大迭代次数；c代表加速度常数； 2.4.4解序列重组 rand服从[0,1]均匀分布。为了增加该算法寻找最优解的概率，本研究 2)位置更新。对每只猫即解序列进行相应的重组操作。首先每每只猫的位置更新由式(13)决定：只猫在记忆池中将自身位置复制H份，对记忆池 X(n+1)=X(n)+Vn+1) (13) 中的猫即解序列进行相应的重组操作，使得所有式中X,(n+1)代表第i只猫更新后的位置。猫能够到达新位置，计算记忆池中所有猫的适应 3)如果第i只猫分的新位置超出搜索空间，度，然后将适应度最高的猫代替当前猫，以完成则将速度乘以-1，从反方向继续搜索。猫的位置更新。在记忆池进行变异操作时，为避 4)利用二元竞赛法更新解序列，即将母体种免局部最优及增加解序列的多样性，本研究将解群与子群的适应度两两对比并将适应度最高的子序列随机切成N个片段，选取最短的两个片段，群代替母体种群，进行下一次搜索

2.4.3 组合人工解为提高解序列的质量，在完成区块挖掘后，利用区块库中保留的区块组合人工解，具体步骤如下： 1) 从人工解的第一个位置开始挖掘，挖掘方法与上述区块挖掘相同，第一个位置利用位置矩阵中概率以轮盘赌的方式选择工件； 2) 其余 N−1 个位置以轮盘赌的形式对合并概率进行选择； 3) 每选出一个工件，将该工件与所有其他区块的起始位置进行比较，若与其他区块的位置及工件都相同，则将此区块直接复制到人工解中，然后从下个位置继续进行选择和比较，直至人工解组合完成。具体的操作方式如图 8 所示。区块库位置2 位置1 位置1 位置1 位置1 位置1 位置3 位置4 位置17位置18位置19 位置6 位置7 位置8 位置9位置10 D3 D4 D5 8 11 12 6 1 4 5 7 6 3 3 4 3 4 5 7 3 4 5 7 9 3 4 5 7 9 8 11 12 6 1 17 9 选择最大的优势矩阵概率选择最大的合并概率与区块数据库中的区块对比从剩余工件中选择最大的合并概率与其余区块比较图 8 人工解组合过程 Fig. 8 The combination process of artificial solution 2.4.4 解序列重组为了增加该算法寻找最优解的概率，本研究对每只猫即解序列进行相应的重组操作。首先每只猫在记忆池中将自身位置复制 H 份，对记忆池中的猫即解序列进行相应的重组操作，使得所有猫能够到达新位置，计算记忆池中所有猫的适应度，然后将适应度最高的猫代替当前猫，以完成猫的位置更新。在记忆池进行变异操作时，为避免局部最优及增加解序列的多样性，本研究将解序列随机切成 N 个片段，选取最短的两个片段，利用遗传算法中的插入搜寻算子操作，对解序列重组，使得两个最短片段形成一个基因片段。若重组之后的片段不再是最短片段，则对解序列中的最长片段及该片段按照合并概率重组，若区块库含有以被选择的工件开头的区块，则直接插入，具体如图 9 和图 10 所示。位置2 位置7 位置2 位置7 3 5 7 9 4 11 8 12 6 1 3 8 5 7 9 4 11 12 6 1 图 9 插入搜寻算子 Fig. 9 Insert search operator 位置1 位置7 位置7 9 11 8 12 6 1 9 3 11 8 12 6 1 9 3 4 5 7 11 8 12 6 1 3 5 7 9 4 11 8 12 6 1 工件位于位置1的概率工件位于位置2的合并概率工件位于位置3的合并概率 P dom 3, 1 = 0.38 P dom 5, 1 = 0.21 P dom 7, 1 = 0.14 P dom 9, 1 = 0.42 P dom 4, 1 = 0.18 CP3 = 0.28 CP5 = 0.17 CP7 = 0.31 CP4 = 0.09 CP7 = 0.28 CP5 = 0.11 CP4 = 0.29 图 10 利用概率重组解序列 Fig. 10 Using probability recombination solution sequence 2.5 跟踪模式猫的跟踪模式是为了使个体靠近全局最优解，在该模式下，猫与群体最优位置进行比较来更新个体速度与位置[18]。跟踪模式可以根据以下两步进行。 1) 速度的更新。 Vi = {vi1, vi2,··· , vil} 任意时刻，每个猫都有一个速度，第 i 只猫的当前速度可表示为，所有猫的速度按照式 (11) 进行更新： Vi(n+1) = Vi(n)×w+c×rand×[Xbest(n)−V(n)] (11) w = wmax −(wmax −wmin)×(t/tmax) (12) 式中：Vi (n+1) 表示更新后第 i 只猫的速度；w 为惯性权重，w 的大小由式 (12) 决定；t 表示迭代信息；tmax 表示最大迭代次数；c 代表加速度常数； rand 服从 [0，1] 均匀分布。 2) 位置更新。每只猫的位置更新由式（13）决定： Xi(n+1) = Xi(n)+Vi(n+1) (13) 式中 Xi(n+1) 代表第 i 只猫更新后的位置。 3) 如果第 i 只猫分的新位置超出搜索空间，则将速度乘以−1，从反方向继续搜索。 4) 利用二元竞赛法更新解序列，即将母体种群与子群的适应度两两对比并将适应度最高的子群代替母体种群，进行下一次搜索。 ·774· 智能系统学报第 14 卷

第4期裴小兵，等：改进猫群算法求解置换流水车间调度问题 ·775· 31 仿真测试 (C-C) ARE= ×100% C (15) 3.1参数设置 WRE= (Cmax-C) ×100% (16) 为了验证基于区块的猫群算法的性能，本研究测试数据采用Carlier9中的Car类基准例题集 3.2实验测试与比较进行测试，应用该算法求解这些案例，并与其他针对Carlier例题，本研究将基于分布估计算文献中的算法进行比较。本研究程序利用Visual 法的改进猫群算法(EDA-CSO)与猫群算法 Studio2015中的C+,在操作系统为Windows8,处 (CSO)21、标准粒子群算法(PSO)2)、蝙蝠算法理器的主频为2.71G的Intel(R)Core(TMi5- (BA)☒进行比较。具体比较结果如表1所示。 6400处理器8G内存的电脑上进行仿真测试。参由表1和图11、图12可知，尽管这4种算法数设计：仿真测试次数为20，初始种群的数量为在Carlier案例中均能求出问题的最优解(BRE 为O),然而EDA-CSO的ARE均优于其他算法。 100,最大的迭代次数为100。本研究将各个算法表明了本算法的整体求解性能优于其他算法。此的最优相对误差(BRE)、平均相对误差(ARE)及外，EDA-CSO显然比CSO、PSO、BA的ARE和最差相对误差(WRE)进行比较。其中，C表示已 WRE更小，这是因为通过调整猫的混合比率，迭知算例的最优解，Cm表示所求解的最优值，C表代前期采用较大的混合比率的跟踪猫，增加了算示所求解的平均值，C表示所求解的最差值。法的全局搜索能力，在算法迭代后期增加搜寻猫 BRE=Cm-C)x100% (14) 所占比率较大，增加了局部搜索能力，减少了求 C 解误差，提高了精度和收敛性，因此EDA-CSO算表1EDA-CSO、CSO、PSO和BA的测试结果对比 Table 1 Comparison of test results for EDA-CSO,CSO.PSO and BA EDA-CSO CSO PSO BA 算例 n、m BRE ARE WRE BRE ARE WRE BRE ARE WRE BRE ARE WRE Car 11、57038 0.00 0.01 0.20 0.000.02 0.27 0.000.52 2.72 0.00 0.32 1.68 Car213、47166 0.00 1.37 5.00 0.002.76 6.01 0.00 5.22 10.8 0.00 3.68 6.29 Car3 12、57312 0.001.85 3.17 0.002.03 3.86 0.00 3.77 9.04 0.00 2.36 3.87 Car4 14、480030.00 0.37 4.98 0.000.44 5.25 0.003.86 6.55 0.00 2.64 5.25 Cars 10、777200.000.18 1.090.000.29 1.31 0.001.24 2.12 0.00 1.01 1.84 Car 8、9 85050.000.52 2.12 0.000.77 2.47 0.00 2.06 5.7 0.001.44 3.39 Car? 7、765900.000.15 2.03 0.000.24 2.47 0.00 1.61 4.51 0.00 0.91 2.58 Cars 8、883660.00 0.09 1.01 0.00 0.29 1.33 0.00 3.85 8.88 0.00 1.08 2.51 12 -BBCSO -BBCSO CS0 --PSO ..PSO -BA -BA 8 3 6 2 0 2 34567 0 34567 案例编号案例编号图11平均相对误差比较图12最差相对误差比较 Fig.11 Comparison of average relative error Fig.12 Comparison of the worst relative error 法明显优于文中其他算法。分布估计算法(BBEDA)刀、基于粒子群算法的为进一步验证算法的有效性，针对Reeves2o 分布估计算法(PS0-EDA)2川各迭代20000次例题，将基于猫群算法的改进估计分布算法并进行比较。具体结果如表2所示。其中，Cmm表 (EDA-CSO)与猫群算法(CSO)1o1、基于区块的示所求解的最优值，s;G表示算法的运行时间，s

3 仿真测试 3.1 参数设置 Cmin C Cmax 为了验证基于区块的猫群算法的性能，本研究测试数据采用 Carlier[19] 中的 Car 类基准例题集进行测试，应用该算法求解这些案例，并与其他文献中的算法进行比较。本研究程序利用 Visual Studio2015 中的 C++，在操作系统为 Windows8，处理器的主频为 2.71 G 的 Intel(R)Core(TM)i5- 6400 处理器 8 G 内存的电脑上进行仿真测试。参数设计：仿真测试次数为 20，初始种群的数量为 100，最大的迭代次数为 100。本研究将各个算法的最优相对误差 (BRE)、平均相对误差 (ARE) 及最差相对误差 (WRE) 进行比较。其中，C *表示已知算例的最优解，表示所求解的最优值，表示所求解的平均值，表示所求解的最差值。 BRE = (Cmin−C ∗ ) C∗ ×100% (14) ARE = (C¯−C ∗ ) C∗ ×100% (15) WRE = (Cmax−C ∗ ) C∗ ×100% (16) 3.2 实验测试与比较针对 Carlier 例题，本研究将基于分布估计算法的改进猫群算法 (EDA-CSO) 与猫群算法 (CSO)[12] 、标准粒子群算法 (PSO)[12] 、蝙蝠算法 (BA)[12] 进行比较。具体比较结果如表 1 所示。由表 1 和图 11、图 12 可知，尽管这 4 种算法在 Carlier 案例中均能求出问题的最优解 (BRE 为 0)，然而 EDA-CSO 的 ARE 均优于其他算法。表明了本算法的整体求解性能优于其他算法。此外，EDA-CSO 显然比 CSO、PSO、BA 的 ARE 和 WRE 更小，这是因为通过调整猫的混合比率，迭代前期采用较大的混合比率的跟踪猫，增加了算法的全局搜索能力，在算法迭代后期增加搜寻猫所占比率较大，增加了局部搜索能力，减少了求解误差，提高了精度和收敛性，因此 EDA-CSO 算法明显优于文中其他算法。为进一步验证算法的有效性，针对 Reeves[20] 例题，将基于猫群算法的改进估计分布算法 (EDA-CSO) 与猫群算法 (CSO)[10] 、基于区块的分布估计算法 (BBEDA)[17] 、基于粒子群算法的分布估计算法 (PSO-EDA)[ 2 1 ] 各迭代 20 000 次并进行比较。具体结果如表 2 所示。其中，Cmin 表示所求解的最优值，s；G 表示算法的运行时间，s。表 1 EDA-CSO、CSO、PSO 和 BA 的测试结果对比 Table 1 Comparison of test results for EDA-CSO、 CSO、PSO and BA 算例 n、m C * EDA-CSO CSO PSO BA BRE ARE WRE BRE ARE WRE BRE ARE WRE BRE ARE WRE Car1 11、5 7 038 0.00 0.01 0.20 0.00 0.02 0.27 0.00 0.52 2.72 0.00 0.32 1.68 Car2 13、4 7 166 0.00 1.37 5.00 0.00 2.76 6.01 0.00 5.22 10.8 0.00 3.68 6.29 Car3 12、5 7 312 0.00 1.85 3.17 0.00 2.03 3.86 0.00 3.77 9.04 0.00 2.36 3.87 Car4 14、4 8 003 0.00 0.37 4.98 0.00 0.44 5.25 0.00 3.86 6.55 0.00 2.64 5.25 Car5 10、7 7 720 0.00 0.18 1.09 0.00 0.29 1.31 0.00 1.24 2.12 0.00 1.01 1.84 Car6 8、9 8 505 0.00 0.52 2.12 0.00 0.77 2.47 0.00 2.06 5.7 0.00 1.44 3.39 Car7 7、7 6 590 0.00 0.15 2.03 0.00 0.24 2.47 0.00 1.61 4.51 0.00 0.91 2.58 Car8 8、8 8 366 0.00 0.09 1.01 0.00 0.29 1.33 0.00 3.85 8.88 0.00 1.08 2.51 0 6 5 4 3 2 1 1 2 3 4 案例编号平均百分比误差 ARE/% 5 6 7 8 BBCSO CSO PSO BA 图 11 平均相对误差比较 Fig. 11 Comparison of average relative error 0 12 10 8 6 4 2 1 2 3 4 案例编号最差百分比误差 WRE/% 5 6 7 8 BBCSO CSO PSO BA 图 12 最差相对误差比较 Fig. 12 Comparison of the worst relative error 第 4 期裴小兵，等：改进猫群算法求解置换流水车间调度问题 ·775·

·776· 智能系统学报第14卷表2 Reeves案例测试结果比较 Table 2 Performance comparison on Reeves's instances EDA-CSO CSO PSO-EDA BBEDA 算例 n、m C* Cmin/s BRE Gls Cmir/s BRE Gls Cmin/s BRE Gls Cmin/S BRE Gls Rec01 20、512471247 0.00 2.5 1247 0.00 2.0 1247 0.00 3.0 1247 0.00 2.7 Rec0320、5110911090.00 3.0 11090.00 3.0 11090.00 2.9 11090.00 3.2 Rec0520、5124212420.00 2.1 12450.24 1.0 12450.24 1.3 12420.00 1.9 Rec0720、10156615660.00 3.1 15660.00 3.0 15660.00 2.5 15660.00 3.6 Rec0920、10153715370.00 2.0 15370.00 2.0 15370.00 2.3 15370.00 2.5 Rec1120、101431 14310.00 1.0 14310.00 1.0 14310.00 2.1 14310.00 1.8 Rec1320、15 1930 1930 0.00 110 1930 0.00 178.0 19300.10 181.1 19300.00 119.0 Recl520、15 1950 1950 1950 0.00 101.0 19500.00 101.7 19500.00 100.0 Rec1720、15 1902 1902 1902 000 115.8 19020.00 119.0 19020.00 110.2 Rec1930、10 209 29 02 40 2099 029 20990.29 37.0 20990.29 36.9 Rec2130、10 36q 2020 01 486.2 2040 114 484.0 20360.94 374.0 Rec2330、10 201 2017 2020 41 219 2019 040 26.3 20200.45 15.2 Rec2530、15 2 341 2525 0.48 377. 2520 0.28 369 25300.68 352.6 Rec2730、15 373 739 0.97 60.8 2396 0.97 59.8 23790.25 69.4 Rec2930、15 2287 2289 0.09 259. 2305 0.79 332.1 2295 0.35 267.7 22920.22 268.5 Rec3150、103045 3051 22 3058 0.43 900.0 30530.26 608.5 30560.36 610.2 Rec3350、103114 31140.00 123.8 31140.00 163.0 31140.00 125.9 31140.00 131.7 Rec3550、10327732770.00 4.6 32770.00 7.1 32770.00 8.7 32770.00 7.5 Rec3775、20495150041.08943.0 50962.931583.0 50411.84 850.0 5111 3.23 867.1 Rec3975、20508751250.74395.051611.45 568.1 51340.92 639.0 5189 2.01 644.0 Rec4175、20496050080.981542.050872.562071.050501.821601.051154.261550.1 由表2可知，由于增加算子，尽管本算法在求 1700 .....BBEDA 解Rec0l、Rec05、Rec07时，处理时间上慢于 1650 -EDA-CSO CSO算法，但BRE均优于CSO、BBEDA及PSO- U1600 EDA算法。这是因为虽然迭代过程中增加了算厘1550 子，但由于区块具有降维的作用，且随着问题复 150 杂度的增加，效果越明显，因而在一定程度上降 1450 低了运算时间。为直观体现本算法降低复杂度， 1400 10 15 加快收敛速度的性能，以EDA-CSO、BBEDA求迭代次数T 解Rec09、Recl1、Recl3、Recl5为例，具体如图图14Rec11收敛图 13-16所示。 Fig.14 Rec11 convergence graph 1800 2300 -BBEDA BBEDA 1750 -EDA-CSO 2250 -EDA-CSO 2200 1700 2150 三2100 1600 至2050 识2000 1550 1950 1500 10 15 20lo: 1900 10 15 迭代次数T 迭代次数T 图13Rec09收敛图图15Rec13收敛图 Fig.13 Rec09 convergence graph Fig.15 Rec13 convergence graph

表 2 Reeves 案例测试结果比较 Table 2 Performance comparison on Reeves’s instances 算例 n、m C* EDA-CSO CSO PSO-EDA BBEDA Cmin/s BRE G/s Cmin/s BRE G/s Cmin/s BRE G/s Cmin/s BRE G/s Rec01 20、5 1 247 1 247 0.00 2.5 1 247 0.00 2.0 1 247 0.00 3.0 1 247 0.00 2.7 Rec03 20、5 1 109 1 109 0.00 3.0 1 109 0.00 3.0 1 109 0.00 2.9 1 109 0.00 3.2 Rec05 20、5 1 242 1 242 0.00 2.1 1 245 0.24 1.0 1 245 0.24 1.3 1 242 0.00 1.9 Rec07 20、10 1 566 1 566 0.00 3.1 1 566 0.00 3.0 1 566 0.00 2.5 1 566 0.00 3.6 Rec09 20、10 1 537 1 537 0.00 2.0 1 537 0.00 2.0 1 537 0.00 2.3 1 537 0.00 2.5 Rec11 20、10 1 431 1 431 0.00 1.0 1 431 0.00 1.0 1 431 0.00 2.1 1 431 0.00 1.8 Rec13 20、15 1 930 1 930 0.00 114.0 1 930 0.00 178.0 1 930 0.10 181.1 1 930 0.00 119.0 Rec15 20、15 1 950 1 950 0.00 99.0 1 950 0.00 101.0 1 950 0.00 101.7 1 950 0.00 100.0 Rec17 20、15 1 902 1 902 0.00 108.0 1 902 0.00 115.8 1 902 0.00 119.0 1 902 0.00 110.2 Rec19 30、10 2 093 2 097 0.21 14.0 2 099 0.29 18.1 2 099 0.29 37.0 2 099 0.29 36.9 Rec21 30、10 2 017 2 019 0.10 369.0 2 020 0.15 486.2 2 040 1.14 484.0 2 036 0.94 374.0 Rec23 30、10 2 011 2 017 0.30 13.0 2 020 0.45 21.9 2 019 0.40 26.3 2 020 0.45 15.2 Rec25 30、15 2 513 2 515 0.11 341.1 2 525 0.48 377.1 2 520 0.28 369 2 530 0.68 352.6 Rec27 30、15 2 373 2 373 0.00 53.3 2 396 0.97 60.8 2 396 0.97 59.8 2 379 0.25 69.4 Rec29 30、15 2 287 2 289 0.09 259.0 2 305 0.79 332.1 2 295 0.35 267.7 2 292 0.22 268.5 Rec31 50、10 3 045 3 051 0.22 604.1 3 058 0.43 900.0 3 053 0.26 608.5 3 056 0.36 610.2 Rec33 50、10 3 114 3 114 0.00 123.8 3 114 0.00 163.0 3 114 0.00 125.9 3 114 0.00 131.7 Rec35 50、10 3 277 3 277 0.00 4.6 3 277 0.00 7.1 3 277 0.00 8.7 3 277 0.00 7.5 Rec37 75、20 4 951 5 004 1.08 943.0 5 096 2.93 1 583.0 5 041 1.84 850.0 5 111 3.23 867.1 Rec39 75、20 5 087 5 125 0.74 395.0 5 161 1.45 568.1 5 134 0.92 639.0 5 189 2.01 644.0 Rec41 75、20 4 960 5 008 0.98 1 542.0 5 087 2.56 2 071.0 5 050 1.82 1 601.0 5 115 4.26 1 550.1 由表 2 可知，由于增加算子，尽管本算法在求解 Rec01、Rec05、Rec07 时，处理时间上慢于 CSO 算法，但 BRE 均优于 CSO、BBEDA 及 PSOEDA 算法。这是因为虽然迭代过程中增加了算子，但由于区块具有降维的作用，且随着问题复杂度的增加，效果越明显，因而在一定程度上降低了运算时间。为直观体现本算法降低复杂度，加快收敛速度的性能，以 EDA-CSO、BBEDA 求解 Rec09、Rec11、Rec13、Rec15 为例，具体如图 13~16 所示。 0 1 800 1 750 1 700 1 650 1 600 1 550 1 500 5 10 15 迭代次数 T 完工时间 Cmax/s 20 ×103 EDA-CSO BBEDA 图 13 Rec09 收敛图 Fig. 13 Rec09 convergence graph 0 1 700 1 650 1 600 1 550 1 500 1 450 1 400 5 10 15 迭代次数 T 完工时间 Cmax/s 20 EDA-CSO BBEDA ×103 图 14 Rec11 收敛图 Fig. 14 Rec11 convergence graph 0 2 300 2 250 2 200 2 150 2 100 2 050 2 000 1 950 1 900 5 10 15 迭代次数 T 完工时间 Cmax/s 20 EDA-CSO BBEDA ×103 图 15 Rec13 收敛图 Fig. 15 Rec13 convergence graph ·776· 智能系统学报第 14 卷

第4期裴小兵，等：改进猫群算法求解置换流水车间调度问题 ·777· 2200 BBEDA 4099:854-858 2150 -EDA-CSO [4]GANAPATI P,PRADHAN P M,MAJHI B.II R system J2100 identification using cat swarm optimization[J].Expert sys- ▣2050 吾200 tems with applications,2011,38(10):12671-12683. [5]PRADHAN P M.PANDA G.Solving multiobjective prob- 1950 1900 103 lems using cat swarm optimization[J].Expert systems with 0 10 20 applications,2012,39(3):2956-2964 迭代次数T [6]GUO Lei,MENG Zhuo,SUN Yize,et al.A modified cat 图16Recl5收敛图 Fig.16 Rec15 convergence graph swarm optimization based maximum power point tracking method for photovoltaic system under partially shaded con- 从图13~16可以看出，在相同的迭代次数下， dition[J].Energy,2018,144:501-514. EDA-CSO与BBED算法相比，尽管两者最优误差 [7]PAPPULA L,GHOSH D.Cat swarm optimization with 均为O,但EDA-CSO的收敛速度均优于BBEDA normal mutation for fast convergence of multimodal func- 算法的收敛速度。 tions[J].Applied soft computing,2018,66:473-491. 4结束语 [8]TSAI P W,PAN JS,CHEN S M,et al.Parallel cat swarm optimization[C]//Proceedings of 2008 International Con- 本研究在猫群算法的基础上进行改进，提出 ference on Machine Learning and Cybernetics.Kunming, 了基于分布估计算法的改进猫群算法，用以解决 China.2008:3328-3333. 置换流水车间调度问题。在猫搜寻阶段，运用贪 [9]刘琼，范正伟，张超勇，等.基于多目标猫群算法的混流婪准则于轮盘赌相结合的方式初始化种群，加快装配线排序问题).计算机集成制造系统，2014,20(2) 收敛速度；采用位置矩阵与相依矩阵结合的方式 333-342 挖掘区块；利用区块竞争产生人工解；在不同的 LIU Qiong,FAN Zhengwei,ZHANG Chaoyong,et al 进化阶段采用不同的变异方式以提高人工解的质 Mixed model assembly line sequencing problem based on 量和多样性；同时，为了使个体靠近全体最优解， multi-objective cat swarm optimization[J].Computer in- 通过与群体最优位置进行比较来更新个体速度与 tegrated manufacturing system,2014,20(2):333-342. 位置。针对Carlier和Reeves标准案例运用该算 [10]BOUZIDI A,RIFFI M E.Cat swarm optimization to 法进行求解，最后，将各个算法的实验结果进行 solve flow shop scheduling problem[J].Journal of theor- 比较，验证了该算法的有效性和鲁棒性。 etical and applied information technology,2015,72(2): 本研究仅将该算法应用于置换流水车间调度 239-243. 问题，未将该算法应用于混流生产线、TSP等其 [11]BOUZIDI A,RIFFI M E.Cat swarm optimization to 他组合优化问题，今后可以进一步从这几个方面 solve job shop scheduling problem[C]//Proceedings of the 展开研究。 Third IEEE International Colloquium in Information Sci- 参考文献： ence and Technology.Tetouan,Morocco,2015:202-205. [12]马邦雄，叶春明.利用猫群算法求解流水车间调度问题 [1]GAREY M R.JOHNSON D S,SETHI R.The complexity [).现代制造工程，20146：12-15,71 of flowshop and jobshop scheduling[J].Mathematics of MA Bangxiong,YE Chunming.The research of flow- operations research,1976,1(2):117-129. shop scheduling problem based on cat swarm optimiza- [2]李小缤，白焰，耿林霄.求解置换流水车间调度问题的改 tion[J].Modern manufacturing engineering,2014(6): 进遗传算法J.计算机应用，2013,33(12)：3576-3579. 12-15,71. LI Xiaobin,BAI Yan,GENG Linxiao,et al.Improved ge- [13]陶新民，徐鹏，刘福荣，等.组合分布估计和差分进化的 netic algorithm for solving permutation flow shop schedul- 多目标优化算法[J.智能系统学报，2013,8(1：39-45. ing problem[J].Journal of computer applications,2013, TAO Xinmin,XU Peng,LIU Furong,et al.Multi-object- 33(12):3576-3579. ive optimization algorithm composed of estimation of dis- [3]CHU Shuchuan,TSAI P W,PAN J S.Cat swarm optimiza- tribution and differential evolution[J].CAAI transactions tion[C]//Proceedings of the 9th Pacific Rim International on intelligent systems,2013,8(1):39-45. Conference on Artificial Intelligence.Guilin,China,2006, [14]TZENG Y R,CHEN C L.CHEN C L.A hybrid EDA

0 2 200 2 150 2 100 2 050 2 000 1 950 1 900 5 10 15 迭代次数 T 完工时间 Cmax/s 20 EDA-CSO BBEDA ×103 图 16 Rec15 收敛图 Fig. 16 Rec15 convergence graph 从图 13~16 可以看出，在相同的迭代次数下， EDA-CSO 与 BBED 算法相比，尽管两者最优误差均为 0，但 EDA-CSO 的收敛速度均优于 BBEDA 算法的收敛速度。 4 结束语本研究在猫群算法的基础上进行改进，提出了基于分布估计算法的改进猫群算法，用以解决置换流水车间调度问题。在猫搜寻阶段，运用贪婪准则于轮盘赌相结合的方式初始化种群，加快收敛速度；采用位置矩阵与相依矩阵结合的方式挖掘区块；利用区块竞争产生人工解；在不同的进化阶段采用不同的变异方式以提高人工解的质量和多样性；同时，为了使个体靠近全体最优解，通过与群体最优位置进行比较来更新个体速度与位置。针对 Carlier 和 Reeves 标准案例运用该算法进行求解，最后，将各个算法的实验结果进行比较，验证了该算法的有效性和鲁棒性。本研究仅将该算法应用于置换流水车间调度问题，未将该算法应用于混流生产线、TSP 等其他组合优化问题，今后可以进一步从这几个方面展开研究。参考文献： GAREY M R, JOHNSON D S, SETHI R. The complexity of flowshop and jobshop scheduling[J]. Mathematics of operations research, 1976, 1(2): 117–129. [1] 李小缤, 白焰, 耿林霄. 求解置换流水车间调度问题的改进遗传算法 [J]. 计算机应用, 2013, 33(12): 3576–3579. LI Xiaobin, BAI Yan, GENG Linxiao, et al. Improved genetic algorithm for solving permutation flow shop scheduling problem[J]. Journal of computer applications, 2013, 33(12): 3576–3579. [2] CHU Shuchuan, TSAI P W, PAN J S. Cat swarm optimization[C]//Proceedings of the 9th Pacific Rim International Conference on Artificial Intelligence. Guilin, China, 2006, [3] 4099: 854–858. GANAPATI P, PRADHAN P M, MAJHI B. ⅡR system identification using cat swarm optimization[J]. Expert systems with applications, 2011, 38(10): 12671–12683. [4] PRADHAN P M, PANDA G. Solving multiobjective problems using cat swarm optimization[J]. Expert systems with applications, 2012, 39(3): 2956–2964. [5] GUO Lei, MENG Zhuo, SUN Yize, et al. A modified cat swarm optimization based maximum power point tracking method for photovoltaic system under partially shaded condition[J]. Energy, 2018, 144: 501–514. [6] PAPPULA L, GHOSH D. Cat swarm optimization with normal mutation for fast convergence of multimodal functions[J]. Applied soft computing, 2018, 66: 473–491. [7] TSAI P W, PAN J S, CHEN S M, et al. Parallel cat swarm optimization[C]//Proceedings of 2008 International Conference on Machine Learning and Cybernetics. Kunming, China, 2008: 3328–3333. [8] 刘琼, 范正伟, 张超勇, 等. 基于多目标猫群算法的混流装配线排序问题 [J]. 计算机集成制造系统, 2014, 20(2): 333–342. LIU Qiong, FAN Zhengwei, ZHANG Chaoyong, et al. Mixed model assembly line sequencing problem based on multi-objective cat swarm optimization[J]. Computer integrated manufacturing system, 2014, 20(2): 333–342. [9] BOUZIDI A, RIFFI M E. Cat swarm optimization to solve flow shop scheduling problem[J]. Journal of theoretical and applied information technology, 2015, 72(2): 239–243. [10] BOUZIDI A, RIFFI M E. Cat swarm optimization to solve job shop scheduling problem[C]//Proceedings of the Third IEEE International Colloquium in Information Science and Technology. Tetouan, Morocco, 2015: 202–205. [11] 马邦雄, 叶春明. 利用猫群算法求解流水车间调度问题 [J]. 现代制造工程, 2014(6): 12–15, 71. MA Bangxiong, YE Chunming. The research of flowshop scheduling problem based on cat swarm optimization[J]. Modern manufacturing engineering, 2014(6): 12–15, 71. [12] 陶新民, 徐鹏, 刘福荣, 等. 组合分布估计和差分进化的多目标优化算法 [J]. 智能系统学报, 2013, 8(1): 39–45. TAO Xinmin, XU Peng, LIU Furong, et al. Multi-objective optimization algorithm composed of estimation of distribution and differential evolution[J]. CAAI transactions on intelligent systems, 2013, 8(1): 39–45. [13] [14] TZENG Y R, CHEN C L, CHEN C L. A hybrid EDA 第 4 期裴小兵，等：改进猫群算法求解置换流水车间调度问题 ·777·

点击进入文档下载页（PDF格式）

已到末页，全文结束

点击下载（PDF格式）

浏览记录