计算网络s-t可靠性的直接不交界限值算法
|
摘要
网络两端可靠性的精确求解属于NP困难问题,对于规模较大的工程网络,求解过程非常耗时.可行的办法是采用满足实际精度要求的近似算法,其中利用两端界限逼近求解的方法是一类较为有效的近似算法.提出了一种可利用界限求解的直接不交化算法.算法可直接生成不交最小路集和不交最小割集,并实时逼近网络可靠性的真实解,可在有限计算时间内求出小型网络可靠性的精确解或大型复杂网络可靠性的近似解.与改进Dotson算法相比,此算法可更快地求解单元处于低可靠度状态时的网络两端连通可靠性;与最小割递推分解算法相比,此算法可得到较优不交解集.
The evaluation of source to terminal(s-t) reliability of a network is classed in the NP hard family.The exact computation method of large networks is extremely time-consuming.Therefore,approximate computation methods are generally used.One feasible approximation approach is to use bounds.This paper proposes a directly disjoint algorithm using bounds for s-t reliability evaluation of large networks.This algorithm can obtain disjoint minimal path and disjoint minimal cut without prior enumeration of minimal path or minimal cut.On the principle of breadth-first search and minimal-distance-first search,the algorithm can get exact solution of simple networks and approximation of large networks with real-time accumulation of disjoint minimal paths and cuts.Compared with the modified Dotson algorithm,this algorithm is faster in solving the reliability of large network with low element operation probability.Compared with the minimal cut-based recursive decomposition algorithm,a more optimum disjoint set can be obtained by this algorithm.
The evaluation of source to terminal(s-t) reliability of a network is classed in the NP hard family.The exact computation method of large networks is extremely time-consuming.Therefore,approximate computation methods are generally used.One feasible approximation approach is to use bounds.This paper proposes a directly disjoint algorithm using bounds for s-t reliability evaluation of large networks.This algorithm can obtain disjoint minimal path and disjoint minimal cut without prior enumeration of minimal path or minimal cut.On the principle of breadth-first search and minimal-distance-first search,the algorithm can get exact solution of simple networks and approximation of large networks with real-time accumulation of disjoint minimal paths and cuts.Compared with the modified Dotson algorithm,this algorithm is faster in solving the reliability of large network with low element operation probability.Compared with the minimal cut-based recursive decomposition algorithm,a more optimum disjoint set can be obtained by this algorithm.
引文
[1]JANE C C,SHEN W H,LAIH Y W.Practical sequentialbounds for approximating two-terminal reliability[J].European Journal of Operational Research,2009,195:427-441.
[2]BALL M O.Computational complexity of network reliabilityanalysis:an overview[J].IEEE Transaction onReliability,1986,R35(3):230-239.
[3]ABRAHAM J A.An improved algorithm for networkreliability[J].IEEE Transaction on Reliability,1979,R28(1):58-61.
[4]DOTSON W P,GOBIEN J O.A new analysis techniquefor probabilistic graphs[J].IEEE Transaction on Circuitsand Systems,1979,26:855-865.
[5]KUO S Y,LU S K,YEH F M.Determining terminal-pairreliability based on edge expansion diagrams using OBDD[J].IEEE Transaction on Reliability,1999,48(3):234-246.
[6]CHATURVEDI S K,MISRA K B.A hybrid method toevaluate reliability of complex networks[J].InternationalJournal of Quality&Reliability Management,2002,19:1098-1112.
[7]YOO Y B,DEO N.A comparison of algorithms forterminal-pair reliability[J].IEEE Transaction onReliability,1988,R37(2):210-215.
[8]SEVTAP-SELCUK A,SEMIH-YUCEMEN M.Reliabilityof lifeline networks under seismic hazard[J].ReliabilityEngineering and System Safety,1999,65:213-227.
[9]LI J,HE J.A recursive decomposition algorithm fornetwork reliability evaluation[J].Earthquake Engineeringand Structural Dynamics,2002,31:1525-1539.
[10]李杰,刘威,钱摇琨.网络可靠性分析的最小割递推分解算法[J].地震工程与工程振动,2007,27(5):33-39.LI Jie,LIU Wei,QIAN Yao-kun.Minimal cut-basedrecursive decomposition algorithm for network reliabilityanalysis[J].Journal of Earthquake Engineering andEngineering Vibration,2007,27(5):33-39.(inChinese)
[11]刘威,李杰.网络可靠性分析的最小路算法和最小割算法研究[J].地震工程与工程振动,2008,28(3):33-38.LIU Wei,LI Jie.Comparison between path-based andcut-based algorithms for reliability analysis of networks[J].Journal of Earthquake Engineering and EngineeringVibration,2008,28(3):33-38.(in Chinese)
[12]AHMAD S H.A simple technique for computing networkreliability[J].IEEE Transaction on Reliability,1982,R30(1):41-44.
[13]AHMAD S H,JAMIL A T M.A modified technique forcomputing network reliability[J].IEEE Transaction onReliability,1987,R36(5):554-556.
[14]武小悦,沙基昌.构造网络不交化最小路集的一种新算法[J].系统工程理论与实践,2000(1):62-66.WU Xiao-yue,SHA Ji-chang.A new algorithm forconstructing disjoint minimal path set of network[J].Systems Engineering—Theory&Practice,2000(1):62-66.(in Chinese)
[15]贾进章,鲁忠良,姜克寒.基于网络简化技术的通风网络可靠度新算法[J].辽宁工程技术大学学报,2007,26(5):641-644.JIA Jin-zhang,LU Zhong-liang,JIANG Ke-han.Newalgorithm for computing ventilation network reliabilitybased on network simplification technology[J].Journal ofLiaoning Technical University,2007,26(5):641-644.(in Chinese)
[16]JAVANBARG M B,SCAWTHORN C,KIYONO J,et al.Minimal path set seismic reliability evaluation of lifelinenetworks with link and node failures[C]∥Proceeding ofTCLEE Lifeline Earthquake Engineering in a MultihazardEnvironment,Oakland,CA,June 28-July 1,2009.
[17]刘威,李杰.基于网络缩减的递推分解算法[J].同济大学学报:自然科学版,2009,37(2):43-47.LIU Wei,LI Jie.Recursive decomposition algorithmbased on network reduction technologies[J].Journal ofTongji University:Natural Science Edition,2009,37(2):43-47.(in Chinese)
[18]SHOOMAN A M,KERSHENBAUM A.Methods forcommunication-network reliability analysis:probabilisticgraph reduction[C]∥Proceedings of the AnnualReliability&Maintainability Symposium,Las Vegas,NV,January 21-23,1992.
[2]BALL M O.Computational complexity of network reliabilityanalysis:an overview[J].IEEE Transaction onReliability,1986,R35(3):230-239.
[3]ABRAHAM J A.An improved algorithm for networkreliability[J].IEEE Transaction on Reliability,1979,R28(1):58-61.
[4]DOTSON W P,GOBIEN J O.A new analysis techniquefor probabilistic graphs[J].IEEE Transaction on Circuitsand Systems,1979,26:855-865.
[5]KUO S Y,LU S K,YEH F M.Determining terminal-pairreliability based on edge expansion diagrams using OBDD[J].IEEE Transaction on Reliability,1999,48(3):234-246.
[6]CHATURVEDI S K,MISRA K B.A hybrid method toevaluate reliability of complex networks[J].InternationalJournal of Quality&Reliability Management,2002,19:1098-1112.
[7]YOO Y B,DEO N.A comparison of algorithms forterminal-pair reliability[J].IEEE Transaction onReliability,1988,R37(2):210-215.
[8]SEVTAP-SELCUK A,SEMIH-YUCEMEN M.Reliabilityof lifeline networks under seismic hazard[J].ReliabilityEngineering and System Safety,1999,65:213-227.
[9]LI J,HE J.A recursive decomposition algorithm fornetwork reliability evaluation[J].Earthquake Engineeringand Structural Dynamics,2002,31:1525-1539.
[10]李杰,刘威,钱摇琨.网络可靠性分析的最小割递推分解算法[J].地震工程与工程振动,2007,27(5):33-39.LI Jie,LIU Wei,QIAN Yao-kun.Minimal cut-basedrecursive decomposition algorithm for network reliabilityanalysis[J].Journal of Earthquake Engineering andEngineering Vibration,2007,27(5):33-39.(inChinese)
[11]刘威,李杰.网络可靠性分析的最小路算法和最小割算法研究[J].地震工程与工程振动,2008,28(3):33-38.LIU Wei,LI Jie.Comparison between path-based andcut-based algorithms for reliability analysis of networks[J].Journal of Earthquake Engineering and EngineeringVibration,2008,28(3):33-38.(in Chinese)
[12]AHMAD S H.A simple technique for computing networkreliability[J].IEEE Transaction on Reliability,1982,R30(1):41-44.
[13]AHMAD S H,JAMIL A T M.A modified technique forcomputing network reliability[J].IEEE Transaction onReliability,1987,R36(5):554-556.
[14]武小悦,沙基昌.构造网络不交化最小路集的一种新算法[J].系统工程理论与实践,2000(1):62-66.WU Xiao-yue,SHA Ji-chang.A new algorithm forconstructing disjoint minimal path set of network[J].Systems Engineering—Theory&Practice,2000(1):62-66.(in Chinese)
[15]贾进章,鲁忠良,姜克寒.基于网络简化技术的通风网络可靠度新算法[J].辽宁工程技术大学学报,2007,26(5):641-644.JIA Jin-zhang,LU Zhong-liang,JIANG Ke-han.Newalgorithm for computing ventilation network reliabilitybased on network simplification technology[J].Journal ofLiaoning Technical University,2007,26(5):641-644.(in Chinese)
[16]JAVANBARG M B,SCAWTHORN C,KIYONO J,et al.Minimal path set seismic reliability evaluation of lifelinenetworks with link and node failures[C]∥Proceeding ofTCLEE Lifeline Earthquake Engineering in a MultihazardEnvironment,Oakland,CA,June 28-July 1,2009.
[17]刘威,李杰.基于网络缩减的递推分解算法[J].同济大学学报:自然科学版,2009,37(2):43-47.LIU Wei,LI Jie.Recursive decomposition algorithmbased on network reduction technologies[J].Journal ofTongji University:Natural Science Edition,2009,37(2):43-47.(in Chinese)
[18]SHOOMAN A M,KERSHENBAUM A.Methods forcommunication-network reliability analysis:probabilisticgraph reduction[C]∥Proceedings of the AnnualReliability&Maintainability Symposium,Las Vegas,NV,January 21-23,1992.
版权所有：© 2023 中国地质图书馆 中国地质调查局地学文献中心