仿真优化：理论与应用综述

王龙飞; 侍乐媛

doi:10.3724/SP.J.1004.2013.01957

仿真优化：理论与应用综述

doi: 10.3724/SP.J.1004.2013.01957

1.
北京大学工学院工业工程与管理系北京 100871

基金项目:

Supported by National High Technology Research and Development Program of China (863 Program) (2012AA040909)

计量
- 文章访问数: 3229
- HTML全文浏览量: 130
- PDF下载量: 3733
- 被引次数: 0
出版历程
- 收稿日期: 2013-07-01
- 修回日期: 2013-08-29
- 刊出日期: 2013-11-20

Simulation Optimization： A Review on Theory and Applications

1.
Department of Industrial Engineering and Management, College of Engineering, Peking University, Beijing 100871, China

Funds:

Supported by National High Technology Research and Development Program of China (863 Program) (2012AA040909)

More Information

Corresponding author: SHI Le-Yuan

摘要

摘要: 对于现实中的复杂系统, 仿真优化是一种非常强大的分析和优化工具. 本文对仿真优化领域的相关理论与方法进行了介绍与回顾. 根据系统中决策变量的性质的不同(连续或者离散变量), 我们对仿真优化问题进行了分类. 而且我们对仿真优化领域中的重要技术进行了详细地讨论, 包括它们的原理、使用方法、优势和劣势以及应用等. 关于仿真优化领域未来的研究方向, 我们也进行了相关论述.
- 仿真优化 /
- 基于梯度的方法 /
- 排序与选择 /
- 最优计算预算分配 /
- 嵌套分割方法
Abstract: Simulation optimization is a very powerful tool in analysis and optimization of complex real systems. In this paper, a tutorial introduction and review of simulation optimization are given. The simulation optimization problems are classifed according to the underlying structure of decision variables (discrete or continuous). And some important techniques for simulation optimization are discussed in detail, including their principles, implementation procedures, advantages and disadvantages, and applications. The future research directions are also provided in this paper.
- Simulation optimization /
- gradient-based methods /
- ranking and selection /
- optimal computing budget allocation(OCBA) /
- nested partitions method

HTML全文

参考文献(100)

[1]	Tekin E, Sabuncuoglu I. Simulation optimization: a comprehensive review on theory and applications. IIE Transactions, 2004, 36(11): 1067-1081
[2]	Meketon M S. Optimization in simulation: a survey of recent results. In: Proceedings of the 1987 Winter Simulation Conference. Piscataway, NJ: IEEE, 1987. 58-67
[3]	Jacobson S H, Schruben L W. Techniques for simulation response optimization. Operations Research Letters, 1989, 8(1): 1-9
[4]	Azadivar F. A tutorial on simulation optimization. In: Proceedings of the 1992 Winter Simulation Conference. Piscataway, NJ: IEEE, 1992. 198-204
[5]	Fu M C. Optimization via simulation: a review. Annals of Operations Research, 1994, 53(1): 199-247
[6]	Carson Y, Maria A. Simulation optimization: methods and applications. In: Proceedings of the 1997 Winter Simulation Conference. Atlanta, Georgia: IEEE, 1997. 118-126
[7]	Andradóttir S. A review of simulation optimization techniques. In: Proceedings of the 1998 Winter Simulation Conference. Piscataway, NJ: IEEE, 1998. 151-158
[8]	Bowden R O, Hall J D. Simulation optimization research and development. In: Proceedings of the 1998 Winter Simulation Conference. Washington, DC: IEEE, 1998. 1693-1698
[9]	Azadivar F. Simulation optimization methodologies. In: Proceedings of the 1999 Winter Simulation Conference. Phoenix, AZ: IEEE, 1999. 93-100
[10]	Swisher J R, Hyden P D, Jacobson S H, Schruben L W. A survey of simulation optimization techniques and procedures. In: Proceedings of the 2000 Winter Simulation Conference. Orlando, FL: IEEE, 2000. 119-128
[11]	Law A M, McComas M G. Simulation-based optimization. In: Proceedings of the 2000 Winter Simulation Conference. San Diego, CA, USA: IEEE, 2000. 46-49
[12]	Fu M C. Simulation optimization. In: Proceedings of the 2001 Winter Simulation Conference. Arlington, VA, USA: IEEE, 2001. 53-61
[13]	Fu M C. Optimization for simulation: theory vs. practice. INFORMS Journal on Computing, 2002, 14(3): 192-215
[14]	Ólafsson S, Kim J. Simulation optimization. In: Proceedings of the 2002 Winter Simulation Conference. Piscataway, NJ: IEEE, 2002. 79-84
[15]	Law A M, McComas M G. Simulation optimization: simulation-based optimization. In: Proceedings of the 2002 Winter Simulation Conference. San Diego, CA, USA: IEEE, 2002. 41-44
[16]	April J, Glover F, Kelly J P, Laguna M. Practical introduction to simulation optimization. In: Proceedings of the 2003 Winter Simulation Conference. New Orleans, LA, USA: IEEE, 2003. 71-78
[17]	Fu M C, Glover F W, April J. Simulation optimization: a review, new developments, and applications. In: Proceedings of the 2005 Winter Simulation Conference. Orlando, FL: IEEE, 2005. 83-95
[18]	Fu M C, Chen C H, Shi L. Some topics for simulation optimization. In: Proceedings of the 2008 Winter Simulation Conference. Austin, TX: IEEE, 2008. 27-38
[19]	Ho Y C, Eyler M A, Chien T T. A gradient technique for general buffer storage design in a production line. International Journal of Production Research, 1979, 17(6): 557-580
[20]	Ho Y C, Cao X R. Perturbation Analysis of Discrete Event Dynamic Systems. Norwell, MA, USA: Kluwer Academic Pub, 1991
[21]	Heidelberger P. Limitations of Infinitesimal Perturbation Analysis. International Business Machine Research Report RC 11891, IBM Watson Research Labs, Yorktown Heights, NY, 1986
[22]	Glasserman P. Structural conditions for perturbation analysis derivative estimation: finite-time performance indices. Operations Research, 1991, 39(5): 724-738
[23]	L'Ecuyer P, Perron G. On the convergence rates of IPA and FDC derivative estimators. Operations Research, 1994, 42(4): 643-656
[24]	Dai L L. Perturbation analysis via coupling. IEEE Transactions on Automatic Control, 2000, 45(4): 614-628
[25]	Ho Y C, Suri R, Cao X R, Diehl G W, Dille J W, Zazanis M. Optimization of large multiclass (non-product-form) queueing networks using perturbation analysis. Large Scale Systems, 1984, 7: 165-180
[26]	Ho Y C. On the perturbation analysis of discrete-event dynamic systems. Journal of Optimization Theory and Applications, 1985, 46(4): 535-545
[27]	Ho Y C, Hu J Q. An infinitesimal perturbation analysis algorithm for a multiclass G/G/1 queue. Operations Research Letters, 1990, 9(1): 35-44
[28]	Chong E K P, Ramadge P J. Optimization of queues using an infinitesimal perturbation analysis-based stochastic algorithm with general update times. SIAM Journal on Control and Optimization, 1993, 31(3): 698-732
[29]	Fu M C, Hu J Q. Smoothed perturbation analysis derivative estimation for Markov chains. Operations Research Letters, 1994, 15(5): 241-251
[30]	Fu M C. Sample path derivatives for (s, S) inventory systems. Operations Research, 1994, 42(2): 351-364
[31]	Bashyam S, Fu M C. Application of perturbation analysis to a class of periodic review (s, S) inventory systems. Naval Research Logistics (NRL), 1994, 41(1): 47-80
[32]	Bashyam S, Fu M C. Optimization of (s, S) inventory systems with random lead times and a service level constraint. Management Science, 1998, 44(12-Part-2): S243-S256
[33]	Donohue K L, Spearman M L. Improving the design of stochastic production lines: an approach using perturbation analysis. International Journal of Production Research, 1993, 31(12): 2789-2806
[34]	Yan H, Yin G, Lou S X C. Using stochastic optimization to determine threshold values for the control of unreliable manufacturing systems. Journal of Optimization Theory and Applications, 1994, 83(3): 511-539
[35]	Liberopoulos G, Caramanis M. Infinitesimal perturbation analysis for second derivative estimation and design of manufacturing flow controllers. Journal of Optimization Theory and Applications, 1994, 81(2): 297-327
[36]	Cheng D W. On the design of a tandem queue with blocking: modeling, analysis, and gradient estimation. Naval Research Logistics (NRL), 1994, 41(6): 759-770
[37]	Heidergott B. Sensitivity analysis of a manufacturing workstation using perturbation analysis techniques. International Journal of Production Research, 1995, 33(3): 611-622
[38]	Brooks C A, Varaiya P. Using augmented infinitesimal perturbation analysis for capacity planning in intree ATM networks. Discrete Event Dynamic Systems, 1997, 7(4): 377-390
[39]	Heidergott B. Optimisation of a single-component maintenance system: a smoothed perturbation analysis approach. European Journal of Operational Research, 1999, 119(1): 181-190
[40]	Schruben L W, Cogliano V J. Simulation sensitivity analysis: a frequency domain approach. In: Proceedings of the 1981 Winter Simulation Conference. Piscataway, NJ: IEEE, 1981. 455-459
[41]	Jacobson S H, Morrice D, Schruben L W. The global simulation clock as the frequency domain experiment index. In: Proceedings of the 1988 Winter Simulation Conference, San Diego, CA, USA: IEEE, 1988. 558-563
[42]	Jacobson S H, Buss A H, Schruben L W. Driving frequency selection for frequency domain simulation experiments. Operations Research, 1991, 39(6): 917-924
[43]	Hazra M M, Morrice D J, Park S K. A simulation clock-based solution to the frequency domain experiment indexing problem. IIE Transactions, 1997, 29(9): 769-782
[44]	Glynn P W. Likelihood ratio gradient estimation: an overview. In: Proceedings of the 1987 Winter Simulation Conference. Piscataway, NJ: IEEE, 1987. 366-375
[45]	Glynn P W. Likelihood ratio gradient estimation for stochastic systems. Communications of the ACM, 1990, 33(10): 75 -84
[46]	Rubinstein R Y. Sensitivity analysis and performance extrapolation for computer simulation models. Operations Research, 1989, 37(1): 72-81
[47]	Rubinstein R Y. Optimization of computer simulation models with rare events. European Journal of Operational Research, 1997, 99(1): 89-112
[48]	Rubinstein R Y, Shapiro A. Discrete Event Systems: Sensitivity Analysis and Stochastic Optimization by the Score Function Method. New York: Wiley, 1993
[49]	Nakayama M K, Goyal A, Glynn P W. Likelihood ratio sensitivity analysis for Markovian models of highly dependable systems. Operations Research, 1994, 42(1): 137-157
[50]	Nakayama M K, Shahabuddin P. Likelihood ratio derivative estimation for finite-time performance measures in generalized semi-Markov processes. Management Science, 1998, 44(10): 1426-1441
[51]	Andradóttir, S. Optimization of the transient and steady-state behavior of discrete event systems. Management Science, 1996, 42(5): 717-737
[52]	Fu M C, Hu J Q, Nagi R. Comparison of gradient estimation techniques for queues with non-identical servers. Computers and Operations Research, 1995, 22(7): 715-729
[53]	Fu M C, Hu J Q. Efficient design and sensitivity analysis of control charts using Monte Carlo simulation. Management Science, 1999, 45(3): 395-413
[54]	Fu M C. 2006. Gradient estimation. Handbooks in Operations Research and Management Science: Simulation, Chapter 19 (Henderson S G, Nelson B L (editor)). Amsterdam: Elsevier. 575-616
[55]	Fu M C. What you should know about simulation and derivatives. Naval Research Logistics (NRL), 2008, 55(8): 723-736
[56]	Robbins H, Monro S. A stochastic approximation method. The Annals of Mathematical Statistics, 1951, 22(3): 400-407
[57]	Kiefer J, Wolfowitz J. Stochastic estimation of the maximum of a regression function. The Annals of Mathematical Statistics, 1952, 23(3): 462-466
[58]	Glynn P W. Stochastic approximation for Monte Carlo optimization. In: Proceedings of the 1986 Winter Simulation Conference. Piscataway, NJ: IEEE, 1986. 356-365
[59]	Kouritzin M A. On the convergence of linear stochastic approximation procedures. IEEE Transactions on Information Theory, 1996, 42(4): 1305-1309
[60]	Kulkarni S R, Horn C S. An alternative proof for convergence of stochastic approximation algorithms. IEEE Transactions on Automatic Control, 1996, 41(3): 419-424
[61]	L'Ecuyer P, Yin G. Budget-dependent convergence rate of stochastic approximation. SIAM Journal on Optimization, 1998, 8(1): 217-247
[62]	Andradóttir S. A stochastic approximation algorithm with varying bounds. Operations Research, 1995, 43(6): 1037-1048
[63]	Kleinman N L, Spall J C, Naiman D Q. Simulation-based optimization with stochastic approximation using common random numbers. Management Science, 1999, 45(11): 1570-1578
[64]	Fu M C, Ho Y C. Using perturbation analysis for gradient estimation, averaging and updating in a stochastic approximation algorithm. In: Proceedings of the 1988 Winter Simulation Conference. San Diego, CA, USA, 1988. 509-517
[65]	Fu M C. Convergence of a stochastic approximation algorithm for the GI/G/1 queue using infinitesimal perturbation analysis. Journal of Optimization Theory and Applications, 1990, 65(1): 149-160
[66]	L'Ecuyer P, Glynn P W. Stochastic optimization by simulation: convergence proofs for the GI/G/1 queue in steady-state. Management Science, 1994, 40(11): 1562-1578
[67]	Hill S D, Fu M C. Optimizing discrete event systems with the simultaneous perturbation stochastic approximation algorithm. In: Proceedings of the 33rd IEEE Conference on Decision and Control. Lake Buena Vista, FL: IEEE, 1994. 2631-2632
[68]	Fu M C, Hill S D. Optimization of discrete event systems via simultaneous perturbation stochastic approximation. IIE Transactions, 1997, 29(3): 233-243
[69]	Fu M, Hu J Q. Conditional Monte Carlo: Gradient Estimation and Optimization Applications. Boston: Kluwer Academic Publishers, 1997
[70]	Chong E K P, Ramadge P J. Optimal load sharing in soft real-time systems using likelihood ratios. Journal of Optimization Theory and Applications, 1994, 82(1): 23-48
[71]	Andradöttir S. A scaled stochastic approximation algorithm. Management Science, 1996, 42(4): 475-498
[72]	Tang Q Y, Chen H F, Han Z J. Convergence rates of Perturbation-Analysis-Robbins-Monro-Single-Run algorithms for single server queues. IEEE Transactions on Automatic Control, 1997, 42(10): 1442-1447
[73]	Tang Q Y, L'Ecuyer P, Chen H F. Asymptotic efficiency of perturbation-analysis-based stochastic approximation with averaging. SIAM Journal on Control and Optimization, 1999, 37(6): 1822-1847
[74]	Tang Q Y, Chen H F. Central limit theorems for stochastic optimization algorithms using infinitesimal perturbation analysis. Discrete Event Dynamic Systems, 2000, 10(1-2): 5-32
[75]	Hasan C N, Spearman M L. Optimal material release times in stochastic production environments. International Journal of Production Research, 1999, 37(6): 1201-1216
[76]	Andradóttir S. A new algorithm for stochastic optimization. In: Proceedings of the 1990 Winter Simulation Conference. New Orleans, LA: IEEE, 1986. 364-366
[77]	Andradóttir S. A projected stochastic approximation algorithm. In: Proceedings of the 1991 Winter Simulation Conference. Phoenix, AZ: IEEE, 1991. 954-957
[78]	Yakowitz S. A globally convergent stochastic approximation. SIAM Journal on Control and Optimization, 1993, 31(1): 30 -40
[79]	Kushner H J, Yin G. Stochastic Approximation and Recursive Algorithms and Applications (2nd edition). New York: Springer-Verlag, 2003
[80]	Gurkan G, Yonca-Ozge A, Robinson T M. Sample-path optimization in simulation. In: Proceedings of the 1994 Winter Simulation Conference. Lake Buena Vista, FL, USA: IEEE, 1994. 247-254
[81]	Homem-de-Mello T, Shapiro A, Spearman M L. Finding optimal material release times using simulation-based optimization. Management Science, 1999, 45(1): 86-102
[82]	Kleywegt A J, Shapiro A, Homem-de-Mello T. The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 2002, 12(2): 479-502
[83]	Chen H F, Schmeiser B W. Retrospective approximation algorithms for stochastic root finding. In: Proceedings of the 1994 Winter Simulation Conference. Lake Buena Vista, FL, USA: IEEE, 1994. 255-261
[84]	Shapiro A. Simulation based optimization. In: Proceedings of the 1996 Winter Simulation Conference. Washington, DC: IEEE, 1996. 332-336
[85]	Box G E P, Wilson K B. On the experimental attainment of optimum conditions. Journal of the Royal Statistical Society. Series B (Methodological), 1951, 13(1): 1-45
[86]	Box G E P. The exploration and exploitation of response surfaces: some general considerations and examples. Biometrics, 1954, 10(1): 16-60
[87]	Biles W E. A gradient-regression search procedure for simulation experimentation. In: Proceedings of the 1974 Winter Simulation Conference. Piscataway, NJ: IEEE, 1974. 491-497
[88]	Smith D E. Automatic optimum-seeking program for digital simulation. Simulation, 1976, 27(1): 27-31
[89]	Daughety A F, Turnquist M A. Simulation optimization using response surfaces based on spline approximations. In: Proceedings of the 1978 Winter Simulation Conference. Piscataway, NJ: IEEE, 1978. 183-193
[90]	Wilson J R. Future directions in response surface methodology for simulation. In: Proceedings of the 1987 Winter Simulation Conference. Piscataway, NJ: IEEE, 1987. 378-381
[91]	Myers R H, Khuri A I, Carter W H Jr. Response surface methodology: 1966-1988. Technometrics, 1989, 31(2): 137-157
[92]	Safizadeh M H, Signorile R. Optimization of simulation via quasi-Newton methods. ORSA Journal on Computing, 1994, 6(4): 398-408
[93]	Joshi S, Sherali H D, Tew J D. An enhanced response surface methodology (RSM) algorithm using gradient deflection and second-order search strategies. Computers and Operations Research, 1998, 25(7-8): 531-541
[94]	Kleijnen J P C. 1998. Experimental design for sensitivity analysis, optimization, and validation of simulation models. Handbook of Simulation, Chapter 6 (Banks J (editor)). New York: Wiley. 173-223
[95]	Kleijnen J P C. Simulation and optimization in production planning: a case study. Decision Support Systems, 1993, 9(3): 269-280
[96]	Kleijnen J P C. Sensitivity analysis and optimization of system dynamics models: regression analysis and statistical design of experiments. System Dynamics Review, 1995, 11(4): 275-288
[97]	Shang J S, Tadikamalla P R. Output maximization of a CIM system: simulation and statistical approach. International Journal of Production Research, 1993, 31(1): 19-41
[98]	Barton R R, Meckesheimer M. 2006. Metamodelbased simulation optimization. Handbooks in Operations Research and Management Science: Simulation, Chapter 18 (Henderson S G, Nelson B L (editor)). Amsterdam: Elsevier. 535-574
[99]	Kleijnen J P C. Design and Analysis of Simulation Experiments. New York: Springer, 2007
[100]	Dudewicz E J, Dalal S R. Allocation of observations in ranking and selection with unequal variances. Sankhyã: The Indian Journal of Statistics, Series B, 1975, 37(1): 28-78