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

董攀 陳陽

摘 要： 研究在不使用局部搜索情況下參數組合對改進型蟻群算法的影響。以帶時間窗的車輛路徑問題為例，針對基于最大最小蟻群算法的改進蟻群算法中的五個參數，運用均勻設計法對最優參數配置問題進行了研究。仿真實驗表明改進的蟻群算法效果明顯，能有效解決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]采用自適應調整信息素增量和信息素揮發率都屬于此類。……