置信传播和模拟退火相结合求解约束满足问题

约束满足问题是人工智能领域的一个重要问题。针对一个具有精确相变现象和能产生大量难解实例的随机约束满足问题,提出了置信传播和模拟退火相结合的求解算法。这种算法先通过置信传播方程收敛后得到变量取值的边际概率分布,分别采用最大概率和最小分量熵的策略产生一组启发式的初始赋值,再用模拟退火对这组赋值进行修正。实验结果表明：该算法大大提高了初始赋值向最优解收敛的速度,表现出了显著优越于模拟退火算法的求解性能。     

基于改进迭代收缩阈值算法的微观3D重建方法

迭代收缩阈值算法（ISTA）求解离焦深度恢复动态优化问题时,采用固定迭代步长,导致算法收敛效率不佳,使得重建的微观3D形貌精度不高。为此,提出一种基于加速算子梯度估计和割线线性搜索的方法优化ISTA——FL-ISTA。首先,在每一次迭代中,由当前点和前一个点的线性组合构成加速算子重新进行梯度估计,更新迭代点;其次,为了改变迭代步长固定的限制,引入割线线性搜索,动态确定每次最优迭代步长;最后,将改进的迭代收缩阈值算法用于求解离焦深度恢复动态优化问题,加快算法的收敛速度、提高微观3D形貌重建的精度。在对标准500 nm尺度栅格的深度信息重建实验中,与ISTA、快速ISTA （FISTA）和单调快速ISTA （MFISTA）相比,FL-ISTA收敛速度均有所提升,重建的深度信息值下降了10个百分点,更接近标准500 nm栅格尺度;与ISTA相比,FL-ISTA重建的微观3D形貌均方差（MSE）和平均误差分别下降了18个百分点和40个百分点。实验结果表明,FL-ISTA有效提升了求解离焦深度恢复动态优化问题的收敛速度,提高了微观3D形貌重建的精度。     

混沌动态步长果蝇优化算法

为了进一步提高标准果蝇优化算法的收敛速度和寻优精度,将混沌优化与迭代步长动态调节策略相结合,提出一种混沌动态步长果蝇优化算法。算法在寻优过程中引入动态步长调节因子对基本果蝇优化算法的步长实现持续动态更新,利用混沌优化方法对混沌变量与优化变量进行映射操作,同时引入混沌扰动使得果蝇个体能够快速跳出局部最优。实验结果表明:该算法在收敛速度和寻优精度上大幅提高。     

一种求解命题公式骨干集的警示传播算法

警示传播WP算法是一类重要的信息传播算法,在命题公式的可满足性判定中非常有效。通过对WP算法的数学原理分析发现,当算法收敛时以高概率固定部分变元的赋值,可以对公式进行化简。基于这样的特征修改WP算法的迭代方程和变元赋值条件,设计了一种求解命题公式骨干集的信息传播算法。当变元数目超过400时,与经典骨干集求解算法对比,效率提高了40%,与目前常用算法对比也有10%的提高。结果表明,所提算法求解命题公式骨干集时非常有效。     

基于符号运算的归纳变量识别与约化

针对归纳变量的识别及归约问题提出一种基于符号运算的新算法。通过初始变量替换赋值语句中的右值,用以表达变量间的迭代与依赖关系,由此建立有向依赖图用于识别归纳变量。为归纳变量构建递归方程组并利用符号运算进行求解,获得独立的仅依赖于迭代次数的数学形式。实验结果表明,该方法适用于各种复杂的归纳变量,能够解决现有算法无法处理的一些问题。     

基于警示传播与DPLL算法的启发式极性决策算法

警示传播(WP)算法是信息传播算法的重要基础,WP算法的本质是因子图上警示信息的迭代过程,在算法收敛时得到一组稳定的警示信息,并利用局部腔域得到公式变元的部分赋值。分析了警示传播算法的基本原理,给出了算法的改进。RB实例集上的实验证明,改进后的算法比原算法具有迭代次数和运行时间,提高了收敛速度。然而,在RB模型产生的大部分实例集上,警示传播算法不收敛,因而不能有效求解公式。警示传播算法与DPLL算法的组合使用使回溯计算次数大大降低,从而有效地弥补了WP算法的不足。通过在RI3实例集上的测试实验表明,该方法是有效的。     

双层法用于化工流程模拟的方法与原理

将双层法用于数学模型求解,采用简化模型参数逼近平衡常数,利用相平衡条件,用严格模型校正简化模型.该法分为内层迭代和外层的简化模型参数迭代,简化模型参数初值一般可赋值1,内层初值即使与真值相差几百也可快速收敛.具有初值范围大,收敛迅速,适用于不同宽窄沸程体系,程序设计简单,占用内存小等优点.     

一种改进的变步长自适应GSO算法

基本萤火虫群优化(GSO)算法在求解全局优化问题时,存在收敛速度慢、求解精度不高等问题。为此,提出一种变步长自适应GSO算法。该算法在一定程度上可以避免GSO算法过早陷入局部最优,且步长随迭代次数的增加而自适应地调整,从而使算法在后期获得精度更高的解。运用6个标准测试函数进行实验,结果表明,与GSO算法相比,该算法的收敛速度及精度均有明显提高。     

几何约束求解的简化迭代算法

针对几何约束系统图分解中复合顶点的求解问题,提出复合顶点的图分解算法和等价自由变量的简化迭代求解算法.通过去除复合顶点部分边界约束对复合顶点进行图分解,对求解序列中的欠约束顶点添加等价自由变量、以等价自由变量的部分迭代求解、替代系统的整体数值求解,以提高求解效率和稳定性.该算法具有很强的通用性,并在实际应用中得到验证.     

基于连通度的分布式加权多维尺度节点定位算法

研究了迭代优化方法在无线传感器网络节点定位中的应用,针对多维尺度分析定位技术和传统的梯度迭代优化方法,根据数值实验确定了迭代步长和网络连通度之间的函数关系,提出了一种基于连通度的分布式多维尺度分析节点定位算法(a connectivity-based distributed weighted multidimensional scaling algorithm,简称dwMDS(C)).该算法首先根据网络的平均连通度确定迭代步长,然后对每个未知节点的局部代价函数进行优化求解.实验表明该迭代算法收敛快速且稳定,比基于SMACOF算法的dwMDS(G)算法在定位精度上有明显的提高.     

Solving SAT problem by heuristic polarity decision-making algorithm

This paper presents a heuristic polarity decision-making algorithm for solving Boolean satisfiability (SAT). The algorithm inherits many features of the current state-of-the-art SAT solvers, such as fast BCP, clause recording, restarts, etc. In addition, a preconditioning step that calculates the polarities of variables according to the cover distribution of Karnaugh map is introduced into DPLL procedure, which greatly reduces the number of conflicts in the search process. The proposed approach is implemented as a SAT solver named DiffSat. Experiments show that DiffSat can solve many "real-life" instances in a reasonable time while the best existing SAT solvers, such as Zchaff and MiniSat, cannot. In particular, DiffSat can solve every instance of Bart benchmark suite in less than 0.03 s while Zchaff and MiniSat fail under a 900 s time limit. Furthermore, DiffSat even outperforms the outstanding incomplete algorithm DLM in some instances.     

在形式验证和ATPG中的布尔可满足性问题

介绍布尔可满足性(SAT)求解程序在测试向量自动生成、符号模型检查、组合等价性检查和RTL电路设计验证等电子设计自动化领域中的应用．着重阐述如何在算法中有机地结合电路拓扑结构及其与特定应用相关的信息，以便提高问题求解效率．最后给出下一步可能的研究方向。     

An Effective Algorithm for the Futile Questioning Problem

In the futile questioning problem, one must decide whether acquisition of additional information can possibly lead to the proof of a conclusion. Solution of that problem demands evaluation of a quantified Boolean formula at the second level of the polynomial hierarchy. The same evaluation problem, called Q-ALL SAT, arises in many other applications. In this paper, we introduce a special subclass of Q-ALL SAT that is at the first level of the polynomial hierarchy. We develop a solution algorithm for the general case that uses a backtracking search and a new form of learning of clauses. Results are reported for two sets of instances involving a robot route problem and a game problem. For these instances, the algorithm is substantially faster than state-of-the-art solvers for quantified Boolean formulas.     

一类可分离SAT问题的O(1.890n)精确算法

布尔可满足性问题（SAT）是指对于给定的布尔公式,是否存在一个可满足的真值指派.这是第1个被证明的NP完全问题,一般认为不存在多项式时间算法,除非P=NP.学者们大都研究了子句长度不超过k的SAT问题（k-SAT）,从全局搜索到局部搜索,给出了大量的相对有效算法,包括随机算法和确定算法.目前,最好算法的时间复杂度不超过O（（2-2/k）ⁿ）,当k=3时,最好算法时间复杂度为O（1.308ⁿ）.而对于更一般的与子句长度k无关的SAT问题,很少有文献涉及.引入了一类可分离SAT问题,即3-正则可分离可满足性问题（3-RSSAT）,证明了3-RSSAT是NP完全问题,给出了一般SAT问题3-正则可分离性的O（1.890ⁿ）判定算法.然后,利用矩阵相乘算法的研究成果,给出了3-RSSAT问题的O（1.890ⁿ）精确算法,该算法与子句长度无关.     

基于布尔矩阵的关联规则算法研究*

针对可快速在大型交易事务数据库中挖掘关联规则的问题,基于布尔矩阵提出一种新的挖掘算法。该算法通过仅需存储布尔位节约了内存,通过简单布尔运算提高了求解频繁项集的效率。实验证明该算法较之于Apriori 算法有更好的性能。     

基于动态奖惩的CDCL SAT求解器分支启发式算法

分支启发式算法在CDCL SAT求解器中有着非常重要的作用,传统的分支启发式算法在计算变量活性得分时只考虑了冲突次数而并未考虑决策层和冲突决策层所带来的影响。为了提高SAT问题的求解效率,受EVSIDS和ACIDS的启发,提出了基于动态奖惩DRPB的分支启发式算法。每当冲突发生时,DRPB通过综合考虑冲突次数、决策层、冲突决策层和变量冲突频率来更新变量活性得分。用DRPB替代VSIDS算法改进了Glucose 3.0,并测试了SATLIB基准库、2015年和2016年SAT竞赛中的实例。实验结果表明,与传统、单一的奖励变量分支策略相比,所提分支策略可以通过减少搜索树的分支和布尔约束传播次数来减小搜索树的规模并提高SAT求解器的性能。     

Simple algorithm portfolio for SAT

The importance of algorithm portfolio techniques for SAT has long been noted, and a number of very successful systems have been devised, including the most successful one—SATzilla. However, all these systems are quite complex (to understand, reimplement, or modify). In this paper we present an algorithm portfolio for SAT that is extremely simple, but in the same time so efficient that it outperforms SATzilla. For a new SAT instance to be solved, our portfolio finds its k-nearest neighbors from the training set and invokes a solver that performs the best for those instances. The main distinguishing feature of our algorithm portfolio is the locality of the selection procedure—the selection of a SAT solver is based only on few instances similar to the input one. An open source tool that implements our approach is publicly available.     

一个适于形式验证的ATPG引擎

自动测试产生(ATPG)不仅应用于芯片测试向量生成，也是芯片设计验证的重要引擎之一．提出了一种组合电路测试产生的代数方法，既可作为组合验证的ATPG引擎，又可用于通常的测试产生．该算法充分发挥了二叉判决图(BDD)及布尔可满足性(SAT)的优势，通过启发式策略实现SAT算法与BDD算法的交替，防止因构造BDD可能导致的内存爆炸，而且使用增量的可满足性算法，进一步提高了算法的效率．实验结果表明了该算法的可行性和有效性．     

求解SAT问题的线性半定规划算法

将线性半定规划应用到SAT问题的求解过程中。首先将SAT实例转化为整数规划问题,然后松弛为线性规划模型,最后再转化为一般的线性半定规划模型去求解。用SDPA-M软件求解线性半定规划问题后,规定了如何根据目标函数值去判定SAT实例和当CNF公式可满足时如何根据最优指派的概率X^＊i（i=1,…,n）去进行变元赋值,以期求得该公式的可满足指派。上述算法不仅可以判定SAT问题,而且对于符合算法规定可满足的CNF公式皆可给出一个可满足指派。求解SAT问题的线性半定规划算法在文章中被描述并被给予相应算例。     

Online over time processing of combinatorial problems

In an online environment, jobs arrive over time and there is no information in advance about how many jobs are going to be processed and what their processing times are going to be. In this paper, we study the online scheduling of Boolean Satisfiability (SAT) and Mixed Integer Programming (MIP) instances that are well-known NP-complete problems. Typical online machine scheduling approaches assume that jobs are completed at some point in order to minimize functions related to completion time (e.g., makespan, minimum lateness, total weighted tardiness, etc). In this work, we formalize and present an online over time problem where arriving instances are subject to waiting time constraints. We propose computational approaches that combine the use of machine learning, MIP, and instance interruption heuristics. Unlike other approaches, we attempt to maximize the number of solved instances using single and multiple machine configurations. Our empirical evaluation with well-known SAT and MIP instances, suggest that our interruption heuristics can improve generic ordering policies to solve up to 21.6x and 12.2x more SAT and MIP instances. Additionally, our hybrid approach observed up to 90% of solved instances with respect to a semi clairvoyant policy (SCP).