Ad Hoc网络中一种新的能量优化多播路由算法

探讨了Ad Hoc网络中能量优化的多播路由问题.在一次多播会话中节点功率不变的假设前提下,分析了NJT(Node-Join-Tree)算法,针对NJT算法所生成的多播树中可能存在冗余发送节点的问题,提出了一种新的能量优化多播路由算法——RMT(Refine-Multi-cast-Tree)算法,给出了RMT算法的复杂性分析,并设计了RMT算法的分布式实现方案.RMT算法在已有多播树中进行本地搜索,寻找是否存在冗余的发送节点,若存在冗余发送节点则将其从多播树发送节点集合中删除,重构多播树,从而达到减少多播树能量消耗的目的,生成能量更优的多播树.仿真实验表明RMT算法性能优于NJT算法.     

一种频繁复合项目集的混合求解方法

关联规则挖掘的关键在于频繁项目集的求解,为了能够在含有数值类型数据的交易数据库中快速求解含有多值的频繁项目集,拓展了含有多种数值的交易数据库定义.在此基础上,根据树的思想,建立含有交易项和交易数量的树,并结合Apriori算法和智能搜索,提出在各个较小的树枝路径中求解频繁项目集求解方法FABCTA(Fast Algorithm ByCandidate Transaction Tree and Apriori).通过采用真实数据实验对比,FABCTA效率明显优于Apriori算法.      

基于二进制标签的改进HSSE—tree算法

随着对航天器自主生存能力要求的提高,基于模型的故障诊断成为国内外的研究热点.计算全体极小碰集是基于模型的故障诊断中的关键步骤,以HSSE-tree算法为基础,结合二进制位标记,提出一种HSSE-tree的高效改进算法——Binary-label HSSE.改进算法采用二进制位标记来代替实际节点元素,并采用了有效的剪枝策略及节点扩展方式,避免了HSSE-tree算法中存在的节点个数及超集个数随着问题规模增大而产生的爆炸式增长的问题;此外,改进算法采用二进制位运算,避免了判断碰集及判断是否超集时的元素遍历,使算法的运行时间进一步减少.仿真结果表明,与HSSE-tree算法相比,改进算法的消耗时间及占用内存均有了大规模减少.这为航天器系统的故障诊断及实时诊断提供了理论依据和应用基础.     

数据流频繁闭集的在线挖掘

基于算法LossyCounting,提出了数据流频繁闭集的在线挖掘算法LC_Closed(LossyCounting_Closed).设计了基于前缀树的频繁闭集压缩存储结构CI-forest(ClosedItemsets-forest),利用该数据结构可以快速的插入和查询闭集模式,且在处理新的事务数据时能够快速定位相关的历史闭集模式.该算法采用在线的处理方式,提高了算法的实时性.实验的结果证明该算法是有效的.      

基于前缀树的数据流容错概要结构构造

应用于数据流环境的数据挖掘算法应首要考虑算法的时空复杂性,而要实现消耗巨大计算资源的容错模式挖掘则更要专注于算法的效率.容错模式挖掘是为了从被噪声干扰的真实世界数据中获取允许一定程度错配的、更加泛化的有用知识.提出一种新的单遍历、高压缩的容错前缀树形概要结构DSFT-tree(Data Stream Fault-Tolerant Frequent Pattern Tree),用来捕捉最近到达的数据流中的数据元素,并且能够高效移除过期数据,实现最大限度地降低计算资源消耗.利用滑动窗指针和位向量表达法实现容错树形概要结构的高效重构,并进一步基于滑动窗口技术实现了数据流环境下的容错频繁项挖掘.实验采用IBM数据发生器产生事务数据,在合理时间内最终挖掘频繁项的数量为FP-stream算法的1.5倍.      

满足战场需求的实时飞行路径规划

基于启发式A*搜索技术,给出了两种战机飞行路径实时规划算法,通过采用折距替代直线距离,达到减少扩展点和提高搜索速度的目的;通过添加虚拟威胁源,解决了飞机最小转弯半径和飞行目标进入角度限制问题,通过飞行速度和飞行到达时间对应的最大飞行距离来对规划过程中扩展节点的剪枝,可以满足飞行速度、飞行时间等战场需求,提出的算法还保证穿越威胁源飞行飞机的生存性达到最大.仿真结果证实了该算法的有效性以及实时性.      

一种有效压缩频繁模式挖掘的算法

频繁模式挖掘的研究最近致力于在一个合理的容错范围内寻找有代表性的模式来压缩庞大的挖掘结果集.一种新型启发式算法AMSA(Approximating Mining based Simulated Annealing)被提出,其采用了模拟退火思想来保证有效性和压缩的质量.依据FIMI(Frequent Itemset Mining Implementations Repository)提供的公用数据集进行的实验结果也证明了这一结论.通过与FPclose算法和RPglobal算法分别进行了性能的比较,AMSA挖掘的结果集规模小于FPclose算法和RPglobal算法得到的结果集规模,特别是当支持度阈值很低时,RPglobal不可在合理时间内产生结果集,AMSA却可在合理时间内得出较精准的结果集.     

基于程序变异的Simulink模型测试方法

为解决当前Simulink模型变异测试中测试执行开销大、测试用例生成效率低等问题,首先根据当前的Simulink模型变异算子集,基于程序变异技术提出了Simulink模型的变异测试过程和一组改进变异算子集.实验表明,在不影响测试用例集变异评分的情况下,该组变异算子集能够有效减少变异模型的生成数量,从而降低测试开销.其次,设计了一种基于搜索的Simulink模型变异测试用例生成方法,该方法将变异模型的测试用例生成问题转换为目标函数极小化问题,通过模拟退火算法对目标函数寻优,最终搜索出能够杀死该变异模型的测试用例.最后,将该方法应用于典型案例,验证了方法的正确性和有效性.      

一种新的判别决策树的建树准则

讨论了一种新的判别决策树评价准则,在建立二分树的过程中,提出采用不可分辨度最大下降作为选择自变量的原则.这种新准则与经典的非纯度下降算法在概念上是近似的.如果适当定义非纯度下降算法中的权重,则这两个准则就是完全等价的.然而,新准则的计算更加简单,并且通过案例分析可知,对新准则计算结果的解释也更加容易.     

基于多最小支持度的加权关联规则挖掘算法

针对交易数据库中数据项重要性不同的现象,提出了新的加权关联规则模型,并基于该模型设计了一个基于多最小支持度的加权关联规则挖掘新算法,允许用户设定多个最小支持度,为数据项设置不同的权重,从而解决数据项的重要性各不相同且出现频率不均匀的问题,发现更多有趣的规则.理论证明了相关性质,并实验验证了算法的有效性.      

基于状态转移图的启发式深空探测器任务规划方法

针对深空探测器复杂系统并行及约束耦合等特点,在时间线描述框架的基础上,引入了状态转移图结构。通过分析探测器任务规划中的耦合约束关系,设计了转移图代价计算方法,并提出了基于状态转移图的启发式任务规划算法。利用转移图设计启发式对无关节点进行剪枝,削减了搜索空间,加速了搜索过程。数值仿真结果表明,该算法能够有效减少不必要的规划步数,提高任务规划的效率。     

STL数据模型的快速切片算法

分析了现有的STL(stereolithography)模型切片处理算法的特点,在此基础上提出了基于分组矩阵和活性三角片表的切片算法.该算法根据三角片的最小和最大z坐标以及切片厚度,建立三角片的分组矩阵和活性三角片表,并在活性三角片表中建立局部的三角片邻接拓扑关系,以减少在切片过程中对三角片的遍历次数、排序次数以及求交计算量,简化了切片轮廓环的构造过程,从而有效地提高了切片算法的整体效率.      

基于参数矩阵计算全体极小碰集的方法

极小碰集计算是基于模型诊断的关键步骤之一.针对参数化求解方法的局限性,以及大型系统诊断中由于状态空间规模增加导致诊断能力下降甚至无法诊断等问题,研究了一种非参数化极小碰集求解算法M-MHS(Matrix-based Minimal Hitting Set)算法.该算法利用参数矩阵描述元素与集合的关系,通过矩阵分解将原始问题逐步分解为多个子问题,并采用有效的剪枝规则避免对无解子问题的计算.仿真结果表明:该算法能够计算全体极小碰集,且在进行较大规模碰集计算时性能优于HSSE(Hitting Set-Set Enumeration)算法和去参数化后的BNB-HSSE(Branch and Bound-HSSE)算法,并对不同规律数据能够维持性能稳定,从而为大型系统基于模型诊断提供了可行方法.