最適なコンピューティング予算の割り当て

コンピュータサイエンスにおいて、最適コンピューティング予算割り当て（OCBA ）は、最適な決定を見つけるための全体的なシミュレーション効率を最大化するアプローチです。 ^[1]これは、1990年代半ばにChun-Hung Chen博士によって導入されました。

OCBAは、与えられたパラメータセット内で許容可能な結果または最良の結果を得るために必要な複製回数またはシミュレーション時間を決定します。 ^{[2]これは、}漸近フレームワークを使用して最適な割り当ての構造を分析することによって実現されます。 ^[3]

OCBAは、決定論的グローバル最適化問題を解決するためのパーティションベースのランダム検索アルゴリズムを強化するのにも効果的であることが示されています。^[4]

OCBA の目標は、最良の選択肢を選択するために、重要な選択肢のみを含む 多数のシミュレーションを実行する体系的なアプローチを提供することです。

言い換えれば、OCBAは最も重要な選択肢の一部にのみ焦点を当て、計算時間を最小限に抑え、これらの重要な推定値の分散を減らします。期待される結果は、必要な精度レベルを維持しながら、必要な作業量を減らします。^[5]

たとえば、5 つの選択肢の間で簡単なシミュレーションを作成できます。目標は、平均遅延時間が最小の選択肢を選択することです。下の図は、予備的なシミュレーション結果 (つまり、必要なシミュレーション複製回数の一部のみを実行) を示しています。選択肢 2 と 3 の遅延時間が大幅に短い (赤で強調表示) ことは明らかです。計算コスト (シミュレーションの実行プロセスに費やされる時間、リソース、および費用) を節約するために、OCBA は、選択肢 2 と 3 にさらに多くの複製が必要であることを提案し、結果を損なうことなく、1、4、および 5 のシミュレーションをはるかに早く停止できます。

OCBA の主な目的は、正しい選択の確率(PCS) を最大化することです。PCS は、特定のサンプリング段階τのサンプリング バジェットの影響を受けます 。

${\displaystyle {\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}}}$

この場合は総計算コストを表します。^[6]${\displaystyle \sum _{i=1}^{k}\tau _{i}=\tau }$

この分野の専門家は、問題によっては、サンプルの中から最良の選択肢を知るだけでなく、上位 5 個、10 個、または 50 個を知ることが重要であると説明しています。これは、意思決定者が、シミュレーションではモデル化されていない、意思決定に影響を与える可能性のある他の懸念事項を持っている可能性があるためです。

Szechtman と Yücesan (2008) によると、^[7] OCBA は実現可能性の判断問題にも役立ちます。これは、意思決定者が実現可能な選択肢と実現不可能な選択肢を区別することだけに関心がある場合です。さらに、より単純でありながらパフォーマンスが類似している代替案を選択することは、他の意思決定者にとって重要です。この場合、最良の選択は、パフォーマンスが望ましいレベルを上回る上位 r の最も単純な代替案の中から選択されます。^[8]

さらに、Trailovic ^[9]と Pao ^[10] (2004) は、最良の平均ではなく、最小の分散を持つ代替案を見つけるOCBA アプローチを示しています。ここでは、分散が不明であると仮定し、OCBA ルールを無効にします (分散が既知であると仮定)。2010 年には、t 分布に基づく OCBA アルゴリズムに関する研究が行われました。結果は、t 分布と正規分布の結果の間に有意差がないことを示しています。上記の OCBA の拡張は完全なリストではなく、まだ完全に調査およびコンパイルされていません。^[11]

多目的最適計算予算配分（MOCBA）は、多目的問題に適用されるOCBAの概念です。典型的なMOCBAでは、PCSは次のように定義されます。

${\displaystyle \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\},}$

その中で

• ${\displaystyle S_{p}}$は観測されたパレート集合であり、
• ${\displaystyle {\overline {S}}_{p}}$は非パレート集合、すなわち、${\displaystyle {\overline {S}}_{p}=\Theta \backslash S_{p}}$
• ${\displaystyle E_{i}}$デザインが他のすべてのデザインに支配されないという出来事である。${\displaystyle i}$
• ${\displaystyle E_{i}^{c}}$デザインが少なくとも 1 つのデザインによって支配されるイベントです。${\displaystyle i}$

正しいパレート集合を識別するためのタイプIエラー とタイプIIエラーはそれぞれ ${\displaystyle e_{1}}$ ${\displaystyle e_{2}}$

${\displaystyle e_{1}=1-\Pr \left\{\bigcap _{i\in {\overline {S}}_{p}}E_{i}^{c}\right\}}$そして。 ${\displaystyle e_{2}=1-\Pr \left\{\bigcap _{i\in S_{p}}E_{i}\right\}}$

さらに、

${\displaystyle 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]}}$

そして

${\displaystyle 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],}$

ここで、 は目的関数の数、 は事後分布に従います。 および は、設計 の目的関数に対する観測されたパフォーマンス指標の平均と標準偏差であり、は観測値の数であること に注意してください。${\displaystyle H}$${\displaystyle {\tilde {J}}_{il}}$ ${\displaystyle Normal\left({\bar {J}}_{il},{\frac {\sigma _{il}^{2}}{N_{i}}}\right).}$${\displaystyle {\bar {J}}_{il}}$${\displaystyle \sigma _{il}}$${\displaystyle l}$${\displaystyle i}$${\displaystyle N_{i}}$

したがって、 を最大化する代わりに、その下限、つまり を最大化することができます。と仮定すると、ラグランジュ法を適用して次の規則を結論付けることができます。 ${\displaystyle \Pr\{CS\}}$${\displaystyle APCS{-}M\equiv 1-ub_{1}-ub_{2}.}$${\displaystyle \tau \rightarrow \infty }$

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

その中で

• デザインについては、、${\displaystyle h\in S_{A}}$${\displaystyle \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}}}}}$
• デザインについては、、${\displaystyle d\in S_{B}}$${\displaystyle \beta _{d}={\sqrt {\sum _{i\in \Theta _{d}^{*}}{\frac {\sigma _{dl_{d}^{i}}^{2}}{\sigma _{il_{d}^{i}}^{2}}}\beta _{i}^{2}}}}$

そして${\displaystyle \delta _{ijl}={\bar {J}}_{jl}-{\bar {J}}_{il},}$

${\displaystyle 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\}},}$

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

${\displaystyle 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\},}$

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

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

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

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

前のセクションと同様に、複数のパフォーマンス指標が存在する状況は数多くあります。複数のパフォーマンス指標が同等に重要である場合、意思決定者は MOCBA を使用できます。他の状況では、意思決定者は 1 つの主要なパフォーマンス指標を最適化する必要があり、二次的なパフォーマンス指標は特定の制限によって制約されます。

主要なパフォーマンス指標は主目的と呼ばれ、二次的なパフォーマンス指標は制約指標と呼ばれます。これは制約付き最適化の問題に該当します。選択肢の数が固定されている場合、問題は制約付きランキングと選択と呼ばれ、主目的と制約指標の両方を確率的シミュレーションで推定する必要があることを前提に、最も実行可能な設計を選択することが目標となります。制約付き最適化のためのOCBA法（OCBA-COと呼ばれる）は、Pujowidiantoら（2009） ^[12]およびLeeら（2012）^[13]に記載されています。

重要な変更点は、PCS の定義にあります。制約付き最適化には、最適性と実現可能性という 2 つの要素があります。その結果、シミュレーション予算は、最適性または実現可能性に基づいて、各非最適設計に割り当てることができます。言い換えると、非最適設計が実行不可能であるか、真の最良実行可能設計よりも劣っている場合、非最適設計が誤って最良実行可能設計として選択されることはありません。設計が明らかに最良よりも劣っている場合、実現可能性を判断するために予算の大部分を費やす必要はない、という考え方です。同様に、設計が主な目的に関してすでに最良よりも優れている場合は、実現可能性に基づいて割り当てることで予算を節約できます。

この問題の目的は、有限の設計選択肢からすべての実行可能な設計を決定することです。ここで、実行可能な設計とは、パフォーマンスの尺度が指定された制御要件 (制約) を満たす設計として定義されます。すべての実行可能な設計が選択されると、意思決定者は他のパフォーマンスの考慮事項 (コストなどの決定論的基準、または数学的に評価するのが難しい定性的な基準など) を組み込むことで、簡単に最終決定を下すことができます。実行可能性の決定問題にも確率的制約が含まれますが、これは、単一の最良の実行可能な設計ではなく、すべての実行可能な設計を特定することを目的とする点で、上で紹介した制約付き最適化問題とは区別されます。

定義する

• ${\displaystyle k}$: デザインの総数;
• ${\displaystyle m}$: パフォーマンス測定制約の合計数。
• ${\displaystyle c_{j}}$:すべての設計に対する 番目の制約の制御要件、 ;${\displaystyle j}$${\displaystyle j=1,2,...,m}$
• ${\displaystyle S_{A}}$: 実行可能な設計のセット。
• ${\displaystyle S_{B}}$: 実行不可能な設計のセット。
• ${\displaystyle \mu _{i,j}}$:番目の制約尺度と設計のシミュレーションサンプルの平均。${\displaystyle j}$${\displaystyle i}$
• ${\displaystyle \sigma _{i,j}^{2}}$:番目の制約尺度と設計のシミュレーションサンプルの分散。${\displaystyle j}$${\displaystyle i}$
• ${\displaystyle \alpha _{i}}$: 設計に割り当てられたシミュレーション予算全体の割合。${\displaystyle i}$
• ${\displaystyle {\bar {X}}_{i,j}}$:番目の制約測度と設計のシミュレーションサンプルのサンプル平均。${\displaystyle j}$${\displaystyle i}$

すべての制約が、の形式で与えられていると仮定します。すべての実行可能な設計を正しく選択する確率は ${\displaystyle \mu _{i,j}\leq c_{j}}$${\displaystyle i=1,2,...,k,j=1,2,...,m}$

${\displaystyle {\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) ^{[14]によって示されている。}

${\displaystyle {\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}}}$

ととする。漸近最適予算配分規則は ${\displaystyle I_{i,j}(x)={\frac {(x-\mu _{i,j})^{2}}{2\sigma _{i,j}^{2}}}}$${\displaystyle j_{i}\in \mathrm {argmin} _{j\in \{1,...,m\}}I_{i,j}(c_{j})}$

${\displaystyle {\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}}}$

直感的に言えば、上記の割り当てルールは、(1)実行可能な設計の場合、支配的な制約はすべての制約の中で正しく検出するのが最も難しい制約であり、(2)実行不可能な設計の場合、支配的な制約はすべての制約の中で正しく検出するのが最も簡単な制約であることを示しています。

オリジナルの OCBA は、最適な設計を正しく選択する確率 (PCS) を最大化します。実際には、もう 1 つの重要な尺度は期待機会費用(EOC) です。これは、選択された設計の平均が実際の最適な設計の平均からどれだけ離れているかを定量化します。この尺度が重要なのは、EOC を最適化すると、最適な設計を選択する可能性が最大化されるだけでなく、最適な設計が見つからない場合に、選択された設計の平均が最適な設計の平均からあまり離れないことが保証されるためです。PCS と比較すると、EOC はわずかに間違った選択よりも特に悪い選択にペナルティを課すため、リスク中立の実践者や意思決定者に好まれます。

具体的には、期待される機会費用は

${\displaystyle {\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}}}$

どこ、

• ${\displaystyle k}$デザインの総数です。
• ${\displaystyle t}$本当に最高のデザインです。
• ${\displaystyle {\mathcal {T}}}$実現すると観測された最良の設計となるランダム変数です。
• ${\displaystyle \mu _{i}}$は設計のシミュレーションサンプルの平均です。${\displaystyle i}$${\displaystyle i=1,2,...,k}$
• ${\displaystyle \delta _{i,j}=\mu _{i}-\mu _{j}}$。

EOC客観的尺度を用いた予算配分問題は、Gao et al. (2017) ^{[15]によって示されている。}

${\displaystyle {\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}}}$

ここで は設計に割り当てられたシミュレーション予算全体の割合です。すべての に対してと仮定すると、この問題に対する漸近最適予算配分規則は次のようになります。 ${\displaystyle \alpha _{i}}$${\displaystyle i}$${\displaystyle \alpha _{t}\gg \alpha _{i}}$${\displaystyle i\neq t}$

${\displaystyle {\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}}}$

ここで、は設計のシミュレーションサンプルの分散です。この割り当てルールは問題(1)の漸近最適解と同じです。つまり、漸近的に言えば、PCSを最大化することとEOCを最小化することは同じことです。 ${\displaystyle \sigma _{i}^{2}}$${\displaystyle i}$

前述の OCBA 法の暗黙の仮定は、真の入力分布とそのパラメータが既知であるということですが、実際には、それらは通常未知であり、限られた履歴データから推定する必要があります。これにより、推定された入力分布とそのパラメータに不確実性が生じ、選択の品質に（重大な）影響を与える可能性があります。不確実性セットには、基礎となる入力分布とパラメータのシナリオが有限数含まれていると仮定して、Gao ら (2017) ^{[16] は}、固定されたシミュレーション予算の下で最適な設計を正しく選択する確率を最大化する新しい OCBA アプローチを導入しています。この場合、設計のパフォーマンスは、不確実性セット内のすべての可能なシナリオの中で最悪のパフォーマンスによって測定されます。

次のリンクでは、簡単な例を使用した OCBA のデモが提供されています。デモでは、OCBA は従来の均等割り当てアプローチとは異なる方法でコンピューティング バジェットを実行し、割り当てます。

• 不確実性下でのシミュレーションベースの意思決定のための最適なコンピューティング予算割り当て (OCBA) (シミュレーション最適化)