最佳達成次數配置之稀罕事件切割模擬-應用於電力系統大停電模擬

Optimal Hit-Based Splitting Technique for Rare-Event Simulation and Its Application to Power Grid Blackout Simulation

王星博(Sing-Po Wang)

指導教授 ： 陳正剛

共同指導教授 ： 陳俊宏(Chun-Hung Chen)

國立臺灣大學/工學院/工業工程學研究所/碩士(2011年)

https://doi.org/10.6342/NTU.2011.02047

摘要

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

關鍵字

稀罕事件 ； 切割模擬 ； OCBA ； 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.

並列關鍵字

rare event ； multilevel splitting ； OCBA ； OSTRE ； hit-based splitting ； power grid ； blackout

參考文獻

[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

[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.

[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.