g支配策略的MOEA/D算法求解多目标流水车间调度问题
|
摘要
采用基于二范数的方法生成权重向量并引入g支配策略对MOEA/D算法进行改进,提出g支配策略的MOEA/D算法(g-MOEA/D).将g支配思想与MOEA/D算法有效结合,生成适应决策者DM偏好的有效解的集合,来代替整个Pareto解集或单个有效解,加速种群的收敛性,提高种群的均匀性.通过仿真实验对比分析g-MOEA/D算法与MOEA/D算法的性能,结果表明,g支配策略的MOEA/D算法所得解集整体性能更优.
To improve MOEA/D,the MOEA/D algorithm with g-dominating strategy(g-MOEA/D)is proposed. In g-MOEA/D,weight vectors are generated by the method based on 2-Norm and g-dominating strategy is adopted. By combining MOEA/D and g-dominating strategy,the solution set that can embody the decision-maker's preference can be generated. This set is used to take the place of the entire Pareto solution set or the single effective solution. Then the convergence of the population can be accelerated and the uniformity of the population can be improved. The performance of g-MOEA/D and MOEA/D are compared and analyzed by simulation experiments. The experimental results show that the overall performance of the solutions obtained by g-MOEA/D is better.
To improve MOEA/D,the MOEA/D algorithm with g-dominating strategy(g-MOEA/D)is proposed. In g-MOEA/D,weight vectors are generated by the method based on 2-Norm and g-dominating strategy is adopted. By combining MOEA/D and g-dominating strategy,the solution set that can embody the decision-maker's preference can be generated. This set is used to take the place of the entire Pareto solution set or the single effective solution. Then the convergence of the population can be accelerated and the uniformity of the population can be improved. The performance of g-MOEA/D and MOEA/D are compared and analyzed by simulation experiments. The experimental results show that the overall performance of the solutions obtained by g-MOEA/D is better.
引文
[1]潘全科.流水车间调度及其优化算法[M].武汉:华中科技大学出版社,2013:5-9.
[2]李智.智能优化算法研究及应用展望[J].武汉轻工大学学报,2016,35(4):1-9.
[3]崔琪,吴秀丽,余建军.变邻域改进遗传算法求解混合流水车间调度问题[J].计算机集成制造系统,2017,23(9):1917-1927.
[4]BOZEJKO W,PEMPERA J,SMUTNICKI C. Parallel tabu search algorithm for the hybrid flow shop problem[J]. Computers&Industrial Engineering,2013,65(3):466-474.
[5]黄明,郝倩,张春蕾,等.改进的免疫模拟退火算法求解混合流水车间调度问题[J].大连交通大学学报,2015,36(2):96-100.
[6]徐华,张庭.改进离散粒子群算法求解柔性流水车间调度问题[J].计算机应用,2015,35(5):1342-1347.
[7]ZHANG Q,LI H. MOEA/D:amultiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation,2007,11(6):712-731.
[8]LI H,ZHANG Q. Multiobjective optimization problems with complicated pareto sets,MOEA/D and NSGA-II[J]. IEEE Transactions on Evolutionary Computation,2009,13(2):284-302.
[9]ISHIBUCHI H,SAKANE Y,TSUKAMOTO N,et al. Simultaneous use of different scalarizing functions in MOEA/D[C]//Proceedings of Genetic and Evolutionary Computation Conference. Portland:ACM Press,2010:519-526.
[10]郑金华,喻果,贾月.基于权重迭代的偏好多目标分解算法解决参考点对算法影响的研究[J].电子学报,2016,44(1):67-76.
[11]NASIR M,MONDAL A K,SENGUPTA S,et al. An improved multiobjective evolutionary algorithm based on decomposition with fuzzy dominance[C]//IEEE Congress on Evolutionary Computation(CEC). New Orleans:IEEE,2011:765-772.
[12]CHANG P C,CHEN S H,ZHANG Q,et al. MOEA/D for flowshop scheduling problems[C]//IEEE World Congress on Computational Intelligence. Hong Kong:IEEE,2008:1433-1438.
[13]刘文娟.基于分解的多目标量子差分进化算法研究[D].太原:山西财经大学,2015.
[14]MOLINA J,SANTANA L V,HERNANDEZ A G,et al. g-dominance:reference point based dominance for multiobjective metaheuristics[J]. European Journal of Operational Research,2009,197(2):685-692.
[15]雷德明.现代制造系统智能调度技术及其应用[M].北京:中国电力出版社,2011.
[16]郁磊. MATLAB智能算法30个案例分析[M]. 2版.北京:北京航空航天大学出版社,2015.
[17]贺利军,刘超,朱光宇.基于模糊关联熵的高维多目标流水车间调度优化[J].计算机集成制造系统,2015,21(10):2704-2710.
[18]林震,侯杏娜,韦晓虎.基于动态多策略差分进化模型的MOEA/D算法[J].计算机应用研究,2017,34(9):2624-2628.
[19]YUAN Y,XU H,WANG B,et al. Balancing convergence and diversity in decomposition-based many-objective optimizers[J].IEEE Transactions on Evolutionary Computation,2016,20(2):180-198.
[20]ISHIBUCHI H,MASUDA H,NOJIMA Y. Comparing solution sets of different size in evolutionary many-objective optimization[C]//IEEE Congress on Evolutionary Computation(CEC). Sendai:IEEE,2015:2859-2866.
[21]MOHAMMADI A,OMIDVAR M N,LI X,et al. Sensitivity analysis of penalty-based boundary intersection on aggregationbased EMO algorithms[C]//IEEE Congress on Evolutionary Computation(CEC). Sendai:IEEE,2015:2891-2898.
[22]马庆.基于多目标进化算法的MOEA/D权重向量产生方法[J].计算机科学,2016,43(增刊2):117-122.
[23]TAO Q,CHANG H,YI Y,et al. A rotary chaotic PSO algorithm for trustworthy scheduling of a grid workflow[J]. Computers&Operations Research,2011,38(5):824-836.
[24]齐学梅,罗永龙,赵诚.求解流水车间调度问题的混合粒子群算法[J].计算机工程与应用,2012,48(9):33-39.
[25]ABRAHAM A,JAIN L,GOLDBERG R. Evolutionary multiobjective optimization:theoretical advances and applications[M].Berlin:Springer,2005.
[2]李智.智能优化算法研究及应用展望[J].武汉轻工大学学报,2016,35(4):1-9.
[3]崔琪,吴秀丽,余建军.变邻域改进遗传算法求解混合流水车间调度问题[J].计算机集成制造系统,2017,23(9):1917-1927.
[4]BOZEJKO W,PEMPERA J,SMUTNICKI C. Parallel tabu search algorithm for the hybrid flow shop problem[J]. Computers&Industrial Engineering,2013,65(3):466-474.
[5]黄明,郝倩,张春蕾,等.改进的免疫模拟退火算法求解混合流水车间调度问题[J].大连交通大学学报,2015,36(2):96-100.
[6]徐华,张庭.改进离散粒子群算法求解柔性流水车间调度问题[J].计算机应用,2015,35(5):1342-1347.
[7]ZHANG Q,LI H. MOEA/D:amultiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation,2007,11(6):712-731.
[8]LI H,ZHANG Q. Multiobjective optimization problems with complicated pareto sets,MOEA/D and NSGA-II[J]. IEEE Transactions on Evolutionary Computation,2009,13(2):284-302.
[9]ISHIBUCHI H,SAKANE Y,TSUKAMOTO N,et al. Simultaneous use of different scalarizing functions in MOEA/D[C]//Proceedings of Genetic and Evolutionary Computation Conference. Portland:ACM Press,2010:519-526.
[10]郑金华,喻果,贾月.基于权重迭代的偏好多目标分解算法解决参考点对算法影响的研究[J].电子学报,2016,44(1):67-76.
[11]NASIR M,MONDAL A K,SENGUPTA S,et al. An improved multiobjective evolutionary algorithm based on decomposition with fuzzy dominance[C]//IEEE Congress on Evolutionary Computation(CEC). New Orleans:IEEE,2011:765-772.
[12]CHANG P C,CHEN S H,ZHANG Q,et al. MOEA/D for flowshop scheduling problems[C]//IEEE World Congress on Computational Intelligence. Hong Kong:IEEE,2008:1433-1438.
[13]刘文娟.基于分解的多目标量子差分进化算法研究[D].太原:山西财经大学,2015.
[14]MOLINA J,SANTANA L V,HERNANDEZ A G,et al. g-dominance:reference point based dominance for multiobjective metaheuristics[J]. European Journal of Operational Research,2009,197(2):685-692.
[15]雷德明.现代制造系统智能调度技术及其应用[M].北京:中国电力出版社,2011.
[16]郁磊. MATLAB智能算法30个案例分析[M]. 2版.北京:北京航空航天大学出版社,2015.
[17]贺利军,刘超,朱光宇.基于模糊关联熵的高维多目标流水车间调度优化[J].计算机集成制造系统,2015,21(10):2704-2710.
[18]林震,侯杏娜,韦晓虎.基于动态多策略差分进化模型的MOEA/D算法[J].计算机应用研究,2017,34(9):2624-2628.
[19]YUAN Y,XU H,WANG B,et al. Balancing convergence and diversity in decomposition-based many-objective optimizers[J].IEEE Transactions on Evolutionary Computation,2016,20(2):180-198.
[20]ISHIBUCHI H,MASUDA H,NOJIMA Y. Comparing solution sets of different size in evolutionary many-objective optimization[C]//IEEE Congress on Evolutionary Computation(CEC). Sendai:IEEE,2015:2859-2866.
[21]MOHAMMADI A,OMIDVAR M N,LI X,et al. Sensitivity analysis of penalty-based boundary intersection on aggregationbased EMO algorithms[C]//IEEE Congress on Evolutionary Computation(CEC). Sendai:IEEE,2015:2891-2898.
[22]马庆.基于多目标进化算法的MOEA/D权重向量产生方法[J].计算机科学,2016,43(增刊2):117-122.
[23]TAO Q,CHANG H,YI Y,et al. A rotary chaotic PSO algorithm for trustworthy scheduling of a grid workflow[J]. Computers&Operations Research,2011,38(5):824-836.
[24]齐学梅,罗永龙,赵诚.求解流水车间调度问题的混合粒子群算法[J].计算机工程与应用,2012,48(9):33-39.
[25]ABRAHAM A,JAIN L,GOLDBERG R. Evolutionary multiobjective optimization:theoretical advances and applications[M].Berlin:Springer,2005.