基于深度强化学习的随机局部搜索启发式方法

摘要：

为了更充分地利用可满足问题(SAT)的数据分布中的信息,从而提升算法性能,提出了一种基于深度强化学习的随机局部搜索启发式方法.把随机局部搜索算法中变量的选择看作强化学习任务,训练强化学习Agent学习策略作为随机局部搜索算法选择翻转变量的启发式,以期望通过端到端的方式获得效率更好的翻转变量的选择方法.实验结果表明,本文方法是有效的,并且与经典随机局部搜索算法ProbSAT相比,本文方法在性能上也有一定的优势,可以在更少的决策步骤内求出问题的解.

关键词：计算机软件、可满足性、随机局部搜索、深度强化学习

所属期刊栏目：51

分类号：TP181(自动化基础理论)

资助基金：国家重点研发计划;国家自然科学基金;国家自然科学基金;吉林省自然科学基金;吉林省自然科学基金

在线出版日期：2022-05-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：1420-1426