系统的有效贝叶斯网络模型

1、系统的有效贝叶斯网络模型贝叶斯网络在建立系统性能的概率论模型时是一个方便的工具，其方便性尤其体现在当 需要根据观测信息提升系统或其组分的稳定性的情况下。在本文中，研究了以最小链接集或 者最小割集定义的系统性能的BN结构模型。标准BN结构把系统节点定义为其组成成分或 最小链接/割集的子节点，从而会导致收敛结构，这种结构不利于计算，并且可能会严重阻 碍BN在实际系统中的应用。本文发展了一套系统化的方法，它所创造的链状BN结构比标 准结构的计算效率高几个数量级，对于计算存储量尤为如此。这一构想运用了整数最优算法 以确定最有效的BN结构。一些应用实例论证了所提方法并且量化了获得的计算优势。引言工程决策

2、经常涉及对正在演化和具有不确定信息的系统状态的概率论评估。比如说，在 一次自然灾害，比如说影响了一个城市社区的一次地震过后，必须要作出关于派遣救援队和 视察小组，继续使用或者关闭设施，修复的优先性以及恢复服务的决定，所有这些都依赖与 对不同的基础系统运行状态的评估。这些评估会受到所获得信息的强烈影响，而这些灾后信 息却具有相当高的不确定性，并且可能会随着所观测到的不同系统组分状态的改变而发生迅 速的演化。另一个例子是对正在恶化的系统的操控，在这里需要依据观察频率和程度，以及 维持、修复和更换行为作出一些决定，然而系统未来的性能和需求仍然是不确定的。在这两 个例子中，需要有一种方法，以更新系统状

3、态的概率评估，因为信息，通常是不定类型，可 以通过测量、检查以及其他对系统及其组成的观察得到。贝叶斯网络对于分析这类系统，尤其是当需要考虑变化不定的信息而更新系统概率模型 时是一个理想的组织架构。BN是一个包含描述随机变量的节点和描述节点概率相关性的链 接的图像模型。变量可以描述系统组分的状态、它们的容量和需求BN为建立组分状态之 间相关性提供了一个方便的方法，而这在大多数经典的系统可靠性分析方法之中都是相当困 难的。此外，当输入一个或更多变量，比如说一系列组分的观察状态、容量和需求，根据贝 叶斯规则，信息就会通过网络传播并且更新其他随机变量的分布，比如其他组分和系统的状 态。最后，通过添加决

4、策和实用节点，BN依据最大期望效益的原则，给出一个便于作出决 策的图表。这篇文章聚焦于发展一套使用BN为系统行为建模的系统化的方法，系统性能以他们的 最小链接集或者最小割集的形式定义。这篇文章中描述的方法来源于我们在为受到地震灾害 影响的民用基础设施的行为建模的工作，它尤其重视了灾后风险评估和决策制定。对于这样 的一个应用，有效的计算和近乎实时的对大型系统模型的推断是很有必要的。此外，相比于 其他方法，比如故障树、事件树或者可靠性流程图等，被考虑的系统更容易用MLS/MCS方 式来刻画。虽然这篇文章的动机来自这个具体的应用，但是这里描述的方法可以应用于很多 问题。BN曾经被用于系统可靠性分析。

5、这些工作中的一部分以直觉的方式将系统建立为BN 模型。其他的则把故障树，或者可靠性流程图作为系统信息的根本来源。一些论文为相对简 单的系统发展BN，对于这些系统，计算量不是特别关键。这项工作区别与先前工作的地方 在于，其定义了一种用于发展一个有效BN结构的系统化处理方式，使得在当MLS或者 MCS是系统信息的根本来源时，用于为复杂系统的可靠性建立模型。这一方法在处理具有 拓扑性质的系统时尤为有用，在这样的系统里，系统的分解通常是通过MLS或者MCS来 完成的。尽管其他的作者已经使用BN为通过可靠性流程图拓扑定义的系统建立模型，但却 没有做出系统化的尝试以使得BN结构达到最优化，在处理大型、多状

6、态系统时尤为如此。 传统的BN模型在尺寸和密度上都会随着系统尺寸的增加而迅速增加，所以即便是对于中等 尺寸的系统，计算和存储的需求都会使得模型变得不可行，特别是在使用具有多状态节点的 精确推算算法时。考虑到这个缺点，在本文中我们针对二元和多元状态组分，发展了一套生 成有效BN拓扑的方法。发展了一套离散最优化算法以最小化BN密度，从而可以节约几个 数量级的计算时间和存储容量。本文开篇对BN作出简要的介绍。介绍被限定在对文章的后续内容有意义的几个方面。 其次，陈述了为具有二元组分的串联和并联系统建模的有效贝叶斯网络构想。这些构想然后 被拓展到具有二元和多元状态组分的一般性系统。为了自动构建有效贝叶

7、斯网络结构，一个 二元整数最优化问题被明确的表述出来。此外，描述了两个启发式的改进方案以减小最优化 问题的尺寸。最后列出了论述所提方法及其有效性的几个例子。贝叶斯网络简介一个贝叶斯网络可以用包括一组描述随机变量的节点和一组描述概率依赖性的链接的 定向非周期性图表来描述。本文中，我们局限与处理这样的BN，其中所有的随机变量都是 离散的；对具有连续性随机变量的BN感兴趣的读者可以参考Langseth。考虑图1中的简单 BN。从X1和X2到X3的定向链接表示X3的分布是基于X1和X3定义的。在BN术语中， 随机变量X3称为随机变量X1和X2的子节点，而后者称为X3的父节点。类似的，X4是 X1的子节

8、点，而X5是X4的子节点。每一个节点与一组彼此独立且同时明确的状态相联系， 与离散随机变量的结局空间相对应。每个节点都带有一个条件概率表（CPT），提供了随机 变量的条件概率函数。根节点没有父节点，附带一个边缘概率表。Fig. r A simple BN.BN中随机变量的联合分布以条件分布的乘积形式给出，例如:p（xnx2p.,Xfl）= n 口（珀伊敏招）-（1）其中Pa（Xi）是节点Xi的父集合，p是Xi的CPT，n是BN中随机变量（节点）的数目。 因此，对于图1中的BN，联合概率分布函数为：=f 八，（2）BN在回答当观察到一个或多个变量时的概率性疑问时很有用处。例如，假设在图1中 的B

9、N中，X3=x3,X4=x4，需要计算条件分布p（x2|x3,x4）。计算后面的分布时，首先要边缘化 （2）中的联合分布，以获得变量子集的联合分布：Jp(X2A34)=(为 次5)(3)p(x3tx4) = P(X1，,X5)(4)#1 .也.均要计算的条件分布则为p(x2lx3,x4)=p(x2,x3,x4)/p(x3,x4)。虽然通过这种方法可能获得更 新的分布，但对非平庸的BN而言这却不是一个有效的计算方法。一些用于在BN中作出准 确和近似概率推算的有效算法已经被发展起来。这里列出了准确推算算法的一般性原则，以 强调发展有效BN拓扑的必要性。BN的有效性来源于将联合分布分解成局部条件分布

10、，就像在等式(2)中的例子里一样。 当对联合分布求和时，类似于等式(3)和(4)，并没有利用分解，且计算效率较低。然而，通 过以乘积的形式写下联合分布，就有可能根据他们的分布和交换性质，重新安排这些求和和 乘积操作。例如，等式(3)可以写成：p(X2 g g) =、p (x5|x4)p(x4|x1Jp(x3| Xi tx2 )p(为)P的)=P(X2) Wp (阳 I Xi)P (也 I Xi) P(为)fp (*51 &)(5)求和操作可以被理解成节点的消除。因为计算时从右往左进行的，等式(5)对应于X5的 消除，接着是X1的消除。很明显，解;5)的第二行比解第一行有效，因为求和是在较小的区

11、 域中进行的。遍及X5的求和只在X4和X5区域中(且在实际上可以被忽略，因为它的结 果是1)。遍及X1的求和是在XI、X2、X3和X4区域中，为此有必要建立一个表(称为 potential)，表中的条目数量等于这些变量状态数的乘积。通常情况下，potential的尺寸决定 了推算算法的效率。Potentials，也即推算算法的效率，取决于节点消除的顺序。计算上存在着最优消除序列， 所有这些序列都会导致相同的域集，例如在这一过程中产生的potential的域集都是相同的。 与最优消除序列对应的域叫做clique。与这些clique相关的potential的总尺寸能很好的反应 出在贝叶斯网络中进行

12、推算所需要的计算量，在本文中被用于评估和比较不同BN系统架构 的效率。虽然所有的精确推算算法都旨在寻找最优节点消除顺序，但是他们遵循不同的方式。特 别值得一提的是，有些算法旨在为一个具体的推算任务最优化消除，而其他的算法，比如说 交叉树算法，则具有普适性。利用后者，部分计算可以被重新利用。我们感兴趣的是一般性 的推算应用。这些算法中的一部分已经在现有的软件应用程序中得到了使用，为在复杂贝叶 斯网络中进行推算带来了便利。虽然这篇文章集中于提高精确推算算法的计算效率，但是这里所发展的方法对于通过减 小存储的CPT尺寸的近似算法而言同样有用。就像Nielsen等谈到的，在当BN模型的确定 性部分可以

13、用一个布尔型函数描述时，高级的布尔计算可以用于提高精确算法的运行效率。 这样一种方法可以用于进一步提高我们通过拓扑最优化得到的BN模型的计算效率。通过贝叶斯网络为系统性能建立模型考虑一个具有Nc个组分的系统，第i个组分具有ni个离散状态。系统的不同状态的个数从而是1 - 。我们把通过组分状态直接定义系统状态的BN formulation称为naiveBN formulation。图2展示了这样的一种BN,其中节点Ci定义的是第i个组分的状态，节点 Ssys定义的是系统的状态。如果系统有Ns个离散状态，那么与该系统节点相关联的CPT 就具有Ns*个条目。虽然这种formulation曾经也被使用

14、，但是对于一个系统，哪 怕是只具有中等数量组分和组分状态的系统，CPT的尺寸都会变得相当大以至于BN在计算 上变得很棘手。很明显，我们需要一种更加有效的BN架构。Fig. 2. Naive BN formulation.作为上述naive方式的一种替代，在这篇文章中我们描述了另外四种BN formulation0 前面两种利用了最小链接集和最小割集，以处理具有二元组分的系统，但是利用了和在naive formulation中相同的收敛结构。可以看出，MCS架构对于具有多元状态组分的一类系统同 样是适用的。我们接着又发展了两种架构，它们对具有二元状态的系统使用了 MCS/MLS， 但是导致了远比

15、计算目标有效的多的链状BN拓扑结构。这些架构首先用在串并联系统上， 然后推广到一般性的系统。这些有效的MCS架构对于具有多元状态组分的一类系统同样是 适用的。使用最小链接集和割集的BN系统模型4.1二元组分和系统考虑一个具有二元组分的系统和系统状态，例如存活/失败状态。最小链接集(MLS)是组 分的最小集合，其节点存活状态组成了系统的存活状态。最小链接集BN架构在组分和系统 节点间引入了中间节点，其描述了 MLS的状态，如图3所示。Fig. 3. MLS formuhtion.TorresToledano和Sucar用这样的一种BN架构为系统性能建模，尽管其方法比我们这 里使用的方法缺少规范性

16、和一般性。MLS节点的二元状态被定义成，只有当它的所有的组 分存活时才处于存活状态，否则处于失败状态。当任意一个MLS节点存活时，系统节点存 活。用Nmls表示系统MLS的数量，NMLSi表示在第i个MLS中组分的数量。第i个MLS 节点的CPT大小是2NMLS,i+i，系统节点cPt的大小是2Nmls+i。很明显，当MLS数量较大 时，与系统节点关联的CPT尺寸也会变大。对于MLS节点，当组分数量较大时也会出现类 似的问题。与MLS架构对应的是最小割集BN架构。MCS是组分的最小集合，其节点的失败组成 了系统的死亡。在这种架构中，系统节点是代表MCS节点的子节点，每一个MCS节点是 代表其组

17、分状态节点的子节点，如图4所示。Fig. 4. MCS fbrmulAtig系统节点是所有MCS节点的串联系统（例如，如果至少有一个MCS节点处于失败状 态，那么系统节点就处于失败状态），然而每一个MCS都是其父节点的并联系统（例如， 所有的组分必须处于失败状态时，MCS节点才会处于失败状态）。类似于MLS架构，处于 这种架构中的CPT会随着MCS数量的增加，且/或MCS中组分的数量（用NMCSi表示第i 个MCS）的增加而变大。4.2具有多状态组分的多状态流系统具有多状态组分的多状态流系统可以通过应用最大流最小割理论来建立 MCS BN formulation模型。我们不知道存在允许将MLS

18、架构应该用到多状态流系统中的一个类似的 定理。考虑一个描述从源节点到漏节点流动的系统，假定其MCS组分是二元的。系统的每一 个组分都具有一个流容量，其取值被离散化成一个特定状态集合，例如最大容量的0%，25%， 50%，75%和100%。用Capi表示组分i的容量状态。对于一个具有定向流的分布式组分， 我们考虑割线上从源侧到漏侧的容量。为每一个MCS指定一个容量值，其数值等于组分容 量之和。最大流最小割线定理指出，从源到漏的最大流容量等于所有MCS中的最小值，例 如系统的瓶颈。这个定理允许将MCS BN架构应用到多状态问题中，而不需要在当假设组 分是二元时，改变所创建的BN的拓扑性。只需要根据

19、组分，MCS或者系统容量水平，增 加与每个BN节点关联的状态数量，并用算术表示式而不是布尔逻辑关系去定义节点之间的 关系，就像下图所描述的那样。Fig* 5. Equivalent BNs with (a) converging structure and (b) chain structure.SEHE/U &mJ 3N23bm -sop Converging,.Chain Structure4Number of Components (NJNumber of Components (NJFig. 6. Computational demands of system BNs with con

20、verging and chain topologies when components have (a) 2 states and (b) 5 states.图4中的节点q被修改以用于根据每一个组分的容量水平描述多元状态。如果组分具 有连续容量状态，那么可能容量的范围必须被离散化成几个小的间隔；在这种情况下，节点 Ci描述的是一个间隔节点。类似的，节点MCSi具有多个状态，它们所具有的容量值通过 下面的关系式来定义：SmcL f 知Cj w M*系统节点的容量可以通过以下关系获得：。叩晔= min CapMCS.（7）1日1N枕仁时当Ci是间隔节点时，MCSi和Ssys也是间隔节点。在创建后

21、者的CPT时，这些节点的 间隔必须通过考虑从（6）和（7）式中获的得可能容量值的整个范围来选择。关于间隔节点 的CPT计算的更多细节在Bensi等人的文章中给出。5.有效的BN系统模型5.1.动机在前面章节中描述的MLS和MCS架构都会导致收敛的BN结构。一般而言，节点成 链状排列的BN结构比收敛的BN结构更加有效。正如我们稍后会介绍的，在图5中的两个 BN结构表示的是同一个系统。图5a中是一个类似于前面章节表示的收敛结构，而图5b表 示的是链状结构。在两种BN中，组分之间的依赖关系通过引入一个共同需求节点D来体 现。稍后将会在本节中的图5b中给出构建BN的正式描述。图6比较了图5中当系统组分

22、分别具有2个和5个状态时，收敛和链状结构的BN计算 量，该量以总clique尺寸表示。随着组分数量的增加，收敛结构的BN计算量呈指数增加， 而链状BN的计算量则呈线性增加。然而，对于二元组分系统，当组分数量小于4时，收敛 结构比链状结构更加有效。因此，当图5a中系统节点具有3个以上的父节点时（例如，连 续组分），用图5b中的方式建模会更加有利。与推算关联的计算量不仅受到系统尺寸和结构的影响，也会受到组分节点的共同父节点 的数量影响。图7比较了与具有1，2或者3个共同父需求节点二元组分的收敛和链状BN 拓扑结构相关联的计算量。可以看出，计算量会随着共同父节点数量的增加而增加。然而， 随着组分数量

23、的增加，链状结构相比于收敛结构仍显得有利。同时注意到，随着共同需求节 点数量的增加，转折点，即链状结构比收敛结构有利的点，会稍微的上移。对于三个共同需 求节点的情况，当具5个或更多组分时，链状结构更为有效，而对于一个共同需求节点的情 况，当具有4个或者更多组分时更为有效。700500 一-Chain3 Common Demand Modes心N第一 mol Converging 3 Cummun Demand Nodes Converging, 2 Common Demand Nodes- - Chairs 2 Common Demand Medes100Chain. 1 Common Dem

24、and NodesNumber of Components (NJFig. 7. Comparison uf compurational demands associated with converging and chain BN topologies for binary nodes with one or more common parent demand nodes.5.2.具有二元组分的串并联系统我们现在来描述具有二元组分的系统如何用具有链状拓扑结构的BN来建立模型。定义 存活路径序列（SPS）为一系列的事件，与一个MLS相对应，在后者中，序列中的最后一 个事件指出是否MLS中所有的

25、组分都处于存活状态。注意到术语“序列”并不含有任何实 时的含义。串联系统具有一个MLS，而并联系统具有Nc个MLS。相应的一个串联系统具 有一个SPS，而一个并联系统具有Nc个SPS。SPS由一系列的存活路径事件（SPE）组成， 每一个存活路径事件都与一个组分相关联，描述了序列中直到该事件的序列状态。在贝叶斯 网络中，SPE用标记为Esi的节点表示，下标i表示与第i个组分关联。Esi的状态被定义成：s.i = 1 if Egi） = 1 Cl g = 1）=0 otherwise（8）其中Espai定义为Esi的父SPE节点的状态。Esi=1表示节点处于存活状态而Esi=0表 示失败状态（在本

26、文中我们始终使用这种布尔型表述）。因此，对于一个串联系统，贝叶斯 架构采用图8a中所示的形式。Fig. 8. BN using SPEs to model performance of (a) series system, (b) parallel system.节点Es1的状态等于节点C1的状态。Es2仅当Es1和C2都处于存活状态时才处于存活状 态。在这种模式下，EsNc当且仅当EsNc1和CNc都处于存活状态时才处于存活状态。因此， EsNc的状态描述了整个,SPS的状态(表明是否MLS中的所有组分都处于存活状态)，从而 也描述了这个串联系统的状态。节点Ssys的状态就等于图8中EsNc

27、的状态。并联系统中每个组分都对应一个SPS。由此得到的贝叶斯网络见图8b。系统节点表示 当任意一个节点Esi存活时，系统就存活。类似于naive formulation，与系统节点相关的CPT 大小的指数增加致使该贝叶斯网络在当组分数量很大时变得难以处理。将失败路径序列(FPS)定义为一连串的事件，与一个MCS相对应。序列中的终点事 件表明是否MCS中的所有组分都处于失败状态。在一个串联系统中存在Nc个FPS，每一 个都与一个组分对应。在一个并联系统中只有一个MCS，因而也只有一个FPS。一个FPS 由一连串FPE组成，其中每个FPE与一个组分关联，并给出序列直到那个事件的状态。令 Efi是贝

28、叶斯网络中表示与节点i关联的FPE的节点。Efi的状态被定义为：与E = 0 if E/.pm) o n Q = 0=1 otherwise(9)其中Ef,Pa(定义为Efi的父FPE节点的状态。对于一个串联系统，使用FPS的BN架构 采用如图9a的形式，它,具有我们不想要的收敛结构。对于一个并联系统，BN架构采取图 9b所示的链状形式。这些发现表明SPS和FPS架构的结合可能被用于有效的建立一般系统 的模型。这种方法将会在下节中介绍。abFig. 9. BN using FPEs to model performance of (a) series system and (b) parall

29、el system.5.3具有二元组分状态的一般性系统MLS是其组成成分的串联系统。因此，采用上述的架构，系统的每一个MLS都可以用 一个SPS描述，从而导致链状BN结构。考虑在图10a中的范例系统，其具有四个MLS： MLS1=1，7, 8,MLS2=2, 7, 8,MLS3=3,7,8和 MLS4=4, 5, 6, 7, 8。在图 10b 中， 每个MLS被建立为单独的一个SPS模型。SPE，Esij在每个SPS中用一个与关联的组分i和 关联的MLSj对应的角标编号。JFig- ID. (a) ExjfLipie syscem and (b) efficienr Mis fcuniuhTi

30、ovi with diswna SFSi.具有同一个组分的SPE之间的依赖关系通过一个共同的父节点建模。当任意一个SPS 的终端节点处于存活状态时，系统节点存活。作为参照，其中的MLS按链状结构排列的BN 架构被称为有效的MLS BN架构。相似的逻辑构建出一个有效的MCS BN架构。当在贝叶斯网络中执行推断时，具有相同组分的SPE和FPE之间的依赖关系会增加计 算量。通过合并出现在多个SPS/FPS中的共同的SPE/FPE，贝叶斯网络中节点和链接的数 量会减少，从而计算量也会减少。在范例系统中，组分7和8出现在所有的SPS里。我们 利用这一发现，并只引入一个与这些组分关联的SPE的instan

31、ce，得到的BN如图11a所示。Fig-11. Efficient MLS formulations for the example system with coalesced SPEs associated with components 7 and 8 using (a) a converging structure (b) a chain structure.注意到这种结构也会避免系统节点的收敛结构。它确实可以如此，但是要求有一个收敛的 SPE节点(图11a中的节点Es7)。像这样具有多个SPE作为父辈的SPE节点可以用如下的 布尔关系描述：if uEgh = i门G = 1)(10=0

32、 otherwise图11a中引入的一个值得注意的变化是:每个SPE节点的上标现在代表SPE的instance， 而以前表示MLS的编号。例如，当有多个SPE与共同的组分关联时，它们就作为SPE的不 同instance被识别出来，并通过这些上标区分。对于这个示例系统，因为每一个组分至于一 个SPE关联，从而图11a中的所有上标都是1。在下文中我们丢掉上标，除非有必要特别说 明。注意到图11a中节点Es7的收敛结构，因为需要用它来代表一个并联子系统。由于并联 系统可以用FPE链非常理想的描述，从而这个收敛结构可以通过用链状排列的FPE节点代 替与节点1,2,3关联的SPE节点来改进，从而导致了图

33、11b中的BN结构。具有SPE作为父节点的FPE的定义遵从原始定义：Ef= O if 切,w =。门E$p堀=0 C G =。(11)=1 otherwise尽管示例系统中的三个BN模型都被称为是有效的MLS架构，但是事实上它们的效率 却大不相同。图10b中BN模型的总clique大小是224，图11a中是108，图11b中的值则 是64。这表明当合并在不同SPS中的多个SPE的instance时可以提高计算效率。迄今为止，一个SPS中的SPE(FPS中的FPE)，与一个特定的MLS(MCS)对应，是按 一种随意选择的顺序排列的。对于复杂系统，在SPS中的SPE的排列可能强烈的影响我们 合并不

34、同SPS中SPE的多重instance的能力。SPE出现的顺序可以被优化，以至于在尽可 能多的SPS中的SPE可以被合并。正如早先说明的，这会减少在BN中节点和链接的数量。 这个优化问题将在下面描述。简洁起见，我们只给出了使用SPS的架构；相对的架构同样 适用于FPS。因为我们的焦点只是在SPE上，从而并没有考虑组合SPE和FPE的可能性。 这样的一种组合可以当做是在最优化SPE之后的额外步骤，与图11b中的例子类似。6.生存路径事件的最佳序列本节的目标是规范化对一个一般性的系统，寻找SPS中SPE最优排序的问题。令 L(im,jn)=1表示存在从节点Es,im到节点Es,jn的直接连接，L=

35、0表示不存在这样一个连接， 其中i和j是组分编号，m和n是BN中表示这些SPE节点instance的编号。同样的，令Cim=1 表示在代表组分i的节点和节点Esim之间存在直接连接，Sim=1表示在Esim和系统节点之 间存在直接连接。在最优化问题中的决策变量是SPE节点之间的连接，L(im,jn)。这种优化 问题的架构假定只使用SPE节点以及系统节点处具有收敛结构。为了进一步增加BN的计 算效率，在系统中或者任意其他节点处的收敛结构可以通过使用FPE而被链状结构取代。采用BN中链接数量作为当需要进行推断时描述计算量的替代物，最优化问题的目标就 是最小化在BN中的链接数。这可以用下式来描述:、

36、虬 Nc M NfNc M虬 Njnun(12)EEEsrf = lj=1 m = ln=1(= 1 m = 1 t = 1 m = 1其中NI是任意SPE的instance个数的最大值。我们想要NI尽可能的小，但是它的数 值在求解优化问题之前是未知的。因此，一个迭代程序被用于寻找使得最优化问题存在可行 解的最小Ni。为了确保BN结构能够以在前面章节中描述的方式，利用SPE来表示系统， 一系列的关于最优化问题的限制被提了出来。第一，每一个SPE节点必须有一个从相应组分节点指向它的链接。具体来讲，如果节 点Esim存在于BN中(如果决策变量指示存在一个链接进入或离开节点Esim时会发生)， 则C

37、im=1 (没有链接进入或离开的节点可以从BN中移除)。从数学上说，这被规范化为一 个对最优化问题的限制，写成下式：第二，如果Esim存在并没有其他SPE节点作为子节点，那么它就是SPS中的一个终端 节点。这样一个节点必须有一个指向系统节点的链接，例如Sim=1。这导致对最优化问题的 第二个限制：一些有名的技术可以用于为“如果-那么”这类问题建立模型，正如在前两个等式中的 那样，为数值优化问题提出限制条件。第三，存在两个限制条件控制BN中SPE节点的排列：(a)每一个MLS必须用一个SPS 表示；(b)不严格是MLS的SPS不存在。破坏第一条限制会排除一个或者更多的MLS，导 致对系统可靠性的

38、低估。破坏第二条限制会导致包含一个或者更多虚假MLS的BN，从而 会高估系统的可靠性。限制(a)要求每一个MLS被表示为一个SPS，例如，至少一个与MLS中的组分相关的 SPE的permutation必须被连接为一条链。令NMLSi表示MLSi中的组分的数量。对于在图10a 中的示例系统，我们有NmcS1=NmcS2=NmcS3=3,NmCS4=5。令Pi表示permutation的集合，且 没有替换掉MLSi中组分的序号，定义一.，？，甘作为其第a个成员。 举例来说，对于图10a中的系统，我们有P1=p11=(1,7,8),p12=(1,8,7),p13=(8,1,7),p14=(7,1,8

39、),p15=(7,8,1),p16=(8,7,1).其次，令Qi表示置换集，其中NMCSi被从序数集1,.NI中排除出去。并定义 qib=qib1,qib2,.qibNMLSi作为其第b个成员。使用图10a中的例子，假设NI=2，我们有 Q1=q11=(1,1,1),q12=1：1,2,q13=(1,2,1), q14=(1,2,2),q15=(2,1,1),q16=(2,1,2),q17=(2,2,1),q18=(2,2,2)。注意到 Pi 具有 Nmls个成员， 然而Qi具有NINMLSi个成员。定义集合riab=ri1ab,ri1ab,.riNMLSiab，其结合了 pia和qib的元素

40、。具体来说，riab包 括了 pia中的组分序号，其上标则来源于qib。对于示例系统，r111=11,71,81等。总而言之， 对于这种特殊的MLS，存在48中可能的方法来排列组分序号和instance的上标。简便起见，我们定义:其中rilab是riab的第l个元素。Xiab=NMLSi-1只当与MLSi中的组分对应的SPE以pia 和qib表示的顺序构成SPS时才成立。对于与存在于BN中的第i个MLS关联的SPS而言，我们对来源于集合riab中的至少一个组分/instance的序号顺序具有：Xiab=NMLS1。这个限 制被写成：ImaxX Nmls.l 1% a = 1,NmlsjLfi

41、=(16)为了最优化算法的方便，这里使用不等号而不是等号。限制(b)要求BN中的每一个SPS都要与一个MLS对应。考虑图12a中所示的BN分割。令阴影节点上：. 土一 二表示组分/instance序号的一个特定置换，这种置换导致一个有效的SPS。限制(b)必须禁止一个SPE Esj,n，对于任意的n，在任意节点处将SPS 分支，例如成为链中任意节点的子节点，除非组分j存在于所有先前组分都在序列中的MLS 中。Fig. 12. BN used to illustrate constraint (b).举例来说，在图12a中，Esj,n不能作为Es3,1的子节点存在，除非组分1,2,3和j都同时存

42、在 与MLS中。如果组分1,2,3和j不存在于一个MLS中，那么具有虚线边缘的错误存活路径就 被引入BN中。与所有有效SPS关联的限制表示如下：|玲，=阻*1 土廿=0, Vj 1 p%L 一 崩Vi； nY L (17)进一步的，限制(b)必须禁止SPE Esj,n，对于任意n，成为在有效SPS中任一节点的父 节点，除非组分i存在于所有后续组分都在序列中的MLS中。举例来说，在图12b中，Esj,n 不能是Es2,1的父节点除非组分2,3,4和j都存在于一个MLS中。对所有有效SPS的第二条限 制采取如下形式：*咨=o,力：j,pp第心LSnvm, * n. L 敏 #(IS)综合(17)和

43、(18)可以得到限制(b)，表示如下凶5 = Nm成I nE EE E m凿垣 i m m n = U = % 明 P的#M昼N,wu N+ E EE E卬5涔=o瑚心叩苗一或儿叫4(19)限制(b)以及目标函数(其最小化可以确保在构建需要的SPS中非必须的链接不存在与 BN中)，禁止了在BN中形成无效的SPS。有效的MCS架构是有效MLS架构的对应物，后者中FPS链依据每一个MCS构建。因 此，对于构建一个FPS架构，与上述等价的优化结构被表述出来，上述的SPE需要被替换 为 FPE。上面描述的整数最优化问题要求考虑组分和instance序号的排列。因此，问题的大小会 随着组分的数量增加而迅

44、速增加。为了克服这个困难，在本文的稍后章节中会引入一些启发 式方法。6.1多状态流系统的延伸(20)因为具有标准的MCS架构，通过应用最大流最小割定理，有效的MCS架构可以被用 于解决多状态问题。BN的拓扑性不需要和二元状态问题中使用的拓扑性有所不同，仅仅是 需要增加与每个节点关联的状态数量，并使用算术表达式而不是布尔关系去定义CPT。FPE 节点的状态与容量值相关联，后者被定义为P%=E %忠 任PE/j+C叩E即指派给节点Efi的容量值等于其父FPE节点容量值与关联节点容量之和的最小值。因 此，每一个FPE节点的容量可以被认为是描述MCS的总运行容量。节点Ssys的容量代表 了系统的最大运

45、行水平，它是所有MCS中的最小容量，定义为|(21)6.2.实例H (di) Lnim血 nrt.mk lyriE-nn;也)irlTii.iiriil ML &M fmnnjivi miO eet SK kiK&iiiJilird will N) fiFta ihcwnn LCEiwnfflEjiiri la raaiinn .Wdfi.ZHZHZHZHZJ为了阐明采用本文所提出的有效BN结构的计算优势，我们考虑在图13a中由10个被 标记的组分组成的系统。在这个例子中，一个源和一个漏被默认的用两个连接路径连接起来。 一个连接路径用一条实线表示，另一条则用短虚线表示。在这种结构下，系统具有三

46、个MLS： 1,2,3,4,5,6,7,8,9.组分10代表一个开关，它可以用于从默认结构转变到一个用长虚线表 示的可选结构。这会在系统中增加4个连接路径:1,3,10,1,4,10,2,3,10,2,4,10.因此，总 而言之，系统具有7个MLS,采用本文所提出的最优算法获得的BN如图13b所示,其中与 MLS5,6,7,8,9对应的SPS用阴影节点突出出来.图13c中表示与和每个剩余MLS对应的SPS 相同BN也被类似的强调出来.与这个BN关联的总大小是184.具有收敛结构的MLS BN的 总大小是5140,而具有naive BN结构的系统的数值为2048.当在MLS BN结构中引入中间节

47、 点以确保没有节点具有三个以上的父节点时，总的集团大小减到804,但是大体上仍然比用有 效MLS BN拓扑所取得的数值要高.因此，经过最优化处理的BN比其他方案在计算上的有效 性高一个数量级.不仅如此，注意到节点Ssys是其四个父SPS节点的并联系统.一个小的额外 的计算优势可以通过将收敛结构修改为链状结构实现，正如在图11b中展示的那样.7.有启发意义的增加正如早先提到的,由于需要考虑到组分序号和instance的所有排列，二元最优化问题在大 小上增长迅速。为了克服这个困难，在本节中我们给出两种启发式方法:一种旨在减小需要考 虑的组分数量，另一种旨在减少排列的数量.其他的启发式方法可以被发展

48、以进一步改善在本 文中描述的最优化算法的性能和可扩展性.7.1使用超组分的方法Der Kiureghian和Song引入了系统多尺度模型的想法，据此基本元素的子集被分组为 “超组分”。对单个的超组分进行分析，结果然后集中到系统层面上。超组分组成了简单的 子系统，比如沿着系统链接以串联或者并联方式存在的组分。使用超组分可以减少组分的有 效数量，从而减少它们序号的排列数。它也有助于SPS和FPS的组合。我们再一次考虑在图10a中的简单系统。组分C4,C5,C6以串联形式存在，组分C7和C8 也是这样.我们分别用两个超组分SC1和SC2代替这些组分的子集，如图14所示.系统仍然具 有 4 个 MLS

49、,但是它们的组分数量减少了:1,SC2,2,SC2,3,SC2,SC1,SC2.对图14的考察发现，组分C1,C2,C3和SC1以并联方式存在.这些组分接下来被一个单 个的超组分取代，从而得到图15表示的系统.现在，组分SC2和SC3以串联方式存在,并可以被另一个超组分取代。从这种确定可以被 分组和被一个超组分取代的组分的一系列流程得到的BN如图16所示。Fig. 16. BN constructed for system in Fig. IDa using the super component heuristic对于包含少于4个组成成分的超组分，使用了收敛结构.对于包含4个或者更多组成成分

50、 的超组分，则使用链状结构.注意到在超组分中的组分不需要是连续的.举个例子，在图17中的系统中，组分1和4可 以被放入一个超组分，因为考虑到MLS和MCS的形成，他们具有相同的影响，似乎他们在物理 上就是以串联方式存在的.2 、 /Source 1 4 SinkFig. 17. Example system illustrating non-contiguous components that can be combined into a super component我们现在提供一种算法，以用于进行系列性的确认和用超组分取代基本组分，或者用更 高级的超组分取代超组分集。在这个算法中的第一步是

51、构建初始关联矩阵M0,它包括与每 个MLS(MCS)对应的行和与每个基本组分对应的列.矩阵的元素定义为：JM% = 1if component j is a member of MLS (MCS) i=0 otherwise(22)对于在图10a中的系统，矩阵M0在图18的顶部给出.在算法接下来的每一步中，关联矩 阵将要通过消除与被分入超组分的组分相关的列,及创造一个描述新的超组分的行而得到更 新。令Mp表示算法的第p步关联矩阵，其元素记为MijP.定义了两种类型的超组分.A类超组分由若干组组分（或是以前形成的超组分）组成它们总是一起出现在一个MLS中,从不分开出现.在一个基于MLS（MCS）

52、的结构中,A类超组分 与以串联（并联）方式存在的组分对应.为了确认算法迭代P次的超组分，我们为每个组分j（或是以前形成的超组分）指定量mj（A,p），定义为：这个量只有当组分总是同时出现在某个MLS且从不分开出现在不同的MLS中时对于 不同的组分才是等价的.举个例子,对于图10a中的系统,我们有m1A0=2, m2A0=4,m3A0=8 等。具有相同mjAp的每一个组分集合可以分组以形成A类超组分.矩阵MP必须通过移除 与被分组的组分对应的列及增加代表新的超组分的列而更新到MP+1 .令SCj表示新形成的 超组分.更新的矩阵的新列的元素被定义为：M酬=1 if E k w Cfrp(24)0

53、otherwise其中Cgrpp是被分组以形成新的超组分的组分集合.我们重复这种操作直到A类的所有 超组分形成.对于图10中的系统，使用一个MLS formulation，两个A类超组分被确定,更新后 的矩阵M1和M如图18中间所示.M，ML”Fig- 18. Correspondence uia trices of example system. tefore and after IdentificatiQn and formation of Class A and ass B super components.B类超组分由出现在不同MLS（MCS）中，但是相同其他组分相同集合共享这些MLS

54、的组 分组成。对于一个基于MLS（MCS）的结构，这些与并联（串联）排列的组分对应.为了确定算法p 次迭代的超组分，我们为每个成分j指定量mjbp，定义为：啪叫 x（25）我们可以容易的证实具有相同mjBp值的组分（或超组分）满足上述对于B类超组分的 条件，并可以被这样分组.作为一个例子,对于图10a中的系统,我们有m1B2=32.矩阵Mp现在 通过移除与一被分组组分对应的列及增加对应于具有按24式定义的元素的超组分的列而更 新.因为组合的成分来自于不同的MLS（MCS）,这个过程使得矩阵的一些行为0,从而可以被移 除.对于示例系统,这个过程导致了更新的关联矩阵M3,如图18底部所示.以上用于

55、寻找和用A类和B类超组分替换普通组分的迭代程序将一直重复下去,直到系 统中不存在剩余的超组分.与最后一次迭代对应的矩阵Mp接着被用于对组分及需要被用于 定义最优化问题的相应的MLS或者MCS进行说明.7.2用于减少排列数量的启发式方法回想起最优化算法考虑到成分序号和instance的所有排列.第二种启发式方法的目的在 于丢弃这些集合的若干选定的成员.注意到如果一组组分在所有的MLS中出现，那么就没有 必要考虑它们序号的排列情况（实际上，这样一组组分应该被识别出来并组合成一个超组分）. 这里展示的方法识别出现在几个（但不是全部）MLS中成分，并锁定了它们的序号出现的顺 序，因此移除riab被选定

56、的成员.这种方法可能会导致次优化的BN结构,但是当最优化问题的 尺寸超过所提供的资源处理限度时则是必须的.这种方法应该用在通过识别超组分以减少问 题的大小之后。为了便于解释这种方法,我们用了一个示例系统来阐明这个过程的每一个步骤考虑到具 有7个MLS的任意一个系统： MLS1=1,2,3,4,MLS2=1,4,5,6,8,MLS3=1,4,7,MLS4=2,3,5,MLS5=1,5,7,MLS6=1,2,9 ,MLS7=7,9.第1步:基于组分序号在不同MLS中出现的次数为其创建一个有序列.我们称其为O列. 对于示例系统，一个MLS中每个组分出现的次数见下表：ComponentNumber o

57、f appearances in a MLS543上表导致有序列O=1,2,4,5,7,3,9,6,8。这个序列是以指数值为基础的。第2步：基于序列O重新对MLS中的成分排序.对于示例系统，新的MLS成分序列为：MLS1=1,2,4,3, MLS2=1,4,5,6,8, MLS3=1,4,7, MLS4=2,5,3,MLS5=1,5,7,MLS6=1,2,9,MLS7=7,9第3a步:确定MLS之间的所有成对交叉集合：Mj-j = MLS； nMLSp i = 11）=（i+1）（26）对于示例系统，我们有M1,2=M1,3=M2,3=1,4,M1,6=1,2,M3,5=1,7,M2,5=1,

58、5,M1,4=2,3,M1,5, M2,4, M2,6,M3,6, M3,7, M4,5, M4,6, M5,6, M5,7 和 M6,7 是只包含一个元素的集合,M17=M27=M34=M47=空集。第3b步:定义G作为包含元素个数大于1的特殊集合Mij的集合.对于示例系统统,G=1,4,1,2,1,5,1,7,2,3。这个集合包含同时在两个或者更多MLS中出现， 且组分序号由第1步排序的组分集合。第4步:继续为每个MLS指定一个集合，该集合来自G且与MLS的交集具有最大的基 数。令gik是第i个MLS与G的第k个成员，Gk的交集，例如：(27)定义gi为具有最大基数的集合gik:考虑到对集合基数的要求，我们选择G中第一个出现的集合gi是被指定给第i个MLS 的集合.一旦一个集合从G中被指定给一个MLS,就把它放在一个新集合G中,如果它还没有 被放在那里的话。定义ncj作为成分j出