臺灣博碩士論文加值系統

為了評估複雜的隨機網路系統之效能，對於管理者而言，網路可靠度是一項決定性的關鍵指標。本研究目的為如何在有限的時間內得到更精確的估計值。由於利用數學解析法評估網路可靠度為一個非確定性的多項式時間難題(NP-hard)，另一個可行的替代方案即是利用電腦模擬估計系統可靠度。在高可靠度網路下，傳統蒙地卡羅法需要很大的抽樣成本以得到精確的估計值，因此在不增加抽樣成本的情況下，使用變異數縮減技術降低估計量的變異程度是必須的。Cancela,H. and Khadiri,M.E在2003年提出結合串聯-並聯化簡於遞迴變異數縮減技術，避免冗餘的重覆計算。本研究提出一個徹底的分層抽樣計劃以提高變異數縮減程度。實驗結果顯示本研究提出的方法勝過現存的抽樣方法。

In order to evaluate the performance of a complicated stochastic network system, network reliability is a decisive key factor to the administrator. The purpose of this paper is to obtain a more accurate estimator within limited time. Because numerical evaluation method for network reliability is an NP-hard problem, an alternative approach to the exact evaluation is to estimate network reliability using computer simulation. Crude Monte Carlo method suffers from requiring large sampling efforts when the network is highly reliable, so variance reduction techniques which reduces the variance of the estimator without increasing the sampling efforts must be used. Cancela,H. and Khadiri,M.E (2003) incorporates series-parallel reductions in a recursive variance reduction algorithm and avoids redundant identical computations. This paper proposes an exhaustively stratified sampling scheme to enhance the variance reduction. Empirical results show that the proposed method outperforms the existing sampling methods.

第一章 導論
1.1 研究背景與動機
1.2 研究目的
1.3 研究範圍
1.4 論文架構
第二章 理論與相關文獻之探討
2.1 網路模型及符號定義
2.2 網路可靠度 - 解析法
2.3 原始蒙地卡羅法(Crude Monte Carlo, CMC)
2.4 變異數縮減技術(Variance Reduction Techniques)
2.5 分層抽樣(Stratified Sampling)
2.6 遞迴變異數縮減技術(Recursive Variance-Reduction Technique, RVR)
2.7 串聯-並聯化簡結合遞迴變異數縮減技術(Series-Parallel Reduction in Recursive Variance-Reduction Technique,RVR-SP)
2.8 一種新的遞迴變異數縮減技術(NRVR)
2.9 文獻總整理與比較
第三章 研究方法
3.1 模型介紹
3.2 分層抽樣結合遞迴變異數縮減技術(SRVR)
3.3 分層抽樣結合串聯-並聯化簡與遞迴變異數縮減技術(SRVR-SP)
第四章 實驗步驟與結果分析
4.1 系統模擬軟體簡介
4.2 實驗說明
4.3 評估方法
4.4 實驗步驟
4.5 實驗結果分析
第五章 結論與未來研究方向
5.1 結論
5.2 未來研究方向

Bulteau,S. and Khadiri,M.El
"A Monte Carlo Simulation of the Flow Network Reliability Using Importance and Stratified Sampling",
Recherche operationnelle/Operations Research,
Vol.32, No.3, 271-287, 1998.
Cristian C.
"Using Multi-Stage and Stratified Sampling for Inferring Fault-Coverage Probability",
IEEE TRANSACTIONS ON RELIABILITY,
Vol.44, No.4, 632-639, 1995.
Cancela,H. and Khadiri,M.El
"A Recursive Variance-Reduction Algorithm For Estimating Communication-Network Reliability",
IEEE TRANSACTIONS ON RELIABILIT,
Vol.44, No.4, 595-602, 1995.
Cancela,H. and Khadiri,M.El
"Series-Parallel Reductions in Monte Carlo Network-Reliability Evaluation",
IEEE TRANSACTIONS ON RELIABILITY,
Vol.47, No.2, 159-164, 1998.
Cancela,H. and Khadiri,M.El
"The Recursive Variance-Reduction Simulation Algorithm for Network Reliability Evaluation",
IEEE TRANSACTIONS ON RELIABILITY,
Vol.52, No.2, 207-212, 2003.
Charnes,J.M.
"Statistical Analysis of Output Processes"
Proceedings of the 1993 winter Simulation conference,
41-49, 1993.
Cheng,R.C.H.
"Variance Reduction Methods"
Proceedings of the 1986 winter Simulation conference},
60-68, 1986.
Fishman, G.S.
"A Monte Carlo Sampling Plan for Estimating Network Reliability",
Operations Research,
Vol.34, No.4, 581-594, 1986.
Fishman, G.S.
"Estimating the s-t Reliability function Using Importance and Stratified Sampling",
Operations Research,
Vol.37, No.3, 462-473, 1989.
Fishman G.S.
"A First Course in Monte Carlo",
Thomson, 2005.
Jacek J.
"Network Reliability"
Seminar TCS-RUN Rigi Kaltbad,
2006.
Law, A.M. and Kelton, W.D.
"Simulation Modeling and Analysis, 3nd edition",
McGraw-Hill,Inc, 2000.
Takeshi K. and Shuichi S. and Hiroaki I.
"Efficient Computation of Network Reliability Importance on K-Terminal Reliability"
International Journal of Reliability, Quality and Safety Engineering,
Vol.12, No.3, 213-226, 2005.
Valiant, L.G.
"The Complexity of Enumeration and Reliability Problems",
SIAM Journal on Computing,
Vol.8, No.3, 410-412, 1979.
Willson,J.R.
"Variance Reduction in Simulation"
Proceedings of the 1984 winter Simulation conference,
123-128, 1984.
台灣科技大學楊維寧博士
"統計學",
新陸書局, 2003.