改進型蟻群算法參數優化研究

董攀 陳陽

摘 要： 研究在不使用局部搜索情況下參數組合對改進型蟻群算法的影響。以帶時間窗的車輛路徑問題為例，針對基于最大最小蟻群算法的改進蟻群算法中的五個參數，運用均勻設計法對最優參數配置問題進行了研究。仿真實驗表明改進的蟻群算法效果明顯，能有效解決Solomon數據集中的R類和RC類問題，且具有較強的魯棒性。對最優參數的局部調整沒有明顯提高算法獲取最優解能力的問題，分析了其可能的原因。

關鍵詞： 最大最小蟻群算法； 均勻設計； 有時間窗車輛路徑問題； Solomon數據集

中圖分類號：TP301.6 文獻標志碼：A 文章編號：1006-8228（2014）06-53-03

0 引言

車輛路徑問題（Vehicle Routing Problem，VRP）屬于組合優化問題，其理論涉及到運籌學、管理學、交通運輸、計算機應用等多個學科。VRP問題中加入節點可訪問的時間窗約束即成為有時間窗車輛路徑問題（Vehicle Routing Problem with Time Windows， VRPTW）。由于現實生活中很多問題可以歸結為VRPTW，因此VRPTW的研究受到學術界的廣泛重視。

蟻群算法雖然具有較強魯棒性，但存在搜索速度慢和容易出現停滯的缺點。為此，學術界除了引進其他算法來加強其搜索能力外，還從蟻群算法本身的參數設置角度來克服其弱點，目前有三種方式。第一種是用其他算法來自動篩選參數，例如劉利強[1]等利用粒子群優化算法，將離子當前位置作為算法參數來優選ACS算法的參數。第二種是動態調整蟻群算法參數，如藺媛媛等[2]采用自適應調整q參數，劉武陽等[3]采用自適應調整信息素增量和信息素揮發率都屬于此類。第三類是通過研究參數與最優解的關系，如王明芳[4]通過數據仿真來研究全局最優解與參數的關系，甘屹[5]則是通過正交優化實驗來研究算法之間的交互作用以提高求解精度和收斂速度。

本文通過基于最大最小蟻群算法（MMAS）的改進來研究參數設置在有時間窗車輛路徑問題上的應用。通過均勻設計法，找出參數的最優組合。對Solomon標準數據集的計算，驗證了算法和參數設置的有效性。

1 有時間窗車輛路徑問題的定義

VRPTW的一般定義如下：從某一物流中心用多臺配送車輛從多個客戶取貨，每個客戶的位置和需求量和需求時間一定，每個客戶只能由一臺車輛服務一次，要求合理安排車輛配送路線，使目標函數得到最優，即在不違背約束條件下所用車輛數最少和行走路線長度最短。本文將最小化車輛數量作為第一目標，最小化車輛行駛路線長度作為第二目標。

2 最大最小蟻群算法及其在有時間窗車輛路徑問題中的應用

MMAS對AS的關鍵改進在于將路徑上的信息素濃度限定[τmin，τmax]之間，這較好地避免了搜索陷入局部最優解。因為在搜索過程中，隨著信息素的揮發和累積，某些路徑上的信息素濃度會遠遠高于其他路徑，從而導致搜索過早停滯。

2.1 狀態轉移概率

螞蟻在選擇下一個節點時，在滿足容量約束和時間窗約束下，需要考慮如下三個因素：①通往下個節點的路徑長度以及路徑上的信息素濃度[6]；②時間窗因素的擇優性[6]，由下個客戶j的時間窗寬度和所在客戶i到達下個客戶j的時間等因素決定，這種擇優性的優先原則為，需等待時間較短優先原則和時間窗較小優先原則；③基于Wissner-Gross，A.D.[7]的事物傾向于向自由度大的方向進化的理論，潛在下一可行節點數多的節點有優先權。

其中，Ω={vj|vj為可被訪問的客戶}，v0為配送中心。為客戶j的時間窗；tij為從客戶i到達客戶j的時間（等于開始為客戶i服務的時刻+客戶i所需服務時間+從客戶i到客戶j的時間）；VCij為客戶j的下一潛在可被訪問客戶數，由所有滿足LTi+Si+Lij?LTj的客戶組成。τij為vi和vj之間路徑上的信息素；ηij為路徑可見性，這里ηij=1/dij，dij為客戶i與j之間路徑長度。α和β為路徑上信息素與路徑可見性的權重。

2.2 動態啟發式信息更新

因為VRPTW問題的第一目標值是最小化車輛數量，因此為強化改進蟻群算法構建最小化車輛數量路徑的能力，本文對上面狀態轉移概率中的信息素和路徑長度啟發式做如下改變：

該式中，antTypei為信息素更新的螞蟻類型，rand（）為隨機值，t為信息素更新隨機因子。因為ηij為路徑值啟發式信息，因此將其以t的概率增加螞蟻構建更優的車輛數量的解集合。

3 數值試驗分析

3.1 均勻設計優化參數

蟻群算法參數優化是一個多因素多水平優化設計問題，對于參數設定不可能遍歷所有可能。利用均勻設計和均勻設計表，選取具有代表性的樣本進行試驗，能極大減少試驗的次數，而且能取得較好的參數配置。

本文的改進蟻群算法有五個需要優化的算法參數：①信息素權重α；②路徑可見性權重β；③信息素揮發率ρ；④最好可能信息素量PBest；⑤信息素更新隨機因子t。

參照原始MMAS取值，并經過逐步改進，這里首先選取以下參數組合進行初步計算：α=1；β=2；ρ=0.02；PBest=0.05；t=0.5。

通過比較原始MMAS結果和參數未優化前結果（見表4的4-7列），可知改進的蟻群算法在C類數據集上不具有優勢，在R類和RC類數據集上比較有優勢。為最大限度獲取解的優化，本文選取R103和RC104進行參數優化試驗，同時確定試驗的參數范圍為：α∈（0，2]；β∈[1，3]；ρ∈[0.01，0.03]；PBest∈[0.04，0.06]；t∈[0，1]。

根據因素數量，可以選擇、和，從它們的使用表可以查到，當s=5時，它們的偏差分別為0.2414，0.4286和0.2272。因此這里選擇作為本文的均勻設計表。根據該表，對各因素取12個水平如表1。

3.2 實驗結果及分析

受限于篇幅，我們只將每類數據的前三項結果列出，見表4。

4 結束語

研究表明，本文對最大最小蟻群算法的改進效果明顯，由于蟻群算法本身的魯棒性，加上初期算法參數的逐步改良，后期蟻群算法參數在一定范圍內的波動不會明顯改變計算結果。同時，蟻群算法受到兩大因素的制約，一是必須達到運能和時間窗瓶頸才能返回，二是時間窗大的節點擁有更為靈活的組合方式。這使得局部搜索算法成為構造高效蟻群算法的必要組成部分，這也是我們下一步研究的關鍵性問題。此外，盡量改善C類問題的計算效能也是值得研究的問題。

參考文獻：

[1] 劉利強，戴運桃，王麗華.蟻群算法參數優化[J].計算機工程，2008.34（11）：208-210

[2] 藺媛媛，朱耀庭，賈雯.蟻群算法的參數優化[J].天津工程師范學院學報，2009.19（3）：30-33

[3] 劉武陽，于世偉，陳英武等.帶有動態參數決策模型的改進蟻群優化算法[J].科學技術與工程，2010.10（2）：435-440

[4] 付明，王麗芳.蟻群算法中最優參數設置研究[J].科技信息，2010.20：765-766

[5] 甘屹，李勝.蟻群算法的參數優化配置研究[J].制造業自動化，2011.33（3）：66-69

[6] 萬旭，林建良，楊曉偉.改進的最大最小螞蟻算法在有時間窗車輛路徑問題中的應用[J].計算機集成制造系統，2005.11（4）： 572-576

[7] Wissner-Gross，A.D.， C.E.Freer. Causal Entropic Forces[J].PhysicalReview Letters 110，168702（2013）.