The cross-entropy method for network reliability estimation

被引：74

作者：

Hui, KP ^{[1
]}

Bean, N

Kraetzl, M

Kroese, DP

机构：

[1] Def Sci & Technol Org, IN Div, Edinburgh 5111, Australia

[2] Univ Adelaide, Dept Appl Math, Adelaide, SA 5005, Australia

[3] Def Sci & Technol Org, ISR Div, Edinburgh 5111, Australia

[4] Univ Queensland, Dept Math, Brisbane, Qld 4072, Australia

来源：

ANNALS OF OPERATIONS RESEARCH | 2005年 / 134卷 / 01期

关键词：

network reliability; cross-entropy; rare events; importance sampling; permutation Monte Carlo; merge process;

D O I：

10.1007/s10479-005-5726-x

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

Consider a network of unreliable links, modelling for example a communication network. Estimating the reliability of the network-expressed as the probability that certain nodes in the network are connected-is a computationally difficult task. In this paper we study how the Cross-Entropy method can be used to obtain more efficient network reliability estimation procedures. Three techniques of estimation are considered: Crude Monte Carlo and the more sophisticated Permutation Monte Carlo and Merge Process. We show that the Cross-Entropy method yields a speed-up over all three techniques.

引用

页码：101 / 118

页数：18

共 35 条

[1] Application of the cross-entropy method to the buffer allocation problem in a simulation-based environment [J].

Alon, G ;

Kroese, DP ;

Raviv, T ;

Rubinstein, RY .

ANNALS OF OPERATIONS RESEARCH, 2005, 134 (01) :137-151

[2]

[Anonymous], 1992, PROBAB ENG INFORM SC

[3] BOUNDS FOR DISTRIBUTIONS WITH MONOTONE HAZARD RATE .2 [J].

BARLOW, RE ;

MARSHALL, AW .

ANNALS OF MATHEMATICAL STATISTICS, 1964, 35 (03) :1234-&

[4]

Barlow RE, 1975, STAT THEORY RELIABIL

[5]

BURTIN YD, 1972, ENG CYBERN, V10, P445

[6]

Colbourn C. J., 1994, Telecommunication Systems - Modeling, Analysis, Design and Management, V2, P275

[7]

Colbourn C.J., 1987, The combinatorics of network reliability

[8] A tutorial on the cross-entropy method [J].

De Boer, PT ;

Kroese, DP ;

Mannor, S ;

Rubinstein, RY .

ANNALS OF OPERATIONS RESEARCH, 2005, 134 (01) :19-67

[9]

de Boer PT, 2000, PROCEEDINGS OF THE 2000 WINTER SIMULATION CONFERENCE, VOLS 1 AND 2, P646, DOI 10.1109/WSC.2000.899776

[10] A fast cross-entropy method for estimating buffer overflows in queueing networks [J].

de Boer, PT ;

Kroese, DP ;

Rubinstein, RY .

MANAGEMENT SCIENCE, 2004, 50 (07) :883-895

← 1 2 3 4 →