改進(jìn)型蟻群算法參數(shù)優(yōu)化研究

董攀 陳陽(yáng)

摘 要： 研究在不使用局部搜索情況下參數(shù)組合對(duì)改進(jìn)型蟻群算法的影響。以帶時(shí)間窗的車輛路徑問(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類和RC類問(wèn)題，且具有較強(qiáng)的魯棒性。對(duì)最優(yōu)參數(shù)的局部調(diào)整沒(méi)有明顯提高算法獲取最優(yōu)解能力的問(wèn)題，分析了其可能的原因。

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

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

0 引言

車輛路徑問(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)可訪問(wèn)的時(shí)間窗約束即成為有時(shí)間窗車輛路徑問(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ā)率都屬于此類。……