Abstract
Model-based algorithms are a class of stochastic search methods that have successfully addressed some hard deterministic optimization problems. However, their application to simulation optimization is relatively undeveloped. This chapter reviews the basic structure of model-based algorithms, describes some recently developed frameworks and approaches to the design and analysis of a class of model-based algorithms, and discusses their extensions to simulation optimization.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
G. Allon, D. P. Kroese, T. Raviv, and R. Y. Rubinstein. Application of the cross-entropy method to the buffer allocation problem in a simulation-based environment. Annals of Operations Research, 134:137–151, 2005.
S. Andradóttir. An overview of simulation optimization with random search. In S. G. Henderson and B. L. Nelson, editors, Handbooks in Operations Research and Management Science: Simulation. Elsevier, 2006.
R. R. Barton and M. Meckesheimer. Metamodel-based simulation optimization. In S. G. Henderson and B. L. Nelson, editors, Handbooks in Operations Research and Management Science: Simulation. Elsevier, 2006.
M. Benaim. A dynamical system approach to stochastic approximations. SIAM Journal on Control and Optimization, 34:437–472, 1996.
V. S. Borkar. Stochastic approximation: a dynamical systems viewpoint. Cambridge University Press; New Delhi: Hindustan Book Agency, 2008.
Y. Cai, X. Sun, and P. Jia. Probabilistic modeling for continuous eda with boltzmann selection and kullback-leibeler divergence. In Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, pages 389–396, 2006.
A. Costa, O. D. Jones, and D. Kroese. Convergence properties of the cross-entropy method for discrete optimization. Operations Research Letters, 35(5):573–580, 2007.
M. Dorigo and L. M. Gambardella. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1:53–66, 1997.
F. W. Glover. Tabu search: A tutorial. Interfaces, 20:74–94, 1990.
D. E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Kluwer Academic Publishers, Boston, MA, 1989.
W. B. Gong, Y. C. Ho, and W. Zhai. Stochastic comparison algorithm for discrete optimization with estimation. SIAM Journal on Optimization, 10:384–404, 1999.
W. J. Gutjahr. A converging aco algorithm for stochastic combinatorial optimization. In Proceedings of SAGA 2003 Stochastic Algorithms: Foundations and Applications, pages 10–25, 2003.
T. Homem-de-Mello. A study on the cross-entropy method for rare-event probability estimation. INFORMS Journal on Computing, 19:381–394, 2007.
T. Homem-de-Mello. On rates of convergence for stochastic optimization problems under non-independent and identically distributed sampling. SIAM Journal on Optimization, 19:524–551, 2008.
L. J. Hong and B. L. Nelson. Discrete optimization via simulation using compass. Operations Research, 54:115–129, 2006.
J. Hu and H. S. Chang. An approximate stochastic annealing algorithm for finite horizon markov decision processes. In Proceedings of the 49th IEEE Conference on Decision and Control, pages 5338–5343, 2010.
J. Hu, H. S. Chang, M. C. Fu, and S. I. Marcus. Dynamic sample budget allocation in model-based optimization. Journal of Global Optimization, 50:575–596, 2011.
J. Hu, M. C. Fu, and S. I. Marcus. A model reference adaptive search method for global optimization. Operations Research, 55:549–568, 2007.
J. Hu, M. C. Fu, and S. I. Marcus. A model reference adaptive search method for stochastic global optimization. Communications in Information and Systems, 8:245–276, 2008.
J. Hu and P. Hu. On the performance of the cross-entropy method. In Proceedings of the 2009 Winter Simulation Conference, pages 459–468. IEEE, Piscataway, NJ, 2009.
J. Hu and P. Hu. Annealing adaptive search, cross-entropy, and stochastic approximation in global optimization. Naval Research Logistics, 58:457–477, 2011.
J. Hu, P. Hu, and H. S. Chang. A stochastic approximation framework for a class of randomized optimization algorithms. IEEE Transactions on Automatic Control, 57:165–178, 2012.
J. Hu and C. Wang. Discrete optimization via approximate annealing adaptive search with stochastic averaging. In Proceedings of the 2011 Winter Simulation Conference, pages 4206–4216. IEEE, Piscataway, NJ, 2011.
J. Hu, E. Zhou, and Q. Fan. Model-based annealing random search with stochastic averaging. ACM Transactions on Modeling and Computer Simulation, forthcoming, 2014.
J. Kennedy and R. Eberhart. Particle swarm optimization. In Proceedings of IEEE International Conference on Neural Networks, pages 1942–1948, 1995.
S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220:671–680, 1983.
A. Kleywegt, A. Shapiro, and T. Homem-de-Mello. The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 12:479–502, 2001.
H. J. Kushner and D. S. Clark. Stochastic Approximation Methods for Constrained and Unconstrained Systems and Applications. Springer-Verlag, New York, 1978.
H. J. Kushner and G. G. Yin. Stochastic Approximation Algorithms and Applications. Springer-Verlag, New York, 1997.
P. Larrañaga and J. A. Lozano. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer Academic Publisher, Boston, MA, 2002.
S. Mannor, R. Y. Rubinstein, and Y. Gat. The cross-entropy method for fast policy search. In Proceedings of the 20th International Conference on Machine Learning, pages 512–519, 2003.
H. E. Romeijn and R. L. Smith. Simulated annealing and adaptive search in global optimization. Probability in the Engineering and Informational Sciences, 8:571–590, 1994.
R. Y. Rubinstein. Optimization of computer simulation models with rare events. European Journal of Operational Research, 99:89–112, 1997.
R. Y. Rubinstein. Combinatorial optimization, ants and rare events. In S. Uryasev and P. M. Pardalos, editors, Stochastic Optimization: Algorithms and Applications, pages 304–358, 2001.
R. Y. Rubinstein and D. P. Kroese. The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation, and Machine Learning. Springer, New York, 2004.
L. Shi and S. Ólafsson. Nested partitions method for global optimization. Operations Research, 48:390–400, 2000.
D. H. Wolpert. Finding bounded rational equilibria part i: Iterative focusing. In T. Vincent, editor, Proceedings of the Eleventh International Symposium on Dynamic Games and Applications, 2004.
D. Yan and H. Mukai. Stochastic discrete optimization. SIAM Journal on Control and Optimization, 30:594–612, 1992.
Z. B. Zabinsky. Stochastic Adaptive Search for Global Optimization. Kluwer Academic Publishers, 2003.
Z. B. Zabinsky, R. L. Smith, J. F. McDonald, H. E. Romeijn, and D. E. Kaufman. Improving hit-and-run for global optimization. Journal of Global Optimization, 3:171–192, 1993.
Q. Zhang and H. Mühlenbein. On the convergence of a class of estimation of distribution algorithm. IEEE Transactions on Evolutionary Computation, 8:127–136, 2004.
E. Zhou, M. C. Fu, and S. I. Marcus. A particle filtering framework for randomized optimization algorithms. In Proceedings of the 2008 Winter Simulation Conference, pages 647–654. IEEE, Piscataway, NJ, 2008.
E. Zhou and J. Hu. Gradient guided adaptive stochastic search. IEEE Transactions on Automatic Control, 59:1818–1832, 2014.
M. Zlochin, M. Birattari, N. Meuleau, and M. Dorigo. Model-based search for combinatorial optimization: A critical survey. Annals of Operations Research, 131:373–395, 2004.
Acknowledgements
This work was supported in part by the National Science Foundation (NSF) under Grant CMMI-1130761 and by the Air Force Office of Scientific Research (AFOSR) under Grant FA95501010340.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer Science+Business Media New York
About this chapter
Cite this chapter
Hu, J. (2015). Model-Based Stochastic Search Methods. In: Fu, M. (eds) Handbook of Simulation Optimization. International Series in Operations Research & Management Science, vol 216. Springer, New York, NY. https://doi.org/10.1007/978-1-4939-1384-8_12
Download citation
DOI: https://doi.org/10.1007/978-1-4939-1384-8_12
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4939-1383-1
Online ISBN: 978-1-4939-1384-8
eBook Packages: Business and EconomicsBusiness and Management (R0)