簡易檢索 / 詳目顯示

回結果列表
研究生： 楊策
Yang, Tse
論文名稱： 考慮單一隨機限制式之快速篩選法
Rapid Screening Considering a Single Stochastic Constraint
指導教授： 蔡青志
Tsai, Shing-Chih
學位類別： 碩士
Master
系所名稱： 管理學院 - 工業與資訊管理學系
Department of Industrial and Information Management
論文出版年： 2015
畢業學年度： 103
語文別： 中文
論文頁數： 79
中文關鍵詞： 模擬最佳化 、目標式篩選 、限制式篩選程序 、相異樣本數下可行性驗證程序 、單一隨機限制式
外文關鍵詞： Optimization via Simulation, Rapid Screening, Constraint Screening, Feasibility Check Procedure, Single Stochastic Constraint
相關次數： 點閱：134  下載：6 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 模擬最佳化(Optimization via Simulation; OvS)是從許多不同的模擬候選解中，找出期望績效最優良的候選解，相較於一般的最佳化方法，可以納入更多隨機性及較大變異的考量。其中，排序與選擇程序(Ranking and Selection; R&S)用以處理從少量的模擬候選解中，找出最佳候選解的問題，且其在統計上給予保證性。

    現有的模擬演算法在處理0-1最佳化問題時，往往會因為偏向純隨機搜尋法(Pure Random Search)而顯得效果不彰。快速篩選法(Rapid Screening Procedure; RS)為一用來處理單一隨機目標式的模擬最佳化演算法，其在處理0-1問題時，較現有的演算法來得更有效率。本研究將原有的快速篩選法延伸至可以處理具有單一隨機限制式的演算法，分為三種演算法。演算法A在正確選擇機率(Probability of Correct Selection; PCS)上證明其統計保證性，但其抽樣成本較高，且可能有浪費樣本的狀況；在演算法B中，提出限制式篩選程序與相異樣本數下可行性驗證程序，藉以改善演算法A的缺點。此演算法在抽樣成本上較為節省，但無法證明其統計保證性；演算法C統合演算A與演算法B，藉由可行性驗證與目標式篩選的交互使用，不用確認所有候選解可行性後才執行目標式篩選，且在目標式篩選階段記錄候選解間目標式期望值的優劣。也因為其刪除條件較為嚴格，其在有錯誤刪除發生的情境中，可以同時兼顧樣本的節省以及正確選擇機率的保證。

    藉由本研究所提出的演算法，透過對於候選解空間的搜尋能力，可以在限制的時間下，以系統化的方式找出最佳近似解，且在找到之最佳可行解的正確選擇機率上，本研究亦證明其統計保證性。

    Some existing simulation optimization algorithms become pure random search methods and thus are
    ineffective for the problem of zero-one optimization via simulation. In this paper, we present a highly efficient rapid screening procedure for solving the problem
    of zero-one simulation optimization considering a single stochastic constraint. Three algorithms adopting different mechanisms and providing different statistical
    guarantees are described, and empirical studies are performed to compare the efficiency of each algorithm and other existing processes.

    摘要 i 英文延伸摘要 ii 目錄 viii 圖目錄 xii 表目錄 xiii 第一章 緒論 1 1.1 研究背景與動機 . . . . . . . . . . . . . . . . . . 1 1.2 研究目的 . . . . . . . . . . . . . . . . . . . . . 2 1.3 論文架構 . . . . . . . . . . . . . . . . . . . . . 3 第二章 文獻探討 4 2.1 排序與選擇程序(Ranking and Selection; R&S) . . . 4 2.1.1 無差異程序(Indifference Zone Procedure; IZ) . . . .5 2.1.2 子集合選擇程序(Subset Screening Procedure) . . . . 5 2.1.3 NSGS . . . . . . . . . . . . . . . . . . . . . . 6 2.1.4 與標準比較問題(Comparison with a Standard; CwS) . 8 2.1.5 可行性驗證程序(Feasibility Check Procedure; FCP) . 10 2.2 快速篩選法(Rapid Screening; RS) . . . . . . . . . . 16 2.2.1 離散型模擬最佳化(Discrete Optimization via Simulation; OvS) 16 2.2.2 快速篩選程序(Rapid Screening Procedure) . . . . . 17 2.2.2.1 起始解產生法(Setting Up Initial Solutions) . . . 20 2.2.2.2 候選解產生法(Generation of New Solutions) . . . .21 第三章 研究方法 22 3.1 研究問題與假設 . . . . . . . . . . . . . . . . . . . 22 3.2 演算法A . . . . . . . . . . . . . . . . . . . . . . 24 3.3 演算法B . . . . . . . . . . . . . . . . . . . . . . 28 3.3.1 限制式篩選程序(Constraint Screening Procedure) . . 33 3.3.2 相異樣本數可行性驗證程序(FCP with Unequal Sample Size) 36 3.4 演算法C . . . . . . . . . . . . . . . . . . . . . . 38 第四章 實驗設計與分析 43 4.1 實驗評估 . . . . . . . . . . . . . . . . . . . . . 43 4.1.1 0-1隨機背包問題(0-1 Stochastic Knapsack Problem) . 44 4.1.2 考慮限制式之0-1二次問題(Constrained Binary Quadratic Problem; CBQP) . . . . . . . . . . . . . . . . . . . . 47 4.1.3 參數設定. . . . . . . . . . . . . . . . . . . . . 49 4.2 實驗結果 . . . . . . . . . . . . . . . . . 53 4.2.1 0-1隨機背包問題-可行候選解比率低、變異程度低 . . . . 53 4.2.2 0-1隨機背包問題-可行候選解比率低、變異程度高 . . . . 55 4.2.3 0-1隨機背包問題-可行候選解比率中等、變異程度低 . . . 56 4.2.4 0-1隨機背包問題-可行候選解比率中等、變異程度高 . . . 57 4.2.5 0-1隨機背包問題-可行候選解比率高、變異程度低 . . . . 57 4.2.6 0-1隨機背包問題-可行候選解比率高、變異程度高 . . . . 58 4.2.7 0-1隨機背包問題-特殊情境 . . . . . . . . . . . . . 59 4.2.8 考慮限制式之0-1二次問題、二次限制式 . . . . . . . . 60 4.2.9 考慮限制式之0-1二次問題、遞增限性限制式、可行解比率低 61 第五章 結論與未來研究方向 63 5.1 結論與貢獻 . . . . . . . . . . . . . . . . . . . . . 63 5.1.1 各演算法之適用情境及優缺點 . . . . . . . . . . . . . 63 5.2 未來研究方向 . . . . . . . . . . . . . . . . . . . . 67 A 附錄 68 A.1 演算法A整體統計保證性證明 . . . . . . . . . . . . . . 68 A.2 限制式篩選程序統計保證性證明 . . . . . . . . . . . . . 69 A.3 相異樣本數下可行性驗證程序統計保證性證明 . . . . . . . 71 A.4 演算法B.II統計保證性證明 . . . . . . . . . . . . . . 73 A.5 演算法C統計保證性證明 . . . . . . . . . . . . . . . . 74 參考文獻 77

    [1]S. Andradottir, S.H. Kim, 2010. Fully Sequential Procedures for Comparing Constrained Systems via
    Simulation. Naval Research Logistics 57, 403--421.

    [2]R.E. Bechhofer, 1954. A Single-Sample Multiple Decision
    Procedure for Ranking Means of Normal Populations with Known Variance. The Annals of Mathematical Statistics 25, 16--39.

    [3]J. Boesel, B.L. Nelson, S.H. Kim, 2003. Using Ranking and Selection to "Clean Up" after Simulation Optimization. Operations Research 51, 814--825.

    [4]D. Batur, S.H. Kim, 2010. Finding Feasible Systems in the Presence of Constraints on Multiple Performance Measures. ACM Transactions on Modeling and Computer Simulation 20, Article 13, 1--26.

    [5]F. Barahona, M. Junger, G. Reinelt, 1989. Experiments in Quadratic 0-1 Programming. Math Programming 44(2), 127--137.

    [6]V. Fabian, 1974. Note on Anderson's Sequential Procedures with Triangular Boundary. Annals of Statistics 2, 170--176.

    [7]S.S. Gupta, 1956. On a Decision Rule for a Problem in Ranking Means. Ph.D. dissertation Institute of Statistics, University of North Carolina, Chapel Hill, NC.

    [8]L.J. Hong, B.L. Nelson, 2007. Selecting the Best System when Systems are Revealed Sequentially. IIE Transactions 39, 723--734.

    [9]C. Jennison, I.M. Johnstone, B.W Turnbull, 1982.
    Asymptotically Optimal Procedures for Sequential Adaptive Selection of the Best of Several Normal Means. In: Statistical Decision Theory and Related Topics III, Volume~2. New York: Academic Press.

    [10]S.H. Kim, B.L. Nelson, 2001. A Fully Sequential Procedure for Indifference-Zone Selection in Simulation. ACM Transactions on Modeling and Computer Simulation 11, 251--273.

    [11]S.H. Kim, B.L. Nelson, 2006. Selecting the Best
    System. In: Henderson, S.G., Nelson, B.L. (Eds.), Handbooks in Operations Research and Management Science: Simulation. Elsevier Science, Amsterdam, pp. 501--534.

    [12]S. Kosuch, A. Lisser, 2010. Upper Bounds for the 0-1
    Stochastic Knapsack Problem and a Branch and Bound Algorithm. Annals of Operations Research 176, 77--93.

    [13]L.H. Lee, N.A. Pujowidianto, L.W. Li, 2012. Approximate Simulation Budget Allocation for Selecting the Best Design in the Presence of Stochastic Constraints. IEEE Transactions on Automatic Control 57, 2940--2945.

    [14]B.L. Nelson, J. Swann, D. Goldsman, 2001. Simple Procedures for Selecting the Best Simulated System when the Number of Alternatives is Large. Operations Research 49, 950--963.

    [15]B.L. Nelson, D. Goldsman, 2001. Comparisons with a Standard in Simulation Experiments. Management Science 47, 449--463.

    [16]J. Pichitlamken, B.L. Nelson, 2001. Selection of the Best Procedure for Optimization vai Simulation. Winter Simulation Conference.

    [17]J. Pichitlamken, B.L. Nelson, L.J. Hong, 2006. A Sequential Procedure for Neighborhood Selection of the Best in Optimization via Simulation. European Journal of Operational Research 173, 283--298.

    [18]Y.L Tong, 1980. Probability Inequalities in
    Multivariate Distributions. Academic Press, New York.

    [19]S.C. Tsai, 2011. Control-Variate Methods for Comparison with a Standard. Journal of Statistical Computation and Simulation 81, 1703--1716.

    [20]S.C. Tsai, 2013. Rapid Screening Procedures for Zero-One Optimization via Simulation. INFORMS Journal on Computing 25, 317--331.

    下載圖示 校內：2020-07-31公開
    校外：2020-07-31公開
    QR CODE