Hybrid Probabilistic Search Methods for Simulation Optimization

Document Type : Research Paper

Author

Department of Industrial and Manufacturing Systems Engineering, Iowa State University, Black Engineering, Ames, IA 50011, USA

Abstract

Discrete-event simulation based optimization is the process of finding the optimum design of a stochastic system when the performance measure(s) could only be estimated via simulation. Randomness in simulation outputs often challenges the correct selection of the optimum. We propose an algorithm that merges Ranking and Selection procedures with a large class of random search methods for continuous simulation optimization problems. Under a mild assumption, we prove the convergence of the algorithm in probability to a global optimum. The new algorithm addresses the noise in simulation outputs while benefits the proven efficiency of random search methods.

Keywords

Main Subjects


[1] Andradóttir S. (2006), An overview of simulation optimization via random search. In Henderson and
Nelson (eds.); Handbooks in operations research and management science 13; 617 – 632, Elsevier.
[2] Andradóttir S. (1998), A review of simulation optimization techniques. In D.J. Medeiros, E.F.Watson,
J.S. Carson, and M.S. Manivannan (eds.); Proceedings of the 1998 Winter Simulation Conference;
151-158.
[3] Azadivar F. (1999), Simulation optimization methodologies; Proceedings of the 1999 Winter
Simulation Conference; 93-100.
[4] Barton R.R., Meckesheimer M. (2006), Metamodel-based simulation optimization, In Henderson and
Nelson (eds.), Handbooks in operations research and management science 13; 617 – 632, Elsevier.
[5] 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.
[6] Bechhofer R.E., Santner T.J., and Goldsman D.M. (1995), Design and analysis of experiments for
statistical selection screening and multiple comparisons; John Wiley & Sons, Inc, New York.
[7] Benson K.C., Goldsman D., and Pritchett A.R. (2006), Ranking and election procedures for
simulation, proceedings of the 2006 winter simulation conference; 179-185.
[8] Boesel J, Nelson B.L., and Kim S-H. (2003), Using ranking and selection to “clean up” after
simulation optimization; Operations Research 51(5); 814–825.
[9] Chick S.E., Inoue K. (2001a), New two-stage and sequential procedures for selecting the best
simulated system; Operations Research 49(5); 732-743.
[10] Chick S.E., Inoue K. (2001b), New procedures for identifying the best simulated system using
common random numbers; Management Science 47(8); 1133–1149.
[11] Deng G., Ferris M.C. (2009), Variable-number sample-path optimization, Mathematical Programming
117(1-2); 81-109.
[12] Fu M.C. (2006), Gradient estimation. In Henderson and Nelson (eds.), Handbook in operations
research and management science 13; 575-616, Elsevier.
[13] Fu M.C., Glover F.W., and April J. (2005), Simulation optimization: a review, new developments, and
applications; Proceedings of the 2005 Winter Simulation Conference; 83-95.
[14] Glover F. (1997), A template for scatter search and path relinking; Lecture Notes in Computer Science
1997, edited by Hao J.K., Lutton E., Ronald E., Schoenauer M., and Snyers D.; 1363: 1-53.
[15] Glover, F. (1989), Tabu search – part I; ORSA Journal on Computing 1; 190-206.
[16] Glover, F. (1990), Tabu search –part II; ORSA Journal on Computing 2; 4-32.
[17] Goldsman D., Nelson B.L. (1998), Comparing systems via simulation. In Banks (ed), Handbooks of
simulation (13); John Wiley and Sons.
[18] Gong W.B., Ho Y.C., and Zhai W. (1999), Stochastic comparison algorithm for discrete optimization
with estimations; SIAM Journal on Optimization 10(2); 384-404.
[19] Gosavi A. (2003), Simulation-based optimization: parametric optimization techniques and
reinforcement learning; Kluwer Academic Publishers.
[20] Holland J.H. (1992), Genetic algorithms; Scientific American July 1992; 66-72.
[21] Kabirian A. (2006), A review of current methodologies and developing a new heuristic method of
simulation optimization; Unpublished Master of Science Dissertation, Under supervision of Professor
Hashem Mahlooji Jan. 2006; Sharif University of Technology, Tehran, Iran.
[22] Kabirian A., Hemmati M.R. (2007), A strategic planning model for natural gas transmission networks,
Energy Policy 35(11); 5656-5670, Elsevier.
[23] Kabirian A., Olafsson S. (2007a), Allocation of simulation runs for simulation optimization;
Proceedings of the 2007 Winter Simulation Conference; PhD Colloquium & Poster Session,
Washington D.C., December 2007.
[24] Kabirian A., Olafsson S. (2007b), Simulation based optimization via golden region search; Working
Paper; Department of Industrial and Manufacturing Systems Engineering, Iowa State University,
Ames, IA, USA.
[25] Kabirian A., Olafsson S. (2007c), Multiresponse golden partition search under noisy constraints;
Working Paper, Department of Industrial and Manufacturing Systems Engineering; Iowa State
University, Ames, IA, USA.
[26] Kabirian A., Olafsson S. (2008), Selection of the best with multiple stochastic constraints; Working
Paper, Department of Industrial and Manufacturing Systems Engineering; Iowa State University,
Ames, IA, USA.
[27] Kiefer J., Wolfoxitz J. (1952), Stochastic estimation of the maximum of a regression function. Annals
of Mathematical Statistics 23; 462-466.
[28] Kim S., Nelson B.L. (2006), Selecting the best system. In Henderson and Nelson (eds.), Handbooks in
operations research and management science 13; 501-534, Elsevier.
[29] Krikpatrick S., Gelatt Jr.C.D., Vecchi M.P. (1983), Optimization by simulated annealing; Science 220;
671-680.
[30] Nelson B.L., Goldsman L.D. (2001), Comparison with a standard in simulation experiments;
Management Science 47; 449-463.
[31] Nelson B.L., Swann J., Goldsman D., and Song W. (2001), Simple procedures for selecting the best
simulated system when the number of alternatives is large; Operations Research 49; 950–963.
[32] Olafsson S., Kim J. (2002), Simulation optimization; Proceedings of the 2002 Winter Simulation
Conference; 1931-1936.
[33] Olafsson S. (2006), Metaheuristics. In Henderson and Nelson (eds.); Handbook in operations research
and management science 13; 633–654, Elsevier.
[34] Robins H., Monro S. (1951), A stochastic approximation method; Annals of Mathematical Statistics
22; 400-407.
[35] Robinson S.M. (1996), Analysis of sample-path optimization; Mathematics of Operations Research;
21 (3); 513-528.
[36] Shapiro A. (1996), Simulation based optimization, Proceedings of the 1996 Winter Simulation
Conference, ed. J.M. Charnes, D.J. Morrice, D.T. Brunner, and J.J.Swain; 332-336.
[37] Yan D., Mukai H. (1992), Stochastic discrete optimization; SIAM Journal on Control and
Optimization 30; 594-612.