臺灣博碩士論文加值系統

估計稀罕事件的發生機率是件相當關鍵的議題，特別是在可靠度、通訊、航空安全管理。當事件真的非常的罕見，採用一般蒙地卡羅模擬方法會變得非常難以執行。多水準切割(Level Splitting)模擬是一個能夠有效改善的手法，其概念主要是將到達稀罕事件分成不同的階段加以模擬。另外，各階段應該配置多少模擬次數也是一件相當重要的問題。Optimal Splitting Technique for Rare-Event (OSTRE)是一個最佳配置切割模擬次數的方法，能夠有效地配置模擬次數到各階段。一般配置模擬次數的方法，皆可能因各階段事件發生機率仍太低，導致所配置之模擬次數不足以觀察到事件之發生，進而無法計算事件發生機率。本文中，我們提出了一個新的方法能夠解決這個問題，此方法配置予各階段所需達成事件(Hit)之次數，而非如OSTRE配予模擬次數，稱之最佳達成次數配置切割(Optimal hit-based splitting)模擬。實驗數據結果顯示最佳配置達成次數的方法在大部分情況下能夠跟OSTRE表現一樣好。除此之外，選擇好的水準在切割模擬中也是一個關鍵的問題。我們藉由決定達成次數為基礎之切割模擬方法提出了一套演算步驟，能夠透過少量模擬次數的初始估計來選擇一組最佳的切割水準，並由案例研究驗證其結果。最後我們將最佳達成次數配置模擬方法應用到一個知名的電力網路大停電問題以驗證並比較該方法之效益，結果證實該方法能有效得在電力網路中找出最容易導致大停電的特定線路。

Rare-event probability estimation is a crucial issue in areas such as reliability, telecommunications and aircraft management. When an event rarely occurs, naive Monte Carlo simulation becomes unreasonably demanding for computing power and often results in an unreliable probability estimate, i.e., an estimate with a large variance. Level splitting simulation has emerged as a promising technique to reduce the variance of a probability estimate by creating separate copies (splits) of the simulation whenever it gets close to a rare event. This technique allocates simulation runs to levels of event progressively approaching a final rare event. However, determination of a good number of simulation runs at each stage can be challenging. An optimal splitting technique called the Optimal Splitting Technique for Rare Events (OSTRE) provides an asymptotically optimal allocation solution of simulation runs. A splitting simulation characterized by allocating simulation runs may fail to obtain a probability estimate because the probability of an event occurring at a given level is too low, and the number of simulation runs allocated to that level is not enough to observe it. In this research, we propose a hit-based splitting method that allocates a number of hits, instead of the number of simulation runs, to each stage. The number of hits is the number of event occurrences at each stage. Regardless of the number of simulation runs required, the allocated number of hits has to be reached before advancing to the next level of splitting simulation. We derive an asymptotically optimal allocation of hits to each stage of splitting simulation, referred to as Optimal Hit-based Splitting Simulation. Experiments indicate that the proposed method performs as well as OSTRE under most conditions. In addition to the allocation problem, choice of levels is also a critical issue in level splitting simulation. Based on the proposed hit-based splitting simulation method, we have developed an algorithm capable of obtaining optimal levels by effectively estimating the initial probability for some events to occur at each stage of progression. Results indicate that the choice of optimal levels is effective. Furthermore, we apply our technique to an IEEE-bus electric network and demonstrate our approach is just as effective as conventional techniques in detecting the most vulnerable link in the electric grid, i.e., the link with the highest probability leading to a blackout event.

口試委員會審定書 #
中文摘要 i
ABSTRACT iii
CONTENTS v
LIST OF FIGURES vii
LIST OF TABLES viii
Chapter 1 Introduction 1
Chapter 2 Rare-Event Simulation Method Review 6
2.1 Level Splitting 6
2.2 Optimal Splitting Technique for Rare Events 10
2.3 Adaptive Multilevel Splitting 12
Chapter 3 Hit-based Splitting Simulation 15
3.1 Maximum Likelihood Estimator of Hit-based Splitting 15
3.2 Optimal Hit-based Splitting 17
Chapter 4 Estimate of Rare-Event Probabilities 21
4.1 Choice of Optimal Levels 21
4.2 Numerical Results 25
4.2.1 Limited simulation budget 25
4.2.2 A large simulation budget with specific levels 27
4.2.3 A large simulation budget with linear and optimal levels 28
4.2.4 Different computing budgets 30
Chapter 5 Analysis of Power Grid System Blackouts 31
5.1 Blackout Problems in Power Systems 31
5.2 Choice of Optimal Splitting Levels 34
5.3 Detection of Vulnerable Links 36
Chapter 6 Conclusion and Future Work 39
REFERENCE 41
Appendix - Proof in Chapter 3 43
1. Proof of Lemma 3.1 43

[1]Garvels, M. J. J., and D. P. Kroese. 1998. A comparison of RESTART implementations. In Proceedings of the 1998 Winter Simulation Conference, 601-609: IEEE Press.
[2]Koeunyi Bae, James S. Thorp, “A stochastic study of hidden failures in power system protection”, Decision Support Systems, Vol. 24, pp. 259-268, 1999
[3]Rich Christie, “118 power flow test case”, University of Washington, 1993, [Online]. Available: http://www.ee.washington.edu/research/pstca/pf118/pg_tca118bus.htm
[4]Jie Chen, James S. Thorp, Ian Dobson, “Cascading dynamics and mitigation assessment in power system disturbances via a hidden failure model”, Electrical Power and Energy Systems, 2004.
[5]Speijker, L., H. Blom, G. Bakker, A. Karwal, G. Van Baren, M. Klompstra, E. Kruijsen. 2000. RASMAR final report: Risk analysis of simultaneous missed approaches on Schiphol converging runways 19R and 22. Tech. rep., National Aerospace Laboratory NLR, The Netherlands. NLR-TP-2000-644.
[6]Glynn, P. W. 1994. Efficiency improvement technique. Annals of Operations Research 53 175-197.
[7]Heidelberger, P. 1993. Fast simulation of rare events in queueing and reliability models. L. Donatiello, R. Nelson, eds., Performance Evaluation of Computer and Communication Systems. Springer Verlag, 165-202.
[8]Rubino, G., B. Tu_n, eds. 2009. Rare Event Simulation using Monte Carlo Methods. Wiley, Chichester, U.K.
[9]L''Ecuyer, P., V. Demers, B. Tu_n. 2006. Splitting for rare-event simulation. L. F. Perrone, F. P. Wieland, J. Liu, B. G. Lawson, D. M. Nicol, R. M. Fujimoto, eds., Proceedings of 2006 Winter Simulation Conference. IEEE, Piscataway, NJ, 137-148.
[10]Chen, C. H., D. He, M. Fu, L. H. Lee. 2008. Efficient simulation budget allocation for selecting an optimal subset. INFORMS Journal on Computing 20 579-595.
[11]Chen, C. H., and D. He, "Intelligent Simulation for Alternatives Comparison and Application to Air Traffic Management," Journal of Systems Science and Systems Engineering, Vol. 14, No. 1, pp. 37-51, March 2005
[12]Chen, C. H., E. Yücesan, L. Dai, and H. C. Chen, "Efficient Computation of Optimal Budget Allocation for Discrete Event Simulation Experiment," IIE Transactions, Vol. 42, No. 1, pp. 60-70, January 2010.
[13]Villén-Altamirano, M., J. Villén-Altamirano. 2006. On the efficiency of RESTART for multidimensional state systems. ACM Transactions on Modeling and Computer Simulation 16 251-279
[14]Garvels, M. J. J., D. P. Kroese, and J.-K. C. W. VanOmmeren. "On the Importance Function in Splitting Simulation," European Transactions on Telecommunications, Vol. 13, No. 4, pp. 363–371, 2002.
[15]C´erou, F., and A. Guyader. 2005, October. Adaptive multilevel splitting for rare event analysis. Technical Report 5710, INRIA
[16]Villén-Altamirano, M., J. Villén-Altamirano. 1994. RESTART: A straightforward method for fast simulation of rare events. In Proceedings of the 1994 Winter. Simulation Conference, 282–289: IEEE Press.