最优计算量分配

最优计算量分配（OCBA） 是最早由陈俊宏教授于90年代中期提出的一个概念。这一方法试图在找到一个最优决策的前提下最大化仿真效率。^[1] 简言之，OCBA是一种仿真方法，它能够在给定一组仿真参数的情况下，帮助确定所需的仿真次数及（或）所需的仿真时间，以达到可接受的（或最好的）结果。^[2] 其具体做法是通过使用一个渐进框架对最优分配的结构进行分析。^[3]

直观解释

OCBA的目标是为大量仿真提供一种系统方法，最终从一些候选解中选取最优解（其中只有部分解是重要解）。换言之，它主要关注于最重要的那些解，从而最小化计算时间并降低重要解的估计值的方差。OCBA的预期效果是事半功倍，即到达所需的精度要求的同时使用更少的仿真量^[4]。比如我们可以进行一个包含5个解的简单仿真，目标是选择平均时延最小的解。下图给出了初步仿真结果（即只对每个节进行了部分数量的仿真）。显然解2和解3的时延要远远低于其它解 (由红色方框圈出)。为节省计算量花费（也即运行仿真所花费的时间，资源和金钱），OCBA建议应该把更多的计算量分配给解2和解3，并可以提前终止对解1，4和5的仿真，同时不影响最终结果。

OCBA解决的问题

OCBA的主要目标是最大化正确选择最优解的概率（PCS）。PCS服从给定采样阶段时的采样数量τ的约束。

{\begin{aligned}\max _{\tau _{1},\tau _{2},\ldots ,\tau _{k}}&\mathrm {PCS} \\{\text{subject to }}&\sum _{i=1}^{k}\tau _{i}=\tau ,\\&\tau _{i}\geq 0,i=1,2,...,k.\qquad (1)\end{aligned}}

此时， $\sum _{i=1}^{k}\tau _{i}=\tau$ 代表总计算量花费。^[5]

OCBA主要结果

OCBA的主要理论结果基于对一个渐进的情况的考虑。该情况中，τ趋近于 ∞，同时采样数量β趋向于∞，而且τ_i 也增大到n_i。使用“OCBA解决的问题”一节中的式（1）可以得到，当满足以下两个方程时，PCS可以被最大化。

有趣的是，式（2）表明每个解的仿真次数正比于信噪比的平方。这里的噪声指的是样本标准差，而信号指的是的样本均值和最优解样本均值之差。

数值测试示例

这里用图1中的简单例子对OCBA进行数值测试。我们试图把31个并行服务器分配给一个两阶段的排队系统。本例中的一个约束条件是，每个队列中的服务器数量(p1, p2)都不少于11台。用数学语言描述，即为：p₁ + p₂ = 31, p₁ > 11 and p₂ > 11.

给定以上信息，可知总共有10种关于(p₁, p₂)的分配方法。我们的目标是最小化前100个到达的顾客的平均等待时间。为了描述不同排队过程的性能，我们引入关于计算量（即使用的资源，如时间，能源等）的函数β，该函数的取值在200到8000之间的范围。PCS的估计值是β的函数。PCS是通过计算正确选择的事件数与独立实验数的比值进行估计的。不同的β对应的PCS值如图2所示。

表2给出了图2一例的数值结果。结果中对使用OCBA和平均分配方法达到0.95和0.99的PCS值所需的采样数量进行了比较。

PCS	OCBA	Equal allocation
0.95	470	1450
0.99	850	2890

接下来进行另一个实验，实验中解的数量有k个。例如，可以假设服务器的数量大于31。则我们可以观察使用不同分配方法达到所需PCS值时的加速因子。在本例中，我们想达到的PCS值为0.99。表3给出了使用OCBA和平均分配方法时的加速因子。加速因子通过计算β_EA/ β_OCBA得到。可以看到，加速因子随着解的数量增大而增大。这正是对大量解进行仿真时可以节省仿真时间的原因。

Number of alternatives (k)	4	10	20	50	75	100
Speedup factor	1.75	3.42	6.45	12.8	16.3	19.8

^[6]

OCBA推广

该领域中的专家指出，有些问题中仅仅知道一个最优解是不够的，而知道排名前5，前10前50的解更加重要，因为可能存在决策者关心的其它因素，这些因素将影响决策，而这些决策没有被包含在模型中。根据Szechtman和Yücesan (2008),^[7] OCBA对于可行性确定问题也有帮助。在这一问题中，决策者只对区分可行解和不可行解感兴趣。此外，对于其他一些决策者，更重要的是如何选择性能相似但结构简更单的解。这种情况下，最好的选择是排名前r，结构最简单，且性能排名高于所需水平的解。^[8] 另外，Trailovic^[9]和Pao^[10] (2004)提出了一种OCBA方法，这种选取的是方差而非均值最小的解。这里，我们假设方差未知，舍弃了OCBA的规则（即假设方差已知）。2010的对基于t分布的OCBA方法的研究表明，使用t分布和正态分布并没有显著的差别。以上所提及的OCBA的推广研究并不完整，还需要进一步的探索和编辑。^[6]

多目标最优计算量分配

多目标最优计算量分配（MOCBA）将OCBA应用于多目标问题。在典型的MOCBA中，PCS被定义为

$\Pr\{CS\}\equiv \Pr \left\{\left(\bigcap _{i\in S_{p}}E_{i}\right)\bigcap \left(\bigcap _{i\in {\overline {S}}_{p}}E_{i}^{c}\right)\right\},$

其中

$S_{p}$ 为观测的帕累托集合，
${\overline {S}}_{p}$ 为非帕累托集合，即 ${\overline {S}}_{p}=\Theta \backslash S_{p}$ ,
$E_{i}$ 为一个事件，它定义为解 $i$ 被任何其它解支配，
$E_{i}^{c}$ 为一个事件，它定义为解 $i$ 至少被一个解支配。

注意到，识别一个正确的帕累托解集的一类错误率 $e_{1}$ 和二类错误率 $e_{2}$ 分别为

$e_{1}=1-\Pr \left\{\bigcap _{i\in {\overline {S}}_{p}}E_{i}^{c}\right\}$ and $e_{2}=1-\Pr \left\{\bigcap _{i\in S_{p}}E_{i}\right\}$ .

另外，可以证明

$e_{1}\leq ub_{1}=H\left|{\overline {S}}_{p}\right|-H\sum _{i\in {\overline {S}}_{p}}{\max _{j\in \Theta ,j\neq i}\left[\min _{l\in {1,\ldots ,H}}\Pr \left\{{\tilde {J}}_{jl}\leq {\tilde {J}}_{il}\right\}\right]}$

以及

$e_{2}\leq ub_{2}=(k-1)\sum _{i\in S_{p}}\max _{j\in \Theta ,j\neq i}\left[\min _{l\in {1,\ldots ,H}}\Pr \left\{{\tilde {J}}_{jl}\leq {\tilde {J}}_{il}\right\}\right],$

其中 $H$ 为目标的个数， ${\tilde {J}}_{il}$ 服从 $Normal\left({\bar {J}}_{il},{\frac {\sigma _{il}^{2}}{N_{i}}}\right)$ 的后验分布。注意到 ${\bar {J}}_{il}$ 和 $\sigma _{il}$ 是对于目标 $l$ 下的解 $i$ 的观测性能测度的均值和标准差，而 $N_{i}$ 为观测次数。

因此，不同于最大化 $\Pr\{CS\}$ ，我们可以最大化它的下界，即 $APCS{-}M\equiv 1-ub_{1}-ub_{2}.$ 假设 $\tau \rightarrow \infty$ ，可以利用拉格朗日方法得到以下结论：

$\tau _{i}={\frac {\beta _{i}}{\sum _{j\in \Theta }\beta _{j}}}\tau ,$

其中

对于解 $h\in S_{A}$ , $\beta _{h}={\frac {\left({\hat {\sigma }}_{hl_{j_{h}}^{h}}^{2}+{\hat {\sigma }}_{j_{h}l_{j_{h}}^{h}}^{2}/\rho _{h}\right)/{\delta _{hj_{h}l_{j_{h}}^{h}}^{2}}}{\left({\hat {\sigma }}_{ml_{jm}^{m}}^{2}+{\hat {\sigma }}_{j_{m}l_{jm}^{m}}^{2}/\rho _{m}\right)/{\delta _{mj_{m}l_{j_{m}}^{m}}^{2}}}}$ ,

对于解 $d\in S_{B}$ , $\beta _{d}={\sqrt {\sum _{i\in \Theta _{d}^{*}}{\frac {\sigma _{dl_{d}^{i}}^{2}}{\sigma _{il_{d}^{i}}^{2}}}\beta _{i}^{2}}}$ ,

且 $\delta _{ijl}={\bar {J}}_{jl}-{\bar {J}}_{il},$

$j_{i}\equiv \arg \max _{j\in \Theta ,j\neq i}\prod _{l=1}^{H}{\Pr \left\{{\tilde {J}}_{jl}\leq {\tilde {J}}_{il}\right\}},$

$l_{j_{i}}^{i}\equiv \arg \min _{l\in {1,\ldots ,H}}\Pr \left\{{\tilde {J}}_{jl}\leq {\tilde {J}}_{il}\right\},$

$S_{A}\equiv \left\{design\;h\in S\mid {\frac {\delta _{hj_{h}l_{j_{h}}^{h}}^{2}}{{\frac {{\hat {\sigma }}_{hl_{j_{h}}^{h}}^{2}}{\alpha _{h}}}+{\frac {{\hat {\sigma }}_{j_{h}l_{j_{h}}^{h}}^{2}}{\alpha _{j_{h}}}}}}<\min _{i\in \Theta _{h}}{\frac {\delta _{ihl_{h}^{i}}^{2}}{{\frac {{\hat {\sigma }}_{il_{h}^{i}}^{2}}{\alpha _{i}}}+{\frac {{\hat {\sigma }}_{hl_{h}^{i}}^{2}}{\alpha _{h}}}}}\right\},$

$S_{B}\equiv S\backslash S_{A},$

$\Theta _{h}={i|i\in S,j_{i}=h},$

$\Theta _{d}^{*}={h|h\in S_{A},j_{h}=d},$

$\rho _{i}=\alpha _{j_{i}}/\alpha _{i}.$

有约束优化中的最优计算量分配

与之前几节提到的类似，许多情况下性能指标是多重的。如果这些性能指标同样重要，决策者可以使用MOCBA。在其它的一些情形中，决策者需要对一个主要性能进行优化，同时必须满足关于次要性能的某些约束条件。主要性能指标被称为主目标，而次要性能测度被称为约束指标。这一问题属于带约束优化的范畴。当解的数目固定，该问题被称为带约束的排名和选择，其目的在主目标和约束指标需要通过随机仿真进行估计的情况下，选择最优的可行解。针对带约束优化问题的OCBA方法（称为OCBA-CO）可参见Pujowidianto等人（2009）^[11] 和Lee等人（2012）^[12]。

关键的区别在于PCS的定义。带约束的优化问题中有两个主要部分，即最优性和可行性。因此，可以基于最优性或可行性把仿真计算量分配给非最优的解。换言之，如果一个非最优的解一直保持不可行或比真实最优可行解的性能更差的状态，它就不会被错误地选为最优可行解。因此基本思想是，如果一个解明显比最优解差，则不需要用大量的计算量去验证它的可行性。类似地，如果一个解的性能（主目标函数值）明显好于其它解，我们可以基于可行性进行分配，从而节省计算量。

可行性检测的最优计算量分配

该问题的目标是高效检测一个有限集合内所有解的可行性。如果所有可行解都能被正确选出，决策者可以以此为依据，结合其它确定性的限制条件，做出最优的决策。尽管可行性检测问题也涉及随机约束，但是该问题和之前的有约束的优化问题有本质的区别。可行性检测问题的目标是找出所有可行解，而非单一的最优可行解。

定义

$k$ : 解的数量;
$m$ : 约束条件的数量;
$c_{j}$ : 第 $j$ 个约束条件的控制参数, $j=1,2,...,m$ ;
$S_{A}$ : 可行解的集合;
$S_{B}$ : 非可行解的集合;
$\mu _{i,j}$ : 第 $j$ 个约束条件以及第 $i$ 个解的仿真样本的均值;
$\sigma _{i,j}^{2}$ : 第 $j$ 个约束条件以及第 $i$ 个解的仿真样本的方差;
$\alpha _{i}$ : 分配给第 $i$ 个解的仿真预算的比例;
${\bar {X}}_{i,j}$ : 第 $j$ 个约束条件以及第 $i$ 个解的仿真样本的样本均值.

假设所有的约束条件都是 $\mu _{i,j}\leq c_{j}$ 的形式， $i=1,2,...,k,j=1,2,...,m$ . 正确选择所有可行解的概率是

{\begin{aligned}\mathrm {PCS} =\mathbb {P} \left(\bigcap _{i\in S_{A}}{\Big (}\bigcap _{j=1}^{m}({\bar {X}}_{i,j}\leq c_{j}){\Big )}\cap \bigcap _{i\in S_{B}}{\Big (}\bigcup _{j=1}^{m}({\bar {X}}_{i,j}>c_{j}){\Big )}\right).\end{aligned}}

可行性检测的计算量分配问题可以写成 (Gao and Chen (2017)^[13])

{\begin{aligned}\max _{\alpha _{1},\alpha _{2},\ldots ,\alpha _{k}}&\mathrm {PCS} \\{\text{subject to }}&\sum _{i=1}^{k}\alpha _{i}=1,\\&\alpha _{i}\geq 0,i=1,2,...,k.\end{aligned}}

定义 $I_{i,j}(x)={\frac {(x-\mu _{i,j})^{2}}{2\sigma _{i,j}^{2}}}$ 以及 $j_{i}\in \mathrm {argmin} _{j\in \{1,...,m\}}I_{i,j}(c_{j})$ ，该问题的渐进最优的计算量分配方案是

{\begin{aligned}{\frac {\alpha _{i}}{\alpha _{i'}}}={\frac {I_{i',j_{i'}}(c_{j_{i'}})}{I_{i,j_{i}}(c_{j_{i}})}},i,i'\in \{1,2,...,k\}.\end{aligned}}

基于机会成本的最优计算量分配

最初的最优计算量分配问题的目标是最大化正确选择最优解的概率(PCS)，而实际当中另一个常用的目标计量是机会成本的期望(EOC）。EOC衡量选到的解的表现和最优解的表现的差异，其意义体现在，如果最优解最终并没有被选到，EOC计量下选到的解的表现也不会太差。

机会成本的期望的表达式如下：

{\begin{aligned}EOC=\mathbb {E} _{\mathcal {T}}[\mu _{\mathcal {T}}-\mu _{t}]=\sum _{i=1,i\neq t}^{k}\delta _{i,t}\mathbb {P} ({\mathcal {T}}=i).\end{aligned}}

其中，

$k$ 是解的数量;
$t$ 代表最优解;
${\mathcal {T}}$ 是观测到的最优解;
$\mu _{i}$ 是第 $i$ 个解的仿真样本的均值, $i=1,2,...,k$ ;
$\delta _{i,j}=\mu _{i}-\mu _{j}$ .

基于EOC计量的计算量分配问题可以写成如下形式 (Gao et al. (2017)^[14])

{\begin{aligned}\min _{\alpha _{1},\alpha _{2},\ldots ,\alpha _{k}}&\mathrm {EOC} \\{\text{subject to }}&\sum _{i=1}^{k}\alpha _{i}=1,\\&\alpha _{i}\geq 0,i=1,2,...,k.\end{aligned}}

其中 $\alpha _{i}$ 是分配给第 $i$ 个解的仿真预算的比例。如果我们假设对所有的非最优解 $i\neq t$ , $\alpha _{t}\gg \alpha _{i}$ ，那么该问题的渐进最优分配方案如下

{\begin{aligned}&{\frac {\alpha _{t}^{2}}{\sigma _{t}^{2}}}=\sum _{i=1,i\neq t}^{k}{\frac {\alpha _{i}^{2}}{\sigma _{i}^{2}}},\\&{\frac {\alpha _{i}}{\alpha _{j}}}={\frac {\sigma _{i}^{2}/\delta _{i,t}^{2}}{\sigma _{j}^{2}/\delta _{j,t}^{2}}},i\neq j\neq t.\end{aligned}}

其中 $\sigma _{i}^{2}$ 是第 $i$ 个解的仿真样本的方差。该分配方案和问题(1)的渐进最优解一致，也就是说，渐进意义下，最大化PCS和最小化EOC其实是一样的。

存在输入不确定性的最优计算量分配

OCBA方法的一个潜在的假设是，输入仿真模型的分布和参数的真实值是已知的，而实际当中它们是未知的，需要用历史数据来估计。这个估计会导致分布和参数输入的不确定性，继而可能(严重)影响选到的解的质量。在Gao et al. (2017)^[15]文章当中，作者考虑了该问题，为每个解建立了一个关于不确定性的集合，包含有限多个可能输入的分布和参数。每个解的不确定性集合中最差的分布和参数输入对应的系统表现被视作该解的表现，基于此，这篇文章找到了存在输入不确定性的渐进最优的计算量分配方案。

基于web的OCBA演示

以下链接提供了一个OCBA演示的简单例子。在演示中，你将看到与传统的平均分配方法相比，OCBA如何以不同的方式分配计算量。

http://seor.vse.gmu.edu/~cchen9/ocba.html （页面存档备份，存于互联网档案馆）

参考资料

^ 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, and Loo H. Lee. Stochastic simulation optimization an optimal computing budget allocation. Singapore Hackensack, NJ: World Scientific, 2011. Print..
^ 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, Chun-Hung. Optimal Computing Budget Allocation (OCBA) for Simulation-based Decision Making Under Uncertainty. [9 July 2013]. （原始内容存档于2013年10月1日）.
^ Chen, and Loo H. Lee. Stochastic simulation optimization an optimal computing budget allocation. Singapore Hackensack, NJ: World Scientific, 2011. Print.
^ ^6.0 ^6.1 Chen, C. H., M. Fu, L. Shi, and L. H. Lee, “Stochastic Systems Simulation Optimization,” Frontiers of Electrical and Electronic Engineering in China, 6(3), 468–480, 2011
^ Szechtman R, Yücesan E (2008) A new perspective on feasibility determination. Proc of the 2008 Winter Simul Conf 273–280
^ Jia QS, Zhou E, Chen CH (2012). efficient computing budget allocation for finding simplest good designs. IIE Trans, To Appear.
^ Trailovic Tekin E, Sabuncuoglu I (2004) Simulation optimization: A comprehensive review on theory and applications. IIE Trans 36:1067–1081
^ Trailovic L, Pao LY (2004) Computing budget allocation for efficient ranking and selection of variances with application to target tracking algorithms, IEEE Trans Autom Control 49:58–67.
^ Pujowidianto NA, Lee LH, Chen CH, Yap CM (2009) Optimal computing budget allocation for constrained optimization. Proc of the 2009 Winter Simul Conf 584–589.
^ Lee LH, Pujowidianto NA, Li LW, Chen CH, Yap CM (2012) Approximation simulation budget allocation for selecting the best design in the presence of stochastic constraints, IEEE Trans Autom Control 57:2940–2945.
^ Gao, S. and W. Chen, "Efficient feasibility determination with multiple performance measure constraints," IEEE Transactions on Automatic Control, 62, 113–122, 2017.
^ Gao, S., W. Chen and L. Shi, "A New Budget Allocation Framework for the Expected Opportunity Cost," Operations Research, 63, 787–803, 2017.
^ Gao, S., H. Xiao, E. Zhou and W. Chen, "Robust Ranking and Selection with Optimal Computing Budget Allocation," Automatica, 81, 30–36, 2017.

外部链接

Optimal Computing Budget Allocation (OCBA) for Simulation-based Decision Making Under Uncertainty (Simulation Optimization) -- Find the best design using a minimum simulation time （页面存档备份，存于互联网档案馆）

[1] 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.

[2] Chen, and Loo H. Lee. Stochastic simulation optimization an optimal computing budget allocation. Singapore Hackensack, NJ: World Scientific, 2011. Print..

[3] 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.

[4] Chen, Chun-Hung. Optimal Computing Budget Allocation (OCBA) for Simulation-based Decision Making Under Uncertainty. [9 July 2013]. （原始内容存档于2013年10月1日）.

[5] Chen, and Loo H. Lee. Stochastic simulation optimization an optimal computing budget allocation. Singapore Hackensack, NJ: World Scientific, 2011. Print.

[Chen-6] 6.0 ^6.1 Chen, C. H., M. Fu, L. Shi, and L. H. Lee, “Stochastic Systems Simulation Optimization,” Frontiers of Electrical and Electronic Engineering in China, 6(3), 468–480, 2011

[7] Szechtman R, Yücesan E (2008) A new perspective on feasibility determination. Proc of the 2008 Winter Simul Conf 273–280

[8] Jia QS, Zhou E, Chen CH (2012). efficient computing budget allocation for finding simplest good designs. IIE Trans, To Appear.

[9] Trailovic Tekin E, Sabuncuoglu I (2004) Simulation optimization: A comprehensive review on theory and applications. IIE Trans 36:1067–1081

[10] Trailovic L, Pao LY (2004) Computing budget allocation for efficient ranking and selection of variances with application to target tracking algorithms, IEEE Trans Autom Control 49:58–67.

[11] Pujowidianto NA, Lee LH, Chen CH, Yap CM (2009) Optimal computing budget allocation for constrained optimization. Proc of the 2009 Winter Simul Conf 584–589.

[12] Lee LH, Pujowidianto NA, Li LW, Chen CH, Yap CM (2012) Approximation simulation budget allocation for selecting the best design in the presence of stochastic constraints, IEEE Trans Autom Control 57:2940–2945.

[13] Gao, S. and W. Chen, "Efficient feasibility determination with multiple performance measure constraints," IEEE Transactions on Automatic Control, 62, 113–122, 2017.

[14] Gao, S., W. Chen and L. Shi, "A New Budget Allocation Framework for the Expected Opportunity Cost," Operations Research, 63, 787–803, 2017.

[15] Gao, S., H. Xiao, E. Zhou and W. Chen, "Robust Ranking and Selection with Optimal Computing Budget Allocation," Automatica, 81, 30–36, 2017.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]