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

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