第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·
·778· 智能系统学报 第14卷 with ACS for solving permutation flow shop scheduling cing[J].Computers and operations research,1995,22(1): [J].The international journal of advanced manufacturing 5-13. technology,2012,60(9/10/11/12:1139-1147. [21]LIU Hongcheng,GAO Liang,PAN Quanke.A hybrid [15]CHANG PC.HUANG W H,TING C J.Dynamic di- particle swarm optimization with estimation of distribu- versity control in genetic algorithm for mining un- tion algorithm for solving permutation flowshop schedul- searched solution space in TSP problems[J].Expert sys- ing problem[J].Expert systems with applications,2011, tems with applications,2010,37(3):1863-1878. 38(4):4348-4360 [16]KIM D,HALDAR J P.Greedy algorithms for nonnegat- 作者简介： ivity-constrained simultaneous sparse recovery[J].Signal 裴小兵，男，1965年生.教授，博 processing.2016,125:274-289. 土，天津工业工程学会理事，主要研究 [17]CHANG PC,CHEN Menghui.A block based estimation 方向为生产调度、系统仿真。发表学 of distribution algorithm using bivariate model for 术论文30余篇。 scheduling problems[J].Soft computing,2014,18(6): 1177-1188. [18]RAUTRAY R,BALABANTARAY R C.Cat swarm op- timization based evolutionary framework for multi docu- 于秀燕，女，1992年生，硕士研究 ment summarization[J].Physica a:statistical mechanics 生，主要研究方向为生产调度、系统 仿真。 and its applications,2017,477:174-186. [19]CARLIER J.Ordonnancements a contraintes disjonctives [J].RAIRO-operations research,1978,12(4):333-350. [20]REEVES C R.A genetic algorithm for flowshop sequen-
with ACS for solving permutation flow shop scheduling [J]. The international journal of advanced manufacturing technology, 2012, 60(9/10/11/12): 1139–1147. CHANG P C, HUANG W H, TING C J. Dynamic diversity control in genetic algorithm for mining unsearched solution space in TSP problems[J]. Expert systems with applications, 2010, 37(3): 1863–1878. [15] KIM D, HALDAR J P. Greedy algorithms for nonnegativity-constrained simultaneous sparse recovery[J]. Signal processing, 2016, 125: 274–289. [16] CHANG P C, CHEN Menghui. A block based estimation of distribution algorithm using bivariate model for scheduling problems[J]. Soft computing, 2014, 18(6): 1177–1188. [17] RAUTRAY R, BALABANTARAY R C. Cat swarm optimization based evolutionary framework for multi document summarization[J]. Physica a: statistical mechanics and its applications, 2017, 477: 174–186. [18] CARLIER J. Ordonnancements à contraintes disjonctives [J]. RAIRO-operations research, 1978, 12(4): 333–350. [19] [20] REEVES C R. A genetic algorithm for flowshop sequencing[J]. Computers and operations research, 1995, 22(1): 5–13. LIU Hongcheng, GAO Liang, PAN Quanke. A hybrid particle swarm optimization with estimation of distribution algorithm for solving permutation flowshop scheduling problem[J]. Expert systems with applications, 2011, 38(4): 4348–4360. [21] 作者简介： 裴小兵，男，1965 年生，教授，博 士，天津工业工程学会理事，主要研究 方向为生产调度、系统仿真。发表学 术论文 30 余篇。 于秀燕，女， 1992 年生，硕士研究 生，主要研究方向为生产调度、系统 仿真。 ·778· 智 能 系 统 学 报 第 14 卷
