董攀 陳陽(yáng)

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

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

中圖分類(lèi)號(hào)：TP301.6 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2014）06-53-03

0 引言

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

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

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

1 有時(shí)間窗車(chē)輛路徑問(wèn)題的定義

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

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

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

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

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

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

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

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

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

3 數(shù)值試驗(yàn)分析

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

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

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果及分析

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

[3] 劉武陽(yáng)，于世偉，陳英武等.帶有動(dòng)態(tài)參數(shù)決策模型的改進(jìn)蟻群優(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è)自動(dòng)化，2011.33（3）：66-69

[6] 萬(wàn)旭，林建良，楊曉偉.改進(jìn)的最大最小螞蟻算法在有時(shí)間窗車(chē)輛路徑問(wèn)題中的應(yīng)用[J].計(jì)算機(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）.