- 學位論文
序優化演算法求解隨機模擬最佳化問題
Apply Ordinal Optimization for Solving the Stochastic Simulation Optimization Problems
若您是本文的作者，可授權文章由華藝線上圖書館中協助推廣。
摘要
在本篇文章中，我們提出一個結合序優化(OO)和計算最佳預算分配(OCBA)的進化式演算法(EA)，並且用來解決具有巨大的離散解空間的即時隨機模擬最佳化組合問題，以找出一個足夠好的解。首先我們會先使用一個事先離線訓練好的半徑函數網路(RBF)作為替代模型，搭配進化式演算法在所考慮的問題中獲得一個足夠好的子集解，接著使用計算最佳預算分配的技術繼續尋找最佳的解，最後便可獲得足夠好的解。另外，我們將提出的演算法應用在飯店訂房限制(HBL)收益最大化問題中，飯店訂房限制是一個隨機模擬最佳化組合問題。為了測試我們的方法所獲得足夠好的解在解的品質與計算效能上的表現，將我們的方法與另外三個方法，基因演算法(GA)粒子群演算法(PSO)與演化策略(ES)進行比較，發現我們方法的表現的確超越其他方法。
並列摘要
In this paper, we propose an evolutionary algorithm (EA) assisted by a surrogate model in the framework of ordinal optimization (OO) and optimal computing budget allocation (OCBA) to solve the real-time combinatorial stochastic simulation optimization problem with huge discrete solution space for a good enough solution. For the purpose of real-time application, we use an off-line trained radial basis function (RBF) as the surrogate model. We apply EA assisted by the trained RBF to the considered problem to obtain a subset of good enough solutions S. Also for the sake of real-time application, we use OCBA technique to find the best solution in S, and which is the obtained good enough solution. We apply the proposed algorithm to a hotel booking limit (HBL) problem, which is a combinatorial stochastic simulation optimization problem. To demonstrate the computational efficiency of our approach and the quality of the obtained solution, we have compared with three competing methods, the genetic algorithm (GA) and particle swarm optimization (PSO) algorithm and the evolution strategies (ES). Test results show that our approach is an excellent alternative for the combinatorial stochastic simulation optimization problem.
參考文獻
[1] M.- C. Fu, “Optimization for simulation: theory vs. practice,” INFORMS Journal on Computing, 2002, No. 14, pp. 192-215.
[4] R.H. Myers, D.C. Montgomery, G.G. Vining, C.M. Borror, and S.M. Kowalski, “Response surface methodology: A retrospective and literature survey,” Journal Of Quality Technolog, 2004, Vol. 36, No. 1, pp.53-77.
[5] J. April, F. Glover, J.P. Kelly, and M. Laguna, “Practical introduction to simulation optimization,” Proceedings of the 2003 Winter Simulation Conference, New Orleans, LA, 2003, pp. 71-78.
[6] E. Tekin, and I. Sabuncuoglu, “Simulation optimization: A comprehensive review on theory and applications,” IIE Transactions, 2004, Vol. 36, No. 11, pp. 1067-1081.
[8] B. Suman, and P. Kumar, “A survey of simulated annealing as a tool for single and multiobjective optimization,” Journal of the Operational Research Society, 2006, Vol. 57, No. 10, pp. 1143-1160.