基于学习-推理的约束求解方法研究进展  

Methods for Constraint Solving Problems Based on Learn to Reason Model:A Review

作　　者：邹悦 赖家洋 张永刚[2,3] ZOU Yue;LAI Jia-Yang;ZHANG Yong-Gang(College of Software,Jilin University,Changchun 130012,China;College of Computer Science and Technology,Jilin University,Changchun 130012,China;Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education(Jilin University),Changchun 130012,China)

机构地区：[1]吉林大学软件学院,吉林长春130012 [2]吉林大学计算机科学与技术学院,吉林长春130012 [3]符号计算与知识工程教育部重点实验室(吉林大学),吉林长春130012

出　　处：《软件学报》2024年第1期220-235,共16页Journal of Software

基　　金：国家自然科学基金(62076108,61872159);吉林省自然科学基金(20210101172JC)。

摘　　要：机器学习与自动推理的融合是当前人工智能研究的新趋势.约束满足问题是人工智能研究的经典问题,现实世界中大量的调度、规划和配置等问题均可以建模为约束满足问题,高效的求解算法一直是研究热点.近年来涌现出众多将机器学习应用于约束满足问题求解的新方法,这些基于“学习-推理”的新方法为约束满足问题求解开辟了新方向并展示出巨大发展潜力,方法的突出优点是适应性强、可在线优化并具有更强的可扩展性.将当前的“学习-推理”方法分为基于消息传递神经网络、基于序列到序列和基于最优化等3类进行综述,详细分析各类方法的特点和在不同的问题集上求解效果,尤其对每类方法所涵盖的相关工作进行多角度的对比分析.最后,对基于“学习-推理”的约束求解方法进行总结和展望.The integration of machine learning and automatic reasoning is a new trend in artificial intelligence.Constraint satisfaction is a classic problem in artificial intelligence.A large number of scheduling,planning,and configuration problems in the real world can be modeled as constraint satisfaction problems,and efficient solving algorithms have always been a research hotspot.In recent years,many new methods of applying machine learning to solve constraint satisfaction problems have emerged.These methods based on“learn to reason”open up new directions for solving constraint satisfaction problems and show great development potential.They are featured by better adaptability,strong scalability,and online optimization.This study divides the current“learn to reason”methods into three categories including message-passing neural network-based,sequence-to-sequence-based,and optimization-based methods.Additionally,the characteristics of various methods and their solution effects on different problem sets are analyzed in detail.In particular,a comparative analysis is conducted on relevant work involved in each type of method from multiple perspectives.Finally,the constraint solving method based on“learn to reason”is summarized and prospected.

关 键 词：约束满足问题 消息传递神经网络 序列到序列 强化学习 最优化 

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