模擬最佳化(Optimization via Simulation; OvS)是從許多不同的模擬系統中，找出績效表現最佳的系統，藉以分析現實生活中存在的複雜性隨機問題。其中，排序與選擇程序(Ranking and Selection; R&S)即是從有限且少量的模擬系統中，在信心水準之下，找出期望績效表現最佳的系統。從過去的研究中發現，排序與選擇程序的研究主要追求隨機目標最佳化，很少考量隨機限制式問題。因此，Andrad´ottir and Kim (2010)發展可行性判定程序(Feasibility Determination Procedure; FDP)，在統計的理論基礎下，找出滿足隨機限制式的可行或接近可行的系統。然而，假若系統或隨機限制式數量過多，將造成實驗所需之抽樣數量提高，導致抽樣成本大幅增加。
有鑒於此，Boesel and Nelson(2003)提出隨機基因演算法(Stochastic Genetic Algorithm; SGA)，用以處理系統數量龐大下之隨機目標問題。本研究將此一問題延伸至具有隨機目標函數與限制式問題，發展一全新隨機限制化基因演算法(Stochastic Constrained Genetic Algorithm; SCGA)進行求解，並且證明當實驗抽樣數量足夠多時，其最佳解滿足全域收斂性。由於基因演算法其收斂速率緩慢，本研究亦提出另一啟發式基因演算法，透過分群程序與限制式處理技巧相結合，使得在時間的限制下，能夠以系統化的方式找出最佳近似解，但沒辦法保證其全域收斂性。

Optimization via simulation (OvS) is the process of optimizing the expected performance of a discrete event, stochastic system through computer simulation. Ranking and Selection (R&S) is one branch of OvS, which mainly focuses on finding the best among a finite number of simulated alternatives with respect to a expected performance measure. In most relevant literature of R&S, however, only one performance measure is considered and very little work has been done in handling stochastic constraints. Andradottir and Kim (2010) present a feasibility determination procedure that determines the feasibility of candidate systems in the presence of single stochastic constraint (secondary performance measure), and finds the best feasible system based on a primary performance measure. However, if the number of stochastic constraints or simulated systems are too large, the feasibility determination procedure will become inefficient (i.e., incurring prohibitive sampling cost).
To solve a problem with a stochastic objective function and huge solution space, Boesel and Nelson (2003) present Stochastic Genetic Algorithm (SGA) to control statistical error within a heuristic search procedure. We extend their procedure to be able to solve the problem with single stochastic objective along with single stochastic constraint. We provide an algorithm called Stochastic Constrained Genetic Algorithm (SCGA), which guarantees global convergence as the simulation effort goes to infinity. Due to the disadvantage of slow convergence rate that is inherent in GA, we provide another heuristic algorithm which combines grouping procedure and constraint handling technique to be able to find near-optimal solution in a reasonable amount of time, though it cannot guarantee to attain global convergence.

Alrefaei, M., Andrad´ottir, S., 1999. A simulated annealing algorithm with constant temperature for discrete stochastic optimization. Management Science 45, 748-764.

Alrefaei, M., Andrad´ottir, S., 1999. A modification of the stochastic ruler method for discrete stochastic optimization. European Journal of Operation Research 133, 160-182.

Andrad´ottir, S., 1995. A method for discrete stochastic optimization. Management Science 41, 1946-1961.

Andrad´ottir, S., Kim, S. H., 2010. Fully sequential procedures for comparing con¬strained systems via simulation. Naval Research Logistics 57, 403-421.

Atlason, Epelman, J. M., Henderson, S. G., 2004. Call center staffing with simulation and cutting plane methods. Annals of Operation Research 127, 333-358.

Avriel, M., 1976. Nonlinear programming: Analysis and Methods. Englewood Cliffs.

N.J. Baker, J. E., 1987. Reducing bias and inefficiency in the selection algorithm. In Proceedings of the 2nd International Conference on Genetic Algorithms. 14-21.

Barton, R. R., Meckesheimer, M., 2006. Metamodel-Based simulation optimization. Handbook in OR.

Batur, D., Kim, S. H., 2008. Finding feasible systems in the presence of constraints on multiple performance measures. ACM Transactions on Modeling and Computer Simulation 20, Article 13.

Bazaraa, M. S., H.D. Sherali, C.M. Shetty, 2006. Nonlinear programming :theory and algorithms. John Wiley and Sons, New York.

Bechhofer, R. E., 1954. A single-sample multiple decision procedure for ranking means of normal populations with known variances. Annals of Mathematical Statistics 25, 16-39.

Boesel, J. 1999. Search and selection for large-scale stochastic optimization. Doctor dissertation, Department of IEMS, Northwestern University, Evanston, IL.

Boesel, J., Nelson, B. L., Ishii, N., 2003. A framework for simulation-optimization software. IIE Transactions 35, 221-230.

Boesel, J., Nelson, B. L., Kim S.-H., 2003. Using ranking and selection to ”clean up” after simulation optimization. Operations Research 51, 814-825.

Cezik, M. T., L'Ecuyer, P., 2008. Staffing multiskill call centers via linear programming and simulation. Operations Research 54, 310-323.

Chen, S. Y., Dajan , S. D., 1998. Improving the efficiency of genetic algorithms for frame designs. Engineering Optimization 30, 281-307.

Coello, C. A. C., 2002. Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: A survey of the state of the art. Computer Methods in Applied Mechanics and Engineering 191, 1245-1287.

De Jong, K. A., 1975. An Analysis of the Behavior of a Class of Genetic Adaptive Systems. Doctoral Dissertation, The University of Michigan.

Fu, M. C., 2002. Optimization for simulation: Theory vs. Practice. INFORMS Journal on Computing 14, 192-215.

Gong, W. B., Ho, Y. C., Zhai, W., 1999. Stochastic comparison algorithm for discrete optimization with estimation. SIAM Journal on Optimization 10, 384-
404.

Hadj-Alouane, A. B., Bean, J. C., 1997. A genetic algorithm for the multiple-choice integer program, Operations Research 45, 92-101.

Herrera, F., Lozano, M., Verdegay, J. L., 1998. A learning process for fuzzy control rules using genetic algorithms. Fuzzy Sets and Systems 100, 143-158.

Homaifar, A., Lai, S. H. Y., Qi, X., 1994. Constrained optimization via genetic algorithms. Simulation 62, 242-254.

Hong, L. J., Nelson, B. L., 2006. Discrete optimization via simulation using COMPASS. Operations Research 54, 115-129.

Hong, L. J., Nelson, B. L., 2009. A Brief Introduction to Optimization via Simulation. Winter Simulation Conference Proceedings, 75-85.

Kim, S. H., Nelson, B. L., 2001. A fully sequential procedure for indifference-zone selection in simulation, ACM Transactions on Modeling and Computer Simulation 11, 251-273.

Kim, S. H., Nelson, B. L., 2005. Selecting the best system,Chapter 17 in Elsevier Handbooks in Operations Research and Management Science: Simulation, Elsevier.

Kim, S. H., 2005. Comparison with a standard via fully sequential procedures, ACM Transactions on Modeling and Computer Simulation 15, 1-20.

Lee, L. H., Lee, C. U., Tan Y. P., 2007. A multi-objective genetic algorithm for robust flight scheduling using simulation, European Journal of Operation Research 177, 1948-1968.

Michalewicz, Z., 1995. Genetic algorithms, numerical optimization and constraints. Proceedings of the Sixth International Conference on Genetic Algorithms, 151-
158.

Michalewicz, Z., 1996. Genetic Algorithms + Data Structures = Evolution Algorithms 3rd Ed. Springer, Berlin.

Nelson, B. L., Swann, J., Goldsman, D., Song, W., 2001. Simple procedures for selecting the best simulated system when the number of alternatives is large. Operations Research 49, 950-963.

Olafsson, S., 2006. Metaheuristics. Handbooks in Operations Research and Management Science VII, 633-654.

Pichitlamken, J., Nelson, B. L., 2003. A combined procedure for optimization via simulation. ACM Transactions on Modeling and Computer Simulation 13, 155-179.

Pichitlamken, J., Nelson, B. L., 2006. A sequential procedure for neighborhood selection-of-the-best in optimization via simulation, European Journal of Operation Research 173, 283-298.

Ray, T., Kang, S. K., 2000. An evolutionary algorithm for constrained optimization, in: D. Whitley, D. Goldberg, E. Cant´u-(GECCP’2000), Morgan Kaufmann, San Francisco, CA, 771-777.

Rinott, Y., 1978. On two-stage selection procedures and related probability-inequalities. Communications in Statistics -Theory and Methods 7, 799-811.

Runarsson, T. P., Yao, X., 2000. Stochastic ranking for constrained evolutionary optimization. IEEE Transactions on Evolutionary Computation 4, 284-294.

Shi, L., S. Olafsson., 2000. Nested partitions method for stochastic optimization. Methodology and Computing in Applied Probability 2, 271-291.

Xu, J., Hong, L. J., Nelson, B. L., 2010. Industrial strength COMPASS: A comprehensive algorithm and software for optimization via simulation. ACM Transactions on Modeling and Computer Simulation 20, 1-29.