簡易檢索 / 詳目顯示

研究生: 林姿妘
Lin, Tzu-Yun
論文名稱: 結合控制變量與重要性取樣之估計方法
Combined Estimation Method of Control Variates and Importance Sampling
指導教授: 蔡青志
Tsai, Shing-Chih
學位類別: 碩士
Master
系所名稱: 管理學院 - 工業與資訊管理學系
Department of Industrial and Information Management
論文出版年: 2021
畢業學年度: 109
語文別: 中文
論文頁數: 54
中文關鍵詞: 控制變量重要取樣法合併變異縮減技術樣本平均近似法
外文關鍵詞: Control Variates, Importance Sampling, Integrated Variance Reduction Technique, Sample Average Approximation
相關次數: 點閱:105下載:0
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 在各個領域中存在許多具有隨機性或是難以透過數學模式分析之複雜問題,此時決策者可以利用電腦模擬生成樣本觀察值來協助分析。然而各領域中除一般事件外,許多重要問題屬罕見事件,在模擬罕見事件時,由於事件發生機率過低,導致可取得之有效估計點過少,因此要得到一有效樣本需耗費大量抽樣成本,不但花費長時間抽樣,其取得的樣本變異數大、準確度低,不符效益,為此在模擬領域中發展一套方法 — 變異縮減技術,其利用統計上之估計方法取代一般的樣本平均估計量 ,在新估計量維持不偏的情況下,使其樣本變異數下降且低於原始變異數的技術,藉此獲得更精準之結果並有效提升使用者決策之準確度。
    本研究所提出之模型結合了控制變量與重要性取樣法,在一般情況下,變異縮減技術中縮減效果較好之方法為控制變量,亦是研究中較常被用來與其他變異縮減技術合併探討;而在罕見事件中,重要取樣法是各方法中最適合用來解決樣本抽取的問題,但相對的此方法在使用上較為困難。因此本研究提出將控制變量與重要性取樣法兩種同為輸出型之變異縮減技術依不同形式結合,期望兩變異縮減技術之合併能優於單獨使用變異縮減技術之效益,並使合併後之變異縮減技術所能使用之範圍較單一使用變異縮減技術時廣泛。
    透過數值實驗發現本研究所提出之模型 Model 1 僅於特定事件上能有效優於單一使用 VRT,而其中 CV+ISreg 較於 CV+ISint 穩定,其表現均不劣於單一使用 VRT;提出之模型 Model 2 表現範圍較廣,在使用 IS 方法之變數與輸出值兩者相關性高的前提下,其均適用此方法予以估計,有效達到變異縮減的效果並且優於單一使用 VRT。

    Simulation can help us to identify the best systems and make the best decisions. In this paper, we propose two estimators that combine two different Variance Reduction Techniques (VRT), respectively Control Variates (CV) and Importance Sampling (IS). Here we use two types of IS, integration IS (ISint) and regression IS (ISreg). To choose the optimal change of measure in the context of importance sampling, we use a stochastic optimization approach -- Sample Average Approximation (SAA). The idea is to use IS to adjust the original output, then use CV to reduce the variance of the control variable. We applied the proposed methods to two cases : Normal and Stochastic Activity Networks (SAN). Numerical experiments show that Model 2 has better performance in terms of variance reduction which is related to the correlation between output, control variable, and the importance sampling variable. However, the performance of Model 1 is not as expected; it only works in special case. But the performance of CV+ISreg estimator is better than CV+ISint estimator. CV+ISint estimator may be worse than single method, but CV+ISreg estimator will not. Combining these two VRTs can achieve 95% confidence level of variance reduction benefit from a single method.

    中文摘要                     i 英文延伸摘要                   ii 誌謝                       vii 目錄                       viii 圖目錄                      x 表目錄                       xi 第一章 緒論                     1 1.1 研究背景與動機 . . . . . . . . . . . . . . . 1 1.2 研究目的 . . . . . . . . . . . . . . . . . . 2 1.3 研究架構 . . . . . . . . . . . . . . . . . . 3 第二章 文獻回顧                  4 2.1 變異縮減技術 . . . . . . . . . . . . . . . . 4 2.1.1 控制變量 . . . . . . . . . . . . . . . . . 5 2.1.2 重要性取樣法 . . . . . . . . . . . . . . . 7 2.2 合併變異縮減技術 . . . . . . . . . . . . . . 11 2.3 樣本平均近似法 . . . . . . . . . . . . . . . 13 2.4 小結 . . . . . . . . . . . . . . . . . . . 15 第三章 研究方法                   16 3.1 控制變量(CV Model 0) . . . . . . . . . . . 16 3.1.1 變數期望值之估計 . . . . . . . . . . . . . 16 3.1.2 機率期望值之估計 . . . . . . . . . . . . . 17 3.2 結合控制變量與重要性取樣法(CV+IS Model 1) . . 18 3.2.1 變數期望值之估計 . . . . . . . . . . . . . 18 3.2.2 機率期望值之估計 . . . . . . . . . . . . . 24 3.3 結合控制變量與重要性取樣法(CV+IS Model 2) . . 25 3.3.1 變數期望值之估計 . . . . . . . . . . . . . 25 3.3.2 機率期望值之估計 . . . . . . . . . . . . . 29 第四章 實驗分析與設計               31 4.1 常態假設 . . . . . . . . . . . . . . . . . . 31 4.1.1 實驗設定 . . . . . . . . . . . . . . . . . 31 4.1.2 實驗分析 . . . . . . . . . . . . . . . . . 40 4.2 隨機作業網路 (Stochastic Activity Networks;SAN). . 44 4.2.1 實驗設定 . . . . . . . . . . . . . . . . . 44 4.2.2 實驗分析 . . . . . . . . . . . . . . . . . 49 4.3 小結 . . . . . . . . . . . . . . . . . . . . 50 第五章 結論與未來研究方向             51 5.1 研究總結與建議 . . . . . . . . . . . . . . . 51 5.2 未來研究方向 . . . . . . . . . . . . . . . . 51 外文參考文獻                     52

    Anonuevo, R., & Nelson, B. L. (1988). Automated Estimation and Variance Reduction ˜ via Control Variates for Infinite-Horizon Simulations. Computers and Operations Research, 15(5), 447–456.
    Avramidis, A. N., & Wilson, J. R. (1996). Integrated Variance Reduction Strategies for Simulation. Operations Research, 44(2), 327–346.
    Bratley, P., & Fox, B. L., & Schrage, L. E. (1983). A Guide to Simulation(2nd ed.), Chapter 2. Springer Science & Business Media.
    Burt Jr, J. M., & Garman, M. B. (1971). Conditional Monte Carlo: A Simulation Technique for Stochastic Network Analysis. Management Science, 18(3), 207–217. Bauer, K. W., & Venkatraman, S., & Wilson, J. R. (1987). Estimation Procedures Based on Control Variates with Known Covariance Matrix. Proceddings 1987 Winter Simulation Conference, 334–341.
    Bauer, K. W., & Wilson, J. R. (1992). Control-Variate Selection Criteria. Naval Research Logistics, 39(3), 307–321.
    Grant, F. H. (1983). Hybrid Variance Reduction Techniques Using Antithetic Sampling, Control Variates and Stratified Sampling. Computers & Industrial Engineering, 7(2), 159–169.
    Heidelberger, Philip. (1995). Fast Simulation of Rare Events in Queueing and Reliability Models. ACM Transactions on Modeling and Computer Simulation, 5(1), 43–85.
    Hesterberg, T. (1996). Control Variates and Importance Sampling for Efficient Bootstrap Simulations. Statistics and Computing, 6(2), 147–157.
    Hesterberg, T. C., & Nelson, B. L. (1998). Control variates for probability and quantile estimation. Management Science, 44(9), 1295-1312.
    Hesterberg, T. C. (2003). Advances in importance sampling, Chapter 2. Ph. D. thesis, Stanford University.
    Jourdain, B., & Lelong, J. (2009). Robust Adaptive Importance Sampling for Normal 52 Random Vectors. The Annals of Applied Probability, 19(5),1687–1718.
    Kleijnen, J. P. C., & Ridder, A.A.N., & Rubinstein, R. Y. (2010). Variance Reduction Techniques in Monte Carlo Methods. In Gass, S. I., & Fu, M. C. (Eds.), Encyclopedia of Operations Research and Management Science. Boston: Springer.
    Kleywegt, A. J., & Shapiro, A., & Homem-de-Mello, T. (2002). The Sample Average Approximation Method for Stochastic Discrete Optimization. SIAM Journal on Optimization, 12(2), 479–502.
    Kwon, C., & Tew, J. D. (1994). Strategies for Combining Antithetic Variates and Control Variates in Designed Simulation Experiments. Management Science, 40(8), 1021– 1034.
    L’Ecuyer, P., & Buist, E. (2006). Variance Reduction in the Simulation of Call Centers. In Proceedings of the 38th conference on Winter simulation (pp. 604–613). Winter Simulation Conference.
    Lavenberg, S. S., & Welch, P. D. (1981). A Perspective on the Use of Control Variables to Increase the Efficiency of Monte Carlo Simulations. Management Science, 27(3), 322–335.
    Nelson, B. L. (1989). Batch Size Effects on the Efficiency of Control Variates in Simulation. European Journal of Operational Research, 43(2), 184–196.
    Nelson, B. L. (1990). Control-Variate Remedies. Operations Research, 38(6), 974–992.
    Owen, A. & Zhou, Y. (2000). Safe and Effective Importance Sampling. Journal of the American Statistical Association, 95(449), 135–143.
    Ross, S. M., & Lin, K. Y. (2001). Applying Variance Reduction Ideas in Queuing Simulations. Probability in the Engineering and Informational Sciences, 15(04), 481–494.
    Shapiro, A. (1991). Asymptotic Analysis of Stochastic Programs. Annals of Operations Research, 30(1), 169–186.
    Sabuncuoglu, I., & Fadiloglu, M. M., & Celik, S. (2008). Variance Reduction Techniques: Experimental Comparison and Analysis for Single Systems. IIE Transactions, 40(5), 53 538–551.
    Wang, W., & Ahmed, S. (2008). Sample Average Approximation of Expected Value Constrained Stochastic Programs. Operations Research Letters, 36(5), 515–519.
    Yang, W. N., & Liou, W. W. (1996). Combining Antithetic Variates and Control Variates in Simulation Experiments. ACM Transactions on Modeling and Computer Simulation, 6(4), 243–260.
    Yang, W. N., & Nelson, B. L. (1992). Multivariate Batch Means and Control Variates. Management Science, 38(10), 1415–1431.

    下載圖示
    2026-02-01公開
    QR CODE