在本篇文章中，我們提出一個結合序優化(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.

索引目錄
中文摘要 I
Abstract II
致謝 IIII
索引目錄 IV
表目錄 VI
圖目錄 VII
符號說明 VIII
第一章　緒論 1
1.1 研究動機與目的 1
1.2 研究方法與論文架構 4
第二章　相關問題的回顧 7
2.1 隨機組合最佳化問題 7
2.2 替代輔助進化式演算法模型應用於序優化的架構 9
2.2.1 半徑函數網路替代模型 10
2.2.2 使用基因演算法輔助替代模型 13
2.2.3 使用計算最佳預算分配技術獲得足夠好的解 21
2.2.3.1 簡單介紹計算最佳分配演算法步驟 21
第三章　序優化理論以及應用 28
3.1 回顧飯店訂房預定限制(HBL)問題 28
3.2 問題敘述 32
3.3 應用最佳計算分配方法輔助半徑函數網路解決飯店預定限制問題 34
3.3.1 建構近似模型 34
3.3.2 使用半徑函數網路輔助基因演算法 35
3.3.3 使用計算最佳分配技術從S中獲得足夠好的解 36
第四章　測試結果與比較 38
4.1 方法比較 40
4.1.1 粒子群最佳化(PSO) 40
4.1.2 演化策略(ES) 44
4.2 比較結果 48
第五章　結論 51
參考文獻 52

表目錄
表1. 模擬10次所獲得的值 24
表2. 計算獲得的平均值及標準差 24
表3. 發展更新預定限制對於五個要求 32
表4. 28個保留的關聯矩陣. 38
表5. 28個保留的停止預定時間. 38
表6. 足夠好的解和相對應的預期收益以及計算花費時間 40

圖目錄
圖1. 半徑函數網路 12
圖2. 輪盤法示意圖 16
圖3. 單點交配示意圖 17
圖4. 基因演算法的基本架構圖 19
圖5. 基因演算法流程圖 20
圖6.計算最佳分配的循環過程 22
圖7. 飯店收益管理程序輸入與輸出關係流程圖 34
圖8. 飯店收益管理程序流程圖 34
圖9. 序優化為基礎的二層次演算法流程圖 37
圖10. 說明離散重組及中間重組 45
圖11. 方法比較所獲得的解的計算效率及品質結果圖 50

參考文獻
[1] M.- C. Fu, “Optimization for simulation: theory vs. practice,” INFORMS Journal on Computing, 2002, No. 14, pp. 192-215.
[2] J. Nocedal, and S.J. Wright, “Numerical Optimization,” Heidelberg, Germany: Springer-Verlag, 2000.
[3] J.C. Spall, “Introduction to stochastic search and optimization,” Hoboken, New Jersey: John Wiley & Sons, 2003.
[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.
[7] R.L. Haupt, and S.E. Haupt, “Practical genetic algorithms,” 2nd edition, Hoboken, New Jersey:John Wiley, 2004.
[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.
[9] A.R. Hedar, and M. Fukushima, “Tabu Search directed by direct search methods for nonlinear global optimization,” European Journal of Operational Research, 2006, Vol. 170, No. 2, pp. 329-349.
[10] M. Dorigo, V. Maniezzo, and A. Colorni, “The ant system: Optimizatoin by a colony of cooperating agents,” IEEE Transactions on Systems and Cybernetics - Part B, 1996, Vol. 26, No. 1, pp. 29-41.
[11] R.G. Reynolds, and W. Sverdlik, “Problem solving using cultural algorithms,” Proceedings of the First IEEE Conference on Evolutionary Computation, Orlando, FL, 1994, Vol. 2, pp. 645-650.
[12] R.C. Eberhart, and J. Kennedy, “A new optimizer using particle swarm theory. Proc,” Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan, 1995, pp. 39-43.
[13] J. Kennedy, and R.C. Eberhart, “Particle swarm optimization,” Proc. IEEE International Conference on Neural Networks, Perth, Australia, 1995, Vol. 4, pp. 1942-1948.
[14] D. Karaboga, “An Idea Based On Honey Bee Swarm for Numerical Optimization,” Technical Report-TR06, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005.
[15] Y.C. Jin, M. Olhofer, B. Sendhoff, “A framework for evolutionary optimization with approximate fitness functions,” IEEE Trans. Evol. Comput, 2002, Vol. 6, No. 5, pp. 481-494.
[16] M.K. Karakasis, K.C. Giannakoglou, “On the use of metamodel-assisted, multi-objective evolutionary algorithms,” Eng. Optimiz, 2006, Vol. 38, No. 8, pp. 941-957.
[17] D. Lim, Y.C. Jin, Y.S. Ong, B. Sendhoff, “Generalizing surrogate-assisted evolutionary computation,” IEEE Trans. Evol. Comput, 2010, Vol. 14, No. 3, pp. 329-355.
[18] I. Paenke, E. Branke, Y.C. Jin, “Efficient search for robust solutions by means of evolutionary algorithms and fitness approximation,” IEEE Trans. Evol. Comput, 2006, Vol. 10, No. 4, pp. 405-420.
[19] P.K.S. Nain, K. Deb, “Computationally effective search and optimization procedure using coarse-to-fine approximations,” In Proc. IEEE Congr. Evol. Comput., Canberra, Australia, 2003, pp. 2081-2088.
[20] M.D. Schmidt, H. Lipson, “Coevolution of fitness predictors,” IEEE Trans. Evol. Comput, 2008, Vol. 12, No. 6, pp. 736-749.
[21] Z. Zhou, Y.S. Ong, P.B. Nair, A.J. Keane, K.Y. Lum, “Combining global and local surrogate models to accelerate evolutionary optimization,” IEEE Trans. Syst. Man Cyber., C, Appl. Rev, 2007, Vol. 37, No. 1, pp. 66-76.
[22] Y. Tenne, S.W. Armfield, “A framework for memetic optimization using variable global and local surrogate models,” Soft Comput, 2009, Vol. 13,No. 8-9, pp. 781-793.
[23] F.G. Guimaraes, D.A. Lowther, J.A. Ramirez, “Analysis of approximation-based memetic algorithms for engineering optimization,” In: Y. Tenne and C.K. Goh (Eds.), Computational Intel. in Expensive Opti. Prob., ALO 2, Springer-Verlag, Berlin Heidelberg, 2010, pp. 163-191.
[24] C.K. Ting, C.C. Liao, “A memetic algorithm for extending wireless-sensor network lifetime,” Inf. Sci, 2010, Vol. 180, No. 24, pp. 4818-4833.
[25] W. Chen, Y.J. Shi, H.F. Teng, X.P. Lan, L.C. Hu, “An efficient hybrid algorithm for resource-constrained project scheduling,” Inf. Sci, Vol. 180, No. 6, pp. 1031-1039.
[26] Y.C. Jin, “A comprehensive survey of fitness approximation in evolutionary computation,” Soft Comput, 2005, Vol. 9, No. 1, pp. 3-12.
[27] Y.C. Ho, “An explanation of ordinal optimization: Soft computing for hard problems,” Information Sciences, 1999, Vol. 113, No. 3-4, pp. 169-192.
[28] T.W.E. Lau, and Y.C. Ho, “Universal alignment probability and subset selection for ordinal optimization,” Journal of Optimization Theory and Applications, 1997, Vol. 93, No. 3, pp. 455-489.
[29] Y.C. Ho, Q.C. Zhao, Q.S. Jia, “Ordinal optimization: Soft optimization for hard problems,” New York:Springer-Verlag, 2007.
[30] R. Ilin, R. Kozma, and P.J. Werbos, “Beyond feedforward models trained by backpropagation: a practical training tool for a more efficient universal approximator,” IEEE Trans. Neural Networks, 2008, Vol. 19, No. 6, pp. 929-937.
[31] Li Y.F., Ng S.H., Xie M., Goh T. N., “A systematic comparison of metamodeling techniques for simulation optimization in Decision Support Systems,” Applied Soft Computing, 2010, Vol. 10, No. 4, pp. 1257-1273.
[32] D.S. Moore, G.P. McCabe, and B. Craig, “Introduction to the Practice of Statistics, 7th ed.,” New York: W.H. Freeman and Company, 2011.
[33] D.E. Goldberg, K. Sastry, “Genetic Algorithms: The Design of Innovation, 2nd ed.,” Springer-Verlag, New York, 2010.
[34] C.H. Chen, D. He, M. Fu, L.H. Lee, “Efficient simulation budget allocation for selecting an optimal subset,” INFORMS J. Comput, 2008, Vol. 20, No. 4, pp. 579-595.
[35] C.H. Chen, J. Lin, E. Yucesan, S.E. Chich, “Simulation budget allocation for further enhancing the efficiency of ordinal optimization,” Discret. Event Dyn. Syst.-Theory Appl, 2000, Vol. 10, No. 3, pp. 251-270.
[36] S.Y. Lin, S.C. Horng, “Application of an ordinal optimization algorithm to the wafer testing process,” IEEE Trans. Syst., Man Cybern.-Part A, Syst. and Humans, 2006, Vol. 36, No 6, pp. 1229-1234.
[37] SimOpt.org, Booking limits at a hotel: Full. [Online]. (2009) Available: http://www.simopt.org/problems/integer/unconstrained.php
[38] C.H. Chen and L.H. Lee, “Stochastic Simulation Optimization: An Optimal Computing Budget Allocation,” NJ: World Scientific, 2010.
[39] H.G. Beyer, “The Theory of Evolution Strategies, Berlin,” Heidelberg: Springer-Verlag, 2001.