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

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

[關(guān)鍵詞] 蟻群優(yōu)化算法 旅行商問題 蟻群系統(tǒng) 信息素更新 路徑安排

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

一、TSP模型

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

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

二、蟻群算法

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

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

(3.1)

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

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

(3.2)

其中為到目前為止找出的全局最優(yōu)路徑，算法已經(jīng)發(fā)現(xiàn)的最好解稱為。除了全局信息素更新外，算法還在解構(gòu)造過程中通過弧后立即進行局部的信息素更新，其更新方法如下:

(3.3)

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

蟻群算法基本實現(xiàn)流程：

初始化各參數(shù)For NC=1 to 循環(huán)次數(shù) dobeginfor k=1 to m dobegin

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

三、應(yīng)用檢驗

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

總行程為L=18.1(km)

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

參考文獻:

[1]李軍謝秉磊郭耀煌:非滿載車輛調(diào)度問題的遺傳算法.系統(tǒng)工程理論方法應(yīng)用，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]華寶玉王雪峰馮英浚:有時間窗約束單車場單車型非滿載車輛調(diào)度問題的遺傳算法.哈爾濱商業(yè)大學(xué)學(xué)報(自然科學(xué)版)，2002，6: 621～624