高级检索

  • ISSN 1006-3080
  • CN 31-1691/TQ
引用本文:
Citation:

并行系统中排列图的可靠性近似算法

    作者简介: 于中宝(1993-),男,安徽人,硕士研究生在读,研究方向为网络可靠性及其算法研究。E-mail:yuzhongbao0312@foxmail.com;
    通讯作者: 邵方明, fmshao@ecust.edu.cn
  • 中图分类号: O29

Approximation Algorithm of Arrangement Graph Reliability in Parallel System

    Corresponding author: Fangming Shao, fmshao@ecust.edu.cn
  • CLC number: O29

  • 摘要: 讨论了排列图子图可靠性界的鲁棒性问题和可靠性的近似算法,并构造了排列图的蒙特卡罗算法。仿真结果说明所构造的蒙特卡罗算法远优于已知的近似算法,A3,2子图可靠性的蒙特卡罗近似计算误差小于1%。
  • 图 1  排列图A4,2、子图X4、节点24

    Figure 1.  A4,2、subgraph X4、node 24

    图 2  1XXX, 2XXX, 3XXX, 4XXX

    Figure 2.  1XXX, 2XXX, 3XXX, 4XXX

    图 3  排列图A5,4子图可靠性的近似计算

    Figure 3.  Approximate calculations of subgraph reliability of A5,4

    图 4  排列图A3,2

    Figure 4.  arrangement graph A3,2

    图 5  排列图A3,2子图可靠性的近似计算

    Figure 5.  The approximate calculation of subgraph reliability for A3,2

    表 1  $\displaystyle\sum\limits_{i < j < l < q} {{r_{\left( {i,j,l,q} \right)}}\left( p \right)} $的计算

    Table 1.  the reliability of four subgraphs

    Reliability
    One position Two positions Three positions Four positions
    ${R_1} = C_k^{\rm{1}}C_n^{\rm{4}}{p^{4A_{n - 1}^{k - 1}}}$ $\begin{aligned} {R_2} =& C_k^{\rm{2}}(2C_n^{\rm{1}}C_{n - 1}^{\rm{2}}{p^{4A_{n - 1}^{k - 1} - 2A_{n - 2}^{k - 2}}} + \\& 2C_n^{\rm{1}}C_{n - 1}^{\rm{3}}{p^{4A_{n - 1}^{k - 1} - 3A_{n - 2}^{k - 2}}} + 2C_n^{\rm{2}}C_{n - 2}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - 3A_{n - 2}^{k - 2}}}+\\ & C_n^{\rm{2}}{p^{4A_{n - 1}^{k - 1} - {\rm{2}}A_{n - 2}^{k - 2}}} + \\& C_n^{\rm{2}}C_{n - 2}^{\rm{2}}{p^{4A_{n - 1}^{k - 1} - {\rm{4}}A_{n - 2}^{k - 2}}} \end{aligned}$ $\begin{aligned} {R_{\rm{3}}} =& C_k^{\rm{3}}({\rm{3}}C_n^{\rm{1}}C_{n - 1}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - 2A_{n - 2}^{k - 2}}} + \\& {\rm{3}}C_n^{\rm{1}}C_{n - 1}^{\rm{2}}{p^{4A_{n - 1}^{k - 1} - {\rm{4}}A_{n - 2}^{k - 2}}} +\\& {\rm{6}}C_n^{\rm{1}}C_{n{\rm{ - 1}}}^{\rm{1}}C_{n - 2}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - {\rm{4}}A_{n - 2}^{k - 2} + A_{n - {\rm{3}}}^{k - {\rm{3}}}}}+\\& {\rm{3}}C_n^{\rm{1}}C_{n{\rm{ - 1}}}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - {\rm{3}}A_{n - 2}^{k - 2}}}+\\ & {\rm{3}}C_n^{\rm{1}}C_{n{\rm{ - 1}}}^{\rm{1}}C_{n - 2}^{\rm{2}}{p^{4A_{n - 1}^{k - 1} - {\rm{5}}A_{n - 2}^{k - 2} + {\rm{2}}A_{n - {\rm{3}}}^{k - {\rm{3}}}}} \end{aligned}$ $\begin{aligned} {R_{\rm{4}}} = & C_k^{\rm{4}}(C_n^{\rm{1}}{p^{4A_{n - 1}^{k - 1}}} + \\& {\rm{4}}C_n^{\rm{1}}C_{n - 1}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - {\rm{3}}A_{n - 2}^{k - 2}}}+ \\& {\rm{3}}C_n^{\rm{1}}C_{n - 1}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - {\rm{4}}A_{n - 2}^{k - 2}}}+ \\& {\rm{6}}C_n^{\rm{1}}C_{n{\rm{ - 1}}}^{\rm{1}}C_{n - 2}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - {\rm{5}}A_{n - 2}^{k - 2} + {\rm{2}}A_{n - {\rm{3}}}^{k - {\rm{3}}}}}+\\& C_n^{\rm{1}}C_{n{\rm{ - 1}}}^{\rm{1}}C_{n - {\rm{2}}}^{\rm{1}}C_{n - {\rm{3}}}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - {\rm{6}}A_{n - 2}^{k - 2} + {\rm{4}}A_{n - {\rm{3}}}^{k - {\rm{3}}} - A_{n - {\rm{4}}}^{k - {\rm{4}}}}}) \end{aligned}$
    下载: 导出CSV

    表 2  A3,2的子图可靠性蒙特卡罗近似计算

    Table 2.  The approximate calculation of the Monte Carlo Method for A3,2

    Cycles N Monte Carlo error/%
    100 0.218
    500 0.185
    1 000 0.084
    下载: 导出CSV

    表 3  排列图An,k子图可靠性的界以及近似计算(n=3,4,5,6,7,k=2,3,4)

    Table 3.  the bounds and the approximate calculation of subgraph reliability for An,kn=3,4,5,6,7, k=2,3,4)

    An,k Lower bound Algorithm1 Ref[1] Monte Carlo algorithm Upper bound
    A3,2 −4.048 0.144 0.999 5 0.988 4.335
    A4,2 −6.446 −0.766 0.999 5 0.994 4.913
    A5,4 0.281 0.297 0.336 0.301 0.313
    A6,3 0.344 0.425 0.509 0.434 0.506
    A7,3 0.139 0.140 0.149 0.141 0.142
    下载: 导出CSV

    表 4  排列图A3,2子图可靠性的近似计算

    Table 4.  The approximate calculation of subgraph reliability for A3,2

    p Real value Ref [1] Monte Carlo
    0.5 0.718 8 0.822 0.718
    0.6 0.848 4 0.931 3 0.842
    0.7 0.934 8 0.982 4 0.933
    0.8 0.981 0.997 8 0.986
    0.9 0.997 8 0.999 95 0.997
    下载: 导出CSV
  • [1] LIN L, XU L, ZHOU S, et al. The Reliability of Subgraphs in the Arrangement Graph[J]. IEEE Transactions on Reliability, 2015, 64(2): 807-818. doi: 10.1109/TR.2015.2413372
    [2] CHIANG W K, CHEN R J. On the arrangement graph[J]. Information Processing Letters, 1998, 66(4): 215-219. doi: 10.1016/S0020-0190(98)00052-0
    [3] CHENG E, GROSSMAN J W, QIU K, et al. The number of shortest paths in the arrangement graph[J]. Information Sciences, 2013, 240(11): 191-204.
    [4] FENG K, WANG S Y, ZHANG G Z. Link Failure Tolerance in the Arrangement Graphs[J]. International Journal of Foundations of Computer Science, 2015, 26(02): 241-254. doi: 10.1142/s0129054115500148
    [5] YANG W, LI H, GUO X. A kind of conditional fault tolerance of (n,k)-star graphs[J]. Information Processing Letters, 2010, 110(22): 1007-1011. doi: 10.1016/j.ipl.2010.08.015
    [6] CANCELA H, KHADIRI M E, PETINGI L A. Polynomial-Time Topological Reductions That Preserve the Diameter Constrained Reliability of a Communication Network[J]. IEEE Transactions on Reliability, 2011, 60(4): 845-851. doi: 10.1109/TR.2011.2170250
    [7] ZHANG Z, AN W, SHAO F. Cascading Failures on Reliability in Cyber-Physical System[J]. IEEE Transactions on Reliability, 2016, 65(4): 1745-1754. doi: 10.1109/TR.2016.2606125
  • [1] 曹移林余炜 . 平行三阶段流水作业问题的近似算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180206001
    [2] 翁童袁伟娜 . 一种基于SPSO算法降低FBMC系统PAPR的新方法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190731002
    [3] 齐莉莉刘济 . 基于改进CKF算法的一类有色噪声污染的线性观测系统的状态估计. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180427002
    [4] 解冰朱宏擎 . 一种基于选择性卷积特征和最大后验高斯混合模型的细粒度图像分类算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180603001
    [5] 张星崔向伟李宗霖李志敏 . 基于能量循环再生系统酶法生产谷胱甘肽. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190806001
    [6] 陈丹丹王薇徐以汎 . 基于降维的全局优化近似解法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.2018071700
    [7] 伏威袁伟娜 . 一种基于PTS方法降低FBMC系统PAPR的新方法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180409003
    [8] 金艳张永红宋兴福连伟何化于建国 . 耐盐菌MBR系统处理页岩气采出水性能及膜污染特性. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190606001
    [9] 高源安琦 . 轴承座同心度误差对深沟球轴承-转子系统振动性能的影响. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180415001
    [10] 肖凌云马海燕 . 茂金属催化剂催化丙烯聚合的β-Me消除选择性研究. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190329005
    [11] 张融周颖晏琦帆 . 分子内弱相互作用对共轭性的影响. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180902001
    [12] 李俊潮陈启斌谭慧玲孟晨晨刘洪来 . 基于Boc-D-丙氨酸的手性聚合物纳米颗粒的聚集诱导发光. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180514001
    [13] 王秋生曹红亮杲云 . 酸和谷胱甘肽的双重响应性聚合物胶束负载光敏剂用于肿瘤细胞的光动力治疗. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180411003
    [14] 董盛红陈金铸郭旭虹徐益升 . 可见光诱导Pd-Pt/RGO-g-C3N4催化苯甲醛选择性加氢. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180426001
    [15] 肖潮田佳刘峰张显杨王廷虎许立人顾邯沙张伟安 . 基于pH响应两亲性卟啉嵌段共聚物的光动力与化学联合治疗. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190128001
    [16] 宋振振陈兰岚娄晓光 . 基于时序卷积网络的情感识别算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190508001
    [17] 王德勋虞慧群范贵生 . 基于深度学习的面部动作单元识别算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190107003
    [18] 赵菡诸葛晶晶林家骏 . 飞行状态敏感的关联门调节算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180622003
    [19] 吉祥虞慧群范贵生孙怀英 . 基于蚁群算法的延时感知VANET路由协议. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20181116001
    [20] 高天阳虞慧群范贵生 . 基于模拟退火遗传算法的云资源调度方法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180416001
  • 加载中
图(5)表(4)
计量
  • 文章访问数:  3662
  • HTML全文浏览量:  342
  • PDF下载量:  4
  • 被引次数: 0
出版历程
  • 网络出版日期:  2019-11-04

并行系统中排列图的可靠性近似算法

    作者简介:于中宝(1993-),男,安徽人,硕士研究生在读,研究方向为网络可靠性及其算法研究。E-mail:yuzhongbao0312@foxmail.com
    通讯作者: 邵方明, fmshao@ecust.edu.cn
  • 华东理工大学数学系,上海 200237

摘要: 讨论了排列图子图可靠性界的鲁棒性问题和可靠性的近似算法,并构造了排列图的蒙特卡罗算法。仿真结果说明所构造的蒙特卡罗算法远优于已知的近似算法,A3,2子图可靠性的蒙特卡罗近似计算误差小于1%。

English Abstract

  • 并行系统提供了高速的运算潜力,但在高可靠性和容错性方面仍然存在问题,其原因与并行系统的网络拓扑有关,如超立方体,星图和排列图等。系统的可靠性定义为系统没有故障的概率,每个处理器正常运行的概率被记为p。排列图具有高容错性、直径小和低节点度等特点,因此进一步分析排列图的可靠性具有重要意义。

    Lin等[1]定义了排列图An,k子图的可靠性,并利用容斥原理给出了子图可靠性的上界以及子图可靠性的近似计算。Chiang等[2]给出了An,k的相关性质,An,kk (nk)正则图,并且有n!/(nk)!个节点,同时得出An,k的直径为$\left\lfloor {3k/2} \right\rfloor $。Cheng等[3]发现An,k中两个节点之间的最短路径算法,该算法也可用于解决其他相关图的类似问题。此外,Feng等[4]发现最小故障边的边界使An,k的每个子图$A_{n,k}^{n - m,k - m}$失效:当3≤k时,$n + \left\lceil {n/k - 1} \right\rceil - \leqslant {f_1}\left( {n,k} \right){\rm{ }} \leqslant {\rm{ }}2n$;当2≤mk‒2时,$\dfrac{{n!}}{{\left( {n - m} \right)!}} \leqslant {f_n}\left( {n,k} \right) \leqslant \left( {\begin{array}{*{20}{c}} k\\ {m - 1} \end{array}} \right) \times \dfrac{{n!}}{{\left( {n - m} \right)!}}$$ - 2\left( {\begin{array}{*{20}{c}} {k - 3}\\ {m - 1} \end{array}} \right) \times$$ \dfrac{{n!}}{{\left( {n - m + 1} \right)!}}$。Yang等[5]也研究了排列图的容错性和可靠性。Cancela等[6]提出了组合特性,来识别源点到终端直径受限的网络可靠性环境中的不相关边,这产生检测和消除网络不相关边的有效过程,同时保持了可靠性。Zhang等[7]研究了网络物理系统的可靠性问题,提出了k-可靠性模型来描述系统中至少有k个节点的连通性,在随机情况下提高网络的可靠性节点故障,当不考虑体内信息时,常规的分层分配策略比随机分层分配策略产生更强的可靠性;在任何情况下,双向互换分配策略比其子图和相应的单向分配策略具有更强的可靠性。但排列图可靠性的近似值鲜有研究,本文主要提出了排列图可靠性的蒙特卡罗近似算法,以及研究了可靠性界的鲁棒性问题。

    • nk都是整数,其中1≤k<n

      (1)点的定义:从{1,2,···, n}中取k个不同的整数得到排列a1a2···ak,其中ai=aj当且仅当i=j

      (2)边的定义:排列图中的两点连接成边,当且仅当点(排列)中对应位置只有一个不同,比如节点a1···ai‒1aiai+1···aka1···ai‒1biai+1···ak的第i个位置不同,则这两个节点之间有边,其中1≤ik图1A4,2为例进行说明,X4表示A4,2的一个子图。

      图  1  排列图A4,2、子图X4、节点24

      Figure 1.  A4,2、subgraph X4、node 24

    • $A_{n,k}^{n - m,k - m}$,对于节点的排列中固定了m个位置,得到相应的子图。为了研究的方便,本文主要对m=1时的子系统可靠性进行研究。对于An,k,有k种划分方式,每个方式有n个互斥的子图$A_{n,k}^{n - 1,k - 1}$,共有nk个不同的子图$A_{n,k}^{n - 1,k - 1}$。以A4,2为例,X4表示A4,2的一个子图。当m=1时,对于A4,2,其中k=2,A4,2子图的划分就有两种方式,即:固定第一个位置和固定第二个位置划分。如果固定第二个位置,则有X1、X2、X3、X4这4个互斥的子图$A_{4,2}^{3,1}$。如果固定第二个位置共有1X、2X、3X、4X这4个不同的子图$A_{4,2}^{3,1}$

    • 排列图子图可靠性的计算是一个NP-hard问题,所以可以用排列图子图可靠性的界去衡量排列图子图可靠性。

      文献[1]已经给出上界的计算:

      根据容斥原理得:

      $\displaystyle\sum\limits_{i = 1}^{nk} {{r_i}(p)} - \sum\limits_{i < j} {{r_{(i,j)}}(p) + } \sum\limits_{i < j < l} {{r_{(i,j,l)}}(p) - } $$\displaystyle\sum\limits_{i < j < l < q} {{r_{(i,j,l,q)}}(p)} $作为$R_{n,k}^{n - 1,k - 1}(p)$的下界,即:

      算法一:取排列图可靠性的上下界平均值作为其近似值,即:

      根据式(1),只需计算$\displaystyle\sum\limits_{i < j < l < q} {{r_{(i,j,l,q)}}(p)} $即可得(3),下面以例1进行说明。

      例1:A5,4为例,计算$R_{5,4}^{4,3}$的下界。根据下界的计算公式,只需要分析$\displaystyle\sum\limits_{i < j < l < q} {{r_{(i,j,l,q)}}(p)} $。YXXX (因为n=5,所以Y为1、2、3、4、5之间的任意一个数)可以表示一个子图$A_{5,4}^{4,3}$,Y也可以位于第二个位置XYXX,对于A5,4k=4,所以存在4个位置。针对4个子图$A_{{\rm{5,4}}}^{{\rm{4,3}}}$的组合情况,每个子图中有一个位置固定,固定的位置上放置一个常数,记为symbol。则4个子图,就会存在4个symbol放在四个固定的位置上。因为4个symbol最多分布在四个位置上,所以存在4种分类:4个symbol分布在一个位置上、4个symbol分布在两个位置上、4个symbol分布在三个位置上和4个symbol分布在四个位置上。

      (1)一个位置:因为从四个位置中选择一个位置放置symbol,所以位置的选择有$C_4^1$种。因为同一个位置放置4个symbol,而且表示4个不同的子图,4个symbol不能相同,所以symbol的选择有$C_{\rm{5}}^{\rm{4}} $种。对于这样的一组$A_{{\rm{5,4}}}^{{\rm{4,3}}}$,因为相同位置放置不同的symbol,所以它们之间是互斥的,一共有$4A_{\rm{4}}^{\rm{3}}$个节点。(1XXX,2XXX,3XXX,4XXX)就表示这样放置symbol的一组$A_{{\rm{5,4}}}^{{\rm{4,3}}}$,如图2所示。

      图  2  1XXX, 2XXX, 3XXX, 4XXX

      Figure 2.  1XXX, 2XXX, 3XXX, 4XXX

      (2)两个位置:因为从四个位置中选择两个位置放置symbol,所以位置的选择有$C_{\rm{4}}^{\rm{2}}$种。因为将4个symbol放置在两个位置上,有3种分法:(1, 3)、(2, 2)和(3, 1)。(1, 3)表示取得的两个位置,第一个位置放1个symbol,第二个位置放3个symbol。(2, 2)表示取得的两个位置,第一个位置放2个symbol,第二个位置放2个symbol,(3, 1)表示取得两个位置,第一个位置放3个symbol,第二个位置放1个symbol,其所得结果和(1, 3)情况类似。

      (3)三个位置:因为从四个位置中选择三个位置放置symbol,所以位置的选择有$C_{\rm{4}}^{\rm{3}}$种。因为将4个symbol放置在三个位置上,有三种分法:(1, 1, 2)、(1, 2, 1)和(2, 1, 1)。(1, 1, 2)表示第一个位置放1个symbol,第二个位置放2个symbol,第三个位置放2个symbol。由排列组合知这三种分法所得结果一样,所以只对(1, 1, 2)讨论。

      (4)四个位置:因为从四个位置中选择四个位置放置symbol,所以位置的选择有$C_{\rm{4}}^{\rm{4}}$种,有一种分法:(1, 1, 1, 1)。

      和文献[1]类似得到 $\displaystyle\sum\limits_{i < j < l < q} {{r_{\left( {i,j,l,q} \right)}}\left( p \right)} $计算方法见表1,其中k>3。

      Reliability
      One position Two positions Three positions Four positions
      ${R_1} = C_k^{\rm{1}}C_n^{\rm{4}}{p^{4A_{n - 1}^{k - 1}}}$ $\begin{aligned} {R_2} =& C_k^{\rm{2}}(2C_n^{\rm{1}}C_{n - 1}^{\rm{2}}{p^{4A_{n - 1}^{k - 1} - 2A_{n - 2}^{k - 2}}} + \\& 2C_n^{\rm{1}}C_{n - 1}^{\rm{3}}{p^{4A_{n - 1}^{k - 1} - 3A_{n - 2}^{k - 2}}} + 2C_n^{\rm{2}}C_{n - 2}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - 3A_{n - 2}^{k - 2}}}+\\ & C_n^{\rm{2}}{p^{4A_{n - 1}^{k - 1} - {\rm{2}}A_{n - 2}^{k - 2}}} + \\& C_n^{\rm{2}}C_{n - 2}^{\rm{2}}{p^{4A_{n - 1}^{k - 1} - {\rm{4}}A_{n - 2}^{k - 2}}} \end{aligned}$ $\begin{aligned} {R_{\rm{3}}} =& C_k^{\rm{3}}({\rm{3}}C_n^{\rm{1}}C_{n - 1}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - 2A_{n - 2}^{k - 2}}} + \\& {\rm{3}}C_n^{\rm{1}}C_{n - 1}^{\rm{2}}{p^{4A_{n - 1}^{k - 1} - {\rm{4}}A_{n - 2}^{k - 2}}} +\\& {\rm{6}}C_n^{\rm{1}}C_{n{\rm{ - 1}}}^{\rm{1}}C_{n - 2}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - {\rm{4}}A_{n - 2}^{k - 2} + A_{n - {\rm{3}}}^{k - {\rm{3}}}}}+\\& {\rm{3}}C_n^{\rm{1}}C_{n{\rm{ - 1}}}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - {\rm{3}}A_{n - 2}^{k - 2}}}+\\ & {\rm{3}}C_n^{\rm{1}}C_{n{\rm{ - 1}}}^{\rm{1}}C_{n - 2}^{\rm{2}}{p^{4A_{n - 1}^{k - 1} - {\rm{5}}A_{n - 2}^{k - 2} + {\rm{2}}A_{n - {\rm{3}}}^{k - {\rm{3}}}}} \end{aligned}$ $\begin{aligned} {R_{\rm{4}}} = & C_k^{\rm{4}}(C_n^{\rm{1}}{p^{4A_{n - 1}^{k - 1}}} + \\& {\rm{4}}C_n^{\rm{1}}C_{n - 1}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - {\rm{3}}A_{n - 2}^{k - 2}}}+ \\& {\rm{3}}C_n^{\rm{1}}C_{n - 1}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - {\rm{4}}A_{n - 2}^{k - 2}}}+ \\& {\rm{6}}C_n^{\rm{1}}C_{n{\rm{ - 1}}}^{\rm{1}}C_{n - 2}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - {\rm{5}}A_{n - 2}^{k - 2} + {\rm{2}}A_{n - {\rm{3}}}^{k - {\rm{3}}}}}+\\& C_n^{\rm{1}}C_{n{\rm{ - 1}}}^{\rm{1}}C_{n - {\rm{2}}}^{\rm{1}}C_{n - {\rm{3}}}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - {\rm{6}}A_{n - 2}^{k - 2} + {\rm{4}}A_{n - {\rm{3}}}^{k - {\rm{3}}} - A_{n - {\rm{4}}}^{k - {\rm{4}}}}}) \end{aligned}$

      表 1  $\displaystyle\sum\limits_{i < j < l < q} {{r_{\left( {i,j,l,q} \right)}}\left( p \right)} $的计算

      Table 1.  the reliability of four subgraphs

      通过表1,我们得到

      对于k=2,取

      k=3,取

      对于$R_{5,4}^{4,3}$,由(1)、(4)得:

      对于$\tilde R_{5,4}^{4,3}(p)$,取p=eat[1],得到图3

      图  3  排列图A5,4子图可靠性的近似计算

      Figure 3.  Approximate calculations of subgraph reliability of A5,4

      图3知,如果用界的平均值去估算可靠性时,会出现$\tilde R_{5,4}^{4,3}(p) < 0$,我们称这种情况为鲁棒性,即在某些时刻,近似值没有意义。利用二分法找到了$\tilde R_{5,4}^{4,3}(p) = 0$的近似时间节点,当84.6019<t$\tilde R_{5,4}^{4,3}(p) < 0$,即当84.6019<t$\tilde R_{5,4}^{4,3}(p)$没有意义。

      针对鲁棒性的情况,本文提出了基于排列图的子图可靠性的蒙特卡罗算法近似计算排列图的子图可靠性。

    • 蒙特卡罗方法是以概率统计理论为指导的一种非常重要的数值方法,使用随机数解决许多计算问题:

      (1)输入最小值,最大值和最可能的估算数据,并为其选择合适的先验分布模型;

      (2)根据以上输入,采用一定的规则,快速实施大量的随机抽样;

      (3)对随机抽样的数据进行数学计算并处理结果;

      (4)基于累积概率的分析,对结果进行概率分析,得出结论。

    • 对于排列图An,k,排列图子图的可靠性定义为:当系统发生故障时,仍然存在一个正常运行子图的概率。

      利用蒙特卡罗方法对排列图子图的可靠性进行计算的一般过程如下:

      算法二:

      (1)已知排列图An,k,输入循环次数N,节点正常运行概率p,计数器s=0;

      (2)对于第i次循环,生成(0, 1)之间的n!/(nk)!个随机数,构成一个n!/(nk)!维的向量γi

      (3)每个节点正常运行的概率为p,则失败的概率为q=1‒p;若2)中向量γi的第j个随机数大于q,记对应的节点j正常运行,状态变量记为1,否则记为0,得到状态向量λi

      (4)根据3)中λi状态,判断剩下正常运行的节点,是否构成一个排列图子图,如果构成一个排列图子图,则s+=1,否则s=s

      (5)如果iNi+=1,返步骤(2);否则,返步骤(6);

      (6)reliability=s/N

      例2:A3,2(图4)为例,对蒙特卡罗方法进行说明:

      图  4  排列图A3,2

      Figure 4.  arrangement graph A3,2

      利用容斥原理,得到

      (1)输入循环次数N=100,计数s=0,p=0.8,q=0.2;

      (2)随机生成一个6维的向量(0.282 07, 0.136 92, 0.438 19, 0.526 09, 0.065 82, 0.207 75);

      (3)生成状态向量(1,0,1,1,0,1);

      (4)存在正常运行的子图X2(12, 32)和2X(23, 21),则s+=1;

      通过仿真计算,得到表2

      Cycles N Monte Carlo error/%
      100 0.218
      500 0.185
      1 000 0.084

      表 2  A3,2的子图可靠性蒙特卡罗近似计算

      Table 2.  The approximate calculation of the Monte Carlo Method for A3,2

      通过表2,发现蒙特卡罗得到的误差不足1%,而且随着循环次数的增多,其误差越小。

    • p=0.85,N=1 000,得到An, k子图可靠性的界以及近似计算的结果见表3

      An,k Lower bound Algorithm1 Ref[1] Monte Carlo algorithm Upper bound
      A3,2 −4.048 0.144 0.999 5 0.988 4.335
      A4,2 −6.446 −0.766 0.999 5 0.994 4.913
      A5,4 0.281 0.297 0.336 0.301 0.313
      A6,3 0.344 0.425 0.509 0.434 0.506
      A7,3 0.139 0.140 0.149 0.141 0.142

      表 3  排列图An,k子图可靠性的界以及近似计算(n=3,4,5,6,7,k=2,3,4)

      Table 3.  the bounds and the approximate calculation of subgraph reliability for An,kn=3,4,5,6,7, k=2,3,4)

      通过表3发现,A3,2A4,2的上、下界出现了异常,这就是鲁棒性问题。对于A5,4A6,3A7,3,文献[1]中的近似值都大于上界值,而蒙特卡罗模拟的可靠性都在上、下界之间,可见蒙特卡罗模拟的可靠性结果要优于已知算法。

      对于图4,取p=0.5, 0.6, 0.7, 0.8, 0.9得到排列图A3,2子图可靠性的近似解。

      根据表4,得到图5

      p Real value Ref [1] Monte Carlo
      0.5 0.718 8 0.822 0.718
      0.6 0.848 4 0.931 3 0.842
      0.7 0.934 8 0.982 4 0.933
      0.8 0.981 0.997 8 0.986
      0.9 0.997 8 0.999 95 0.997

      表 4  排列图A3,2子图可靠性的近似计算

      Table 4.  The approximate calculation of subgraph reliability for A3,2

      图  5  排列图A3,2子图可靠性的近似计算

      Figure 5.  The approximate calculation of subgraph reliability for A3,2

      通过图5,发现算法一的近似计算会出现鲁棒性问题,已有近似计算的结果要大于真实值,利用蒙特卡罗得到近似结果和真实值基本重合。

    • 本文主要研究了排列图子图的可靠性问题,提出了排列图子图的下界,在此基础上提出了算法一:将上、下界的平均值作为排列图子图可靠性的近似值。在算法一的计算过程中会有鲁棒性问题,针对这一问题,本文提出了基于排列图的蒙特卡罗模拟算法,对于A3,2的排列图子图的可靠性,利用蒙特卡罗去计算,其误差不足1%。对于其他排列图的可靠性,蒙特卡罗算法也优于已知的近似算法。

(5)  表(4) 参考文献 (7) 相关文章 (20)

目录

    /

    返回文章