正在加载图片...
第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 EDA0 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·