可满足性求解器算法基于GPU的加速研究

可满足性求解(SAT)问题被广泛应用于软件验证、理论证明、微处理器验证、模块验证等领域,工业应用实例问题求解变量规模已达到百万数量级,传统的基于CPU的串行和并行SAT求解方法已无法满足如此规模的问题求解。不同于以往的并行SAT研究,利用GPU并行处理的特点和SAT算法的特点,将SAT算法中最耗时的BCP(Boolean Constraint Propagation)过程并行化,设计实现了基于GPU的BCP过程GP_BCP(GPU Paralleled BCP),从而将BCP过程的性能提高了5.4～10.3倍。     

求解多文字可满足SAT问题的置信传播算法

可满足(SAT)问题是指:是否存在一组布尔变元赋值,使得合取范式公式中每个子句至少有一个文字为真.多文字可满足SAT问题是指:是否存在一组布尔变元赋值,使得CNF公式中每个子句至少有两个文字为真.显然,此问题仍然是一个NP难问题.为了研究解决多文字可满足SAT问题的算法,引入随机实例产生模型,设计求解多文字可满足SAT问题的置信传播算法.最后,用实例模型产生了大量数据进行实验验证,结果表明:该算法求解多文字可满足SAT问题的性能优于其他启发式算法.     

利用近似解加速求解SAT问题的启发式完全算法

结合DPLL完全算法能够证明可满足性(SAT)问题的不可满足性和局部搜索算法快速的优点,提出利用近似解加速求解SAT问题的启发式完全算法.首先利用局部搜索算法快速地得到一个近似解,并将该近似解作为完全算法的初始输入,用于其中分支变量的相位决策.该算法引导完全算法优先搜索近似解所在的子空间,加速解决器找到可满足解的过程,为SAT问题的求解提供了一种新的有效途径.实验结果表明,该算法有效地提高了决策的精度和SAT解决器的效率,对很多实例非常有效.     

一种求解3-SAT问题的新方法

可满足性问题(SatisfiabilityProblem,SAT)是计算科学的典型问题之一,目前有DP算法、SAT1.3算法和遗传算法等多种求解方法。文章根据Kennedy和Eberhart提出的二进制粒子群优化算法(BinaryParticleSwarmOptimizers),基于局部随机搜索策略,给出了一种求解3-SAT问题的新方法:基于局部随机搜索的改进二进制粒子群优化算法(ModifedBinaryParticleSwarmOptimizersBasedonlocalstochasticsearch,简称MBPSO)。数值实验表明,对于随机产生的3-SAT问题测试实例,该算法是一种高效实用的新方法。     

基于SAT的多目标故障测试向量动态压缩方法

针对传统的自动测试图形向量生成采用逐个求解单一故障模型导致生成测试向量数据量巨大的缺点, 提出一种基于布尔满足性(boolean satisfiability, SAT)的多目标故障测试向量动态压缩方法, 同时论证多目标故障测试生成问题为布尔满足性问题。该方法将具有鲁棒性的SAT算法嵌入经典的动态压缩流程中, 首先利用经典动态压缩算法求解最小测试向量检测大部分失效故障, 然后采用SAT求解器对未测出的多故障电路进行同一求解和附加约束求解方式, 最终得到故障覆盖率高的测试向量和同一测试最大故障列表。实验数据表明, 在相同电路模型情况下, 此方法求得的测试向量相比经典动态压缩减少高达70%。     

面向结构的Agent组织形成和演化机制

基于Agent组织的多Agent问题求解可以大大降低求解难度和交互复杂性。其中Agent组织的形成和演化是基于Agent计算和合作的关键。给出了面向结构的组织形成和演化机制,解决了麻木性和灵活性差问题,保证了Agent的效用理性和个性倾向,刻画了演化所满足的性质,改进了Shehory,Kraus,Glaser等的组织形成和演化方法。     

QBF求解算法研究综述

近10年来,布尔可满足性(SAT)求解技术飞速发展,并已经成功应用于模型检验、定理证明等领域,特别是在限界模型检验(BMC)中取得了明显的进展,然而,由于命题逻辑公式的长度随系统规模指数倍增长,基于SAT的模型检验仍然存在状态空间爆炸问题.带量词的布尔公式(QBF)作为SAT公式的自然扩展,具有紧凑的空间结构、更强大、更直观的表达能力,能够简洁地描述模型检验中的公式.基于QBF的模型检验有希望缓解状态空间爆炸问题,成为当前研究的一个热点.总结了当前主流的QBF求解算法及常用的优化技术,指出了该领域中值得关注的新趋势.     

基于约束图分片求解DCOP的Agent组织结构

MAS中许多分布式推理问题可以建模为分布式约束优化问题(DCOP),解决DCOP的分布式算法已经成为MAS中的重要基础.已有的Adopt等算法通过对等的Agent之间的平等协商完成求解,强调了异步通信、分布计算与对解质量的保证,在求解问题的组织结构方面仍有改进余地.可以采用一种基于分散与集中相结合的思路,基于对约束图分片的方法及核心结点、通信主干道等概念,构造新颖的Agent组织结构,完成DCOP问题的异步、分布求解.在该组织结构下求解DCOP的算法可在效率、适应动态性方面得到改善,并将一个Agent一个变量和一个Agent多个变量的DCOP求解方法统一起来.     

O(m~2)时间求解SAT问题的随机算法

传统的求解 SAT问题的随机算法主要是对满足解进行搜索 ,在找不到满足解的情况下 ,则无法正确判断问题的可满足性 .该文提出了两个时间复杂度为 O( m2 )求解 SAT问题的随机算法 Sat Test1和 Sat Test2 ,这里 m为CNF公式中的子句数 .这两个随机算法是通过对不满足解数的估计来判断 SAT问题的可满足性 ,不同于传统的随机算法 .其中第二个算法 Sat Test2在搜索满足解的同时又可以对不满足解数进行估计 ,是对传统随机算法的重要改进 .试验结果表明 ,文中提出的算法对相变区域的难 SAT实例有较好的求解能力 .     

基于SystemC的SAT求解器设计

该文描述了可满足性问题(SAT)求解器的设计及性能。首先,基于DPLL算法设计了一个单核SAT求解器的SystemC模型。校准这个模型,使之与工作站级计算机的软件性能相匹配,结果发现通过不连续内存访问数可以准确地估计运行时间。接着,设计了一个多核SAT求解器模型,使之能共享学习短句。通过广泛地仿真,演示了这个方法的并行效率。针对DPLL算法并行化水平低时的性能退化问题,进行了算法改进,结果得到了明显的改善。     

改进蚁群算法求解旅行Agent问题

利用蚁群算法来求解TAP问题是解决移动Agent迁移策略的一种有效途径。旅行Agent问题是复杂的组合优化问题,蚁群算法作为一种新的生物进化算法,具有并行、正反馈和启发式搜索等特点,适合求解NP难问题。在蚁群算法的基础上,提出分泌多种信息素的改进蚁群算法来求解旅行Agent问题,动态反应了节点服务能力和网络负载的变化,使迁移更具有灵活性。实验结果表明了该文算法的可行性。     

基于agen t 的城市交通信号控制

利用agent技术对城市交通信号控制进行研究．首先给出了区域agent(ARA)的组成和结构，然后给出了城市交通控制的模型和协调算法．基于agent技术的城市交通控制系统能对交通状况进行实时反映和处理．在此模型基础上，应用博弈论的相关知识给出城市交通信号协调控制算法．最后通过仿真程序验证了该模型和算法的有效性和实用性．     

一种基于本体的主体服务快速匹配算法

分析了目前主体服务匹配中存在的问题，研究了目前主体服务匹配算法效率低的原因。为了提高主体服务匹配的效率，提出了主体服务本体的概念，研究了如何根据主体服务本体来组织主体服务，提出了一种基于本体的主体服务快速匹配算法，从理论上分析了该服务匹配算法的性能特点，并用仿真实验验证了该服务匹配算法的有效性。     

心战Agent个性及传播建模

心理战作为信息化战争中"软"打击的重要作战方式,受到越来越多的重视。心理战中人的个性形成和传播是个非常复杂的过程,传统建模方法不能反映作战中人的个性因素及对作战产生的难以预料的结果。采用复杂适应系统理论多Agent建模方法探讨作战中人的因素,在微观层面使用Agent参数表示个性,并对Agent行为引入个性表达,在宏观层面使用社会学方法研究个性的传播机制,并使用网络及Agent网络属性表达。在此基础上,构建模拟系统,进行实验。对心理战的实施具有很好的指导作用。     

基于拍卖博弈的电子商务自动协商

为提高电子商务自动协商系统效率,本文以拍卖博弈理论为基础,提出并实现了一种基于拍卖博弈的自动协商Agent模型,并在此基础上实现了一个基于拍卖博弈的电子商务自动协商原型系统,应用于一个企业敏捷供应链管理系统中实现自动协商交易。     

基于CSCW的网络教学系统的设计与实现

从信息技术发展的角度出发,探讨在信息时代现有的教育观念、教学模式如何与现代的信息技术与网络技术相结合,极大限度地利用教育资源.通过分析网络学习模式,结合Agent技术提出一种建立在建构主义学习理论之上的CSCW的多元化的教学模式,并介绍了其主要功能和实现的关键技术,同时在教学资源库的查询方面提出了基于向量模型的条目匹配搜索算法,为网络教学系统的软件实现提供了一个良好的解决方案.     

基于移动Agent的免疫入侵检测模型及算法

结合移动agent技术和免疫系统的特性,从实际应用的角度出发,将两者的优势引入网络入侵检测系统的设计,提出了一个基于移动agent的免疫入侵检测系统MAgentIDS模型,并对其做了较为深入的研究。重点分析了用于入侵检测系统的免疫耐受模型,改进了检测分析agent采用的否定选择核心算法。开发了原型系统并模拟一些典型入侵行为,完成入侵检测系统的检测任务,实验结果表明该模型较原有的方法具有更好的适应性。     

多主体协作系统的一种形式模型

建造能一起工作的计算机系统一直是计算机科学的一项重要任务。目前多主体（Agent）协作的理论与应用研究已成为多学科和AI交叉研究的一个热点前沿课题。关于主体及多主体系统理论研究的主要难点是所谓的“副作用问题”以及动态环境下对主体资源及能力有限的特性的刻画。该文基于情形演算与三值逻辑给出了一个多主体协作的形式模型;本模型能较好的避免“副作用问题”;此外,在此基础上给出的一个多Agent协作规划理论能较好的刻画动态环境下主体的上述特性。     

基于DFL的多Agent时序推理模型研究

Agent的理论、技术,特别是多Agent的理论、技术,为分布式开放系统的分析、设计和实现提供了一个崭新的途径。目前,对Agent的研究大致分为智能Agent、多Agent的程序设计。该文对Agent系统的群体组织结构进行深入研究,基于DFL,给出多Agent时序推理模型理论,进一步丰富Agent系统理论的研究内容。     

Agent在多Agent系统中计算的意愿理论*

提出了Agent在多Agent系统中计算的意愿理论,以支持Agent计算的理论研究.区分了两种意愿：实现型意愿和维护型意愿.基于多Agent系统计算的逻辑框架,给出了两种意愿新的语义定义,获取和描述了它们的一些重要逻辑属性.