计算机应用研究

作者：龙峥嵘,李金龙,梁永濠,

单位：中国科学技术大学计算机科学与技术学院,合肥230026；

关键词：布尔可满足性问题,消息传递网络,机器学习,

当前基于神经网络的端到端SAT求解模型在各类SAT问题求解上展现了巨大潜力。然而SAT问题难以容忍误差存在，神经网络模型无法保证不产生预测误差。为利用SAT问题实例特性来减少模型预测误差，提出了错误偏好变量嵌入架构（architecture of embedding error-preference variables，AEEV）。该架构包含错误偏好变量嵌入调整算法和动态部分标签训练模式。首先，为利用参与越多未满足子句的变量越可能被错误分类这一特性，提出了错误偏好变量嵌入调整算法，在消息传递过程中根据变量参与的未满足子句个数来调整其嵌入。此外，提出了动态部分标签监督训练模式，该模式利用了SAT问题实例的变量赋值之间存在复杂依赖关系这一特性，避免为全部变量提供标签，仅为错误偏好变量提供一组来自真实解的标签，保持其他变量标签为预测值不变，以在训练过程管理一个更小的搜索空间。最后，在3-SAT、k-SAT、k-Coloring、3-Clique、SHA-1原像攻击以及收集的SAT竞赛数据集上进行了实验验证。结果表明，相较于目前较先进的基于神经网络的端到端求解模型QuerySAT，AEEV在包含600个变量的k-SAT数据集上准确率提升了45.81%。

来源：2024年第11期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2024年第11期