董攀 陳陽

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

關(guān)鍵詞： 最大最小蟻群算法； 均勻設(shè)計； 有時間窗車輛路徑問題； Solomon數(shù)據(jù)集

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

0 引言

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

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

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

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

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

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

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

2.1 狀態(tài)轉(zhuǎn)移概率

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

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

2.2 動態(tài)啟發(fā)式信息更新

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

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

3 數(shù)值試驗分析

3.1 均勻設(shè)計優(yōu)化參數(shù)

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

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

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

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

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

3.2 實驗結(jié)果及分析

受限于篇幅，我們只將每類數(shù)據(jù)的前三項結(jié)果列出，見表4。

4 結(jié)束語

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

參考文獻：

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

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

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

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

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

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

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