基于錦標賽思想的最優計算量分配的研究

奚鈺佳

摘要：序優化（Ordinal Optimization，OO）方法在隨機仿真優化（Stochastic Simulation Optimization）中有較為流行。該方法提出了序（Order）比值（Value）更容易獲得的思想，并提供了理論依據。而最優計算量分配（Optimal Computing Budget Allocation，OCBA）算法則是為了進一步提高序優化的效率提出的。該文主要針對最優計算量分配算法進行拓展。在數據和選擇爆發式增長的情況下，在獲得最佳選擇（方案）的同時，也有必要縮短選擇時間。錦標賽思想則是在有大量參賽選手時，兩兩比較選出優勝選手，再從優勝選手中進行選擇，從而減少比較的時間。受此思想啟發，面對大規模候選集，提出了基于錦標賽思想的最優計算量分配算法。該算法在對方案進行仿真資源的分配前，先選擇一半甚至更少的精英方案，以快速的獲得最佳方案。并且實驗數據表明了其有效性。

關鍵詞：隨機仿真;序優化;最優計算量分配;排序和選擇

中圖分類號：TP311.1 文獻標識碼：A

文章編號：1009-3044（2020）05-0253-05

開放科學（資源服務）標識碼（OSID）：

1 序優化方法介紹

序優化方法（Ordinal Optimization，00）在隨機仿真優化中有著較多的應用[1-2]。隨機仿真優化即是基于仿真的目標優化，并且在很多實際系統中都有著廣泛的應用[3][4]，比如復雜工程系統的設計優化、供應鏈和物流系統、制造系統及社會經濟系統[[5-9]等。該方法將問題建模，通過優化算法根據仿真模型的輸出對輸入調整優化，從而選出性能最佳的對象。具體過程如圖1所示：

在其中，有一類排序與選擇（Ranking and Selection）問題，目標或者是要從候選方案（design）中獲得最佳，或者是獲得其方案的排序，抑或者是或者前m個最佳。對于這類問題，序優化思想有著更大的優勢。其認為序（Order）比值（Value）更容易獲得[10]，因此在仿真過程中，不必要對每個方案都大量仿真以獲得其精確值，根據目標，針對性的對方案進行分配，獲得它們的序，從而更高效的達到目標。因此，序優化在應用到學習選擇出最佳方案（子集）等問題時，具有巨大的優勢，并被應用到了多個領域[11]-[13]。

Ho等人提出的序優化方法包含了兩個主要思想：序比值更容易獲得;不要堅持獲得最佳（Best）的方案而要愿意接受足夠好（Cood Enough）的方案[1][2]。該方法旨在從候選集中選出足夠好（Good Enough）的方案，本來目標是選出真是最優，但是運用足夠好（Good Enough）的思想，將選擇范圍拓寬到集合G，而s是仿真獲得的足夠好的集合，s中仿真估計最優也就會在集合G中，這也就達到了選擇算法的目標：獲得足夠好的方案[1]。那么序優化的目標函數可以表示為：

其中AP意為Alignment Probability，表示對齊概率，而P{AP}={IGn JsI≥m），m就表示了想要達到的對齊水平。具體計算過程和分配過程見文獻[1]。

近年來，基于序優化思想，在排序和選擇問題中，已經提出了各種算法。方差比方法[l4]，基于兩階段的方法㈣[15][16]，這兩種方法均是根據仿真結果的樣本方差為方案候選方案分配仿真采樣次數?；跓o差異區的方法[17]和它的幾個變體[18][19]采用頻率派的方法。基于無差異區的方法選擇屬于無差異區的候選方案，這些候選方案的仿真結果并沒有比最佳方案明顯差，然后將大部分資源分配給屬于無差異區的候選項。在文獻[20]和文獻[21]中，Chen等人基于序優化提出了最優計算預算分配方法，該方法根據仿真結果的樣本均值和方差計算分配給各候選方案的仿真采樣次數。

本文在下一節介紹了最優計算量分配算法，第3節介紹了本文提出的算法，第4節是實驗結果及分析，第5節對本文做了總結。

2 最優計算量分配算法的介紹

最優計算量分配是Chen提出的一種基于貝葉斯理論的序優化方法[20][21]。該算法基于序優化中“序比值更好獲得”的思想，在給定仿真采樣資源的前提下，根據仿真獲得的候選方案（design）評價值，給不同候選方案分配不同的仿真采樣次數，并且著重分配給易與目標混淆的候選方案，從而提高算法的效率[21]。此外，該算法還對目標函數進行了嚴格的數學推導，為各候選方案應該獲得多少仿真采樣提供了理論基礎。

該算法有這樣的假設，假設候選方案i的性能服從正態分布N（μi，σ2），且相互獨立。此外，其期望和方差未知，可通過仿

之后，基于最初的最優計算量分配，發展出了很多變體。Fu等人提出了具有相關性的采樣情況下的最優計算量分配算法[22]。Chen等人提出了一種應用于選擇最佳方案子集的最優計算量分配算法，這種最優計算量分配算法可以從方案候選集中選擇出最佳的m個方案[23]。之后Zhang等人又對選擇最佳m各方案的最佳計算量分配算法進行了改進[24]。He等人提出了運用期望機會成本來選擇最佳方案的最優計算量分配算法[25]。

其中有些是以最大化正確選擇概率（Probability of CorrectSelection.PCS）為目標來進行計算量的分配，有些是以最小化期望機會成本（Expected Opportunity Cost，EOC）為目標來進行計算量的分配。本文主要是對基于正確選擇概率的最優計算量分配算法進行拓展，因此下面介紹原始的最優計算量分配。

最初的OCBA分配的目標就是找到真實最佳方案廣，可以表示為[21]

上式表明了各候選方案的方差和與最佳方案6性能差距決定了其獲得仿真采樣的次數。方差越大，與最佳方案6性能差距越小，獲得的仿真資源越多，而當前最佳方案6獲得的仿真資源最多。這也符合前面所說的資源集中于易混淆對象的思想。在分配過程中，主要運用了漸進最優的思想，逐步的最大化APCS。

3 基于錦標賽思想的最優計算量分配算法

原始OCBA以及其變體在序優化問題上性能較好，但是仔細比較發現，這些算法的候選方案個數都偏小，而在如今的生活中，數據規模早已是百萬、千萬級別，個人、企業面對的選擇也更多了。在這種情況下，我們在考慮最好的選擇的同時，也有必要縮短我們的選擇時間。

而錦標賽選擇[26]的思想是在有大量參賽選手時，兩兩比較選出優勝選手，再從優勝選手中進行選擇，從而減少比較的時間。受此思想啟發，面對大規模序優化問題，可以先選擇一半甚至更少的精英方案，再對方案進行仿真采樣分配。

基于這一現實需求，受錦標賽選擇思想啟發，本文在OCBA的基礎上提出一個新的算法：先選擇精英子集，再對子集進行最優計算量分配，目標同樣是最大概率的選出最佳方案。

表1中是本文要用到的數學符號及其定義。

3.1 問題分析

本文的目標是在候選規模較大時，找到這樣一種計算量分配方案，能快速選出最佳方案并且正確選擇概率最大。假設和最優計算量分配一致，候選方案性能的期望方差未知。由中心極限定理可知，大量仿真采樣可以獲得期望的估計[21]。假設每個候選方案的輸出相互獨立，且候選方案i的輸出服從N（μi，σ2），那么μi就表示了方案i的真實性能，在無信息先驗分布的情況下，基于貝葉斯理論對μi進行后驗參數估計[11]得到

受錦標賽思想啟發，先選出精英子集，再從精英子集中進行分配會更高效，因為這相當于子集之外的候選方案都不考慮分配仿真采樣次數。精英子集Ss是從k個候選方案中通過仿真采樣均值比較得出的s.k個均值最小的方案集合，其中s為精英方案占總候選方案的比例，

Ss=[i前s-k個最小的μ]

順序不是必須的，是前s·k個最小均值的方案即可。不失一般性，我們的正確選擇事件就變為

APCS即為PCS的下界，也就是近似正確選擇概率（Approxi-mate Probability of Correct Selection，APCS）。而近似正確選擇概率可以非常容易快速的計算出來。數值實驗表明，使用APCS仍然可以高效的選出最佳方案[20][21]。因此，本文選擇使用APCS來估計PCS。那么目標函數從（3.4）變為

基于OCBA程序框架，根據該定理本章提出了先選擇top-s再進行分配地算法，命名為OCBAss。在程序初始化階段，就對k個方案分別進行n0次仿真采樣，以獲得方案性能的采樣信息，之后每一次循環都根據之前的仿真結果先選出精英子集Ss，再使用定理來計算Ss中各方案的仿真采樣次數，每次循環新增△次仿真采樣，直到T用完。該算法過程如表2所示。

可以看到，隨著仿真的進行，精英子集Ss中的方案和方案6都可能會發生變化，但是隨著仿真采樣次數T—∞，算法會收斂到最佳方案。精英子集Ss的選擇會使得仿真過程加快，因為每次循環都只用對s·k個方案進行分配和仿真。

4 實驗結果及分析選擇概率P{CS}。環境1的實驗結果見圖2，環境2的實驗結果見圖3：

從圖2的（a）（b）（c）可以看到，在環境1中，隨著仿真資源T的增加，PCS也隨之收斂，OCBAss的性能遠高于EA和PTV，和OCBA也不相上下。從仿真時間這一角度進行比較，如下表3所示，可以發現，隨著k的增加，OCBAss相對于OCBA節省的時間越多。

環境2各算法在不同規模下的收斂效果如圖3所示，隨著T的增加，PCS逐漸收斂，并且OCBAss遠勝于EA和PTV，和OC-BA不分伯仲，同樣優秀。而在仿真時間上，OCBAss優于OC-BA，可以更快速地得到同樣的PCS，而隨著k的增加，縮短的時間更多?？梢灶A測，隨著k增長到百萬、千萬，相比OCBA可以更快地達到預定的PCS。

綜上所述，OCBAss在規模較大的環境下具有更高的優勢。因為該算法增加了選擇了精英子集的步驟，使得計算量大大減少。實驗表明，盡管OCBAss策略簡單，但是在候選方案規模較大時，不僅仿真時間縮短數倍，正確選擇概率也和OCBA旗鼓相當。

5 結論

為了提升排序與選擇算法對隨機環境下大規模序優化問題的速度和精度，本文對序優化以及排序與選擇進行了研究，受錦標賽選擇思想啟發，提出了針對大規模序優化問題的算法-OCBAss，并且本文在2個環境3種規模的實驗中將其與EA，PTV，OCBA進行比較，結果表明了其優勢。而這也表明了，在候選方案規模成千上萬、上百萬時，該算法縮短的時間更多，而精度不減。今后，也可以將其應用到各個大規模的領域[3]一[9]。因此，在未來的工作中，對于排序選擇問題，可以對序優化思想進行深入的研究與探索，深入分析關鍵參數與步驟，提出更為有效的分配過程的同時，尋求理論突破。

參考文獻：

[1] Ho Y C，Sreenivas R S，Vakili P.Ordinal optimization ofDEDS[J]. Discrete event dynamic systems， 1992， 2（1）：61-88.

[2] Ho Y C.An ordinal optimization approach to optimal controlproblems[J]. Automatica， 1999， 35（2）：331-338.

[3] Gosavi， Abhijit. Simulation-Based Optimization： ParametricOptimization Techniques and Reinforcement Learning， 2nded.， New York， NY， USA： Springer， 2014： 1-35. vol. 55.

[4] Fu M C.Optimization for simulation： Theory vs. Practice[J].lNFORMS Journal on Computing， 2002， 14（3）：192-215.

[5] van RensburgJ J，He Y，Kleywegt A J.A computer simula-tion model of container movement by sea.Proceedings of theWinter Simulation Conference， 2005. lEEE， 2005：8 pp.

[6] Yun W Y，Choi Y S.A simulation model for container-termi-nal operation analysis using an object-oriented approach[J]. In-ternational Journal of Production Economics， 1999， 59（1-3）：221-230.

[7] Saanen Y A，Valkengoed M V.Comparison of three automatedstacking alternatives by means of simulation. Proceedings ofthe 37th conference on Winter simulation. Winter SimulationConference， 2005： 1567-1576.

[8] Lim A，Rodrigues B，Xu Z.A m-parallel crane schedulingproblem with a non-crossing constraint[J]. Naval Research Lo-gistics （NRL）， 2007， 54（2）：115-127.

[9] Yang C H，Choi Y S，Ha T Y.Simulation-based performanceevaluation of transport vehicles at automated container termi-nals[J]. OR spectrum， 2004， 26（2）：149-170.

[10] Chen C H，Wu S D，Dai L Ordinal comparison of heuristicalgorithms using stochastic optimization[J]. lEEE Transactionson Robotics and Automation， 1999， 15（1）：44-56.

[11] Chick S E.Bayesian analysis for simulation input and out- put. Winter Simulation Conference. 1997： 253-260.

[12] Law A M， Kelton W D，Kelton W D.Simulation modelingand analysis[M]. New York： McGraw-Hill， 2000.

[13] Chen C H.A lower bound for the correct subset-selectionprobability and its application to discrete-event system siruula-tions[J]. lEEE transactions on automatic control， 1996， 41（8）：1227-1231.

[14] Law， Averill M.， Simulation modeling and analysis， 4th ed[M]. New York， NY， USA： McGraw-Hill， 2007.

[15] Dudewicz E J， Dalal S R. Allocation of observations in rank-ing and selection with unequal variances[J]. Sankhya： The In-dian Journal of Statistics， Series B， 1975： 28-78.

[16] Rinott Y. On two-stage selection procedures and relatedprobability-inequalities[J]. Communications in Statistics-Theo-ry and methods， 1978， 7（8）：799-811.

[17] Kim S H， Nelson B L. Selecting the best system[J]. Hand-books in operations research and management science， 2006，13： 501-534.

[18] Hong L J， Nelson B L. The tradeoff between sampling andswitching： New sequential procedures for indifference-zone se-lection[J]. IIE Transactions， 2005， 37（7）：623-634.

[19] Tsai S C， Nelson B L. Fully sequential selection procedureswith control variates[J]. llE Transactions， 2009， 42（1）：71-82.

[20] Chen H C， Chen C H， Yucesan E. Computing efforts alloca-tion for ordinal optimization and discrete event simulation[J].IEEE Transactions on Automatic Control. 2000， 45（5）：960-964.

[21] Chen C H， Lin J， Yucesan E， et al. Simulation budget alloca-tion for further enhancing the efficiency of ordinal optimization[J]. Discrete Event Dynamic Systems， 2000， 10（3）：251-270.

[22] Fu M C， Hu J Q， Chen C H， et al. Simulation allocation fordetermining the best design in the presence of correlated sam-pling[J]. lNFORMS Journal on Computing， 2007， 19（1）：101-111.

[23] Chen C H， He D， Fu M， et al. Efficient simulation budget al-location for selecting an optimal subset[J]. lNFORMS Journalon Computing， 2008， 20（4）：579-595.

[24] Zhang S， Lee L H， Chew E P， et al. A simulation budget allo-cation procedure for enhancing the efficiency of optimal subsetselection[J]. lEEE Transactions on Automatic Control， 2015， 61（1）：62-75.

[25] He D， Chick S E， Chen C H. Opportunity cost and OCBA se-lection procedures in ordinal optimization for a fixed numberof alternative systems[J]. lEEE Transactions on Systems， Man，and Cybernetics， Part C （Applications and Reviews）， 2007， 37（5）：951-961.

[26]夏桂梅.基于錦標賽選擇遺傳算法的隨機微粒群算法[J]計算機工程與應用， 2007， 43（4）：51-53.

[27] Bratley P， Fox B L， Schrage L E. A guide to simulation[M]. Springer Science & Business Media. 2011.

[28] Winston W L， Venkataramanan M， Goldberg J B. Introduc-tion to mathematical programming[M]. Duxbury; Pacific Grove，CA： Thomson/Brooks/Cole， 2003.