基于OBDD的描述逻辑εL循环术语集推理

循环术语集推理是描述逻辑研究中面临的难点问题,尚未得到很好的解决.有序二叉决策图（ordered binary decision diagram,简称OBDD）是一种对布尔函数进行紧凑表示和高效操作的数据结构,适用于表示和处理大规模问题.将OBDD应用于描述逻辑循环术语集的推理.首先,针对描述逻辑εL中的循环术语集,给出了描述图上关于最大模拟关系的重要性质,并借助集合表示和集合运算对该性质进行了表述和证明.在此基础上,应用布尔函数对描述图进行编码,给出了基于OBDD求解最大模拟关系的方法,进而给出了最大不动点语义下基于OBDD对概念包含关系进行判定的算法;接下来,基于OBDD给出了求解描述图中可以到达循环路径的所有结点的方法,进而给出了最小不动点语义下基于OBDD对概念包含关系进行判定的算法;最后,对算法的正确性、复杂度等进行了分析和证明,并对算法进行了编程实现,给出了关于计算性能的实验结果.该工作为循环术语集的推理提供了一条有效途径,也为OBDD在逻辑推理中的应用提供了新的案例.     

一种基于马尔可夫博弈的能量均衡路由算法

针对无线传感器网络中耗能不均问题,引入马尔可夫博弈理论,构建了无线传感器网络的马尔可夫博弈模型.在能量均衡路由分析的基础上,给出了一种基于马尔可夫博弈的能量均衡路由算法,该算法从无线传感器网络整体耗能出发,兼顾节点之间的合作.定义了能量和信誉值的二元收益函数,给出了节点转发的状态转移概率,根据收益函数进行能量调节,求解出能量和收益之间的均衡系数——纳什均衡,实现了节点能量的均衡消耗,延长了网络的生命周期.使用PRISM概率仿真工具进行仿真,验证了该博弈模型存在纳什均衡点,同时表明该模型能促进节点之间合作,最大化无线传感器网络的生命周期.     

基于时态测试器的实时分支时态逻辑模型检测

基于自动机理论的模型检测技术在形式化验证领域处于核心地位, 然而传统自动机在时态算子上不具备可组合性, 导致各种时态逻辑的模型检测算法不能有机整合.本文为了实现集成限界时态算子的实时分支时态逻辑RTCTL*的高效模型检测, 提出一种RTCTL*正时态测试器构造方法, 以及相关符号化模型检测算法.证明了所提出的RTCTL*正时态测试器构造方法是完备的.也证明了该算法时间复杂度与被验证系统呈线性关系, 与公式长度呈指数关系.我们基于JavaBDD软件包成功开发了该算法的模型检测工具MCTK 2.0.0.我们完成了MCTK与著名的符号化模型检测工具nuXmv之间的实验对比分析工作, 结果表明MCTK虽然在内存消耗上要多于nuXmv, 但是MCTK的时间复杂度双指数级小于nuXmv, 使得利用MCTK验证大规模系统的实时时态性质成为可能.     

水体重金属污染的微生物治理研究与应用

本文分析了重金属污染水体的微生物治理的原理及微生物技术在水体重金属污染治理中的应用，概述了该领域中基因工程、酶和细胞的固定化技术以及生物吸附剂的研究进展，提出了污染水体的微生物治理研究方向。     

加权约束满足问题的符号ADD求解算法

加权约束满足问题(WCSP)是一类软约束满足问题。给出WCSP的代数决策图(ADD)描述,以及基于ADD的两种符号求解算法。首先,通过对变量和变量域值的二进制编码,给出软约束图的ADD表示。其次,将分支定界搜索算法与桶消元算法及符号ADD技术相结合,在静态变量序下,利用结点一致性预处理技术,对WCSP问题进行符号ADD求解。通过引入有向弧一致性计数技术提高符号ADD算法的搜索下界,对符号ADD求解算法作了改进。最后,对大量随机生成的测试用例进行实验分析。结果表明,文中算法在性能上明显优于带有存在有向弧一致性或结点一致性预处理技术的具有前向检查功能的深度优先分支定界搜索算法。     

粗糙集多目标并行属性约简算法

粗糙集理论(RST)中,求解最小属性约简MAR (minimal attribute reduction)是一种NP-难(non-deterministic polynomialhard)组合优化问题.蚁群优化算法ACO(antcolonyoptimization)是进化算法中的一种启发式全局优化算法,粗糙集理论与ACO相结合,是求解属性约简的一种有效、可行的方式.针对蚁群优化算法易于陷入局部最优解、收敛速度慢等问题,首先以一种改进的信息增益率作为启发信息,提出了冗余检测机制,对每个被选属性和每代最优约简集合进行冗余检测,并提出了概率提前计算机制,可避免每只蚂蚁在搜索过程中相同路径上的信息反复计算;针对大数据集的属性约简问题,考虑到蚁群优化算法具有并行能力以及粗糙集中“等价类”计算的可并行性,提出一种将ACO与云计算相结合用于求解大数据集的属性约简算法,在此基础上,进一步提出一种多目标并行求解方案.该方案可以同时计算出其余属性相对于当前属性或约简集合的重要度.实验结果表明,该算法在处理大数据的情况下能够得到最小属性约简,计算属性重要度的时间复杂度由O(n2)降至O(|n|).     

基于预测控制的非完整移动机器人视觉伺服镇定

非完整移动机器人视觉伺服镇定越来越受到人们的广泛关注. 目前研究人员在解决该问题时未同时考虑摄像机的可见性约束和机器人系统的控制约束, 所设计的控制器在实际应用中很难实现满意的控制. 针对此问题, 本文设计一种预测控制器来解决移动机器人视觉伺服镇定问题. 首先设计运动学预测镇定控制器来产生参考速度指令; 然后设计动力学预测控制器使移动机器人实际速度渐近逼近期望值; 所设计的预测控制器能够容易处理系统中存在的可见性约束和控制约束; 最后对所提出的视觉伺服镇定方法进行仿真验证, 结果表明所设计的控制器能有效解决移动机器人视觉伺服镇定问题.     

目标独立的Prolog程序路径依赖分析语义

在Prolog程序分析中,考虑程序的执行路径和非逻辑的cut操作可提高程序分析的精度.当前用于Prolog程序路径依赖分析的语义因依赖于程序执行的目标而不适合目标独立的程序分析.为此,本文采用了一种携带路径信息并允许cut操作的Prolog抽象语法,在此基础上给出了Prolog的操作语义和一种目标独立的标号树(LT)语文,并证明了LT语义相对于操作语义的正确性.LT语义可作为目标独立的Prolog程序路径依赖分析的基础.     

基于着色Petri网的Internet电话端系统业务冲突检测

将描述端业务的LESS脚本转换为着色Petri网模型，可以为实现形式化方法检测端业务间的冲突提供基础。本文根据业务逻辑树节点的特性和LESS的定义，提出了通用的转化规则，实现了端业务的形式化建模，从而方便了业务的集成及业务间的离线检测。通过CPN Tools对建立的业务模型进行仿真并分析模型状态空间，检测出端业务之间是否存在冲突。最后，用典型的业务实例验证了所提方法在Internet电话端系统环境中的可行性和有效性。