一种求解SAT问题的人工蜂群算法

针对SAT问题,提出一种求解该问题的离散人工蜂群算法——ABCSAT算法,建立了相应的优化算法模型,解决了问题编码和转化、适应度函数、蜜蜂觅食策略、离散操作等关键问题.不同于处理连续优化问题,ABCSAT将适应度函数定义为当前不可满足子句数.根据问题的特点设计了多种觅食策略,并利用各子句和变量之间约束关系的启发式信息对各阶段的候选解进行离散操作.最后在标准SATLIB测试集上对提出的算法进行了测试并与相关算法进行了比较,结果验证了ABCSAT算法在中小规模SAT问题上的有效性,表明算法能更加有效地解决该问题.     

一种求解SAT问题的人工蜂群算法

针对SAT问题,提出一种求解该问题的离散人工蜂群算法——ABCSAT算法,建立了相应的优化算法模型,解决了问题编码和转化、适应度函数、蜜蜂觅食策略、离散操作等关键问题.不同于处理连续优化问题,ABCSAT将适应度函数定义为当前不可满足子句数.根据问题的特点设计了多种觅食策略,并利用各子句和变量之间约束关系的启发式信息对各阶段的候选解进行离散操作.最后在标准SATLIB测试集上对提出的算法进行了测试并与相关算法进行了比较,结果验证了ABCSAT算法在中小规模SAT问题上的有效性,表明算法能更加有效地解决该问题.     

一次性求解多个SAT问题

在实际应用中通常需要求解对应CNF(Conjunctive Normal Form)公式之间仅相差几个子句的一系列SAT(Satisfiability Problem)问题,但目前绝大多数SAT求解算法都是针对单一SAT问题设计的。为此,基于DPLL提出了nDPLL算法,并在随机问题上对该算法的效率进行测试。实验结果表明,nDPLL算法能一次性求解多个SAT问题,对于特定范围的CNF公式集具有较高的效率,CNF公式集的规模越大、相近因子越高、子句数和变量数的比值越大,则nDPLL算法的效率越高。     

关于合取范式可满足性问题的复杂性分析

合取范式可满足性问题(简称SAT问题)是典型的NP完全问题,本文引入了一个饱和子句集的新概念,利用饱和子句集的特性,研究了SAT问题的复杂性,证明了SAT问题复杂性为多项式的一个充分条件,并揭示了二元可满足性问题与三元可满足性问题的本质差别。因此,通过变换来提炼出SAT问题的复杂性的本质特征,并加以研究的方法,是SAT问题的复杂性研究的一种有效方法。     

两种新的基于扩展规则#SAT问题求解算法

提出一种新的基于扩展规则的#SAT求解算法NCER,该算法在#ER的基础上加入启发式策略.该策略每次选择当前子句集的最长子句来减小极大项空间,使得递归调用的次数减少,从而加快求解效率.为解决基于扩展规则的#SAT求解器在互补因子较小的样例上的不良表现,结合NCER和CDP的优点提出混合#SAT求解算法NCDPER.实验结果表明:NCER较先前的#ER在所有85个随机SAT测试用例上有了显著的提高.通过与目前最好的基于扩展规则的#SAT求解器的比较,该求解器具有更好的性能.     

基于混合蚁群遗传算法的SAT问题求解

根据SAT问题的特点,通过分析传统蚁群算法和遗传算法在求解SAT问题上的不足,提出一种基于混合蚁群遗传算法的SAT问题求解方法。给出一种新的初始解的生成方式;在迭代过程中,根据较优解的累积信息提出进化算子;利用当前得到的最优解,通过改变不满足子句中文字的取值,增加变异算子。最后选取标准测试集中的20个实例对算法进行测试,实验结果表明:改进后的算法通常仅通过较少次数的迭代就能找到解,能够有效避免蚁群算法和遗传算法过早收敛的缺点,具有较强的寻优能力。     

一个SAT问题有解的充要条件

合取范式可满足性问题(简称SAT问题)是一个NP完全问题.引入了一个饱和合取范式的概念,利用饱和合取范式的性质,对SAT问题的本质进行了研究.在此基础上,证明了一个SAT问题有解的充要条件,它为SAT问题完全算法和非完全快速算法的深入研究提供了一条新的思路.     

基于重启策略的学习子句优化方法

以学习子句数据库优化为背景，在原MiniSAT求解器的基础上提出了一种新的学习子句的优化方法.该方法基于博弈论的思想，在若干次重启后，根据当前求解器的实时反馈信息改进MiniSAT原有的增长参数，尽可能靠近学习数据库中子句存储量的均衡点，从而使学习库的存储量尽可能达到Pareto最优.实验表明:所提的优化方法是有效的，并在随机SAT问题上胜过现有优化方法.该方法既不会因为学习数据库的子句过多而影响单元传播速度，也不会因为学习数据库中的子句过少而破坏学习的整体性.     

基于SAT和BDD的频繁序列挖掘技术

【目的】研究模式挖掘领域中的频繁序列挖掘技术,由于序列模式挖掘存在指数级的搜索空间,且传统的SAT求解算法无法高效求解大规模数据集的缺点,因此研究符号表示和操作技术,用来避免冗余计算。【方法】提出基于SAT的频繁序列挖掘的符号OBDD算法,基于深度优先算法的思想,首先将频繁序列挖掘问题构建为SAT模型,其次对变量进行排序并将约束子句分类后分别描述为OBDD,利用OBDD的"与"操作得到满足SAT的所有频繁序列模式。【结果】实例结果表明,该方法准确可行。【结论】该方法能有效缩减搜索空间,提高求解效率。     

MARG-MU(2)的结构和复杂度

SAT问题(可满足性问题)是理论计算机科学的核心问题,研究SAT问题的方法很多,利用极小不可满足公式的性质来研究SAT问题是近几年兴起的一个热点研究方向.本文主要利用(1,*)-消解方法研究了差为2的边缘极小不可满足公式集(MARG-MU(2))的结构和复杂度:在结构方面,MARG-MU(2)中的公式要么是F22,要么是某一文字在其中仅出现一次的公式;在复杂度方面,如果MARG-MU(2)对(1,*)-消解封闭,则某个含有n个变元和n+2个子句的公式是否为MARG-MU(2)中的公式的问题可以在时间0(n3)内被判定.     

可满足性问题的充分必要条件

可满足性问题是计算机和人工智能领域内的一个重要的问题,是第一个被证明是NPC的问题。本文主要把子句集进行分类,给出翻转定义、简单集定义,翻转同构定义,并且证明翻转同构不改变子句集的可满足性。论文证明了可满足子句集的三个充要条件。并且这些充要条件可以用于判断可满足问题的完全搜索和不完全搜索算法。     

可满足性问题的充分必要条件

可满足性问题是计算机和人工智能领域内的一个重要的问题,是第一个被证明是NPC的问题。本文主要把子句集进行分类,给出翻转定义、简单集定义,翻转同构定义,并且证明翻转同构不改变子句集的可满足性。论文证明了可满足子句集的三个充要条件。并且这些充要条件可以用于判断可满足问题的完全搜索和不完全搜索算法。     

基于CNF权重学习求解3-SAT问题的进化算法

SAT（Satisfiability）可满足性问题研究具有很广的应用价值,是计算机和人工智能领域内的一个重要问题,也是第一个被证明为NP完全的问题。随着对SAT问题的深入研究,已经提出了很多高效的算法,其中随机算法（WalkSAT）、进化算法等启发式算法是今年来研究的热点。进化算法是遗传算法的一种,通过对生物组织进化的学习,形成的一种高效算法。针对CNF（Coniecture Normal Formula）权重和生物进化算法相结合,提出一种有效求解难SAT问题的不完全算法WOSAT．