基于新型的蟻群算法在路徑安排的研究

[摘要] 蟻群優化算法作為一種新型的啟發式算法，在解決組合優化問題如旅行商問題，中可以得到較好的次優解而備受重視，但蟻群算法的運算過程由于受各種參數設置以及信息素更新方式的影響，存在著早熟收斂，容易陷入局部最優的現象。本文在這方面應用蟻群系統來進行嘗試解決，并將其應用到郵遞員的路徑安排中進行實證檢驗。

[關鍵詞] 蟻群優化算法 旅行商問題 蟻群系統 信息素更新 路徑安排

路徑優化問題屬于典型的組合優化問題，因為在對其求解的過程中存在著“組合爆炸”等NP類難題，蟻群算法具有良好的并行性、魯棒性以及自組織性，并且可以對其不足之處不斷進行更新改造，容易與其他啟發式算法結合等優點，在解決旅行商問題，二次分配問題等收到很好的效果。

一、TSP模型

旅行商問題TSP(Traveling Salesman Problem)：一個旅行商（推銷員）想到n個城市推銷商品，他面臨如何選擇一條道路使自己走完一遍后回到起點且所走路徑最短的問題。旅行商問題(TSP)的數學模型:

這里，V是一個城市集合，|S|為集合S中所含圖G的頂點個數。前面兩個約束(2.3)、(2.4)意味著對每個頂點而言，僅有一條邊進和一條邊出，約束(2.5)則保證了沒有任何子回路解的產生。

二、蟻群算法

螞蟻優化算法(Ant Colony Optimization. ACO)是一種隨機搜索算法。通常以螞蟻系統(AS)求解平面上n個城市的TSP問題為例來說明蟻群算法模型。m:中螞蟻的數量;dij:城市i和j之間的距離;:t時刻在i與j連線上殘留的信息量。

蟻群系統(Ant Colony System， ACS)的狀態轉移規則：一只位于城市i的螞蟻通過應用式(3.1)給出的規則選擇下一個將要移動到的城市j，螞蟻選擇下一條路徑的方法是：

(3.1)

其中，:城市i到城市j可望程度，有記錄螞蟻k已經訪問過的城市的禁忌表；q為均勻分布在[0，1]上的一個隨機變量，q0為在[0，1]上的參數，當時，使用隨機選擇的方式選擇下一條路徑（稱為開發exploitation）；當時，選擇概率最高的路徑（稱為探險方式exploration）；

僅僅是天才螞蟻才允許在每次解構造完成后釋放信息素，而對于非已知最優路徑上的信息素則也不進行揮發操作，此稱為全局信息素更新。其更新方法如下：

(3.2)

其中為到目前為止找出的全局最優路徑，算法已經發現的最好解稱為。除了全局信息素更新外，算法還在解構造過程中通過弧后立即進行局部的信息素更新，其更新方法如下:

(3.3)

其中，設置可以產生好的結果，n是TSP問題中城市的個數，是通過最近鄰居方法構造的解的長度。實驗表明，局部更新規則可以有效的避免螞蟻收斂到同一路徑。

蟻群算法基本實現流程：

初始化各參數For NC=1 to 循環次數 dobeginfor k=1 to m dobegin

repeat 根據(4.1)式選擇下次訪問的城市jUntil螞蟻k完成一條路徑，計算其路徑長度并保存下來End根據(4.2)(4.3)式進行信息素更新end

三、應用檢驗

假設某一個小鎮 (i=0)有15個村莊，鎮上郵局的一名郵遞員負責每天騎車將報紙書信投遞到每個村莊i (i=1，2，…，15)，相鄰的村莊相互通路（如表1），且郵遞員一次可以完成所有的任務，并且騎車路線尋求最短。在例子中，設置參數。通過蟻群系統的模擬計算，最后得到郵遞員的最優行進路線:

總行程為L=18.1(km)

表1.郵局和各個村莊的坐標

參考文獻:

[1]李軍謝秉磊郭耀煌:非滿載車輛調度問題的遺傳算法.系統工程理論方法應用，2000 3，235～239

[2] Luca Maria Gambardella and Marco Dorigo:Solving symmetric and asymmetric TSP's by antcolonies. IEEE Int. Conf. Evolutionary Computation. IEEE-EC 96，1996，622～627

[3]Desrosiers J， Soumis F， Desrochers M. Routing with time windows by column generation [J].Networks，1984，14，545～565

[4]華寶玉王雪峰馮英浚:有時間窗約束單車場單車型非滿載車輛調度問題的遺傳算法.哈爾濱商業大學學報(自然科學版)，2002，6: 621～624