Computer Integrated Manufacturing System ›› 2022, Vol. 28 ›› Issue (5): 1472-1481.DOI: 10.13196/j.cims.2022.05.018

Previous Articles     Next Articles

Q-learning based hyper-heuristic algorithm for solving multi-mode resource-constrained project scheduling problem

  

  • Online:2022-05-30 Published:2022-06-08
  • Supported by:
    Project supported by the National Natural Science Foundation,China (No.71871017),and the Social Science Foundation of Beijing Municipal Education commission,China (No.SM201910037004).

基于Q—学习的超启发式模型及算法求解多模式资源约束项目调度问题

崔建双,吕玥,徐子涵   

  1. 北京科技大学经济管理学院
  • 基金资助:
    国家自然科学基金资助项目(71871017);北京市教委社科基金资助项目(SM201910037004)。

Abstract: To solve the problems of traditional meta heuristic algorithm such as single mechanism and Insufficient problem-oriented customization,a Reinforcement Learning based Hyper-heuristic Model (RLHM) was presented,and an algorithm on this basis was designed for solving the Multi-mode Resource-Constrained Project Scheduling Problem (MRCPSP).The model architecture was divided into two layers,the Lower Layer Heuristic (LLH) was composed of meta-heuristic operators with multiple heterogeneous mechanisms,and the upper layer automatically selected LLH operators according to the reinforcement learning strategy.The model integrated various excellent meta-heuristic implementation methods with feedback-learning reinforcement mechanisms,which had flexible and scalability.To test the effect of the model,thousands of instances of different sizes were selected from the well-known benchmark of Project Scheduling Problem Library (PSPLIB),and verification links under different conditions were designed and compared with the results provided by the latest public literature.The results showed that RLHM and its algorithm performed well in the performance indicators such as target value,calculation time,and robustness,which were worthy of popularization and application to various combinations and optimization problems in other phases.For the calculation results of the J30,as many as 41 instances had obtained better results than the known optimal solutions reported in the current public literature.

Key words: hyper-heuristic, reinforcement learning, Q-learning, multi-mode resource-constrained project scheduling problem, meta-heuristic implementation methods, feedback-learning reinforcement mechanisms

摘要: 为了更好地解决传统的元启发式算法机制单一和面向问题定制不足等问题,提高算法的整体通用性,本文提出一种基于Q—学习的超启发式模型,并基于该模型设计实现了一种超启发式算法,求解多模式资源约束项目调度问题(MRCPSP)。该模型架构分为高低两层,低层由具有多种异构机制和不同参数的元启发式算子组成,高层则依据Q—学习策略自动选择低层算子。模型将多种优秀的元启发式算法与反馈—学习强化机制有机整合,具备灵活的可扩展性。为检验算法效果,从MRCPSP标杆算例库中选取了上千个规模不等的算例,设计了等价比较实验环节,并与最新公开文献提供的结果进行了比较。结果表明,基于Q—学习的超启发式算法在目标值、通用性、鲁棒性等多项性能指标上均表现优异,可以借鉴应用到其他各种组合优化问题。值得一提的是,针对J30算例的计算结果有多达41个算例获得了比当前公开文献报告的已知最优解更好的结果。

关键词: 超启发式模型, 强化学习, Q—学习, 多模式资源约束项目调度问题, 元启发式算法, 反馈—学习强化机制

CLC Number: