网络可靠度BDD分析中2种边排序策略的性能比较

网络可靠度二元决策图（BDD）分析过程包含边排序、BDD生成和可靠度评估3个步骤,其中BDD生成和可靠度评估的计算复杂度和BDD尺度线性相关,而BDD尺度取决于边排序．因此,边排序问题是研究网络可靠度BDD分析的核心．在实现广度优先和深度优先2种边排序策略的基础上,针对规则网络（N＊N型和M＊N型）,比较了这2种策略的分析性能．实验数据表明：1）规则网络中广度优先边排序策略优于深度优先边排序策略;2）当M〉N时,广度优先边排序策略在M＊N型网络中的性能表现优于与之等价的N＊M型网络．这些结论为设计更优的启发性边排序策略提供了重要依据．     

基于动态筛选算法的二元判定图的优化

作为逻辑布尔函数的一种高效简洁的描述方法,BDD规模结构对应着计算机实现算法的空间和时间复杂性。随着应用领域的不同,BDD的节点和路径的规模成为关注的两个焦点。文章讨论利用基于动态规划的筛选算法来实现从节点规模和路径的大小两方面对BDD的优化。在将筛选算法用于节点优化的基础上,从理论上提出了优化路径的思路及可行算法。     

计算有圈有向网络根通信可靠度的因子分解算法

对有圈有向网络的拓扑结构进行了研究,提出了一个保持网络可靠度不变的缩减规则和因子分解的一个选边规则.由此建立了一个计算有圈有向网络根可靠度的有效算法.算法的时间复杂度是O(N.(|V|+|E|)),其中N是算法所产生二叉树的叶点数,|V|和|E|分别表示网络的节点数和边数.对一些网络进行了计算,结果显示利用该算法计算根通信可靠度所产生的N比其他算法的要小得多,因此,所提算法更有效.     

基于同构子网判定的结点不可靠网络可靠度计算方法

 为提高结点不可靠网络的可靠度计算效率,提出一种基于子网同构判定的高效计算方法。在生成有序二元决策图（OBDD）的因子分解过程中,利用特征合并划分（CMP）识别网络分解产生的同构子网,然后根据网络中边和节点的逻辑联系,执行边替换操作将不可靠结点存储于OBDD;通过遍历OBDD 计算网络的可靠度。结果显示,该方法减少了同构子网带来的重复计算,并充分利用OBDD 的存储结构进一步增强了计算效率,计算中小型网络可靠度的时间保持在100 s 以下,计算数百结点网络可靠度的时间保持在百秒级,且计算中大型网络的开销远低于标准二元决策图（BDD）方法。     

基于BDD的Grover算法仿真

为了解决仿真量子计算过程中复杂性随量子比特数的增加呈指数级递增的问题,采用二项决策图(BDD)表示矩阵算子仿真Grover提出的量子搜索算法.BDD利用矩阵算子在量子计算过程中呈现出的结构化特性,可以高效地压缩存储空间并实现在压缩数据结构上直接进行矩阵的各种运算.利用改进的BDD实现了仿真过程需要的各种矩阵运算,用C++编写的程序对Grover算法的实例进行仿真,最后从多个角度对违反直观的实验结果进行了分析,阐述了量子算法的内在并行性.     

BDD在网络系统可靠度算法中的应用

本文在已有的最小路集算法求网络系统可靠度的基础上,提出了一种利用二元判决图BDD计算网络可靠度的方法。该方法将网络的最小路集用二元判决图来表示,并得到最小路集的不交和,最后获得网络的可靠度。与其他方法比较,该方法所用的二元判决图的规模较小,并且可以计算出在不同故障率条件下、不同时间长度下的网络可靠度。     

计算网络连通可靠度的一种新型算法

大型复杂网络系统的可靠性分析都是NP难问题。结合二分决策图原理和因子分解定理以桥型网络为例提出了一种新型的算法——二分决策分解算法(TPDM算法),该算法便于计算机编程实现,通过与BDD等算法的比较研究表明,该算法的复杂度更低、可行性更高。     

网络可靠度分析的改进最小割递推分解算法

在网络连通可靠度分析的最小割递推分解算法基础上,充分利用分解过程中获得的信息,采用合并节点以及合并并联边的方法,有效地简化了分解出来的子网,大幅度降低了算法分解出来的不交最小割和不交最小路数量,从而大幅度地减少了计算时间.3个网络实例计算分析表明,与最小割递推分解算法相比,改进最小割递推分解算法能更高效地计算得到网络系统的连通可靠度,为生命线工程网络的抗震可靠性提供了1种更加有效的分析工具.     

一种多阶段任务系统的BDD排序新方法

近年来,BDD(二元决策图)的分析方法越来越多地被用于多阶段任务系统可靠性分析中.BDD方法应用的一个关键是在从故障树向BDD转换时需要对底事件进行排序,所选择的排序顺序将影响构造的BDD的节点数.与单一阶段任务系统相比,多阶段任务系统的可靠性分析由于阶段之间的相关性而变得更加复杂,将一般的BDD排序方法直接应用于多阶段任务系统的BDD分析很难得到令人满意大小的BDD.在考虑多阶段任务系统的结构和特性的基础上,通过共同失效组件对多阶段故障树化简,提出了基于最小相邻组件优先相邻排序的多阶段任务系统BDD排序方法.通过与一般的排序方法相比较,这种新方法可以生成更理想的BDD结构.     

基于交易成本和红利的欧式期权二叉树模型及算法

二叉树期权定价模型是期权定价理论中一种重要的数值方法,典型的二叉树模型是在没有交易成本及红利的基础上建立的,本文考虑有交易成本和红利的欧式期权二叉树图法,分别从已知红利率和交易成本比例以及已知红利数额和交易成本数额两方面,给出了欧式期权二叉树模型。 并结合典型二叉树模型的矩阵算法,给出了修正后二叉树模型的矩阵形式算法和MATLAB程序语言,使其在实际金融市场中的应用更加便捷。     

遗传算法在网络最短路径问题上的应用

将网络最短路径问题抽象为求最小生成树问题,分析了最小生成树在解决实际问题时的局限性,引入了节点的度的概念;针对一般遗传算法在求解某些工程问题时存在的一些不足,提出了用量化约束条件来改进适应值函数、节点与度约束相结合编码的二进制编码方式、基于节点域的交叉和变异运算的策略.通过对公路交通网络的仿真表明,采用一般遗传算法与普通遗传算法分别求解,数值计算结果证明了改进后的遗传算法的可行性.     

基于启发式二分策略的属性约简方法

分辨矩阵为属性约简与求核运算提供了一种规范精确的数学模型,通过分辨矩阵模型可方便地获取决策系统全体属性约简.本文基于分辨矩阵运用启发式信息与二分策略扩展结点,设计了一种构造约简树求取全体属性约简的有效算法,该约简树从根结点到叶结点全体路径构成的析取范式与系统分辨函数等价,其极小析取范式所有析取项即为决策系统全体属性约简.该方法适用于满足任意约简准则的分辨矩阵,能够显著地减少搜索空间和保证全体约简求解的完备性,理论分析与实验结果说明了算法的可行性与有效性.     

求网络极小割集的一个新算法

定义了网络连结矩阵的两个变换,引入了L满秩矩阵与L非满秩矩阵的概念·证明了这两类特殊矩阵与网络连通性的关系·利用这一关系和定义的两个变换,给出了求网络极小割集以及与极小割集对应的结点集合的递推公式;建立了一个求网络所有极小割集及与之对应的结点划分集合的有效算法·算法只需对网络的连结矩阵进行处理,在计算机上实现起来很方便·最后通过实例说明了算法的有效性·     

基于动态调整的GA-SVM多分类二叉树的方法

基于遗传算法的支持向量机决策树多分类方法仍然存在错误累积的问题,累积的错误往往使分类准确率下降,分类效果变差,存在全局优化缺陷的问题;并且在每个节点进行二分类常用的实数编码切分方法,效率低下。针对这两方面的问题,提出从根节点开始逐层构造二叉树,运用二进制编码的遗传算法进行每一阶段的二叉树构造。二进制编码对于每个节点的分类以及进行交叉、变异更高效,不用考虑从什么位置切分。针对越靠近根节点产生的误差对后续节点分类误差的累积影响,提出一种动态调整的方法,此方法对每个节点赋予权重再进行对权重的调整使得整体的分类误差减小,最终得到二叉树的全局最优,从而提高分类精度。通过实验并进行五折交叉验证表明,DABT-SVM比多种传统的支持向量机多分类算法在全局优化能力和分类精度上有很大的提升。验证了该算法的可行性和有效性。     

Fault Tree Analysis of a Launching with Binary Decision Diagram Method and Fuzzy Theory

Fault tree analysis(FTA),as a structurally simple,visualized and scientific method,is widely used in various fields.To complete the FTA of the launching device,the binary decision diagram(BDD)method is used to obtain the non-intersect cut sets,the minimum cut sets and the probability importance of components.Then,the expert evaluation method is applied to solving fuzzy probability rate of bottom event with zero failure data.In this paper,the BDD and expert evaluation method are applied into FTA to analyze a launch device.     

一种新的模糊决策树算法 ——基于加权毕达哥拉斯模糊熵

传统的模糊决策树虽然可以从模糊数据中抽取模糊分类规则,但只能获取节点的隶属度信息,无法得出样本数据对于节点的非隶属度和犹豫度信息,导致数据分类的准确率不高。针对此,基于毕达哥拉斯模糊集理论,提出了一种新的加权毕达哥拉斯模糊决策树算法（Weighted Pythagorean Fuzzy Decision Tree,WPFDT）。首先,通过改进的K-means聚类算法得到连续属性数据的聚类中心,并结合三角模糊数对连续数据进行模糊处理;其次,定义并计算每一个属性的加权毕达哥拉斯模糊熵,选择加权毕达哥拉斯模糊熵最小的属性作为决策树根节点,在根节点下递归选择模糊熵最小的属性作为分裂节点,同时通过阈值控制树的规模,得到从根节点到叶子节点路径的模糊规则以及模糊规则的隶属度、非隶属度以及犹豫度,并完成预测分类,直至生成WPFDT模型;最后,选取UCI上的3个医学数据集（Haberman、Breast Cancer、Parkinson）进行实验,在分类准确率和得出模糊规则的数量与3种传统决策树算法（模糊ID3算法、C4.5算法、CART算法）比较,实验结果表明：WPFDT在分类精度和树大小上都优于其他传统决策树算法,并且有较高的召回率和精确率。     

基于攻击树的核电厂DCS系统信息安全脆弱性分析

随着计算机在核电仪控系统中的广泛运用,其信息安全问题受到越来越大的挑战.提出一种基于攻击树的核电仪控系统信息安全脆弱性分析方法,旨在对系统信息安全脆弱性进行量化分析.该方法首先给叶节点赋予三个不同属性,然后采用模糊层次分析法计算各攻击事件属性的权值.最后计算出叶节点、根节点及攻击路径发生概率.实际案例分析表明:计算得出的结果即给出了各节点和攻击路径发生的概率,还指出了攻击者最有可能采取的攻击路径,证明了该方法是合理可行的.基于攻击树的核电仪控系统信息安全脆弱性分析方法对系统管理者建设防御措施有积极的指导意义.     

改进的二进制查询树的RFID标签防碰撞算法

在射频识别系统中,存在阅读器与多个标签同时通信的碰撞问题,标签的防碰撞算法是解决数据冲突的关键。文章详细阐述了已有的典型的二进制查询树的防碰撞算法,并在此基础上提出了一种新的防碰撞算法;该算法利用二时隙的方法,使阅读器的询问次数和标签识别所需的数据流大大减少,提高了标签的识别效率。从仿真实验中表明,该算法比已有的二进制查询树算法具有更明显的优势。     

基于Rough集的决策树算法

针对基于Rough集的经典分类算法值约简算法等不适合大数据集的问题，提出了基于Rough集的决策树算法。采用一个新的选择属性的测度——属性分类粗糙度作为选择属性的启发式，该测度较Rough中刻画属性相关性的测度正区域等更为全面地刻画了属性分类综合贡献能力，并且比信息增益和信息增益率的计算更为简单。采取了一种新的剪枝方法——预剪枝，即在选择属性计算前基于变精度正区域修正属性对数据的初始划分模式，以更有效地消除噪音数据对选择属性和生成叶节点的影响．采取了一种与决策树算法高度融合的简单有效的检测和处理不相容数据的方法，从而使算法对相容和不相容数据都能进行有效处理。对UCI机器学习数据库中几个数据集的挖掘结果表明，该算法生成的决策树较ID3算法小，与用信息增益率作为启发式的决策树算法生成的决策树规模相当。算法生成所有叶节点均满足给定最小置信度和支持度的决策树或分类规则，并易于利用数据库技术实现，适合大数据集。