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

Stochastic local search heuristic method based on deep reinforcement learning

作　　者：吕帅[1] 刘京 LYU Shuai;LIU Jing(College of Computer Science and Technology,Jilin University,Changchun 130012,China;College of Software,Jilin University,Changchun 130012,China)

机构地区：[1]吉林大学计算机科学与技术学院,长春130012 [2]吉林大学软件学院,长春130012

出　　处：《吉林大学学报（工学版）》2021年第4期1420-1426,共7页Journal of Jilin University:Engineering and Technology Edition

基　　金：国家重点研发计划项目(2017YFB1003103);国家自然科学基金项目(61300049,61763003);吉林省自然科学基金项目(20180101053JC,20190201193JC).

摘　　要：为了更充分地利用可满足问题(SAT)的数据分布中的信息,从而提升算法性能,提出了一种基于深度强化学习的随机局部搜索启发式方法。把随机局部搜索算法中变量的选择看作强化学习任务,训练强化学习Agent学习策略作为随机局部搜索算法选择翻转变量的启发式,以期望通过端到端的方式获得效率更好的翻转变量的选择方法。实验结果表明,本文方法是有效的,并且与经典随机局部搜索算法ProbSAT相比,本文方法在性能上也有一定的优势,可以在更少的决策步骤内求出问题的解。In order to make full use of the information in the data distribution of the Satisfiability Problem(SAT)and thereby improve the performance of the algorithm,this paper proposes a stochastic local search heuristic method based on deep reinforcement learning.The selection of the variables in stochastic local search algorithm is regarded as a reinforcement learning task.The strategy agent learns is used as a heuristic for selecting variables,so that we can obtain a more efficient variable selection heuristic in an endto-end way.Experiments show that the method in this paper is effective.Compared with the classical stochastic local search algorithm ProbSAT,our method also has certain advantages in performance,and can solve the problems in fewer decision steps.

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

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]