基于Q—学习的超启发式模型及算法求解多模式资源约束项目调度问题
Q-learning based hyper-heuristic algorithm for solving multi-mode resource-constrained project scheduling problem作者机构:北京科技大学经济管理学院北京100083
出 版 物:《计算机集成制造系统》 (Computer Integrated Manufacturing Systems)
年 卷 期:2022年第28卷第5期
页 面:1472-1481页
核心收录:
学科分类:08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术(可授工学、理学学位)] 081202[工学-计算机软件与理论]
基 金:国家自然科学基金资助项目(71871017) 北京市教委社科基金资助项目(SM201910037004)。
主 题:超启发式模型 强化学习 Q—学习 多模式资源约束项目调度问题 元启发式算法 反馈—学习强化机制
摘 要:为了更好地解决传统的元启发式算法机制单一和面向问题定制不足等问题,提高算法的整体通用性,本文提出一种基于Q—学习的超启发式模型,并基于该模型设计实现了一种超启发式算法,求解多模式资源约束项目调度问题(MRCPSP)。该模型架构分为高低两层,低层由具有多种异构机制和不同参数的元启发式算子组成,高层则依据Q—学习策略自动选择低层算子。模型将多种优秀的元启发式算法与反馈—学习强化机制有机整合,具备灵活的可扩展性。为检验算法效果,从MRCPSP标杆算例库中选取了上千个规模不等的算例,设计了等价比较实验环节,并与最新公开文献提供的结果进行了比较。结果表明,基于Q—学习的超启发式算法在目标值、通用性、鲁棒性等多项性能指标上均表现优异,可以借鉴应用到其他各种组合优化问题。值得一提的是,针对J30算例的计算结果有多达41个算例获得了比当前公开文献报告的已知最优解更好的结果。