進階搜尋


   電子論文尚未授權公開,紙本請查館藏目錄
(※如查詢不到或館藏狀況顯示「閉架不公開」,表示該本論文不在書庫,無法取用。)
系統識別號 U0026-2607201612421500
論文名稱(中文) 合併變異數縮減技術於完全連續選擇程序
論文名稱(英文) Integrated Variance Reduction Strategies in Fully Sequential Selection Procedures
校院名稱 成功大學
系所名稱(中) 工業與資訊管理學系
系所名稱(英) Department of Industrial and Information Management
學年度 104
學期 2
出版年 105
研究生(中文) 宋奇檠
研究生(英文) Chi-Ching Sung
學號 R36034113
學位類別 碩士
語文別 中文
論文頁數 51頁
口試委員 指導教授-蔡青志
口試委員-葉英傑
口試委員-翁慈宗
口試委員-張裕清
中文關鍵字 排序和選擇程序  控制變量  條件期望估計法  事後分層法  合併變異縮減技術 
英文關鍵字 Variance Reduction Technique  Fully Sequential Procedure  Control Variates  Simulation Optimization 
學科別分類
中文摘要 系統模擬包含的應用領域十分廣泛,當遇到不確定性以及擁有隨機變因的問題時,
均可以使用模擬來進行分析,而在決策者面對模擬最佳化問題時,若問題維度不大,則
可使用排序與選擇程序使得在一信心水準下,正確選擇最佳或近似最佳系統使決策者參
考; 然而排序與選擇程序只適用系統個數較小的前提下,若系統之績效值變異程度過
大,將影響程序執行速度,使得抽樣成本及運算時間提高。 因此透過統計中的變異縮減
技術,利用替代估計量取代一般的樣本平均數估計量,使其樣本變異數將較原本變異數
更低,達到變異縮減之效果。 變異縮減技術可分之為兩種:輸入型技術及輸出型技術,
前者是使用相關性的輸入變量,藉此產生具有正或負相關的輸出值;而後者是使用輔助
變數試圖修正輸出值,使得變異數下降。 而本研究將控制變量、條件期望法、事後分層
法等三種不同的變異縮減技術結合所形成的合併變異縮減技術,期望能優於單獨使用變
異縮減技術之效益,以求達到更顯著的變異縮減效果。
本研究建立控制變量結合條件期望法、控制變量結合事後分層法等兩種合併變異縮
減技術之模型,並將推算所得之估計量以及變異數估計量應用於完全連續選擇程序中,
且在滿足信心水準下,比較原始程序以及合併型程序的優劣,並將程序用於一範例加
以實驗比較。 歸納出合併之變異縮減技術之效果皆可優於單一使用,其中在控制變量
與條件期望法合併的部分,在原本的控制變量外,再選擇一個條件變量 (Conditioning
Variate),其可同時對觀察值與控制值取條件觀察值,其合併效果最佳。 而在控制變量
結合事後分層法的部分,只要選擇與觀察值具有相關性的分層變數,而此分層變數與控
制值獨立下,能獲得最佳之合併效果。
英文摘要 Simulation optimization can help us to identify the best systems from all candidate
systems. In this paper, we propose two estimators that combine three different variance
reduction techniques, and use the combined estimators in Fully Sequential Selection
Procedures (FSP). First we combine Control Variates (CV) with Condition Expectation
(CE). The idea is to use a condition variable to replace the origin output or the variable
use in CV with condition expectation. So there are three schemes. And with the case
where the condition variable may not be fully used, we also show that partial condition
expectation can be used as ordinary CE . Second, we combine Control Sum (CS) with
Post-stratified Sampling (PS). The idea is like ordinary PS, but we use CS to estimate
each stratum and to combine each stratum with its weight as in ordinary PS. Then we
replace the ordinary estimator used in FSP with these combined estimators. Empirical
results show that the procedure using CE to replace both the output and control variates
has the most significant reduction effects in CV+CE, and the reduction effects are
related to the correlation between output, control variables, and the condition variable.
When the condition variable can only replace the partial estimators, it still works better
than the ordinary CV, in CS+PS, if we use a stratified variable that is independent to
control variable. Combining the two techniques can obtain a guarantee benefit from a
single method.
論文目次 目 錄
中文摘要 i
英文延伸摘要 ii
誌謝 viii
目錄 ix
表目錄 xi
第一章 緒論 1
1.1 研究背景與動機 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 研究目的 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 研究流程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
第二章 文獻回顧與基本模型介紹 4
2.1 變異縮減技術 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1.1 控制變量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.2 條件期望估計法 . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.3 事後分層法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 合併變異縮減技術 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.1 CV+CI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.2 CV+CE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.3 CV+PS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 運用合併變異縮減技術之排序與選擇程序 . . . . . . . . . . . . . . . . . 17
2.4 小結 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
第三章 研究方法 20
3.1 CV+CE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2 CS+PS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3 完全連續選擇程序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.3.1 CV+CE 程序步驟 . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.3.2 CV+PCE 程序步驟 . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3.3 CS+PS (without Variance updating)程序步驟 . . . . . . . . . . . 31
3.3.4 CS+PS (with Variance updating)程序步驟 . . . . . . . . . . . . . 32
3.3.5 CV (with Variance updating)程序步驟 . . . . . . . . . . . . . . . 33
第四章 實驗設計與分析 35
4.1 實驗評估 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.2 CV+CE 實驗設定 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.3 CV+PCE 部分條件期望法 . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.4 CS+PS 實驗設定 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.5 小結 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
第五章 結論與未來研究方向 44
5.1 研究總結與建議 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.1.1 CV+CE 完全連續選擇程序 . . . . . . . . . . . . . . . . . . . . . 44
5.1.2 CS+PS 完全連續選擇程序 . . . . . . . . . . . . . . . . . . . . . 45
5.2 未來研究方向 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
參考文獻 47
參考文獻 Anonuevo, R. and B. L. Nelson. (1988) Automated stimation and Variance Reduction via Control Variates for Infinite-Horizon Simulations. Computers and Operations Research,15, 447–456.
Avramidis, A. N. and J. R. Wilson. (1996) Integrated Variance Reduction Strategies for
Simulation. Operations Research, 44, 327–346.
Anderson, T.W. An Introduction to Multivariate Statistical Analysis, John Wiley and
Sons, New York, 2003.
Bauer, K. W., S. Venkatraman, and J. R. Wilson. (1987) Estimation Procedures Based on
Control Variates with Known Covariance Matrix. Proceddings 1987 Winter Simulation
Conference, 334–341.
Bauer, K. W. and J. R. Wilson. (1992) Control-Variate Selection Criteria. Naval Research
Logistics, 39, 307–321.
Bechhofer, R. E. (1954) A Single-Sample Multiple Decision Procedure for Ranking Means
of Normal Populations with known Variances. The Annals of Mathematical Statistics,25,
16–39.
Casella, G., & Berger, R. L. (2002). Statistical Inference . Pacific Grove, CA: Duxbury.
Billingsley, P. (1999) Convergence of Probability Measures. John Wiley & Sons, New
York, NY.
Cheng, R. C. H. (1982) The Use of Antithetic Variates in Computer Simulations. Journal
of the Operational Research Society, 3, 229–237.
Fishman, G. S. and B. D. Huang. (1983) Antithetic Variates Revisited. Communications
of the ACM, 26, 964–971.
Glasserman, P. (2003). Monte Carlo Methods In Financial Engineering . Springer Sci-
47
ence & Business Media.
Gupta, S.S. (1956) On a Decision Rule for a Problem in Ranking Means. Ph.D. dissertation
Institute of Statistics, University of North Carolina, Chapel Jill, NC.
Grant, F. H. (1983). Hybrid variance reduction techniques using antithetic sampling,
control variates and stratified sampling. Computers & Industrial Engineering, 7(2),
159-169.
Hammersley, J.M. and K. W. Morton. (1956) A New Monte Carlo Technique: Antithetic
Variates. Mathematical Proceedings of the Cambridge Philosophical Society,
52, 449–475.
Kim, S.-H. and B. L. Nelson. (2001) A Fully Sequential Procedure for Indifference-Zone
Selection in Simulation. ACM Transactions on Modeling and Computer Simulation,
11, 251–273.
Kim, S.-H. and B.Ł. Nelson. (2006)”On the Asymptotic Validity of Fully Sequential
Selection Procedures for Steady-State Simulation,” Operations Research, 54, 475-488.
Kwon, C. and J. D. Tew. (1994) Strategies for Combining Antithetic Variates and Control
Variates in Designed Simulation Experiments. Management Science, 40, 1021–1034.
L’Ecuyer, P., & Buist, E. (2008). On the Interaction Between Stratification and Control
Variates, with Illustrations In a Call Centre Simulation. Journal of Simulation, 2(1),
29-40.
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. and P. D. Welch. (1981) A Perspective on the Use of Control Variables
to Increase the Efficiency of Monte Carlo Simulations. Management Science, 27,
48
322–335.
Langford, E., Schwertman, N., and Owens, M. (2001). Is the Property of Being Positively
Correlated Transitive? The American Statistician, 55(4), 322-325.63
Lehmann, E. L. (1966) Some Concept of Dependence. Annals of Mathematical Statistics,
37, 1137–1153.
Little, R. J. (1993). Post-stratification: a modeler’s perspective. Journal of the American
Statistical Association, 88(423), 1001-1012.
Lesnevski, V., B. L. Nelson, and J. Staum. (2007) Simulation of Coherent Risk Measures
Based on Generalized Scenarios. Management Science, 53, 1756–1769.
Mckay, M. D., R. J. Beckman, and W. J. Conover. (1979) A Comparison of Three Methods
for Selecting Values of Input Variables in the Analysis of Output from a Computer
Code. Technometrics, 21, 239–245.
Minh, D. L. (1989). A Variant of the Conditional Expectation Variance Reduction Technique
and its Application to the Simulation of the GI/G/1 queues. Management science,
35(11), 1334-1340.
Nelson, B. L. (1989) Batch Size Effects on the Efficiency of Control Variates in Simulation.
European Journal of Operational Research, 43, 184–196.
Nelson, B. L. (1990) Control-Variate Remedies. Operations Research, 38, 974–992.
Nelson, B. L. and J. C. Hsu. (1993) Control-Variate Models of Common Random Numbers
for Multiple Comparisons with the Best. Management Science, 39, 989–1001.
Nelson, B. L., J. Swann, D. Goldsman, and W. Song. (2001) Simple Procedures for
Selecting the Best Simulated System when the Number of Alternatives is Large. Operations
Research, 49, 950–963.
Nelson, B. L. and J. Staum. (2006) Control Variates for Screening, Selection, and Esti-
49
mation of the Best. ACM Transactions on Modeling and Computer Simulation, 16,
52–75.
Owen, A. B. (1992) A Central Limit Theorem for Latin Hypercube Sampling. Journal of
the Royal Statistical Society. Series B Methodological, 54, 541–551.
Rinott, Y. (1978) On Two-Stage Selection Procedures and Related Probability-Inequalities.
Communications in Statistics–Theory and Methods, A7, 799–811.
Ripley, B. D. (1987) Stochastic Simulation. John Wiley & Sons, New York, NY.
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.
Sabuncuoglu, I., M. M. Fadiloglu, and S. Celik. (2008) Variance Reduction Techniques:
Experimental Comparison and Analysis for Single Systems. IIE Transactions, 40,
538–551.
Stein, M. (1987) Large Sample Properties of Simulations Using Latin Hypercube Sampling.
Technometrics, 29, 143–151.
Sethi, V. K. (1963). A note on optimum stratification of populations for estimating the
population means. Australian Journal of Statistics, 5(1), 20-33.
Tong, Y. L. (1980) Probability Inequalities in Multivariate Distribution. Academic Presss,
New York.
Tsai, S. C., B. L. Nelson, and J. Staum. (2009) Combined Screening and Selection of the
Best with Control Variates. Advancing the Frontiers of Simulation: A Festschrift in
Honor of George S. Fishman, Kluwer, 263-289.
Tsai, S. C. and B. L. Nelson. (2010) Fully Sequential Selection Procedures with Control
Variates. IIE Transactions, 71-82.
Tsai, S. C., and Kuo, C. H. (2012). Screening and selection procedures with control
50
variates and correlation induction techniques. Naval Research Logistics (NRL), 59(5),
340-361.
Wilson, J. R., and Pritsker, A. A. B. (1984). Experimental evaluation of variance reduction
techniques for queueing simulation using generalized concomitant variables.
Management Science, 30(12), 1459-1472.
Wilson, J. R., and Pritsker, A. A. B. (1984). Variance reduction in queueing simulation
using generalized concomitant variables. Journal of Statistical Computation and
Simulation, 19(2), 129-153.
Yang, W. N. and B. L. Nelson. (1991) Using Common Random Numbers and Control
Variates in Multiple-Comparison Procedures. Operations Research, 39, 583–591.
Yang, W. N. and B. L. Nelson. (1992) Multivariate Batch Means and Control Variates.
Management Science, 38, 1415–1431.
Yang, W. N. and W. W. Liou. (1996) Combining Antithetic Variates and Control Variates
in Simulation Experiments. ACM Transactions on Modeling and Computer Simulation,
6, 243–260.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2021-07-26起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw