1 簡(jiǎn)介

旅行商問(wèn)題的傳統(tǒng)求解方法是遺 傳算法,此算法收斂速度慢,并不能獲得問(wèn)題的最優(yōu)解.為了求取旅行商問(wèn)題的最優(yōu)解,本文在闡述蟻群算法的基本原理,模型以及在旅行商問(wèn)題中的實(shí)現(xiàn)過(guò)程的基 礎(chǔ)上,提出了一種以蟻群算法構(gòu)建的基于MATLAB的求解旅行商問(wèn)題的方法,并最后通過(guò)仿真實(shí)驗(yàn)獲得了目前已知的最好解.

1.1 蟻群算法原理

　蟻群算法是受到對(duì)真實(shí)螞蟻群覓食行為研究的啟發(fā)而提出。生物學(xué)研究表明：一群相互協(xié)作的螞蟻能夠找到食物和巢穴之間的最短路徑,而單只螞蟻則不能。生物學(xué)家經(jīng)過(guò)大量細(xì)致觀察研究發(fā)現(xiàn),螞蟻個(gè)體之間的行為是相互作用相互影響的。螞蟻在運(yùn)動(dòng)過(guò)程中,能夠在它所經(jīng)過(guò)的路徑上留下一種稱(chēng)之為信息素的物質(zhì),而此物質(zhì)恰恰是螞蟻個(gè)體之間信息傳遞交流的載體。螞蟻在運(yùn)動(dòng)時(shí)能夠感知這種物質(zhì),并且習(xí)慣于追蹤此物質(zhì)爬行,當(dāng)然爬行過(guò)程中還會(huì)釋放信息素。一條路上的信息素蹤跡越濃,其它螞蟻將以越高的概率跟隨爬行此路徑,從而該路徑上的信息素蹤跡會(huì)被加強(qiáng),因此,由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象。某一路徑上走過(guò)的螞蟻越多,則后來(lái)者選擇該路徑的可能性就越大。螞蟻個(gè)體之間就是通過(guò)這種間接的通信機(jī)制實(shí)現(xiàn)協(xié)同搜索最短路徑的目標(biāo)的。我們舉例簡(jiǎn)單說(shuō)明螞蟻覓食行為：

如上圖a,b,c的示意圖：

a圖是原始狀態(tài)，螞蟻起始點(diǎn)為A，要到達(dá)E，中途有障礙物，要繞過(guò)才能到達(dá)。BC和BH是繞過(guò)障礙物的2條路徑(假設(shè)只有2條)。各個(gè)路徑的距離d已經(jīng)標(biāo)定。

b圖是t=0時(shí)刻螞蟻狀態(tài)，各個(gè)邊上有相等的信息素濃度，假設(shè)為15；

c圖是t=1時(shí)刻螞蟻經(jīng)過(guò)后的狀態(tài)，各個(gè)邊的信息素濃度，有變化；因?yàn)榇罅课浵伒倪x擇概率會(huì)不一樣，而選擇概率是和路徑長(zhǎng)度相關(guān)的。所以越短路徑的濃度會(huì)越來(lái)越大，經(jīng)過(guò)此短路徑達(dá)到目的地的螞蟻也會(huì)比其他路徑多。這樣大量的螞蟻實(shí)踐之后就找到了最短路徑。所以這個(gè)過(guò)程本質(zhì)可以概括為以下幾點(diǎn)：

1.路徑概率選擇機(jī)制信息素蹤跡越濃的路徑,被選中的概率越大

2.信息素更新機(jī)制路徑越短,路徑上的信息素蹤跡增長(zhǎng)得越快

3.協(xié)同工作機(jī)制螞蟻個(gè)體通過(guò)信息素進(jìn)行信息交流。

從螞蟻覓食的原理可見(jiàn),單個(gè)個(gè)體的行為非常簡(jiǎn)單螞蟻只知道跟蹤信息素爬行并釋放信息素,但組合后的群體智能又非常高螞蟻群能在復(fù)雜的地理分布的清況下,輕松找到蟻穴與食物源之間的最短路徑。這種特點(diǎn)恰恰與元啟發(fā)算法的特點(diǎn)相一致,蟻群優(yōu)化算法正是受到這種生態(tài)學(xué)現(xiàn)象的啟發(fā)后加以模仿并改進(jìn)而來(lái),覓食的螞蟻由人工蟻替代,螞蟻釋放的信息素變成了人工信息素,螞蟻爬行和信息素的蒸發(fā)不再是連續(xù)不斷的,而是在離散的時(shí)空中進(jìn)行。

從深層意義上來(lái)講,蟻群算法作為優(yōu)化的方法之一,屬于人工群集智能領(lǐng)域。人工群集智能,大都受自然群集智能如昆蟲(chóng)群和動(dòng)物群等的啟發(fā)而來(lái)。除了具有獨(dú)特的強(qiáng)有力的合作搜索能力外,還可以利用一系列的計(jì)算代理對(duì)問(wèn)題進(jìn)行分布式處理,從而大大提高搜索效率。

1.2 蟻群算法的基本流程

　　我們還是采用大連理工大學(xué)谷俊峰的PPT來(lái)說(shuō)明問(wèn)題，重要公式進(jìn)行截圖計(jì)算和解釋?zhuān)瑢?duì)PPT難以理解的地方進(jìn)行單獨(dú)解釋?zhuān)?/p>

1.2.1 基本數(shù)學(xué)模型

　　首先看看基本TSP問(wèn)題的基本數(shù)學(xué)模型：

　　問(wèn)題其實(shí)很簡(jiǎn)單，目標(biāo)函數(shù)就是各個(gè)走過(guò)路徑的總長(zhǎng)度，注意的就是距離矩陣根據(jù)實(shí)際的問(wèn)題不一樣，長(zhǎng)度是不一樣的。

1.2.2 蟻群算法說(shuō)明

　　在說(shuō)明群蟻算法流程之前，我們對(duì)算法原理和幾個(gè)注意點(diǎn)進(jìn)行描述：

1.TSP問(wèn)題的人工蟻群算法中，假設(shè)m只螞蟻在圖的相鄰節(jié)點(diǎn)間移動(dòng)，從而協(xié)作異步地得到問(wèn)題的解。每只螞蟻的一步轉(zhuǎn)移概率由圖中的每條邊上的兩類(lèi)參數(shù)決定：1. 信息素值也稱(chēng)信息素痕跡。2.可見(jiàn)度，即先驗(yàn)值。2.信息素的更新方式有2種，一是揮發(fā)，也就是所有路徑上的信息素以一定的比率進(jìn)行減少，模擬自然蟻群的信息素隨時(shí)間揮發(fā)的過(guò)程；二是增強(qiáng)，給評(píng)價(jià)值“好”(有螞蟻?zhàn)哌^(guò))的邊增加信息素。3.螞蟻向下一個(gè)目標(biāo)的運(yùn)動(dòng)是通過(guò)一個(gè)隨機(jī)原則來(lái)實(shí)現(xiàn)的，也就是運(yùn)用當(dāng)前所在節(jié)點(diǎn)存儲(chǔ)的信息，計(jì)算出下一步可達(dá)節(jié)點(diǎn)的概率，并按此概率實(shí)現(xiàn)一步移動(dòng)，逐此往復(fù)，越來(lái)越接近最優(yōu)解。4.螞蟻在尋找過(guò)程中，或者找到一個(gè)解后，會(huì)評(píng)估該解或解的一部分的優(yōu)化程度，并把評(píng)價(jià)信息保存在相關(guān)連接的信息素中。

1.2.3 蟻群算法核心步驟

　　更加我們前面的原理和上述說(shuō)明，群蟻算法的2個(gè)核心步驟是 路徑構(gòu)建 和 信息素更新。我們將重點(diǎn)對(duì)這2個(gè)步驟進(jìn)行說(shuō)明。

1 路徑構(gòu)建

　　每個(gè)螞蟻都隨機(jī)選擇一個(gè)城市作為其出發(fā)城市，并維護(hù)一個(gè)路徑記憶向量，用來(lái)存放該螞蟻依次經(jīng)過(guò)的城市。螞蟻在構(gòu)建路徑的每一步中，按照一個(gè)隨機(jī)比例規(guī)則選 擇下一個(gè)要到達(dá)的城市。隨機(jī)概率是按照下列公式來(lái)進(jìn)行計(jì)算的：

　　上述公式就是計(jì)算 當(dāng)前點(diǎn) 到 每一個(gè)可能的下一個(gè)節(jié)點(diǎn) 的概率。分子是 信息素強(qiáng)度 和 能見(jiàn)度 的冪乘積，而分母則是所有 分子的和值。這個(gè)剛開(kāi)始是很不容易理解的，我們?cè)谧詈髮?shí)例計(jì)算的時(shí)候，可以看得很清楚，再反過(guò)來(lái)理解公式。注意每次選擇好節(jié)點(diǎn)后，就要從可用節(jié)點(diǎn)中移除選擇的節(jié)點(diǎn)。

2 信息素更新

　　信息素更新是群蟻算法的核心。也是整個(gè)算法的核心所在。算法在初始期間有一個(gè)固定的濃度值，在每一次迭代完成之后，所有出去的螞蟻回來(lái)后，會(huì)對(duì)所走過(guò)的路線進(jìn)行計(jì)算，然后更新相應(yīng)的邊的信息素濃度。很明顯，這個(gè)數(shù)值肯定是和螞蟻所走的長(zhǎng)度有關(guān)系的，經(jīng)過(guò)一次次的迭代， 近距離的線路的濃度會(huì)很高，從而得到近似最優(yōu)解。那我們看看信息素更新的過(guò)程。

　　初始化信息素濃度C(0)，如果太小，算法容易早熟，螞蟻會(huì)很快集中到一條局部最優(yōu)路徑上來(lái)，因?yàn)榭梢韵胂?，太小C值，使得和每次揮發(fā)和增強(qiáng)的值都差不多，那么 隨機(jī)情況下，一些小概率的事件發(fā)生就會(huì)增加非最優(yōu)路徑的信息素濃度；如果C太大，信息素對(duì)搜索方向的指導(dǎo)性作用減低，影響算法性能。一般情況下，我們可以使用貪婪算法獲取一個(gè)路徑值Cnn，然后根據(jù)螞蟻個(gè)數(shù)來(lái)計(jì)算C(0) = m/Cnn ,m為螞蟻個(gè)數(shù)

　　每一輪過(guò)后，問(wèn)題空間中的所有路徑上的信息素都會(huì)發(fā)生蒸發(fā),然后，所有的螞蟻根據(jù)自己構(gòu)建的路徑長(zhǎng)度在它們本輪經(jīng)過(guò)的邊上釋放信息素，公式如下：

　　信息素更新的作用：1.信息素?fù)]發(fā)(evaporation)信息素痕跡的揮發(fā)過(guò)程是每個(gè)連接上的 信息素痕跡的濃度自動(dòng)逐漸減弱的過(guò)程，這個(gè)揮發(fā)過(guò)程主要用于避 免算法過(guò)快地向局部最優(yōu)區(qū)域集中，有助于搜索區(qū)域的擴(kuò)展。2.信息素增強(qiáng)(reinforcement)增強(qiáng)過(guò)程是蟻群優(yōu)化算法中可選的部 分，稱(chēng)為離線更新方式（還有在線更新方式）。這種方式可以實(shí)現(xiàn) 由單個(gè)螞蟻無(wú)法實(shí)現(xiàn)的集中行動(dòng)?；鞠伻核惴ǖ碾x線更新方式是 在蟻群中的m只螞蟻全部完成n城市的訪問(wèn)后，統(tǒng)一對(duì)殘留信息進(jìn)行 更新處理。

3 迭代與停止

　　迭代停止的條件可以選擇合適的迭代次數(shù)后停止，輸出最優(yōu)路徑，也可以看是否滿足指定最優(yōu)條件，找到滿足的解后停止。最重要的是，我剛開(kāi)始理解這個(gè)算法的時(shí)候，以為每一只螞蟻?zhàn)咭粭l邊就是一次迭代，其實(shí)是錯(cuò)的。這里算法每一次迭代的意義是：每次迭代的m只螞蟻都完成了自己的路徑過(guò)程，回到原點(diǎn)后的整個(gè)過(guò)程。

回到目錄

4 蟻群算法計(jì)算實(shí)例

　　使用PPT中的一個(gè)案例，非常直觀，對(duì)幾個(gè)符號(hào)錯(cuò)誤進(jìn)行了修改，主要是計(jì)算概率的乘號(hào)，結(jié)果沒(méi)有錯(cuò)誤：

　　過(guò)程總體還是比較簡(jiǎn)單的，注意理解公式，然后把公式和實(shí)例結(jié)合起來(lái)看，最好是拿筆自己手動(dòng)畫(huà)一畫(huà)，容易理解。

2 部分代碼

function ?j=Select_for_aca(R0,Ak,i,Allow,A,B,Pheromone,Heuristic);AllowCity=find(Allow(Ak,:)>0);AllowCity=Allow(Ak,AllowCity);Bpij=(Pheromone(i,AllowCity).^A).*(Heuristic(i,AllowCity).^B);[Bjv Bj]=max(Bpij);R=rand;if(R0>R) ? j=AllowCity(Bj);else ? Gpij=sum(Bpij); ? Pij=Bpij./Gpij; ? Pij=cumsum(Pij); ? Rd=rand;% 賭輪選擇 ? [Anx Any]=size(AllowCity); ? for FitIn=1:Any ? ? ? if Rd<=Pij(FitIn) ? ? ? ? ?j=AllowCity(FitIn); ? ? ? ? ?break; ? ? ? end ? endend

3 仿真結(jié)果

4 參考文獻(xiàn)

[1]黃麗韶, 朱喜基. 基于MATLAB的蟻群算法求解旅行商問(wèn)題[J]. 無(wú)線互聯(lián)科技, 2012(3):3.

博主簡(jiǎn)介：擅長(zhǎng)智能優(yōu)化算法、神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)、信號(hào)處理、元胞自動(dòng)機(jī)、圖像處理、路徑規(guī)劃、無(wú)人機(jī)等多種領(lǐng)域的Matlab仿真，相關(guān)matlab代碼問(wèn)題可私信交流。

部分理論引用網(wǎng)絡(luò)文獻(xiàn)，若有侵權(quán)聯(lián)系博主刪除。