随机正则3-可满足性问题的解簇结构分析

正则3-可满足性(3-SAT)问题是一个NP难问题,研究正则3-SAT问题解簇结构变化,旨在深入理解该问题的判定难度和可满足性解的分布情况。然而,现有分析模型只研究了接近簇集相变点的几个离散值,在不同约束密度下,缺乏统一的分析模型来描述解簇的结构演变。为了解决这一问题,提出解簇结构相变分析模型(PMSS)。该模型主要思想是采用WalkSAT算法和信息传播算法求得正则3-SAT问题可满足的初始解,再利用随机游走构造该初始解的解簇,并对解簇进行分析。用模块度和社区度量解簇社区结构,用结构熵度量解簇结构复杂性。实验结果表明,PMSS能够准确分析解簇结构演变过程,并且正则3-SAT问题实例的可满足相变点位于13~14,与使用Zchaff求解器得到的相变点一致,进一步验证了PMSS的有效性。

求解恰当可满足性问题的随机局部搜索算法

可满足性问题(SAT)是一种NP完全问题,被广泛运用于人工智能和机器学习等研究。恰当可满足性问题(XSAT)是SAT中一类重要的子问题。目前的大部分关于XSAT的研究主要为理论层面,对高效的求解算法特别是具有高效验证性的随机局部搜索算法研究很少。针对以上问题,分析了基础编码和等价编码两种转化方式的公式的部分性质,提出一种直接求解XSAT的随机局部搜索算法WalkXSAT。首先使用随机局部搜索框架进行基础搜索与条件判定;其次加入变元所属文字的恰当不可满足计分值,优先处理不易恰当满足的变元;然后使用防重复选择翻转变元的启发式策略减小搜索空间;最后,采用多种来源以及多种格式的实例进行对比实验。在直接求解XSAT时,相较于ProbSAT,WalkXSAT的变元翻转次数与求解时间显著减少;在求解基础编码转化后的实例中,当实例变元规模大于100时,ProbSAT已失效,而WalkXSAT依然能够在短时间内求解。实验结果表明,所提WalkXSAT精确性高、稳定性强、收敛快。

两种高效局部搜索算法求解RB模型实例

RB(revised B)模型是一种在约束可满足问题中具备精确相变增长域的随机实例模型,提出两种高效的启发式局部搜索算法用于解决RB模型生成的大值域约束可满足问题。首先为基于权重指导搜索的W-MCH算法,该算法通过约束判断和违反约束数计分来进行搜索,并引入了基于约束违反概率的权重计算公式,根据其关联的约束权重进行修正,再对变量进行迭代调整。然后提出最小化值域的MDMCH算法,该算法通过记录违反约束和逐步消除已违反约束变量的启发式策略来减少搜索空间,并在最小化后的变量域内重新校准变量赋值,进而有效提高算法的收敛速度。此外,还提出了融入模拟退火策略的WSCH和MDSCH算法,这两种算法都能根据变量的表征特点对变量域进行针对性的搜索。实验结果表明,与多种启发式算法相比,这两种算法在精度与时间效率方面均呈现明显提升,在复杂难解的实例中能够提供高效的求解效率,验证了算法的有效性和优越性。

求解Max-Re-SAT的离散混沌量子蝙蝠算法

针对最大正则可满足性问题求解算法的研究空缺,以及提升求解最大可满足性问题的智能优化算法的精度,基于蝙蝠算法(bat algorithm,BA),提出了一种基于离散混沌量子的蝙蝠算法。在该算法中,将连续数值转化为离散的二进制编码,对算法进行了离散化处理。该研究运用量子理论、引入量子比特编码和启发式量子变异,通过量子旋转门改变非最优个体的概率振幅来实现变异,解决了早熟和收敛速度慢的问题。在位置更新中,使用混沌映射替代固定参数,增强了灵活性和多样性,提高了全局寻优能力和求解效率。实验结果表明:在随机正则可满足性问题实例产生模型产生的不同规模算例上,所提算法的求解精度远远高于传统启发式算法;同时,与获奖的求解器相比,也具有一定的竞争力,验证了该算法的有效性。

可满足性问题的结构特征进展综述

可满足性(SAT)问题是人工智能的基础问题,也是NP难问题,在机器学习、模式识别和自然语言处理等领域有着实际应用。然而,随着人工智能发展,越来越多的问题呈现出更为复杂的形态,原有的算法不再适用,需进一步优化或者改进,这对基础研究提出了更高要求。为了研究SAT问题难解的内在本质,需要研究其结构特征,进而找出求解SAT问题的高效算法。近年来备受研究人员关注的相变、树宽、结构熵、DNA折纸术是SAT问题结构特征的4种常用度量模型。为了理清关于SAT问题结构特征的研究进展,基于上述4种度量模型,对SAT问题的结构特征进行了综述,指出了SAT问题结构特征研究所面临的挑战及未来的方向。在SAT问题求解中相变分析、树分解算法、结构熵及DNA折纸术等方面虽已取得一定的研究成果,但在相变点精确上界的求解、结构度量模型指导SAT求解器设计,以及树分解算法效率的提高等方面仍待突破,这将成为未来关于SAT问题结构特征研究的重点。

约束可满足性中求解RB模型实例的算法综述

约束满足问题是人工智能领域中最基本的NP完全问题之一。多年来,随着约束满足问题的深入研究,国内外学者提出多种实例模型。其中,RB模型是一种能生成具有精确相变的增长域约束满足问题实例,其求解难度极具挑战性。为了寻找其求解的新型高效算法,促进约束可满足问题的RB模型求解算法领域的研究,首先从约束满足问题的模型发展、求解技术进行分析;其次,对各类求解RB模型实例算法进行梳理,将求解的算法文献划分为回溯启发式类、信息传播类和元启发式类相关改进算法,从算法原理、改进策略、收敛性和精确度等方面进行对比综述;最后给出求解RB模型实例算法的研究趋势和发展方向。