大型隨機系統之模擬最佳化演算法

隨機系統最佳化由於實務上許多成功之應用，近年來為相當熱門之主題。然而，處理系統之隨機性本身即為一相當困難之問題，對於大型隨機系統，其困難度更是大幅之增加。在近年來最知名且最廣泛運用的方法就是反應曲面法(Response Surface Methodology)，簡稱為RSM。RSM為一包含了大量數學與統計技巧之方法，用於處理隨機系統之最佳化，數十年來在學術界與產業界有許多成功之應用。許多隨機系統由於其反應變數與獨立變數之真實關係相當複雜且未知，因此反應曲面法利用一階或二階多項式在鄰近區域建構近似模式，並利用此近似模式搜尋改善區域，並逐步往最佳解移動。反應曲面法的優點為利用許多強而有力之統計方法，例如實驗設計以及回歸分析等，因此在處理大規模之問題時，計算效率遠較其它方法為佳。Chang, Hong, 與Wan (2009)提出了一以反應曲面法為基礎之隨機最佳化方法稱為STRONG (Stochastic Trust Region Response Surface Method)。STRONG結合了反應曲面法和非線性規劃之信賴區域法(Trust Region Method )之優點，不但保存了原始反應曲面法之優點並且消除了其缺點，為一相當吸引人之方法。然而，當STRONG用於處理實務上極為大型之隨機系統時，由於在每次迭代中須使用相當大之計算量，因此在應用上有其困難性。本研究發展了一套以STRONG為基礎之大型隨機系統模擬最佳化之演算法，用以處理大型隨機系統之最佳化問題，其概念是將STRONG結合有效之因子篩選方法(factor screening method)並將其命名為STRONG-LS，以減少處理大型問題時所需之計算量。詳細的說，我們利用篩選方法於每次迭代時篩選出重要因子，再利用篩選出之重要因子建構出小型之反應曲面並進行最佳化，由於大型問題已被拆解為小型問題，因此可以避免直接處理大型問題時所需要之大量的計算量。透過實證研究，我們證實STRONG-LS可用來處理大型隨機系統之模擬最佳化問題；與現存其他演算法比較，STRONG-LS之計算效率亦優於較其他演算法，尤其是在大型問題之上。

關鍵字

隨機系統；實驗設計；模擬最佳化；反應曲面法

參考文獻

[1]Banks, J., ed. 1998. Handbook of Simulation. John Wiley and Sons., New York.

[2]Barton, R.R., J.S. Ivey. 1996. Nelder-Mead simplex modifications for simulation optimization. Management Science, 42(7): 954–973.

[3]Barton, R.R., M. Meckesheimer. 2006. Metamodel-based simulation optimization. S.G. Henderson, B.L. Nelson, eds., Chapter 18 in Handbooks in Operations Research and Management Science, vol. 13: Simulation. Elsevier, Amsterdam, 535–574.

[4]Bettonvil, B., J. P.C. Kleijnen. 1997. Searching for important factors in simulation models with many factors: Sequential bifurcation. European Journal of Operational Research. 96:180–194.

[5]Chang, K.-H., L.J. Hong, and H. Wan. 2009. Stochastic Trust-Region Response-Surface Method (STRONG) – A New Response-Surface Framework for Simulation Optimization. (Working paper)

國際替代計量

大型隨機系統之模擬最佳化演算法

全文下載

主題瀏覽