最優計算量分配

最優計算量分配 是最早由陳俊宏教授於90年代中期提出的一個概念。這一方法試圖在找到一個最優決策的前提下最大化模擬效率。簡言之，OCBA是一種模擬方法，它能夠在給定一組模擬引數的情況下，幫助確定所需的模擬次數及結果。 其具體做法是透過使用一個漸進框架對最優分配的結構進行分析。直觀解釋.OCBA的目標是為大量模擬提供一種系統方法，最終從一些候選解中選取最優解，OCBA建議應該把更多的計算量分配給解2和解3，並可以提前終止對解1，4和5的模擬，同時不影響最終結果。OCBA解決的問題.OCBA的主要目標是最大化正確選擇最優解的機率。PCS服從給定取樣階段時的取樣數量"τ"的約束。formula_1此時，formula_2代表總計算量花費。OCBA主要結果.OCBA的主要理論結果基於對一個漸進的情況的考慮。該情況中，"τ"趨近於 ∞，同時取樣數量"β"趨向於∞，而且"τ""i" 也增大到"n""i"。使用“OCBA解決的問題”一節中的式可以得到，當滿足以下兩個方程時，PCS可以被最大化。有趣的是，式表明每個解的模擬次數正比於信噪比的平方。這裡的噪聲指的是樣本標準差，而訊號指的是的樣本均值和最優解樣本均值之差。數值測試示例.這裡用圖1中的簡單例子對OCBA進行數值測試。我們試圖把31個並行伺服器分配給一個兩階段的排隊系統。本例中的一個約束條件是，每個佇列中的伺服器數量(p1, p2)都不少於11臺。用數學語言描述，即為："p"1 + "p"2 = 31, "p"1 &gt; 11 and "p"2 &gt; 11.給定以上資訊，可知總共有10種關於("p"1, "p"2)的分配方法。我們的目標是最小化前100個到達的顧客的平均等待時間。為了描述不同排隊過程的效能，我們引入關於計算量的函式β，該函式的取值在200到8000之間的範圍。PCS的估計值是β的函式。PCS是透過計算正確選擇的事件數與獨立實驗數的比值進行估計的。不同的β對應的PCS值如圖2所示。表2給出了圖2一例的數值結果。結果中對使用OCBA和平均分配方法達到0.95和0.99的PCS值所需的取樣數量進行了比較。接下來進行另一個實驗，實驗中解的數量有k個。例如，可以假設伺服器的數量大於31。則我們可以觀察使用不同分配方法達到所需PCS值時的加速因子。在本例中，我們想達到的PCS值為0.99。表3給出了使用OCBA和平均分配方法時的加速因子。加速因子透過計算β_EA/ β_OCBA得到。可以看到，加速因子隨著解的數量增大而增大。這正是對大量解進行模擬時可以節省模擬時間的原因。OCBA推廣.該領域中的專家指出，有些問題中僅僅知道一個最優解是不夠的，而知道排名前5，前10前50的解更加重要，因為可能存在決策者關心的其它因素，這些因素將影響決策，而這些決策沒有被包含在模型中。根據Szechtman和Yücesan (2008), OCBA對於可行性確定問題也有幫助。在這一問題中，決策者只對區分可行解和不可行解感興趣。此外，對於其他一些決策者，更重要的是如何選擇效能相似但結構簡更單的解。這種情況下， 最好的選擇是排名前r，結構最簡單，且效能排名高於所需水平的解。 另外，Trailovic和Pao (2004)提出了一種OCBA方法，這種選取的是方差而非均值最小的解。這裡，我們假設方差未知，捨棄了OCBA的規則。2010的對基於t分佈的OCBA方法的研究表明，使用t分佈和正態分佈並沒有顯著的差別。以上所提及的OCBA的推廣研究並不完整，還需要進一步的探索和編輯。多目標最優計算量分配.多目標最優計算量分配將OCBA應用於多目標問題。在典型的MOCBA中，PCS被定義為formula_3其中注意到，識別一個正確的帕累託解集的一類錯誤率formula_11和二類錯誤率 formula_12分別為formula_13 and formula_14.另外，可以證明formula_15以及formula_16其中formula_17為目標的個數，formula_18服從formula_19的後驗分佈。注意到formula_20和formula_21是對於目標formula_22下的解formula_8的觀測效能測度的均值和標準差，而formula_24為觀測次數。因此，不同於最大化formula_25，我們可以最大化它的下界，即formula_26假設formula_27，可以利用拉格朗日方法得到以下結論：formula_28其中且formula_33formula_34formula_35formula_36formula_37formula_38formula_39formula_40有約束最佳化中的最優計算量分配.與之前幾節提到的類似，許多情況下效能指標是多重的。如果這些效能指標同樣重要，決策者可以使用MOCBA。在其它的一些情形中，決策者需要對一個主要效能進行最佳化，同時必須滿足關於次要效能的某些約束條件。主要效能指標被稱為主目標，而次要效能測度被稱為約束指標。這一問題屬於帶約束最佳化的範疇。當解的數目固定，該問題被稱為帶約束的排名和選擇，其目的在主目標和約束指標需要透過隨機模擬進行估計的情況下，選擇最優的可行解。針對帶約束最佳化問題的OCBA方法。關鍵的區別在於PCS的定義。帶約束的最佳化問題中有兩個主要部分，即最優性和可行性。因此，可以基於最優性或可行性把模擬計算量分配給非最優的解。換言之，如果一個非最優的解一直保持不可行或比真實最優可行解的效能更差的狀態，它就不會被錯誤地選為最優可行解。因此基本思想是，如果一個解明顯比最優解差，則不需要用大量的計算量去驗證它的可行性。類似地，如果一個解的效能明顯好於其它解，我們可以基於可行性進行分配，從而節省計算量。可行性檢測的最優計算量分配.該問題的目標是高效檢測一個有限集合內所有解的可行性。如果所有可行解都能被正確選出，決策者可以以此為依據，結合其它確定性的限制條件，做出最優的決策。儘管可行性檢測問題也涉及隨機約束，但是該問題和之前的有約束的最佳化問題有本質的區別。可行性檢測問題的目標是找出所有可行解，而非單一的最優可行解。定義假設所有的約束條件都是formula_59的形式， formula_60. 正確選擇所有可行解的機率是formula_61可行性檢測的計算量分配問題可以寫成 (Gao and Chen (2017))formula_62定義formula_63以及formula_64，該問題的漸進最優的計算量分配方案是formula_65基於機會成本的最優計算量分配.最初的最優計算量分配問題的目標是最大化正確選擇最優解的機率(PCS)，而實際當中另一個常用的目標計量是機會成本的期望(EOC）。EOC衡量選到的解的表現和最優解的表現的差異，其意義體現在，如果最優解最終並沒有被選到，EOC計量下選到的解的表現也不會太差。機會成本的期望的表示式如下：formula_66其中，基於EOC計量的計算量分配問題可以寫成如下形式 (Gao et al. (2017))formula_74其中 formula_54是分配給第formula_8個解的模擬預算的比例。如果我們假設對所有的非最優解formula_77, formula_78，那麼該問題的漸進最優分配方案如下formula_79其中formula_80是第formula_8個解的模擬樣本的方差。該分配方案和問題(1)的漸進最優解一致，也就是說，漸進意義下，最大化PCS和最小化EOC其實是一樣的。存在輸入不確定性的最優計算量分配.OCBA方法的一個潛在的假設是，輸入模擬模型的分佈和引數的真實值是已知的，而實際當中它們是未知的，需要用歷史資料來估計。這個估計會導致分佈和引數輸入的不確定性，繼而可能(嚴重)影響選到的解的質量。在Gao et al. (2017)文章當中，作者考慮了該問題，為每個解建立了一個關於不確定性的集合，包含有限多個可能輸入的分佈和引數。每個解的不確定性集合中最差的分佈和引數輸入對應的系統表現被視作該解的表現，基於此，這篇文章找到了存在輸入不確定性的漸進最優的計算量分配方案。基於web的OCBA演示.以下連結提供了一個OCBA演示的簡單例子。在演示中，你將看到與傳統的平均分配方法相比，OCBA如何以不同的方式分配計算量。