最優計算量分配

最優計算量分配（OCBA） 是最早由陳俊宏教授於90年代中期提出的一個概念。這一方法試圖在找到一個最優決策的前提下最大化仿真效率。 簡言之，OCBA是一種仿真方法，它能夠在給定一組仿真參數的情況下，幫助確定所需的仿真次數及（或）所需的仿真時間，以達到可接受的（或最好的）結果。 其具體做法是通過使用一個漸進框架對最優分配的結構進行分析。

直觀解釋

OCBA的目標是為大量仿真提供一種系統方法，最終從一些候選解中選取最優解（其中只有部分解是重要解）。換言之，它主要關注於最重要的那些解，從而最小化計算時間並降低重要解的估計值的方差。OCBA的預期效果是事半功倍，即到達所需的精度要求的同時使用更少的仿真量。比如我們可以進行一個包含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$代表總計算量花費。

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

OCBA推廣

該領域中的專家指出，有些問題中僅僅知道一個最優解是不夠的，而知道排名前5，前10前50的解更加重要，因為可能存在決策者關心的其它因素，這些因素將影響決策，而這些決策沒有被包含在模型中。根據Szechtman和Yücesan (2008), OCBA對於可行性確定問題也有幫助。在這一問題中，決策者只對區分可行解和不可行解感興趣。此外，對於其他一些決策者，更重要的是如何選擇性能相似但結構簡更單的解。這種情況下， 最好的選擇是排名前r，結構最簡單，且性能排名高於所需水平的解。 另外，Trailovic和Pao (2004)提出了一種OCBA方法，這種選取的是方差而非均值最小的解。這裡，我們假設方差未知，捨棄了OCBA的規則（即假設方差已知）。2010的對基於t分布的OCBA方法的研究表明，使用t分布和正態分布並沒有顯著的差別。以上所提及的OCBA的推廣研究並不完整，還需要進一步的探索和編輯。

多目標最優計算量分配

多目標最優計算量分配（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） 和Lee等人（2012）。

關鍵的區別在於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))

${\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))

${\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)文章當中，作者考慮了該問題，為每個解建立了一個關於不確定性的集合，包含有限多個可能輸入的分布和參數。每個解的不確定性集合中最差的分布和參數輸入對應的系統表現被視作該解的表現，基於此，這篇文章找到了存在輸入不確定性的漸進最優的計算量分配方案。

基於web的OCBA演示

以下鏈接提供了一個OCBA演示的簡單例子。在演示中，你將看到與傳統的平均分配方法相比，OCBA如何以不同的方式分配計算量。

• http://seor.vse.gmu.edu/~cchen9/ocba.html （頁面存檔備份，存於網際網路檔案館）

外部連結

• Optimal Computing Budget Allocation (OCBA) for Simulation-based Decision Making Under Uncertainty (Simulation Optimization) -- Find the best design using a minimum simulation time （頁面存檔備份，存於網際網路檔案館）