改进的模拟退火算法求解规则可满足性问题

对于随机k-SAT问题,限定每个变元出现的次数恰好出现d次,形成随机规则(k,d)-SAT问题,目前国内外对该问题的相关研究较少,且研究随机规则(k,d)-SAT问题比研究k-SAT问题更为具体。文中给出一种随机规则(k,d)-SAT问题的生成实例模型——RRIG(N,k,d)模型,并用改进的模拟退火算法SARSAT求解规则随机规则(k,d)-SAT问题。将变元出现次数d加入到扰动策略中,利用变元出现次数和子句间约束关系中的启发信息对候选解中的赋值选择性改动,加快算法收敛至较优解的速度;同时,模拟退火算法中的Metropolis接受准则和改进后的退火策略保证了算法能够有效跳出局部最优解,最后使用RRIG(N,k,d)模型生成不同参数的测试实例,并与其他相关算法进行比较,结果表明SARSAT算法能有效解决规则可满足问题。

可满足性问题相变研究综述

约束满足问题(CSP)是理论计算机科学领域的组合优化问题,可满足性问题(SAT问题)作为CSP中的一种特殊情形,是理论计算机科学、数理逻辑和人工智能等领域十分关注的热点问题。相变是SAT问题中存在的一种现象,而研究SAT问题的相变现象和相变机制对深入认识SAT问题的难解本质和一般数学现象以及设计更高效的算法求解SAT问题有重要的指导意义。因此,根据近年来国内外学者针对SAT问题的相变现象取得的一些重要研究成果,首先介绍了SAT问题相变的相关知识以及SAT问题的概率分析方法和实例生成模型,其次总结并分析了SAT问题的不可满足相变和可满足相变这两种相变的相变点求解方法和相变阈值,最后展望了SAT问题相变的研究趋势。

实例化空间:一种新的安全协议验证逻辑的语义模型

给出了一个称为“实例化空间(instantiation space)”的安全协议验证逻辑的语义模型.该语义模型是建立在一种自然的加密信息交换(cryptographical message exchange)模型上的.在此语义模型基础上,文章提出了一系列与安全属性相关的验证公理,由此可以证明它们在此语义模型下的正确性.更重要的是,在此语义下的公理集在算法上是完全可以实现的,其对应的工具SPV(Security Protocol Verifier)已经开发成功,并且可以验证复杂的协议.在这套安全协议验证模型理论下,可以很方便地处理包括公钥、私钥、共享密钥和Hash函数组成的复杂信息格式.而且,在此语义基础上的公理集是纯命题逻辑的,因此所需要的验证目标可以很方便地转化成可满足性问题(SAT),从而可以利用工业上快速高效的SAT求解器实现.

一种改进的有界模型检验子句规则

为有界模型检验提出了改进的子句规则。在节点分类的基础上,首先对精简布尔电路表示进行逻辑化简,去掉功能冗余节点;然后识别、记录和处理多元运算的操作数,把多元运算作为单个节点直接生成子句;最后合并相邻节点,根据合并后的逻辑关系生成变量和子句。实验结果表明,改进的子句规则普遍减少了可满足性问题的变量、子句数目和运行时间。

面向多品种变批量生产的制造单元生成方法

针对多品种变批量生产特征下的制造单元构建问题,提出了基于可重构性和利用率的制造单元生成方法。建立了制造单元的需求模型,通过对多工艺路线的相似性分析,构建了多工艺路线的相似函数,提出了以频数为基础的制造单元可重构性和利用率的概念、计算公式。建立了制造单元的生成规则,提出了以可重构性和利用率最大为目标的制造单元生成框架结构和算法。通过具体实例验证了该算法的有效性。

一种可检测类型缺陷攻击的SAT改进模型

针对现有SAT模型检测器不能检测类型缺陷攻击的问题,提出了一种新的SAT#改进模型.该模型通过在匹配模式下引入无类型变量,并利用无类型消息的概念,解除了SAT模型检测器对未知消息的类型限制,并且在诚实主体重写规则中用无类型消息替换了原来的强类型限制消息.通过增加消息匹配算法,使诚实主体能够接受带有类型缺陷的消息,从而实现类型缺陷攻击的检测.通过对Otway-Rees协议进行检测,不仅发现了已有的针对发起者A的类型缺陷攻击,而且发现了新的针对响应者B的类型缺陷攻击,其实验结果证明了SAT#模型具有一定的可靠性.

由统计规律模拟生成的岩体裂隙网络的非稳定渗流数值分析

研究裂隙岩体中渗透水流随时间、边界条件的变化规律,从而客观反映渗透水流情况,具有重要的意义.利用MonteCarlo模拟岩体中裂隙网络分布情况,基于裂隙岩体网络非稳定渗流数学模型,编制相应的程序,并通过算例进行验证,进而对工程实例进行分析.结论表明:运用MonteCarlo方法模拟岩体中裂隙网络分布状况并进行渗流分析是一种较好的分析方法;当边界条件发生变化时,裂隙岩体中水头分布变化存在一定的滞后性,并且当边界条件变化一定时,岩体中水头分布受时间变化影响不大.

结合ATPG和SAT的无界模型检验前像计算方法

提出一种无界模型检验的前像计算方法,该方法有效地结合ATPG和SAT引擎,充分利用引擎各自的优点.SAT用来判断是否已经穷尽所有解;每次SAT枚举出一个前像解后,采用一个专门的ATPG过程减少状态变量上的赋值,从而减少前像解的总个数,加快后面的不动点迭代处理.最后通过在ISCAS89和ITC99电路上的实验证明了文中方法的有效性.

时序电路等价验证的触发器匹配

通常的时序电路等价性验证方法是将触发器按时序展开,从而将时序电路转化为组合电路进行验证。而一般在待验证的两个时序电路中,触发器是一一对应的,找到触发器的对应关系,时序电路的验证就会得到很大的简化。该文通过一种新的基于布尔可满足性(SAT)算法的自动测试模式生成(ATPG)匹配模型建立联接电路,使用时序帧展开传递算法比较触发器的帧时序状态输出,同时在SAT解算中加入信息学习继承等启发式算法,将时序电路的触发器一一匹配。在ISCAS89电路上的实验结果表明,该文算法在对触发器的匹配问题上是非常有效的。