適于風險監測系統的零壓縮二元決策圖基本事件排序方法

汪 進,王 芳,王家群,顧曉慧,殷 園3,袁 潤,李亞洲,胡麗琴,吳宜燦,FDS團隊

(1.中國科學技術大學核科學技術學院,安徽 合肥 230027;

2.中國科學院等離子體物理研究所,安徽 合肥 230031;3.深圳大學理學院,廣東 深圳 518000)

風險監測系統采用的實時風險模型是在基準風險模型的基礎上升版得到,核電站的實際運行特點(比如需要考慮模型完備性、堆型特殊性等問題[1])導致了實時風險模型的自身的復雜性,而且風險監測系統需要對核電站風險水平進行實時分析計算,因此快速計算引擎發展是風險監測系統研發成功關鍵。

為了解決概率安全評價中超大規模故障樹的求解問題,國內外專家進行了很多算法研究,包括二元決策圖(BDD,Binary Decision Diagram)[2-3]、零壓縮二元決策圖(ZBDD,Zerosuppressed Binary Decision Diagram)[4-5],基本事件的排序[6-7]等。其中BDD算法引入使得求解大規模故障樹成為現實,而ZBDD算法在此基礎上又進一步提高了計算速度[4-5]。無論對于BDD還是ZBDD算法計算流程而言,基本事件排序都是必須,而且具有舉足輕重地位的,因為排序將直接影響計算中間結果規模,并進而影響計算速度。

然而傳統排序方法研究針對常規的故障樹求解問題,并沒有結合風險監測系統自身的特點,而且傳統排序方法大多基于BDD,也沒有結合ZBDD算法獨有的特性加以改進。因而如直接利用傳統排序算法則未能很好利用風險監測系統特點達到對于算法性能改良作用。本文在廣泛調研基礎上,同時結合了風險監測系統和ZBDD算法各自的特點,提出了一種可以有效提高風險監測系統實時風險計算引擎的計算速度的基本事件排序方法,并在FDS團隊自主研發的概率安全分析軟件RiskA[8]的計算引擎基礎上開發出了風險監測系統計算引擎。實踐表明這種基本事件排序方法可以有效減少ZBDD的規模,并進而提高計算速度。

1 基本事件排序方法

基本事件排序對ZBDD規模有較大影響,例如,最小割集{A,B,C},{A,B,D}按照A＜B＜C＜D排序得到的ZBDD(圖 1)為“最小ZBDD”,按照C＜D＜A＜B排序得到的ZBDD(圖2)為“最大ZBDD”。

圖1 A＜B＜C＜D時的ZBDD結構Fig.1 ZBDD structure when A＜B＜C＜D

圖2 C＜D＜A＜B時的ZBDD結構Fig.2 ZBDD structure when C＜D＜A＜B

“最小ZBDD”固然是基本事件排序算法追求的最好結果,但是尋找可以構造“最小ZBDD”的排序代價高昂,本文提出的算法能夠以較小的代價得到一種基本事件排序,并且在此排序下的ZBDD較大程度逼近“最小ZBDD”。

本文提出的基本事件排序方法基本思路是：針對風險監測系統實時風險模型的初始狀態,利用常規的ZBDD算法得到實時風險模型的定性分析結果,即最小割集;將割集中的基本事件按照其在所有割集中的出現頻次從大到小排序并將排序信息應用到ZBDD算法中,再將改進后的算法用于該風險監測系統的日常運行。

將一組最小割集C的m個基本事件{E0,E1,…,Em-1}按照排序S依次記為Fi(i=0,1,2,…,m-1),則{F0,F1,…,Fm-1}是基本事件{E0,E1,…,Em-1}的一個排列,其對應關系為Fi=Exi(xi=0,1,2,…,m-1)。根據不同的基本事件排序可以將故障樹轉化為不同的ZBDD,將根據排序S得到的 ZBDD記為ZBDD-S,將Fi在 ZBDD-S中出現的頻率記為Qxi。

下面從理論上分析排序S對ZBDD-S的規模的影響。

(1)按照ZBDD算法[9],ZBDD-S的第0層節點即頭節點,一定是S中序號最小的基本事件,即F0(圖3),則其在ZBDD中出現的頻率Qx0=1。

圖3 F0在ZBDD中的分布情況示意圖Fig.3 F0's distribution in ZBDD

(2)F0將C分成兩部分割集,一部分均包含基本事件F0,另一部分均不包含基本事件F0,F1在這兩部分割集的分布可能有3種情況,如圖3和圖 4a、圖4b所示,基本事件在ZBDD中的出現頻率不會超過其在割集中出現的頻率,所以Qx1=1或m in{2,Px1}。

圖4 第1層節點F1在ZBDD中的分布情況Fig.4 F1's distribution in ZBDD

(3)Qx1的取值情況不同將會影響Qx2的取值。若Qx1=1,如圖 4a所示,若Qx1=m in{2,Px1}=2,如圖3所示,歸納以上兩種情況可得Qx2=q2(q2=1,2,…,min{4,Px2})。

(4)設Qxk+1=qk+1(qk+1=1,2,…,min{max,Pxk+1}),為得到Qxk+1的取值,只需求其最大值max。在ZBDD中,記Fi接在Fj下的次數為Nj,i(i＞j),一方面,由于Fi序號僅大于F0～Fi-1,它只可能是F0～Fi-1的孩子節點,因此有

成立;另一方面,Fi的孩子數為2Qxi,因此有

成立。在給定Qx0～Qxk取值的情況下,當且僅當只有Fxk+1接在F0～Fk之下,而沒有任何其他Fi(i＞k+1)接在F0～Fk之下時可以取到m ax值 ,由式(1)、式(2)可得

由式(3)、式(4)兩式可得

故有max=1+Qx0+Qx1+…+Qxk,若Qx0～Qxk均能取到相應的最大值,即20～2k,則 max=2k+1,所以Qxk+1=qk+1=1,2,…,min{2k+1,Pxk+1}。

(5)令Sk=Qx0+Qx1+…+Qxk,基本事件的排序S不同,Pxk的取值就不同,進而影響Qxk的取值,最終影響Sk的取值,這是基本事件排序對ZBDD規模影響的基本原因。

假設F0、F1、F2、F3在割集中出現的頻率較大,即min{2k,Pxk}=2k,則它們的某種可能取值情況如表1所示。

表1 ZBDD節點出現頻率取值示例Table 1 Counts of a specific basic event in ZBDD

由此能夠看出,當k值越大,Qxk可能取到的最大值min{2k,Pxk}=2k就越大,好在可以利用Pxk對該值進行約束,若將基本事件按其在割集中出現的頻率排序,則隨著k值的增大,Pxk逐漸減小,min{2k,Pxk}也將逐漸收斂,Sk=Qx0+Qx1+…+Qxk的值也會較大程度的向“最小ZBDD”趨近。

理論分析表明,將基本事件按照其在割集中出現的頻率從大到小排列,可以使其對應的ZBDD較大程度的向“最小ZBDD”趨近,同時這種排序方法自身的代價很小。

2 結果與討論

本文在FDS團隊自主研發的概率安全分析軟件RiskA的計算引擎基礎上,應用上述基本事件排序算法開發出了適用于風險監測系統的計算引擎。測試中利用實際核電站風險監測系統基準狀態的實時風險模型,與改進前的RiskA計算結果進行比較以測試排序算法的性能。改進前的RiskA采用的是傳統的“深度優先、從左到右”的順序依次對基本事件進行編號。例題描述見表2,測試結果見表3。

表2 例題描述Table2 Description of testexamp le

表3 性能測試結果Table3 Performance comparison between these twomethods

本文采用的測試例題均為實際電站規模。表2所示例題1為全電站模型,由57棵事件樹鏈接而成,因而可以反映實際核電站運行的特點,其邏輯門和基本事件數目可反映其規模,因而同時能夠驗證算法的有效性;例題2是由大鏈接模型中前26棵事件樹鏈接而成的故障樹模型,例題3是后31棵事件樹鏈接而成的故障樹模型,從邏輯門數目和基本事件數目可以看出其規模均較大,能夠有效驗證本文提出的排序算法對同一套模型的不同覆蓋范圍的有效性。改進前RiskA的基本事件排序是基于啟發式規則的排序方法[10],改進后RiksA應用了本文提出的排序方法,而基本事件的排序不同不會影響結果本身,這一點可以保證改進后RiksA的計算結果的正確性,從表3可以看出改進后RiskA的計算速度得到了較大的提升,在計算實際電站的大規模實時風險模型時表現出了較好的時間性能,運行時間約減少50%以上,在內存占用上也有所改善,降低約20%。

本文利用分析結果中基本事件出現的頻率進行排序,反過來調整分析過程,可以減小最終分析結果ZBDD的規模,從而改善算法性能。將該方法應用于風險監測系統的實時風險模型分析,能加速模型分析計算的過程。對于風險監測系統在日常運行時的不同狀態配置,故障樹模型不會發生較大變化,使得每次分析過程的基本事件排序差別不大,因而該排序方法比較適合風險監測系統的實時風險計算。

3 結論

本文充分利用ZBDD結構及風險監測系統特點,提出了一套適用于風險監測系統的基本事件排序方法,并在FDS團隊自主研發的概率安全分析軟件RiskA的基礎上結合該算法開發出了新的實時風險計算引擎,實踐表明該方法能加速分析計算過程,從而滿足風險監測系統實時分析需求。

[1] Risk O W,IAEA.Risk m onito r：a report on the state of the art in their development and use[R].2004.

[2] Sinnamon R M,Andrew s J D.New app roaches to evaluating fau lt trees[J].Reliability Engineering &System Safety,1997,58：89-96.

[3] Rauzy A.New A lgorithms for Fault-trees Analysis[J].Reliability Engineering&System Safety,1993,40：203-211.

[4] Woo Sik J,Sang H oon H,Jaejoo H.A fast BDD algorithm for large coherent fault trees analysis[J].Reliability Engineering&System Safety,2004,83：369-374.

[5] Woo Sik J.ZBDD algorithm features for an efficient Probabilistic Safety Assessment[J].Nuclear Engineering and Design,2009：2085-2092.

[6] Bouissou M.An ordering heuristic for building binary decision diagram s from fault-trees[J].Annual Reliability and Maintainability Symposium, 1996：208-214.

[7] Ibanez-Liano C,Rauzy A,Melendez,et al.Variable ordering techniques for the application of Binary Decision Diagrams on PSA linked Fau lt Tree models[J].2009.

[8] 吳宜燦,劉萍,胡麗琴,等.大型集成概率安全分析軟件系統的研究與發展[J].核科學與工程,2007,27(3)：270-276.

[9] Minato S.Zero-suppressed BDDs for setmanipulation in combinatorial problems[C]//DAC'93：30th ACM/IEEE-CSDesign Automation Conference,Dallas,TX,1993：272-277.

[10] 劉萍,吳宜燦,李亞洲,等.一種基于ZBDD求解大型故障樹的基本事件排序方法[J].核科學與工程,2007,27(3)：282-288.