面向多目标柔性作业车间调度的强化学习NSGA-II算法
作者:
中图分类号:

TH11

基金项目:

重庆市科技重大主题专项资助项目(cstc2018jszx-cyztzxX0032)。


Reinforcement learning NSGA-II for multi-objective flexible job shop scheduling
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [23]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    针对非支配排序遗传算法 (NSGA-II, non-dominated sorting genetic algorithm II)在求解柔性作业车间多目标优化调度问题中多样性不足、易于早熟与局部收敛的缺点,提出一种基于强化学习的改进NSGA-II算法(RLNSGA-II, reinforcement learning non-dominated sorting genetic algorithm II)。为避免NSGA-II陷入局部收敛问题引入双种群进化策略,利用性别判定法将种群拆分为两个种群,并在进化过程中采用不同的交叉变异算子,增加算法的局部和全局搜索能力;为解决NSGA-II精英策略造成多样性不足的问题,融合多个多样性度量指标,利用强化学习动态优化种群迭代过程中的拆分比例参数以保持多样性,改善算法收敛性能。最后通过Kacem标准算例进行了仿真实验与性能分析,验证了RLNSGA-II的有效性与优越性。

    Abstract:

    Non-dominated sorting genetic algorithm II (NSGA-II) has the shortcomings of insufficient diversity, prematurity and local convergence in solving the multi-objective optimal scheduling problem in flexible job shop. In this study, an improved NSGA-II algorithm based on reinforcement learning (RLNSGA-II) is proposed. To avoid NSGA-II to fall into the problem of local convergence, a two-population evolution strategy is introduced. The sex determination method is used to split the population into two populations, and different cross mut-ation operators are used in the evolution process to increase the local and global search capabilities of the algorithm. In order to solve the problem of insufficient diversity caused by the NSGA-II elite strategy, multiple diversity metrics are integrated, and reinforcement learning is used to dynamically optimize the split ratio parameters in the population iteration process to maintain diversity and improve algorithm convergence performance. Finally, simulation experiments and performance analysis are carried out through Kacem standard calculation examples, verifying the effectiveness and superiority of RLNSGA-II.

    参考文献
    [1] Kacem I, Hammadi S, Borne P. Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2002, 32(1):1-13.
    [2] Moslehi G, Mahnam M. A Paretoapproach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search[J]. International Journal of Production Economics, 2011, 129(1):14-22.
    [3] 王思涵,黎阳,李新宇.基于鲸鱼群算法的柔性作业车间调度方法[J].重庆大学学报, 2020, 43(1):1-11.Wang S H, Li Y, Li X Y. An improved whale swarm algorithm for flexible job-shop scheduling problem[J]. Journal of Chongqing University, 2020, 43(1):1-11.(in Chinese)
    [4] Gong G L, Deng Q W, Gong X R, et al. A new double flexible job-shop scheduling problem integrating processing time, green production, and human factor indicators[J]. Journal of Cleaner Production, 2018, 174:560-576.
    [5] 曾强,常梦辉,王孟华,等.混合工作日历下柔性作业车间多目标调度优化方法[J].重庆大学学报, 2019, 42(7):10-26.Zeng Q, Chang M H, Wang M H, et al. Multi-objective optimization method for FJSP under mixed work calendars[J]. Journal of Chongqing University, 2019, 42(7):10-26.(in Chinese)
    [6] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm:NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197.
    [7] Seng D W, Li J W, Fang X J, et al. Low-carbon flexible job-shop scheduling based on improved nondominated sorting genetic algorithm-II[J]. International Journal of Simulation Modelling, 2018, 17(4):712-723.
    [8] 缪嘉成,李朝阳,陈兵奎.结合Kriging与改进NSGA-Ⅱ的RV减速器优化[J].重庆大学学报, 2021, 44(2):65-78.Miao J C, Li C Y, Chen B K. Optimization of an RV reducer by integrating Kriging with improved NSGA-Ⅱ[J]. Journal of Chongqing University, 2021, 44(2):65-78.(in Chinese)
    [9] 陈辅斌,李忠学,杨喜娟.基于改进NSGA2算法的多目标柔性作业车间调度[J].工业工程, 2018, 21(2):55-61.Chen F B, Li Z X, Yang X J. Multi-objective flexible job shop scheduling based on improved NSGA2 algorithm[J]. Industrial Engineering Journal, 2018, 21(2):55-61.(in Chinese)
    [10] 胡成玉,余果,颜雪松,等.基于改进多目标优化算法的分布式数据中心负载调度[J].控制与决策, 2021, 36(1):159-165.Hu C Y, Yu G, Yan X S, et al. Multi-objective optimization of energy and performance management in distributed data centers[J]. Control and Decision, 2021, 36(1):159-165.(in Chinese)
    [11] 程子安,童鹰,申丽娟,等.双种群混合遗传算法求解柔性作业车间调度问题[J].计算机工程与设计, 2016, 37(6):1636-1642.Cheng Z A, Tong Y, Shen L J, et al. Double population hybrid genetic algorithm for solving flexible job shop scheduling problem[J]. Computer Engineering and Design, 2016, 37(6):1636-1642.(in Chinese)
    [12] Chen Y, Hu J L, Hirasawa K, et al. Optimizing reserve size in genetic algorithms with reserve selection using reinforcement learning[C]//SICE Annual Conference 2007, September 17-20, 2007, Takamatsu. IEEE, 2007:1341-1347.
    [13] 王晓燕,刘全,傅启明,等.基于强化学习的多策略选择遗传算法[J].计算机工程, 2011, 37(8):149-152.Wang X Y, Liu Q, Fu Q M, et al. Multiple policy selection genetic algorithm based on reinforcement learning[J]. Computer Engineering, 2011, 37(8):149-152.(in Chinese)
    [14] 封硕,郑宝娟,陈文兴,等.支持强化学习RNSGA-Ⅱ算法在航迹规划中应用[J].计算机工程与应用, 2020, 56(3):246-251.Feng S, Zheng B J, Chen W X, et al. RNSGA-Ⅱ algorithm supporting reinforcement learning and its application in UAV path planning[J]. Computer Engineering and Applications, 2020, 56(3):246-251.(in Chinese)
    [15] Raghuwanshi M M, Kakde O G. Genetic algorithm with species and sexual selection[C]//2006 IEEE Conference on Cybernetics and Intelligent Systems. June 7-9, 2006, Bangkok, Thailand. IEEE, 2006:1-8.
    [16] 张超勇,饶运清,刘向军,等.基于POX交叉的遗传算法求解Job-Shop调度问题[J].中国机械工程, 2004, 15(23):2149-2153.Zhang C Y, Rao Y Q, Liu X J, et al. An improved genetic algorithm for the job shop scheduling problem[J]. China Mechanical Engineering, 2004, 15(23):2149-2153.(in Chinese)
    [17] 李密青,郑金华,肖桂霞,等.一种多目标进化算法的分布度评价方法[J].模式识别与人工智能, 2008,21(5):695-703.Li M Q, Zheng J H, Xiao G X, et al. A diversity metric for multi-objective evolutionary algorithm[J]. Pattern Recognition and Artificial Intelligence, 2008, 21(5):695-703.(in Chinese)
    [18] Kacem I, Hammadi S, Borne P. Pareto-optimality approach for flexible job-shop scheduling problems:hybridization of evolutionary algorithms and fuzzy logic[J]. Mathematics and Computers in Simulation, 2002, 60(3/4/5):245-276.
    [19] 赵博选,高建民,付颖斌,等.求解柔性作业车间调度问题的多策略融合Pareto人工蜂群算法[J].系统工程理论与实践, 2019, 39(5):1225-1235.Zhao B X, Gao J M, Fu Y B, et al. A multi-strategy integration Pareto artificial bee colony algorithm for flexible job shop scheduling problems[J]. Systems Engineering-Theory&Practice, 2019, 39(5):1225-1235.(in Chinese)
    [20] Huang X B, Guan Z L, Yang L X. An effective hybrid algorithm for multi-objective flexible job-shop scheduling problem[J]. Advances in Mechanical Engineering, 2018, 10(9):168781401880144.
    [21] 孟冠军,杨大春,陶细佩.基于混合人工蜂群算法的多目标柔性作业车间调度问题研究[J].计算机应用研究, 2019, 36(4):972-974,979.Meng G J, Yang D C, Tao X P. Study on multi-objective flexible Job-Shop scheduling problem based on hybrid artificial bee colony algorithm[J]. Application Research of Computers, 2019, 36(4):972-974,979.(in Chinese)
    [22] 王建华,潘宇杰,孙瑞.自适应Jaya算法求解多目标柔性车间绿色调度问题[J].控制与决策, 2021, 36(7):1714-1722.Wang J H, Pan Y J, Sun R. Multi-objective flexible job shop green scheduling problem with self-adaptiveJaya algorithm[J]. Control and Decision, 2021, 36(7):1714-1722.(in Chinese)
    [23] 吴贝贝,张宏立,王聪,等.基于正态云模型的状态转移算法求解多目标柔性作业车间调度问题[J].控制与决策, 2021, 36(5):1181-1190.Wu B B, Zhang H L, Wang C, et al. State transition algorithm based on normal cloud model for solving multiobjective flexible job shop scheduling problem[J]. Control and Decision, 2021, 36(5):1181-1190.(in Chinese)
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

尹爱军,闫文涛,张厚望.面向多目标柔性作业车间调度的强化学习NSGA-II算法[J].重庆大学学报,2022,45(10):113-123.

复制
分享
文章指标
  • 点击次数:591
  • 下载次数: 1131
  • HTML阅读次数: 933
  • 引用次数: 0
历史
  • 收稿日期:2020-11-26
  • 最后修改日期:2021-05-12
  • 在线发布日期: 2022-11-01
文章二维码