基于實驗設計方法確定啟發式算法的參數

朱蘭劍

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

關鍵詞：實驗設計 局部分支算法 循環瓶頸 分配問題

一、引言

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

二、實施過程

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

（一）子問題集的選取

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

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

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

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

表1參數k的變化范圍

表5各參數的步長

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

表6規模為50的算例的參數調整過程

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

表7 各規模算例的參數組合

（三）最優的參數組合

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

表8 規模為20，30，40，45的參數組合

最后我們確定規模 {15，20，25，30，35，40，45，50} 算例較好的參數組合對應結如下：（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）。

三、結論

本文運用實驗設計（DOE）方法對局部分支算法（LB）的參數進行了科學的調整，通過上述四個步驟，我們確定了不同規模算例的參數組合，發現不同規模的算例參數組合差距比較顯著，所以我們針對不同規模的算例，分別給出了不同的參數組合，能夠有效地求解循環瓶頸分配問題。

參考文獻：

[1]汪仁宮，陳榮昭.實驗設計與分析[M]. 中國統計出版社，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）