最优计算量分配法则（OCBA）
针对不确定情况下基于仿真的决策（仿真优化）
--
用最少的仿真时间找到最优解
*** 访问 OCBA 英文原版
*** 访问 Czech版，感谢Andrey Fomin的帮助。
我们研究出了一种为仿真智能分配计算量的先进方法，该方法能使仿真更高效。其最终目标是用最少的仿真时间找到最优解。许多同行和朋友都对这一领域的研究作出了贡献。
仿真是设计大型、复杂、随机系统的常用工具，因为对于此类问题通常不存在闭式解析解。虽然科技的进步让计算能力有了极大的提升，在使用仿真设计大型系统时，由于需要仿真大量候选解，仿真效率仍是不可忽视的问题。更棘手的是，为了捕获系统中的随机行为，多次仿真在所难免。因此，如何大幅减少总计算时间无疑是个至关重要的问题。
解决该问题的一个重要途径，正是我们提出的一种新的控制-理论仿真技术，称为最优计算量分配法则（OCBA）。OCBA方法能为所有候选解智能分配仿真次数或仿真时长，以达到较高的仿真效率。其目的是在计算量固定的情况下，得到最高质量的仿真决策，或用最少的计算量达到所需的仿真决策质量。数值实验表明，我们的方法只需使用十分之一的计算量就能达到相同的仿真效果。
不仅如此，OCBA也是随机仿真优化的理想选择。仿真优化之所以如此困难，主要是因为对目标函数的估计具有随机性，这便意味着我们面临一个最基本的权衡：是将计算量用于搜索新的候选解（广度搜索），还是用于获得对已有最优解的更精确估计（深度挖掘）。换言之，考虑仿真计算效率时，一个主要问题是确定应当把多少计算量用于已搜索过的解，而又该把多少计算量分配给将被搜索的解。实际操作中，OCBA会分阶段有序地确定哪个解需要更多的仿真，以及需要多少次仿真。
直观上，要确保所选解的确为最优解，就需要在辨识最优解的过程中把更大比例的计算量分配给那些重要的解。换句话说，应该对那些重要解进行大量仿真以降低它们估计值的方差。由于消耗在不重要解上的计算量减少了，总体仿真效率也会得到提高。这里用一个简单的例子对这种思想进行阐述。假设我们对5个候选解进行仿真，目的是确定平均时延最小的解。首先，我们对全部5个解进行初步仿真。图1-(a)给出了从初步仿真后99%置信区间的示例。请注意，估计值的不确定性源于系统本身的随机特性以及蒙特卡洛仿真的使用。
图 1. 初步仿真后5个候选解的99%置信区间，其中(a)为特殊情况，(b)为一般情况 。
如图1-(a)所示，虽然每个解的性能估计都存在不确定性，但如果我们要找平均时延最小的解，显然第2和第3个解的性能比其它解好很多。因此只有第2和第3个解需要进一步仿真来减少对其估计的不确定性，进而正确地辨识最优解。通过停止对第1，第4和第5个解的仿真，我们可以节省大量的计算花费。
然而，大部分实际情况并非图1-(a)中的情况那么简单。更普遍的情况如图1-(b)所示，即某些解的性能似乎更好，但并不明显优于其它解。此时应该把哪些解从仿真实验中剔除，以及应当何时停止仿真，都不那么简单明了。好在OCBA提供了一种解决该问题的系统化方法，其分配计算量的方式能将仿真效率最大化。
深入了解OCBA可以从以下两篇论文入手：
OCBA思想导论
Chen, C. H., M. Fu, and L. Shi, "Simulation and Optimization," Tutorials in Operations Research, pp. 247-260, Informs, Hanover, MD, 2008.
Fu, M, C. H. Chen, and L. Shi, "Some Topics for Simulation Optimization," Proceedings of 2008 Winter Simulation Conference, pp. 27-38, Miami, FL, December 2008.
Chen, C. H. and L. H. Lee, Stochastic Simulation Optimization: An Optimal Computing Budget Allocation. World Scientific Publishing Co., 2011.
以下是一些有关OCBA方法的代表性著作。
OCBA的早期发展
Chen, C. H. "An Effective Approach to Smartly Allocate Computing Budget for Discrete Event Simulation," Proceedings of the 34th IEEE Conference on Decision and Control, pp. 2598-2605, December 1995.
Chen, C. H. "A Lower Bound for the Correct Subset-Selection Probability and Its Application to Discrete Event System Simulations," IEEE Transactions on Automatic Control, Vol. 41, No. 8, pp. 1227-1231, August 1996.
Chen, C. H., E. Yucesan, L. Dai, and H. C. Chen, "Efficient Computation of Optimal Budget Allocation for Discrete Event Simulation Experiment," IIE Transactions, Vol. 42, No. 1, pp. 60-70, January 2010.
OCBA用于选择最优解
Chen, C. H., J. Lin, E. Yucesan, and S. E. Chick, "Simulation Budget Allocation for Further Enhancing the Efficiency of Ordinal Optimization," Journal of Discrete Event Dynamic Systems: Theory and Applications, Vol. 10, pp. 251-270, July 2000. PDF
OCBA用于解决多目标问题
Lee, L. H., E. P. Chew, S. Y. Teng, and D. Goldsman, "Optimal computing budget allocation for multi-objective simulation models," Proceedings of 2004 Winter Simulation Conference, pp. 586-594, 2004.
E.J. Chen and L.H. Lee, "A multi-objective selection procedure of determining a Pareto set", Computers and Operations Research, 36(6), : 1872-1879 , 2009.
S. Teng, L.H. Lee and E.P. Chew, "Integration of Indifference-zone with Multi-objective Computing Budget Allocation", European Journal of Operational Research, 203(2): 419-429, 2010.
L. H. Lee, E. P. Chew, S. Y. Teng, and D. Goldsman (2010). Finding the Pareto set for multi-objective simulation models, to appear in IIE Transactions.
OCBA用于选择最优解集（如排名前5的解）
Chen, C. H., D. He, M. Fu, and L. H. Lee, "Efficient Simulation Budget Allocation for Selecting an Optimal Subset," Informs Journal on Computing, Vol. 20, No. 4, pp. 579-595, 2008.
OCBA用于在样本存在关联时选择最优解
Fu, M. C., J. Q. Hu, C. H. Chen, and X. Xiong, "Simulation Allocation for Determining the Best Design in the Presence of Correlated Sampling," Informs Journal on Computing, Vol. 19, No. 1, pp. 101-111, 2007.
OCBA用于仿真及优化
He, D., L. H. Lee, C. H. Chen, M. Fu, and S. Wasserkrug, "Simulation Optimization Using the Cross-Entropy Method with Optimal Computing Budget Allocation," to appear in ACM Transactions on Modeling and Computer Simulation, 2009.
Chew, E. P. , L.H. Lee, S.Y. Teng, and C.H. Koh, "Differentiated Service Inventory Optimization using Nested Partitions and MOCBA", Computers and Operations Research, 36(5), : 1703-1710, 2009.
Lee, L. H., E.P. Chew, S.Y. Teng, and Y.K. Chen, "Multi-objective simulation-based evolutionary algorithm for an aircraft spare parts allocation problem", European Journal of Operational Research, 189 (2): 476-491, 2008.
Chen, C. H., D. He, M. Fu, and L. H. Lee, "Efficient Simulation Budget Allocation for Selecting an Optimal Subset," Informs Journal on Computing, Vol. 20, No. 4, pp. 579-595, 2008.
Shi, L. and C. H. Chen, "A New Algorithm for Stochastic Discrete Resource Allocation Optimization," Journal of Discrete Event Dynamic Systems: Theory and Applications, Vol. 10, pp. 271-294, July 2000.
OCBA的应用
Hsieh, B. W., C. H. Chen, S. C. Chang, "Efficient Simulation-based Composition of Dispatching Policies by Integrating Ordinal Optimization with Design of Experiment," IEEE Transactions on Automation Science and Engineering, Vol. 4, No. 4, pp. 553-568, October 2007.
Romero, V. J., D. V. Ayon, C. H. Chen, "Demonstration of Probabilistic Ordinal Optimization Concepts to Continuous-Variable Optimization Under Uncertainty," Optimization and Engineering, Vol. 7, No. 3, pp. 343-365, September 2006.
Chen, C. H., and D. He, "Intelligent Simulation for Alternatives Comparison and Application to Air Traffic Management," Journal of Systems Science and Systems Engineering, Vol. 14, No. 1, pp. 37-51, March 2005.
Chen, C. H., K. Donohue, E. Yucesan, and J. Lin, "Optimal Computing Budget Allocation for Monte Carlo Simulation with Application to Product Design," Journal of Simulation Practice and Theory, Vol. 11, No. 1, pp. 57-74, March 2003.
Hsieh, B. W., C. H. Chen, and S.
C. Chang, "Scheduling Semiconductor Wafer Fabrication by Using Ordinal
Optimization-Based Simulation," IEEE
Transactions on Robotics and Automation, Vol. 17, No. 5, pp. 599-608, October 2001.
Chen, C. H.,
S. D. Wu, and L. Dai, "Ordinal Comparison of Heuristic Algorithms Using
Stochastic Optimization," IEEE
Transactions on Robotics and Automation, Vol. 15, No. 1, pp. 44-56,
February 1999.
与序优化的关系
Dai, L., C. H. Chen, and J. R. Birge, "Large Convergence Properties of Two-Stage Stochastic Programming," Journal of Optimization Theory and Applications, Vol. 106, No. 3, pp. 489-510, September 2000.
Ho, Y. C., C. G. Cassandras, C. H. Chen, and L. Dai, "Ordinal Optimization and Simulation," Journal of Operational Research Society, Vol. 51, No. 4, pp. 490-500, April 2000.
Dai, L. and C. H. Chen, "Rate of Convergence for Ordinal Comparison of Dependent Simulations in Discrete Event Dynamic Systems," Journal of Optimization Theory and Applications, Vol. 94, No. 1, pp. 29-54, July 1997.
一些其它的推广和相关工作
Blanchet, J., J. Liu, and B. Zwart, "Large Deviations Perspective on Ordinal Optimization of Heavy-Tailed Systems," Proceedings of the 2007 Winter Simulation Conference, pp. 489-494, 2007.
Branke, J., S. E. Chick, and C. Schmidt. Selecting a selection procedure. Management Science 53 1916-1932, 2007.
Chick, S. and K. Inoue. New two-stage and sequential procedures for selecting the best simulated system. Operations Research 49 1609-1624, 2001.
Chick, S. and K. Inoue. New procedures to select the best simulated system using common random numbers. Management Science 47 1133-1149, 2001.
Glynn, P., S. Juneja. A Large deviations perspective on ordinal optimization. Proceedings of the 2004 Winter Simulation Conference, 577-585, 2004.
Pujowidianto, N. A., L. H. Lee, C. H. Chen, C. M. Yep, "Optimal Computing Budget Allocation For Constrained Optimization," to appear in Proceedings of 2009 Winter Simulation Conference, pp. 584-589, Austin, TX, December 2009.
Trailovic, L. and L. Y. Pao. 2004. Computing budget allocation for efficient ranking and selection of variances with application to target tracking algorithms. IEEE Transactions on Automatic Control 49 58-67, 2004.
OCBA
书籍
1. 一本关于OCBA的新书已于2011年出版。书名为《Stochastic Simulation Optimization: An Optimal Computing Budget Allocation》。该书从基本原理、正式发展、研究现状三个角度出发，对高效的仿真优化方法进行了综合和全面的阐述。 您可以从Amazon.com上订购。
2. 另一本推广到序优化框架下的新书是《Stochastic Simulation Optimization for Discrete Event Systems - Perturbation Analysis, Ordinal Optimization, and Beyond》，于2013年出版。
OCBA的C/C++源代码
点击这里获取OCBA的C/C++源代码。您也以在OCBA一书中的214-218页中找到该代码。
OCBA
演示 (及JAVA源代码 )
在您的浏览器上演示OCBA。此OCBA演示由A. Johnson, Cheol Y. Park, 和Ning Lin实现。在演示中，您将看到OCBA如何动态选择下一步最需要仿真的解。
访问 (Samuel) Qing-Shan Jia 教授的个人主页