一种基于MDDs的可达状态的算法研究

以固定点为数学基础,多值决策图(Multi-Valued Decision Diagrams,MDDs)为存储结构来实现系统可达状态空间建立的饱和算法在异步系统的模型中显示其良好的空间和时间效应。对该算法的理论和实现方法进行详细的阐述和分析,提出通过对当前事件中的扩展链的预先判断,修改原饱和算法来实现取消无扩展链的事件的函数递归调用、新节点的内存空间的申请与回收,达到提高算法的时间和空间效率;并从理论推理和实验上进行验证。

开放Petri网可达状态求解系统的开发与实现

Petri网模型是理论计算机科学包括自动机模型和形式语言理论的一个分支,具有自然、直观、简单易懂等特点。开放Petri网是Petri网的一种扩充,在并行模型分析,协议的验证,自动控制等方面有广泛的应用。该文的主要工作在于开发一个可以生成开放Petri网的软件,并能够求解其所有的可达状态,最后通过这样一个软件来研究开放Petri网的可达状态总数随网的规模变化和初始Token数变化而变化的情况。我们得到的结论是在这两种情况下可达状态数都是呈指数增长的。

不确定规划中循环可达状态信息的维护

动态环境下,动作执行的不确定性会因外部因素存在变动,因此将导致不确定系统中的状态可达关系可能发生改变。为解答这一问题,论文对信息传递法中状态之间可达关系的更新方式进行改进,提出一种新的状态可达关系的维护算法。该算法将变更的状态之间可达关系与原可达矩阵对比,利用邻接矩阵中对应可达信息对变更后状态的可达信息进行修改,然后通过状态之间信息传递,求解不确定系统中局部状态可达关系,从而避免了更新过程中的重复计算。实验结果表明,该方法在运算时间上要优于重新利用信息传递法来维护系统的状态可达关系。

基于可达状态集扩张的粒子群算法收敛性改进

针对粒子群算法(PSO)改进设计缺乏数学模型和理论依据支持的问题,研究建立了PSO的吸收态马尔可夫过程模型,并提出了可达状态集作为收敛性分析的关键指标.与以往的收敛性分析不同,研究从可达状态集扩张的角度提出了PSO收敛性对比的理论,并基于此提出了PSO全局收敛性改进的方法.最后,以改进综合学习粒子群算法CLPSO(comprehensive learning particle swarm optimization)为例验证了提出模型与理论的有效性.

基于可达最佳状态标准的叶尔羌河健康评价

为了有效保护和管理干旱区内陆河流,以叶尔羌河卡群—艾力克塔木河段为研究对象,提出"以可达最佳状态为标准"的河流健康评价标准;基于压力-状态-响应模型建立了包含24项指标的河流健康评价指标体系;构建了基于突变级数法的河流健康评价模型,进行河流健康评价研究。结果表明:评价现状年2015年该河段目标层突变级数为0.95,河流健康综合评价等级为Ⅲ级,处于亚健康状态,即河流健康为由健康向不健康过渡的预警状态。评价结果与实际情况基本符合,河流健康生命已受到威胁,河流健康维护工作势在必行,维护河流健康的关键是满足河道生态基流保障率,提高河道外用水尤其是农田灌溉用水效率,以及提高流域管理机构河流综合治理水平和水资源优化配置效率。

基于状态可达图的离散事件系统时态性质分析

离散事件系统的许多重要性质可用时态逻辑方便、直接和简明地进行描述，系统的性质分析可转化成时态公式满足关系的判定。基于状态可达图，给出了有限系统时态特征的判定方法。

时间约束Petri网的状态可达性分析算法

时间约束Petri网是具有广义时间约束的一类Petri网。时间约束的引入使TCPN′s的演化与系统每一时刻的状态都密切相关 ,导致网的动态复杂性。目前有关TCPN′s状态可达性的研究仅局限于一些较简单的网。进一步研究了TCPN′s,给出了更一般的可达性分析方法及变迁可调度决策算法。

基于结构无竞争Petri网的DEDS的状态可达性可控性及其控制

本文给出了依靠代数递推计算判断结构无竞争Ｐｅｔｒｉ网的状态可达性的一种方法；提出了动态子网的概念，提高了判断速度；研究了结构无竞争Ｐｅｔｒｉ网的可达状态控制问题。

SIP软交换系统对话状态可达性的研究

针对SIP软交换系统提出了在同一个会话中点到点终端对话的状态可达性模型。根据SIP及SIP扩展协议,并结合stateless和stateful的模式,研究SIP终端间三方通话时的对话状态可达性模型,通过应答前传送来检证三方通话的对话状态可达性模型。

不确定规划中状态循环可达关系的求解方法

在不确定规划领域中,不确定状态转移系统求规划解常常会搜索大量无用的状态和动作,造成冗余计算。获得不确定状态转移系统的状态可达关系可以避免无用搜索、减少冗余计算,为系统提供引导信息。以非循环可达关系为基础,定义矩阵的计算规则,使用系统的邻接矩阵来计算可达矩阵。同时首次提出了循环可达关系的分类、二可达关系等,并设计了求循环可达关系的算法,且以实例证明了算法的有效性和正确性。在不确定规划中获得状态之间的可达性关系,在求规划解的过程中可以删除大量无用的状态动作序偶,降低问题规模,提高求解规划问题的效率。

利用状态缓存的时序等价性验证算法

为了提高时序电路的等价性验证速度,提出一种改进的基于寄存器匹配的验证算法.除了利用原像计算避免误判之外,该算法还将可达状态和不可达状态引入到验证过程中.将仿真过程中从初始状态可以到达的状态记录为可达状态,将验证过程中确认不能从初始状态到达的状态记录为不可达状态,利用它们减少验证过程中的原像计算.基于mcnc91电路的实验数据表明,该算法有效地减少了验证时间.

基于UML状态图和基本Petri网生成测试用例

结合UM L状态图和Petri网提出了一种生成测试用例的方法。将UM L状态图转换成对应的EN—系统模型,利用EN—系统的性质检测并排除UM L状态图中的不可达状态和事件的冲突和冲撞;再应用与合理的UM L状态图对应的EN—系统生成可达状态图,利用可达状态图生成测试用例。该方法一方面可以很好地实现并行子状态的嵌套问题,避免了将并行的UM L子状态展平成EFSM时引起的状态爆炸问题;另一方面,由于测试用例的覆盖标准是基于可达状态图的基路径、事件和可达状态覆盖,所以还很好地解决了对系统的不同测试要求和状态的可达性问题。

改进的状态空间模型遗传算法及其全局收敛性分析

基于状态空间模型遗传算法(GABS)是一种新型实数编码进化算法,在工程优化问题中取得良好的应用效果.针对GABS缺乏有效的数学模型及理论依据,研究并建立了GABS的吸收态马尔可夫过程模型,从可达状态集的角度对GABS进行分析并证明GABS不是全局收敛的.基于此提出了一种扩张可达状态集的改进型GABS(MGABS),改进方法的两种变异策略不仅扩张了算法的可达状态集、提高了种群多样性,而且加快了算法的收敛速度与精度,并证明了MGABS具有全局收敛性.最后利用经典测试函数验证了其综合性能明显优于其他3种算法,为算法在工程中的应用提供了理论依据.

不确定规划中非循环可达关系的求解方法

对一个不确定状态转移系统求多个规划问题,那么获得不确定状态转移系统的状态可达关系可以方便求解规划问题,减少冗余计算,建立系统的引导信息。提出一个关于矩阵求不确定领域的状态可达性关系的方法,主要思想是以矩阵乘法来模拟状态转移系统中状态转移,对不确定动作带来的扩散和确定关系带来的聚合进行了统计和处理,从而获得状态可达信息。证明了方法的正确性和有效性。在不确定规划中确定了状态之间的可达性关系,可以在求规划解时删除对规划没有用的状态节点和状态动作序偶;选择能到达目标节点的状态节点和状态动作序偶;进行启发式正向搜索;减少大量冗余计算;提高求解效率。

面向程序验证的并行程序状态空间态约简技术综述

程序验证是保证程序安全性的重要手段。随着采用多核技术的硬件环境日渐普及,越来越多的软件正通过转向基于共享内存的并行程序模型来充分利用现有的计算资源。各线程在并行执行时通过共享内存的访问互相干扰执行状态,导致可能执行路径数成几何级数增长,进而产生可达状态空间爆炸问题。由于验证并行程序安全性主要通过分析程序可达状态来实现,因此,对并行程序可达状态空间的约简是决定并行程序验证效率的关键因素。首先对面向并行程序验证的并行程序可达状态空间约简方法进行了分类,然后对各类可达状态空间约简方法分别进行了分析和总结,最后指出了当前存在的问题和未来解决这些问题的研究方向。

混合动态系统SPN的可达性分析

根据混合动态系统SPN(StochasticPetriNets)模型的运行规则,给出了几种典型结构(串行结构、并行结构、冲突结构)中变迁的可激发以及可激发成功概率的计算方法,在此基础上,计算出托肯沿几种基本路径(简单串行路径、简单并行路径、简单Fork/Join路径)从起始库所到达终止库所的可达概率,同时从宏观状态的角度构建了该SPN模型的状态可达树,通过可达树可以判断状态间的可达性并计算可达概率。

概率布尔控制网络的可观性分析

概率布尔控制网络的转移矩阵的不确定性,使得其可观和可控性分析和状态估计更为困难。主要研究了概率布尔控制网络的可观性问题,并在此基础上给出了判断系统可观的条件,以及计算系统初始状态向量的方法。首先,根据系统的可达状态集,定义系统的可区分和不可区分状态,并给出d步可区分的概念以及其判断的充要条件。其次,根据概率布尔控制网络的输出和系统模型,得到系统的概率初始状态集合。接着,在此基础上给出概率布尔控制网络的强可观和弱可观的定义。同时,计算系统初始状态向量,并且给出判断系统是否可观的定理;最后,通过一个算例说明了所提方法的有效性。

论力学系统的自由度

力学系统的自由度定义源自描述系统位形的独立坐标数.在分析力学发展过程中,人们通过对非完整约束的研究,将其拓展为独立的坐标变分数.本文指出,对于含非完整约束的力学系统,该定义存在不妥之处,给出的自由度会过度限制系统的力学行为.文中研究力学系统在状态空间中的可达流形,指出可达流形维数与描述系统动力学的一阶常微分方程组的最少未知函数个数一致,例如Gibbs-Appell方程与广义速度方程联立的未知函数个数,进而将可达流形维数的一半定义为系统自由度.通过含黏弹性支承的振动系统、在倾斜平面上运动的冰橇等案例,讨论了单个非完整约束导致的半自由度概念,指出其力学意义和与相邻整数自由度的关系.此外,文中还给出两个非完整约束导致系统减少一个自由度的案例,讨论了系统的切丛和余切丛维数.

基于变迁指标的Petri网分解方法

通过定义 Petri 网变迁的指标函数,给出一种基于变迁指标的 Petri 网分解方法,通过分解得到子网系统均为结构简单的 T-网。分析了原网系统与子系统在结构性质和动态性质方面的对应关系,并且证明了通过子网之间的共享合成可以得到原先的网系统,这为 Petri 网用于复杂的物理系统分析提供了可靠的理论依据和技术手段。

直觉模糊有限自动机的行为特征

提出了一种新的直觉模糊有限自动机,重点讨论了响应函数、直觉可达状态、直觉初始分布、行为特征、直觉正则的一些性质,揭示了直觉模糊有限自动机的行为特征。