强化学习求解组合最优化问题的研究综述

• 作者: 王扬 陈智斌 吴兆蕊 高远
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 强化学习(RL) 深度强化学习(DRL) 组合最优化问题(COP)
• 年，卷（期）: 2022,（2）
• 所属期刊栏目: 综述·探索|Surveys and Frontiers
• 页码范围: 261-279
• 页数: 19页
• 分类号: TP18|O22
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.2107040

摘要

组合最优化问题(COP)的求解方法已经渗透到人工智能、运筹学等众多领域.随着数据规模的不断增大、问题更新速度的变快,运用传统方法求解COP问题在速度、精度、泛化能力等方面受到很大冲击.近年来,强化学习(RL)在无人驾驶、工业自动化等领域的广泛应用,显示出强大的决策力和学习能力,故而诸多研究者尝试使用RL求解COP问题,为求解此类问题提供了一种全新的方法.首先简要梳理常见的COP问题及其RL的基本原理;其次阐述RL求解COP问题的难点,分析RL应用于组合最优化(CO)领域的优势,对RL与COP问题结合的原理进行研究;然后总结近年来采用RL求解COP问题的理论方法和应用研究,对各类代表性研究所解决COP问题的关键要点、算法逻辑、优化效果进行对比分析,以突出RL模型的优越性,并对不同方法的局限性及其使用场景进行归纳总结;最后提出了四个RL求解COP问题的潜在研究方向.