朱蘭劍

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

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

一、引言

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

二、實(shí)施過(guò)程

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

（一）子問(wèn)題集的選取

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

（二）開(kāi)始水平和變化范圍的確定

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

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

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

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

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

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

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

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

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

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

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

最后我們確定規(guī)模 {15，20，25，30，35，40，45，50} 算例較好的參數(shù)組合對(duì)應(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é)論

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

參考文獻(xiàn)：

[1]汪仁宮，陳榮昭.實(shí)驗(yàn)設(shè)計(jì)與分析[M]. 中國(guó)統(tǒng)計(jì)出版社，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）