基于錦標(biāo)賽思想的最優(yōu)計(jì)算量分配的研究

奚鈺佳

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

關(guān)鍵詞：隨機(jī)仿真;序優(yōu)化;最優(yōu)計(jì)算量分配;排序和選擇

中圖分類號：TP311.1 文獻(xiàn)標(biāo)識碼：A

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

開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

1 序優(yōu)化方法介紹

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

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

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

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

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

本文在下一節(jié)介紹了最優(yōu)計(jì)算量分配算法，第3節(jié)介紹了本文提出的算法，第4節(jié)是實(shí)驗(yàn)結(jié)果及分析，第5節(jié)對本文做了總結(jié)。

2 最優(yōu)計(jì)算量分配算法的介紹

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

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

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

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

最初的OCBA分配的目標(biāo)就是找到真實(shí)最佳方案廣，可以表示為[21]

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

3 基于錦標(biāo)賽思想的最優(yōu)計(jì)算量分配算法

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

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

基于這一現(xiàn)實(shí)需求，受錦標(biāo)賽選擇思想啟發(fā)，本文在OCBA的基礎(chǔ)上提出一個新的算法：先選擇精英子集，再對子集進(jìn)行最優(yōu)計(jì)算量分配，目標(biāo)同樣是最大概率的選出最佳方案。

表1中是本文要用到的數(shù)學(xué)符號及其定義。

3.1 問題分析

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

受錦標(biāo)賽思想啟發(fā)，先選出精英子集，再從精英子集中進(jìn)行分配會更高效，因?yàn)檫@相當(dāng)于子集之外的候選方案都不考慮分配仿真采樣次數(shù)。精英子集Ss是從k個候選方案中通過仿真采樣均值比較得出的s.k個均值最小的方案集合，其中s為精英方案占總候選方案的比例，

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

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

APCS即為PCS的下界，也就是近似正確選擇概率（Approxi-mate Probability of Correct Selection，APCS）。而近似正確選擇概率可以非常容易快速的計(jì)算出來。數(shù)值實(shí)驗(yàn)表明，使用APCS仍然可以高效的選出最佳方案[20][21]。因此，本文選擇使用APCS來估計(jì)PCS。那么目標(biāo)函數(shù)從（3.4）變?yōu)?/p>

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

可以看到，隨著仿真的進(jìn)行，精英子集Ss中的方案和方案6都可能會發(fā)生變化，但是隨著仿真采樣次數(shù)T—∞，算法會收斂到最佳方案。精英子集Ss的選擇會使得仿真過程加快，因?yàn)槊看窝h(huán)都只用對s·k個方案進(jìn)行分配和仿真。

4 實(shí)驗(yàn)結(jié)果及分析選擇概率P{CS}。環(huán)境1的實(shí)驗(yàn)結(jié)果見圖2，環(huán)境2的實(shí)驗(yàn)結(jié)果見圖3：

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

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

綜上所述，OCBAss在規(guī)模較大的環(huán)境下具有更高的優(yōu)勢。因?yàn)樵撍惴ㄔ黾恿诉x擇了精英子集的步驟，使得計(jì)算量大大減少。實(shí)驗(yàn)表明，盡管OCBAss策略簡單，但是在候選方案規(guī)模較大時，不僅仿真時間縮短數(shù)倍，正確選擇概率也和OCBA旗鼓相當(dāng)。

5 結(jié)論

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

參考文獻(xiàn)：

[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]夏桂梅.基于錦標(biāo)賽選擇遺傳算法的隨機(jī)微粒群算法[J]計(jì)算機(jī)工程與應(yīng)用， 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.