基于模拟预算最优分配方法的随机仿真优化问题研究
详细信息    本馆镜像全文|  推荐本文 |  |   获取CNKI官网全文
摘要
随机仿真优化问题研究基于仿真的目标优化问题,即用模型仿真的结果来估计实际系统的性能,然后通过优化算法来得到最优解或满意解的过程。随着问题的复杂程度加深,仿真计算量增加的速度十分惊人。如何大幅降低仿真计算量是这类问题的关键所在,因此,探讨研究随机仿真优化问题具有重要的理论意义和应用价值,本文基于模拟预算最优分配算法的思想,对常见的随机仿真优化问题和带随机约束的仿真优化最优子集选择问题进行了一系列的研究。
     论文在阅读了大量文献的基础上,提出了一种基于模拟预算最优分配的思想来求解随机仿真优化问题。利用数理统计中的Bonferroni不等式估计正确选择的概率,通过对仿真资源的合理分配,使得最优方案被正确选择的概率最大化,从而大大提高了仿真的运行效率。最后仿真试验说明了该方法的高效性。进一步,论文还提出了一种基于改进的模拟预算最优分配的思想来求解带随机约束的仿真优化最优子集选择问题。通过智能控制每个方案的仿真次数,证明了在有限的计算量下,从一系列方案中可选出最优子方案,使得正确选择最优子方案的概率最大化。实践证明,该算法具有普遍性,它可与基于仿真的全局优化算法相结合,来进一步提高解的搜索效率。最后,对随机仿真优化的应用进行了探讨,给出一个与启发式算法的集成化框架,提供了两个应用随机仿真优化方法求解的简单例子并给出了应用模拟预算最优分配方法求解的数值实验。
Stochastic simulation optimization (often shortened as simulation optimization) studies the optimization problem of simulation-based objectives, which using the result of the simulation model to estimate the actual performance of the system, and then an optimal or satisfactory solution is found by using the optimization algorithm. With the complexity of the problem at a deeper level, the amount of the computing in simulation is amazing. How to significantly reduce the amount of computing in simulation is the key to such problems, therefore, explore the problem of stochastic simulation optimization has important theoretical significance and application value. This paper introduced an optimal allocation algorithm based on optimal computing budget allocation and conducted a series of studies on the problem of selecting the best design from a discrete numbers of alternatives and the problem of selecting an optimal subset in the presence of stochastic constraints.
     On the basis of reading a large number of literatures, this paper proposes an idea based on computing budget allocation to solve the stochastic simulation optimization problem. A common approximation procedure used in simulation and statistics literature is adopted to estimates the probability of correct selection, which is based on the Bonferroni inequality. An asymptotic allocation rule is given to maximize the probability of correct selection through rational allocation of simulation resource, and thus greatly improving the efficiency of allocating simulation replications among competing designs. Finally, the simulation result shows the efficiency of the algorithm. Further, this paper provides an alternative approach based on the Optimal Computing Budget Allocation to tackle the problem of selecting an optimal subset in the presence of stochastic constraints. In the limited amount of computation, the top-m out of k designs based on simulated output can be identified and the probability of correct selection can be maximized by intelligent control simulation times of each design. Practice has proved that the algorithm is universal; it can be combined with simulation-based global optimization algorithm to further improve the search efficiency. Finally, the applications of stochastic simulation optimization in supply chain and logistics are discussed, a framework integrated with heuristic algorithm is given, and two examples of stochastic simulation optimization are provided.
引文
[1]Chen C H, Lee L H. Stochastic Simulation Optimization: An Optimal Computing Budget Allocation. Singapore: World Scientific Publishing Company, 2010
    [2]Boesel J, Bowden J R, Glover F, et al. Future of simulation optimization. Proceedings of Winter Simulation Conference, Institute of Electrical and Electronics Engineers, Piscataway, New Jersey, 2001, 1466~1469
    [3]Azadivar F. Simulation optimization methodologies. Proceedings of Winter Simulation Conference. Phoenix, 1999:93~100
    [4]金淳,于越,赵璐,基于仿真优化的集装箱港口大门作业调度研究,系统仿真学报,2008,20(8):1998~2002
    [5]郑为中,史其信,基于微观交通仿真的动态交通管理优化问题研究,系统工程理论与实践,2005,25(12):125~131
    [6]戴辉,孙岩林,张涛,仿真优化技术在一类CAS问题不确定性建模中的应用,系统工程,2004,22(7):4~8
    [7]荣喜民,崔红岩,组合证券选择的最优化模型研究,系统工程学报,2005,20(2):205~210
    [8]Shapiro A. Simulation based optimization. Proceedings of Winter Simulation Conference, SanDiego, 1996:332~336
    [9]Fu M C. Optimization for simulation: theory vs. practice, Informs Journal on Computing, 2002, 14(3):192~215
    [10]杨湘龙,王飞,冯允成,仿真优化理论与方法综述,计算机仿真,2000,17(5),1~5
    [11]王凌,张亮,郑大钟,仿真优化研究进展,控制与决策,2003,18(3): 257~262
    [12]Fu M C, Are we there yet? the marriage between simulation & optimization. OR/MS Today, 2007, June: 16~17
    [13]Ho Y C, Screenivas R S and Vakili P. Ordinal optimization of DEDS, Journal of Discrete Event Dynamic Systems, 1992,2(2):61~88
    [14]Chen H C, J Lin, E Yücesan, et al. Simulation budget allocation for further enhancing the efficiency of ordinal optimization, Discrete Event Dynamic System: Theory and Applications,2000, 10:251~270
    [15]Lee L H, Chew E P, Manikam P. A general framework on the simulation-based optimization under fixed computing budget, European Journal of Operational Research, 2006, 174:1828~1841
    [16]Bachelet B, Yon L. Model enhancement: Improving theoretical optimization with simulation, Simulation Modeling Practice and Theory, 2007, 15:703~715
    [17]王凌,张亮,郑大钟,随机仿真优化的一类遗传序优化框架,控制与决策,2002,17(1):699~702
    [18]董文永,李元香,演化仿真优化的并行实现及其应用,计算机学报,2002,25(11):1236~1242
    [19]Tang H, Xi H S, Yin B Q.A simulation optimization algorithm for CTMDPs based on randomized stationary police.自动化学报,2004,30(2):229~234
    [20]Chen H C, C H Chen, L Dai, et al. New development of optimal computing budget allocation for discrete event simulation. Proceedings of Winter Simulation Conference, Institute of Electrical and Electronics Engineers, Piscataway, New Jersey, 1997, 334~341
    [21]Fu M C, J Q Hu, C H Chen, et al. Simulation Allocation for Determining the Best Design in the Presence of Correlated Sampling. Informs Journal on Computing, 2007, 19(1):101~111
    [22]Glynn P, S Juneja. A large deviations perspective on ordinal optimization. Proceedings of Winter Simulation Conference, Institute of Electrical and Electronics Engineers, Piscataway, New Jersey, 2004, 577~585
    [23]Fu M C, J Q Hu, C H Chen, et al. Optimal computing budget allocation under correlated sampling. Proceedings of Winter Simulation Conference, Institute of Electrical and Electronics Engineers, Piscataway, New Jersey, 2004, 595~603
    [24]Lee L H, E P Chew, S Y Teng, et al. Optimal computing budget allocation for multi-objective simulation models. Proceedings of Winter Simulation Conference, Institute of Electrical and Electronics Engineers, Piscataway, New Jersey, 2004, 586~594
    [25]Chick S E, Y Z Wu. Selection procedures with frequentist expected opportunity cost. Operations Research, 2005, 53 (5): 867~878
    [26]He D, S E Chick, and C H Chen. The opportunity cost and OCBA selection procedures in ordinal optimization. IEEE Transactions on Systems, 2005, 37:951~961
    [27]Trailovic L, L Y Pao. Computing budget allocation for efficient ranking and selection of variances with application to target tracking algorithms. IEEE Transactions on Automatic Control, 2004, 49: 58~67
    [28]Chen C H, D H He, M C Fu, et al. Efficient simulation budget allocation for selecting an optimal subset. INFORMS Journal on Computing, 2008, 20:579~595
    [29]Chick S E, K Inoue. New procedures to select the best simulated system using common random numbers. Management Science, 2001a, 47:1133~1149
    [30]Chick S E, K Inoue. New two-stage and sequential procedures for selecting the best simulated system. Operations Research, 2001b, 49:732~743
    [31]Andradóttir S, D Goldsman and S H Kim. Finding the best in the presence of a stochastic constraint. Proceedings of Winter Simulation Conference, Institute of Electrical and Electronics Engineers, Piscataway, New Jersey, 2005, 732~738
    [32]Kim S H, B L Nelson. Selecting the best system. In Handbooks in Operations Research and Management Science: Simulation, ed. S. G. Henderson and B. L. Nelson, 2006, 501~534
    [33]Pasupathy R, S G Henderson. A testbed of simulation-optimization problems. Proceedings of Winter Simulation Conference, Institute of Electrical and Electronics Engineers, Piscataway, New Jersey, 2006, 255~263
    [34]肖田元,范文慧,系统仿真导论(第2版),北京:清华大学出版社,2010.4~5
    [35]熊光楞,彭毅等,先进仿真技术与仿真环境,北京:国防工业出版社,1997.1~2
    [36]林则孟,系统模拟理论与应用,台中:沧海书局,1995.3~8
    [37]Banks J, Carson II, J S Nelson, et al. Discrete-Event System Simulation(肖田元,范文慧译).北京:机械工业出版社,2007.325~327
    [38]马鑫,胡建强,仿真优化中资源分配问题的研究:[硕士学位论文],上海;复旦大学,2010
    [39]王国新,宁汝新,王爱民等,仿真优化在制造系统中的应用现状及发展趋势,系统仿真学报,2008,20(1):1~6
    [40]Ho Y C, Cassandras C G, Chen C H, et al. Ordinal optimization and simulation, Journal of Operations research Society, 2000,51(4):490~500
    [41]Dai L Y. Convergence property of ordinal comparison in the simulation of discrete event dynamic systems. Journal of Optimization theory and Application, 1996, 91(2):363~388
    [42]Fu M C, C H Chen, L Y Shi. Some topics for simulation optimization. Proceedings of Winter Simulation Conference, Institute of Electrical and Electronics Engineers, Piscataway, New Jersey, 2008, 27~38
    [43]Rinott Y. On Two-stage selection procedures and related probability-inequalities. Communications in Statistics-Theory and methods, 1978, 7(8):799~811
    [44]Branke J, S E Chick, C Schmidt. Selecting a selection procedure. Management Science, 2007, 53:1916~1932
    [45]Pujowidianto N A, L H Lee, C H Chen, et al. Optimal computing budget for constrained optimization. Proceedings of Winter Simulation Conference, Institute of Electrical and Electronics Engineers, Piscataway, New Jersey, 2009, 584~589
    [46]Chen C H, D H He, E Yücesan. Special Topics on Simulation Analysis: Better-Than-Optimal Simulation Run Allocation. Proceedings of Winter Simulation Conference, Institute of Electrical and Electronics Engineers, Piscataway, New Jersey, 2003, 490~495
    [47]Bowden R O, Hall J D. Simulation optimization research and development. Proceedings of Winter Simulation Conference, Institute of Electrical and Electronics Engineers, Piscataway, New Jersey, 1998, 1693~1698
    [48]汪定伟,基于仿真优化的研究综述和主要问题的探讨,系统工程理论与实践,2008,6(增刊),94~101
    [49]Dimitri P B, John N T. Introduction to Probability (2nd edition). Nashua: Athena Scientific, 2008
    [50]Chen C H.A lower bound for the correct subset-selection probability and its application to discrete event system simulation. IEEE Transactions on automatic control, 1996, 41(8):1227~1231
    [51]Chew E P, L H Lee, S Teng, et al.Differentiated service inventory optimization using nested partitions and MOCBA.Computers and Operations Research, 2009, 36:1703~1710
    [52]Kim S H, B L Nelson. Recent advances in ranking and selection. Proceedings of Winter Simulation Conference, Institute of Electrical and Electronics Engineers, Piscataway, New Jersey, 2007, 162~172
    [53]Fu M C, F W Glover, J April. Simulation optimization: A review, new developments, and applications. Proceedings of Winter Simulation Conference, Institute of Electrical and Electronics Engineers, Piscataway, New Jersey, 2005, 83~95
    [54]Szechtman R, E Yücesan. A new perspective on feasibility determination. Proceedings of Winter Simulation Conference, Institute of Electrical and Electronics Engineers, Piscataway, New Jersey, 2008, 273~280
    [55]Ballou R H,企业物流管理—供应链的规划、组织和控制,北京:机械工业出版社,2006.1~7
    [56]Fu M C. Optimization using Simulation: a Review. Operations Research (S0030-364X), 1994, 42(2):199~248
    [57]K?chel P. Solving Logistics Problems through Simulation and Evolution. The 7th International symposium on operational research in Slovenia Pod etrtek, Slovenia, 2003
    [58]Truong T H, Avadivar F. Simulation based optimization for supply chain configuration design. Proceedings of Winter Simulation Conference, Institute of Electrical and Electronics Engineers, Piscataway, New Jersey, 2003, 1268~1275
    [59]Jung J Y, Blau G, Pekny J F.A simulation based optimization approach to supply chain management under demand uncertainty. Computers and Chemical Engineering, 2004, 28:2087~2106
    [60]常发亮,刘长友,自动化立体仓库输送系统调度的优化仿真及其应用研究,系统仿真学报,1998,10(5):14~19
    [61]朱卫锋,费奇,陈广学,复杂物流系统订货点量仿真优化调整策略,华中科技大学学报(自然科学版),2006,34(12):114~116
    [62]戴辉,孙岩林,张涛,仿真优化技术在一类CAS问题不确定性建模中的应用,系统工程,2004, 22(7):4~8

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700