朱蘭劍

摘 要：啟發(fā)式算法的參數(shù)會對其求解效率有著重要影響。如何確定算法中各個參數(shù)的值，是使用啟發(fā)式算法的研究人員不得不面對的問題。本文運用實驗設(shè)計的方法（DOE），去確定局部分支算法（LB）的參數(shù)取值，使其能夠有效地解決循環(huán)瓶頸分配問題。

關(guān)鍵詞：實驗設(shè)計 局部分支算法 循環(huán)瓶頸 分配問題

一、引言

實踐證明，啟發(fā)式算法有效地能夠求解組合優(yōu)化問題，但是啟發(fā)式算法所發(fā)現(xiàn)的解與問題的最優(yōu)解之間的偏離程度往往是很難預(yù)計的。因此，通過控制啟發(fā)式算法的參數(shù)獲得最好的效果十分必要。

二、實施過程

實驗設(shè)計是對系統(tǒng)的輸入變量作一些有目的的改變，以使能夠觀察到和識別出引起輸出響應(yīng)變化的緣由[1]。本文運用實驗設(shè)計的方法，去確定局部分支算法的參數(shù)，主要包含四個步驟：成子問題集選?。淮_定所研究參數(shù)的開始水平和它們的變化范圍；為子問題集中的每個問題選定合適的參數(shù)值；找到對所有問題合適的參數(shù)值。下面主要從這四個步驟來詳細(xì)說明算法參數(shù)確定過程。

（一）子問題集的選取

本文所應(yīng)用的問題是一類比較特殊的分配問題[2]，上述問題的算例共有8個規(guī)模，每個規(guī)模有10個不同的算例，所以在綜合考慮實驗時間和算例的代表性，選取的算例規(guī)模為{15，25，35，50}，并從每個規(guī)模中隨機(jī)選取1個算例，對應(yīng)的序列為{7，5，10，2}，即規(guī)模數(shù)為15，選第7個算例，規(guī)模為25，選第5個算例等。

（二）開始水平和變化范圍的確定

局部分支算法是MatteoFischetti等2003年提出的一種求解混合整數(shù)規(guī)劃的方法[3]，影響其效率的參數(shù)主要有五個： k海明距離；dv多樣化次數(shù)；root-time根節(jié)點計算時間；total-time算法計算的時間；node-time節(jié)點的計算時間。

通過對本算例的預(yù)先處理，發(fā)現(xiàn)多樣化次數(shù)對算法的影響不顯著，所以本文忽略多樣性這一參數(shù)（固定為20），只考慮其余四個參數(shù)。為了粗略地確定設(shè)計中心，我們發(fā)現(xiàn)k = 100，root-time = 20，total-time = 600，node-time = 75，算法能夠取得較好的解，所以選取上述參數(shù)值作為本文的設(shè)計中心。接著確定每個參數(shù)的變化范圍，例如要確定參數(shù)k的變化范圍，我們將參數(shù)dv、total-time，node-time固定在上述設(shè)計中心的值，然后對參數(shù)k的值進(jìn)行變動（增加或減少），直到其所求得的目標(biāo)值連續(xù)多次沒有變化（或變差）為止，表1給出了確定規(guī)模為35的參數(shù)k的變化范圍的數(shù)據(jù)。

表1參數(shù)k的變化范圍

表5各參數(shù)的步長

根據(jù)表5的結(jié)果，以設(shè)計中心（100，20，75，600）為起始點，按照新的步長調(diào)整各參數(shù)的值，進(jìn)行實驗。調(diào)整過程中會發(fā)現(xiàn)部分參數(shù)會達(dá)到其邊界值（低水平或高水平），這時我們固定這部分參數(shù)值，繼續(xù)調(diào)整其他參數(shù)，直到所有參數(shù)都達(dá)到其邊界。對規(guī)模為50的算例，參數(shù)調(diào)整結(jié)果如表6所示，我們發(fā)現(xiàn)當(dāng)total-time = 690，其他參數(shù)將不發(fā)生變化，這時為了減少試驗時間，直接令total-time = 1000，若其求得的解大于已知的較好解，那么其中間（即690-1000）的值也很難發(fā)現(xiàn)更好的值，所以可以省略；反之則要進(jìn)一步確定該參數(shù)值，本文用二分法處理這樣的情況。

表6規(guī)模為50的算例的參數(shù)調(diào)整過程

由以上結(jié)果，并結(jié)合找到最好解的時間，可以知道子問題集中不同規(guī)模算例的最合適參數(shù)組合，詳細(xì)參數(shù)組合見表7：

表7 各規(guī)模算例的參數(shù)組合

（三）最優(yōu)的參數(shù)組合

根據(jù)表7結(jié)果，我們發(fā)現(xiàn)不同規(guī)模的參數(shù)值相差比較明顯，所以我們按不同規(guī)模來確定合適的參數(shù)組合。對整個問題的算例而言，還需要確定規(guī)模為20，30，40，45離那個參數(shù)組合更近，運行的結(jié)果如表8所示：

表8 規(guī)模為20，30，40，45的參數(shù)組合

最后我們確定規(guī)模 {15，20，25，30，35，40，45，50} 算例較好的參數(shù)組合對應(yīng)結(jié)如下：（100，50，15，648）， （100，50，15，648）， （130，50，15，624），（130，50，15，648）， （100，50，90，648）， （100，50，15，648）， （130，50，15，624），（25，10，15，675）。

三、結(jié)論

本文運用實驗設(shè)計（DOE）方法對局部分支算法（LB）的參數(shù)進(jìn)行了科學(xué)的調(diào)整，通過上述四個步驟，我們確定了不同規(guī)模算例的參數(shù)組合，發(fā)現(xiàn)不同規(guī)模的算例參數(shù)組合差距比較顯著，所以我們針對不同規(guī)模的算例，分別給出了不同的參數(shù)組合，能夠有效地求解循環(huán)瓶頸分配問題。

參考文獻(xiàn)：

[1]汪仁宮，陳榮昭.實驗設(shè)計與分析[M]. 中國統(tǒng)計出版社，1996.

[2]Kulkarni， Anand J.， M.F. Baki， Ben A. Chaouch. 2016. Application of the cohort-intelligence optimization method to three selected combinatorial optimization problems[J]. European Journal of Operational Research 250 427–447.

[3]MatteoFischetti， Andrea Lodi. Local Branching [j].Math.Program， Ser.B98 ： 23-47（2003）.

[4]SP. Coy， BL. Golden， GC. Runger， EA. Wasil. Using Experimental Design to Find Effective parameter settings for heuristics[j]. Journal of Heuristics，7：77-97（2001）