考慮單一隨機限制式之快速篩選法

Translated title of the thesis: Rapid Screening Considering a Single Stochastic Constraint
  • 楊 策

Student thesis: Master's Thesis

Abstract

模擬最佳化(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,藉由可行性驗證與目標式篩選的交互使用,不用確認所有候選解可行性後才執行目標式篩選,且在目標式篩選階段記錄候選解間目標式期望值的優劣。也因為其刪除條件較為嚴格,其在有錯誤刪除發生的情境中,可以同時兼顧樣本的節省以及正確選擇機率的保證。 藉由本研究所提出的演算法,透過對於候選解空間的搜尋能力,可以在限制的時間下,以系統化的方式找出最佳近似解,且在找到之最佳可行解的正確選擇機率上,本研究亦證明其統計保證性。
Date of Award2015 Jul 8
Original languageChinese
SupervisorShing-Chih Tsai (Supervisor)

Cite this

'