随机局部搜索求解最大可满足性问题的经验研究

点击上方蓝字

关注我们

导

读

      最大可满足性问题（MAX-SAT）在理论上是一个重要的NP难问题，在实践中具有广泛的应用。随机局部搜索（SLS）正成为求解MAX-SAT的一种越来越流行的方法。最近，一个名为CCLS的强大的SLS算法可以高效求解随机实例和手工实例。然而，CCLS在求解工业MAX-SAT实例方面的表现远远落后。本文专注于实验分析SLS算法用于求解工业MAX-SAT实例的性能。首先，进行实验分析CCLS求解工业实例表现不佳的原因。而后，提出了一种名为加性BMS（多种选择中的最佳选择）的新策略以缓解这一严重问题。通过整合CCLS与加性BMS策略，本文开发了一个新的求解MAX-SAT的SLS算法，名为CCABMS，相关实验表明了CCABMS算法的效率。此外，我们通过实验，分析初始化方法对于求解MAX-SAT的SLS算法的效力，并将有效的初始化方法与CCABMS结合，得到一个增强的算法。实验结果表明，对于求解大量工业MAX-SAT实例上的性能，我们的增强算法优于最先进的SLS算法。

文章精要

请长按下方二维码识别，阅读该文。

相关内容推荐：

基于情感信息和神经网络模型的立场分析 2018 13(1)：127-138 

基于鲁棒特征学习和无需大规模预训练的在线判别式跟踪算法 2018 12(6)：1160-1172

基于BP神经网络和主成分分析的岩体滤波算法 2018 12(6)：1149-1159

卷积自适应降噪自动编码器 2018 12(6)：1140-1148

从上下文语境中学习： 基于相互增强模型的中文微博观点检索  2018 12(4)：714-724

决策树集成学习中的结构多样性 2018 12(3)：560-570

基于LDA模型的协同过滤  2018 12(3)：571-581

结合序列二次规划的回溯搜索算法 2018 12(2)：316-330

一种解决类不平衡问题的进化欠采样bagging集成分类算法 2018 12(2)：331-350

FCS 12(2) 人工智能专栏 | 关于差异进化算法中变异个体的选择

FCS 12(1) 文章 | 多峰问题全局优化的分布式学习粒子群优化算法

FCS 12(1) 文章 | 多层次的中文垃圾短信高效识别方法

---

Frontiers of Computer Science

---

Frontiers of Computer Science （FCS）是由教育部主管、高等教育出版社和北京航空航天大学共同主办、SpringerNature 公司海外发行的英文学术期刊。本刊于 2007 年创刊，双月刊，全球发行。主要刊登计算机科学领域具有创新性的综述论文、研究论文等。本刊主编为周志华教授，共同主编为熊璋教授。编委会及青年 AE 团队由国内外知名学者及优秀青年学者组成。本刊被 SCI、Ei、DBLP、INSPEC、SCOPUS 和中国科学引文数据库（CSCD）核心库等收录，为 CCF 推荐期刊；两次入选“中国科技期刊国际影响力提升计划”；入选“第4届中国国际化精品科技期刊”。

---

长按二维码关注Frontiers of Computer Science公众号