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

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

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

一、TSP模型

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

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

二、蟻群算法

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

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

(3.1)

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

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

(3.2)

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

(3.3)

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

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

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

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

三、應(yīng)用檢驗(yàn)

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

總行程為L(zhǎng)=18.1(km)

表1.郵局和各個(gè)村莊的坐標(biāo)

參考文獻(xiàn):

[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]華寶玉王雪峰馮英浚:有時(shí)間窗約束單車場(chǎng)單車型非滿載車輛調(diào)度問題的遺傳算法.哈爾濱商業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版)，2002，6: 621～624