1、安慶師范學(xué)院數(shù)學(xué)與計算科學(xué)學(xué)院2015屆畢業(yè)論文蟻群算法在路徑優(yōu)化中的應(yīng)用 作者：孫陽陽 指導(dǎo)老師：劉沖摘要 如何在繁雜的道路系統(tǒng)中選擇最優(yōu)的路徑是蟻群算法在路徑優(yōu)化中的重要問題.本文在理解蟻群算法概念和原理的基礎(chǔ)上，用數(shù)學(xué)形式給出了蟻群算法的數(shù)學(xué)模型，得到蟻群算法在應(yīng)用中的基本步驟.通過解決幾路徑規(guī)劃的問題，分析蟻群算法的優(yōu)缺點，就其發(fā)展現(xiàn)狀對該算法未來研究方向做展望. 關(guān)鍵詞 蟻群算法 算法模型 分析應(yīng)用 發(fā)展現(xiàn)狀及趨勢1 引言 隨著社會的飛速發(fā)展和信息的不斷交流，生活中越來越多的事情要求在短時間內(nèi)完成.如城市化的速度加快，如何選擇城市交通的最佳路徑已成為一個亟待解決的問題、以車載導(dǎo)航系統(tǒng)

2、為代表的路徑搜說問題以及近些年研究熱門（機器人路徑規(guī)劃問題）都需要一個最優(yōu)路徑解決方案.當(dāng)然隨著科學(xué)研究的發(fā)展，已經(jīng)有越來越多的方法來解決路徑優(yōu)化問題如：遺傳算法，A*算法，神經(jīng)網(wǎng)絡(luò)算法，人工勢場法，模糊邏輯法.但是這些算法都有不小的弊端：遺傳算法具有隨機優(yōu)化的特點，但是其局部搜素能力并不強，容易出現(xiàn)早熟現(xiàn)象；A*算法雖然往往能得到最優(yōu)的路徑，但是其局限性比較差而且算式中的啟發(fā)式函數(shù)如果選擇錯誤會使得在搜索中進入一個死循環(huán)；神經(jīng)網(wǎng)絡(luò)算法雖然具有學(xué)習(xí)能力很強的特點，但是訓(xùn)練過程比較困難，操作不太容易；模糊邏輯算法的適應(yīng)能力比較差.為此我們利用蟻群算法來解決實際應(yīng)用問題，研究和相關(guān)文獻得出算法的可

3、行性和優(yōu)越性.運用蟻群算法在幾路徑規(guī)劃上的應(yīng)用，掌握其解決實際問題的過程及應(yīng)用.2 蟻群算法2.1 蟻群算法的概念蟻群算法(ant colony optimization),又稱螞蟻算法，簡稱ACO.是由Dorigom、Maniezzov、Colorni等人在1992年所發(fā)表的論文提出的，其靈感來源于螞蟻在尋找食物中發(fā)現(xiàn)路徑的行為.它是一種模擬進化算法，通過人工模擬螞蟻覓食過程，即個體間的信息交流與合作不斷排除不適合的路途，最終尋找到從蟻穴到食物源的最短路徑.2.2蟻群算法的基本原理 螞蟻在搜尋食物過程中總能找到一條從蟻穴到到食物的最優(yōu)路徑，這是因為螞蟻在搜尋路徑上釋放一種特殊的信息素.當(dāng)它們

4、遇到一個還沒有被走過的路口時，會隨機的選擇一條路徑，而選擇的路徑與信息素的濃度有關(guān)，同時在該路徑上它們也會釋放自己的信息素.路徑越短，信息素濃度越大；反正路徑越長信息素堆積的越少.則過一段時間螞蟻選擇信息素濃度高的路徑的概率越來越大，而其它路徑隨著螞蟻越來越少的選擇信息素濃度逐漸減小，這一就形成了一個正反饋現(xiàn)象，最終指導(dǎo)整個蟻群找到從蟻穴到食物源的最短路徑.2.3 蟻群算法數(shù)學(xué)模型2.3.1 問題的描述 求解兩地間最優(yōu)路徑，即為求某兩地間用時最少的行進路線.如在一個城市中，有A、B兩個地點，從A到B有多條路徑線路可選，即求一條從A到B用時最少的路線.又比如在當(dāng)今熱門研究項目機器人路徑規(guī)劃問題中

5、，其本質(zhì)為在規(guī)劃空間內(nèi)依據(jù)環(huán)境信息，在某些評價標(biāo)準(zhǔn)下，找出從出發(fā)點到目標(biāo)點最優(yōu)的路線，比較有代表的問題是噴涂機器人，即在一個復(fù)雜曲面上如何規(guī)劃噴涂機器人的路徑，使其噴涂效率最高. 這些問題都符合蟻群算法的思想，因此可以用蟻群算法來求解.2.3.2模型的建立 首先將螞蟻覓食與路徑優(yōu)化問題進行對照如表1所示表1螞蟻覓食路徑優(yōu)化問題螞蟻要遍歷的各個路徑各個狀態(tài)整個蟻群經(jīng)過的一條完整的路徑解最短路徑最優(yōu)解信息素的濃度各狀態(tài)的吸引度信息素的更新狀態(tài)更新路徑的長度目標(biāo)函數(shù) 以旅行商問題（TSP）為例來構(gòu)建模型，定義路與路段的交叉口為節(jié)點，路段為邊.即TSP問題可描述為給定n個節(jié)點和每兩個節(jié)點之間的距離，要

6、尋找到一條路徑，從某個節(jié)點出發(fā)周游到其它節(jié)點一次且僅一次，最終回到出發(fā)節(jié)點的封閉環(huán)路徑長度最短.設(shè)節(jié)點數(shù)為n，螞蟻的數(shù)目為m，螞蟻從一個節(jié)點到另一個節(jié)點逐步完成搜索的過程.螞蟻k(k=1,2,3.m)，根據(jù)概率轉(zhuǎn)換的規(guī)則選擇下一個節(jié)點.由此可以生成一個由n個節(jié)點組成的行動路線，并伴有信息素的不斷更新.表示位于t時刻節(jié)點i的螞蟻數(shù)目.則有：d 表示兩個節(jié)點 i 和 j 之間的距離在基本蟻群算法模型中，人工智能螞蟻有以下特點： (1) 人工智能螞蟻具有記憶功能.每一個螞蟻k(k=1,2,3,.m)都有一個禁忌表()，即螞蟻經(jīng)過節(jié)點i()后，不能再經(jīng)過節(jié)點i.(2) 兩個節(jié)點的距離越近，能見度則越大

7、，被選擇的期望也就越高，由此來指引人工智能螞蟻的搜索.定義，被稱為期望因子，所以螞蟻k在t時刻從節(jié)點i轉(zhuǎn)移到節(jié)點j的概率可表示為： （1）其中表示禁忌例表中第s個元素，即螞蟻所走過的第s個節(jié)點；為螞蟻所允許到達的節(jié)點的集合，；期望因子表示對邊上的期望程度；表示信息素的相對重要程度；表示啟發(fā)式因子的相對重要程度.這里需要重點說明一下：當(dāng)取較大值時，螞蟻在選擇路徑的過程中路上的信息素非常重要；當(dāng)取較小值時蟻群算法變成隨機的貪婪算法.取較大值時會使整個蟻群陷入隨機搜索，這樣的話收斂速度較慢，很難找到最優(yōu)的結(jié)果，取較小值時雖然加快了收斂速度，這樣會很快得到一個最優(yōu)解但是容易陷入局部最優(yōu)的狀況.得到一個

8、最優(yōu)解但是容易陷入局部最優(yōu)的狀況. (3) 在蟻群算法中有一個非常重要的參數(shù)指標(biāo)，就是信息素濃度.蟻群在節(jié)點i到節(jié)點j時，算法會在路徑ij上遺留信息素，而信息素是時時刻刻動態(tài)變化的，它的多少決定蟻群選擇該路徑的概率大小.下面我們給出信息素濃度公式，設(shè)表示t時刻上的信息數(shù)濃度，則在t+n時刻此路徑上的信息素濃度為 （2）式中，它表示信息物質(zhì)的保留率；表示時刻t在螞蟻k在路徑ij上信息素的增量. （3）式中，Q表示螞蟻釋放的信息素量；L表示螞蟻k在本次周游遍歷中所經(jīng)過邊的總和長度,表示本次遍歷中螞蟻所用的時間總和.以上4個因素即禁忌列表、期望因子、概率轉(zhuǎn)換規(guī)則、信息素濃度蟻群系統(tǒng)路徑選擇的實現(xiàn)和信

9、息素更新策略，兩者互相配合，實現(xiàn)模型的正反饋機制，促進人工智能螞蟻收斂于最優(yōu)解.根據(jù)信息素更新策略的不同，又出現(xiàn)了3種不同的模型：蟻量模型、蟻密模型、蟻周模型. 蟻量模型 （4）在式中，Q為常量，信息素的增加量與邊ij的長度有關(guān). 蟻密模型 （5）在式中，Q為常量，也就是說信息素增加量只是個固定值，與邊ij的距離無關(guān). 蟻周模型 （6）在式中，Q是常量表示k只螞蟻的周游路線，即如果螞蟻經(jīng)過邊ij信息素的增加量為一個常量除以螞蟻k循環(huán)路線長度.這里信息素的增加量只與螞蟻的循環(huán)路線和Q有關(guān)，與沒有關(guān)系.在該模型中采用了全局信息的更新，較前兩種模型性能更優(yōu).原因是蟻周模型利用整體信息，即螞蟻在歷經(jīng)一

10、個循環(huán)路徑所釋放的信息素量與所得解的質(zhì)量成正比.周游路徑長度越短的螞蟻，釋放在該路徑上的信息素量越多，而前兩種模型在搜索解時，只使用了局部更新信息，沒有用到任何解的信息.2.3.3 選參原則 討論的參數(shù)包括.上文已經(jīng)提到信息素的相對重要程度和啟發(fā)式因子的重要程度對算法模型的影響，這里主要說下信息素蒸發(fā)系數(shù)，螞蟻數(shù)目以及螞蟻釋放的信息數(shù)量對搜索過程的影響.增大，殘留信息素減少，負反饋機制增強，隨機性增強，利與發(fā)現(xiàn)更多最優(yōu)解，但是收斂性降低.反之增大，殘留信息素增加，正反饋加強，雖然收斂性加快，但是隨機性減弱容易陷入一個范圍狹小的搜索圈，所以搜索質(zhì)量并不高.螞蟻數(shù)較小時，會使為走過路徑上的信息素減

11、小為0，即搜索的隨機性能會降低，雖然加快了收斂性，但是搜索的全局性能降低，算法穩(wěn)定性差，容易陷入過早的停滯.較大時，會使搜索路徑上的信息素濃度過于平均，收斂速度變慢.對于螞蟻釋放的信息素量來說是一個常量，越大，路徑信息素積累越多，收斂速度越快.顯然可見，參數(shù)的選擇對于搜索的準(zhǔn)確性是很重要的，這里選參原則如下：(1) 確定螞蟻數(shù)目,可參照“問題規(guī)模數(shù)約為螞蟻數(shù)目的1.5倍”;(2) 參數(shù)的粗調(diào)，常用的幾種組合有 (3) 參數(shù)細調(diào)，通常設(shè)定在0.5以下.2.4 蟻群算法的基本步驟（流程） 這里主要是以蟻周算法為例，總結(jié)蟻群算法的基本步驟. 流程框圖如下所示： 注: (1) 在流程圖中整個算法的迭代

12、過程是以N為刻度，（為最大迭代次數(shù)）.在迭代過程中以時間t為刻度(),螞蟻k根據(jù)概率轉(zhuǎn)換公式選擇下一個節(jié)點.(2) 禁忌表(tube):禁忌表是為了避免螞蟻走進同一個節(jié)點的數(shù)據(jù)結(jié)構(gòu).設(shè)為螞蟻k的禁忌列表，則螞蟻k走過節(jié)點i后就將該節(jié)點加入到自己的禁忌列表中，表示下一次不能再走節(jié)點i,用表示禁忌列表中第s個元素，即螞蟻k所走過的第s個節(jié)點，完成一此周游后，也即遍歷n個節(jié)點后，清空禁忌列表.3 蟻群算法的應(yīng)用分析 蟻群算法在優(yōu)化領(lǐng)域的應(yīng)用是很廣泛的，下面我們給出幾個例子進行分析，需要說明一下這些結(jié)果是基于實際情況和仿真實驗的基礎(chǔ)上得出的.3.1 蟻群算法在路徑規(guī)劃中的應(yīng)用3.1.1 利用計算機仿真

13、實驗求兩地最短路徑 蟻群算法在搜尋最短路徑時，對于每一步的擴展，螞蟻在下個節(jié)點的選擇上需要遵循以下兩個原則：每次所選的節(jié)點n在地圖上是可以移動的，在已訪問過的節(jié)點中不包括節(jié)點n.實驗步驟按照上文所給的基本步驟來求解. 本實驗是在VC+ +6.0的環(huán)境下進行的，實驗采用的是美國某州的電子拓撲圖，所選參數(shù)按照選參原則，最大循環(huán)的次數(shù)即迭代次數(shù).將20只螞蟻放置于起始節(jié)點，對于所有螞蟻用式(1)計算出螞蟻選擇路徑的轉(zhuǎn)換概率，利用賭輪法選擇出滿足原則的路徑，并根據(jù)公式(2)(4)對路徑上的信息素進行更新.重復(fù)這一步驟直到所有螞蟻搜尋到最短路徑時結(jié)束或者達到最大的迭代次數(shù)，循環(huán)結(jié)束時輸出最短路徑和長度.

14、在拓撲圖上選擇A.B兩點，利用蟻群算法求出兩地之間的最短路徑，最終得出的結(jié)果如圖1中粗線所示.因為20只螞蟻搜尋路徑的節(jié)點序列表比較大，這里就不在給出. 圖 1從計算的序列表格中可以看出20只螞蟻最終有17只螞蟻找到了最短路徑，另外3只螞蟻找到的雖然不是最短的路徑，但是都接近最短路徑，有可能是第短的路線，對于最優(yōu)路徑的搜尋引導(dǎo)仍具有利用價值.我們還將設(shè)計的參數(shù)數(shù)值做出了如下改變，在前50次循環(huán)中取，在后50次循環(huán)中取參數(shù)為.這樣做是為了防止最優(yōu)路徑上的信息素在搜尋過程中削弱，實驗結(jié)果表明有19只螞蟻找到了最短路徑，只有1只沒有找到準(zhǔn)確的最短路徑.這說明了，適當(dāng)對參數(shù)調(diào)整可以提高解的質(zhì)量.3.1

15、.2 蟻群算法在城市交通路徑選擇中的應(yīng)用 當(dāng)今的城鎮(zhèn)道路布局一般采用的是“棋盤+環(huán)線”的形式，在圖論中可表示如下：無向圖,表示結(jié)點集合(即交叉路口)，,表示所有邊的集合.表示該路段特性的數(shù)為路段的連接長度即.以消防隊員滅火搶險為例，我們都知道在突發(fā)事件中以最快的時間到達現(xiàn)場是最重要的，但是往往用時最短的路徑并不是最短路徑，因為這里要考慮到各條路徑的路況狀態(tài)，都會影響消防車的速度.因此在此優(yōu)化問題中我們將選取最優(yōu)時間來代替最短路徑，可設(shè)和分別表示在邊上影響消防車速度的路況狀態(tài)參數(shù)和交通狀態(tài)參數(shù).因為，可用來衡量，表示消防車在邊上所消耗的時間.可得出：式中是一個固定值.圖2為某市簡化的交通路網(wǎng)，一

16、共有13個節(jié)點，節(jié)點1表示消防車站，節(jié)點10和11為兩處失火點.給出了連線上的的數(shù)據(jù)，為實際路徑的長度，和是根據(jù)實際情況給出的數(shù)值.現(xiàn)求從消防站出發(fā)到兩失火點的最優(yōu)路徑.單一的蟻群算法顯然解決起來比較復(fù)雜，因此需要改進蟻群算法(具體改進措施參考文獻8).將蟻群算法與TA算法相結(jié)合，利用閾值排序法改進蟻群算法，可以加快算法的收斂性.這里取.基于改進后的算法，按照算法步驟在奔騰雙核上，以圖2為對象，利用程序編寫改進后的算法程序. 圖 2 閾值排序法得到的個邊由好到壞的排列：所以可得出由1到10的最優(yōu)路徑為，循環(huán)次數(shù)為:135；由1到11的最優(yōu)路徑為循環(huán)次數(shù)為:186.分別對改進的蟻群算法和基本蟻群

17、算法各運行50次，結(jié)果對比如表2所示，失敗表示所得結(jié)果并不是最優(yōu)結(jié)果. 表2 改進蟻群算法與基本蟻群算法對比結(jié)果 算法 失敗 成功率改進蟻群算法 4 92%基本蟻群算法 10 80% 表3為蟻群算法改進前后所用迭代次和所得結(jié)果的比較. 路表3 算法改進前后的比較算法 路徑 平均迭代次數(shù) 實際最優(yōu)路徑改進后的蟻群算法 137 189基本蟻群算法 323 431可以看出蟻群算法可以應(yīng)用于應(yīng)急搶險中，而對其改進算法大大提高了應(yīng)用中的效率.3.2 蟻群算法在機器人路徑規(guī)劃中的應(yīng)用 隨著社會不斷發(fā)展和科學(xué)的進步，簡單的求解兩地間的最優(yōu)路徑顯然已經(jīng)不能滿足人們生活生產(chǎn)已經(jīng)科研研究的需要.在高科技領(lǐng)域蟻群算

18、法的優(yōu)化性能也得到了極大的應(yīng)用，而且單一的蟻群算法往往會得不到最優(yōu)解，所以是和其他優(yōu)化算法相結(jié)合起來的，即改進后的蟻群算法應(yīng)用更加廣泛.這里我們講引用文獻中的幾例研究來說明蟻群算法在機器人路徑規(guī)劃中的應(yīng)用.文獻4是基于蟻群算法在移動機器人路徑規(guī)劃的改進算法，是引用柵格法來對蟻群算法進行改進.主要是在迷宮問題中算法原理的實現(xiàn)，給出迷宮大小和規(guī)模以及迷宮中最短路徑的目標(biāo)函數(shù)，還給出了在節(jié)點時螞蟻的四方移動圖，得到算法模型和算法步驟，實驗表明改進后的算法解決了螞蟻搜索過程中過早陷入局部最優(yōu)解的問題，擴大了螞蟻的搜索空間.除了運用柵格法來改進蟻群算法外還可以在幾何環(huán)境下建立模型，文獻7就是采用這種方法

19、來求解問題的，通過對終點啟發(fā)函數(shù)、轉(zhuǎn)移規(guī)則、信息素更新三個方面進行改變從而對基本蟻群算法進行改進.在圖1中利用該文算法進行仿真研究，設(shè)定了參數(shù).實驗結(jié)果如文中圖3所示，搜索路徑為，長度為153.9217，也是所有路徑中的最短路徑.講基本蟻群算法與改進算法進行比較，如表一所示.說明改進后的算法收斂性明顯提升，計算復(fù)雜度也減笑了很多. 文獻5是基于蟻群算法的噴漆機器人的路徑規(guī)劃，不同與移動機器人的路徑，因為在噴漆過程中機器人所處的環(huán)境是一個曲面，所以到對曲面進行分布處理，用“”方法生成噴漆路徑，最后用蟻群算法來解決路徑組合優(yōu)化問題，即ORPP問題，在實驗研究中設(shè)置了相關(guān)參數(shù)，利用ACO算法得出了的

20、結(jié)果比非優(yōu)化方法節(jié)約了20%噴涂時間.文獻6也是對蟻群算法進行改進從而應(yīng)用與機器人路徑的規(guī)劃，給出了柵格環(huán)境示意圖.針對螞蟻過早收斂從而結(jié)束算法的問題，因為螞蟻可能陷入U型陷阱中，螞蟻逃不出陷阱就會陷入“死亡”狀態(tài)，會使算法提前停滯，所以將環(huán)境中的障礙物進行凸化處理，消除了單個障礙物產(chǎn)生的陷阱，但該方法不能消除障礙物與環(huán)境邊界產(chǎn)生的陷阱.故文中提出了螞蟻回退策略，即一旦螞蟻發(fā)現(xiàn)陷阱就從當(dāng)前退回一步，并講該點加入到禁忌列表中，這樣的過程持續(xù)下去，并最終走出陷阱為止.在仿真實驗中設(shè)定：螞蟻數(shù)目，利用MATLAB設(shè)計了基本蟻群算法和改進的算法的程序.通過圖4和圖5比較可知利用回退機制螞蟻最終在“陷阱

21、”中走了出來，而在圖4中螞蟻提前結(jié)束了算法，陷入停滯狀態(tài).圖6為基本算法得到最優(yōu)路徑長度為38.90，圖7為改進后算法的最優(yōu)路徑長度為31.73，可知改進型算法得到的路徑長度明顯優(yōu)于基本算法得到的結(jié)果.說明螞蟻回退策略可以順利的解決機器人搜索過程中出現(xiàn)算法停滯的現(xiàn)象，使每個機器人都能安全的到達目標(biāo)，完成搜索路徑，從而擴大了機器人的搜索范圍，提高了蟻群算法在應(yīng)用中的收斂性和有效性. 在以上文獻可以看出為了解決機器人路徑規(guī)劃問題，單一的蟻群算法往往不能滿足需要，所以一般都是在引入其它方法對蟻群算法進行改進，這樣在應(yīng)用中大大提高了算法的有效性，也提高了蟻群算法在機器人路徑規(guī)劃中的應(yīng)用.3.3 蟻群算

22、法在TSP問題中的應(yīng)用3.3.1 TSP問題的描述 TSP問題：一個商人去個城市銷售貨物，所有城市走一遍之后再回到起點，使做走的路徑最短。TSP問題也可用有向圖來表示，即一個N個城市的有向圖，其中 ,城市之間的距離 可設(shè)目標(biāo)函數(shù)為 其中為所到城市的一個排列，且.3.3.2蟻群算法在TSP問題應(yīng)用中的原理利用蟻群算法去解決TSP問題，假設(shè)只在圖的相鄰節(jié)點移動，從而相互協(xié)作得到問題的解.每只螞蟻的下一步轉(zhuǎn)移概率由圖中每條邊上的兩類參數(shù)來決定的：1 信息素值即信息素蒸發(fā)系數(shù),2 能見度即期望因子.信息素更新方式有兩種，一是揮發(fā)，也就是所有螞蟻經(jīng)過的路徑上的信息素以一定的比例進行減少，從而模擬自然環(huán)境

23、下蟻群的信息素隨時間的變化揮發(fā)的過程；二是增強，對于評價值優(yōu)秀即螞蟻數(shù)量多的路徑增加信息素.對于算法模型的建立在上文中以及給出式(1)至(6)，所以在計算問題過程中要選擇合適的式子.3.3.3蟻群算法在TSP問題應(yīng)用中的算法步驟初始的蟻群算法是一種基于圖的蟻群算法，簡稱為GBAS算法，可利用它作為本問題的算法步驟，具體如下：步驟1：對于TSP問題，給予每條路徑賦予信息數(shù)初值，假設(shè)有m只螞蟻在工作且所以螞蟻都從同一個城市出發(fā)，當(dāng)前得到的最優(yōu)解為.步驟2：如若滿足算法的停止規(guī)則，則停止計算并輸出算法得到的最優(yōu)解.否則使螞蟻從起始點出發(fā)，用表示螞蟻所行走過的城市集合，初始為空集，.該步驟是一個外循環(huán)

24、.步驟3：按照螞蟻分別來計算.當(dāng)螞蟻在城市i，若或者，完成第只螞蟻的計算.否則，若且，則以概率 ， 到達 j, 若且則到達 重復(fù)步驟3.該步驟是一個內(nèi)循環(huán). 步驟4: 對于，若，按照中的城市順序計算路徑程度；若，可將路徑長度設(shè)置為一個無窮大值(即螞蟻不可到達).比較m只螞蟻的路徑長度，記走最短路徑的螞蟻為c.如果，則.可用以下公式對路徑上的信息素濃度進行加強，對其它路徑上的信息素痕跡進行揮發(fā).得到新的，重復(fù)步驟2.在步驟4中，揮發(fā)因子對于一個固定的，滿足并且經(jīng)過t次揮發(fā)，非最優(yōu)路徑的信息素逐漸減少蜘蛛消失.在上面的算法中，螞蟻搜尋過程中，以信息素的概率分布來決定城市i到城市j的轉(zhuǎn)移.而信息素的

25、更新不外乎揮發(fā)和增強兩個方面，在2.3.3選參原則中我們已經(jīng)給出了信息素濃度的減少和增加對算法結(jié)果的影響，步驟3中，蟻群永遠記憶到目前為止的最優(yōu)解.3.3.4蟻群算法在TSP問題應(yīng)用中的數(shù)據(jù)驗證因為下式滿足：即是一個隨機矩陣.給出4個城市非對稱的TSP問題，距離矩陣和城市圖(圖3)如下所示：圖3假設(shè)螞蟻數(shù)目，所有的螞蟻都從城市出發(fā)，揮發(fā)因子.根據(jù)GBAS的計算步驟，矩陣共有12條弧，初始信息素記憶矩陣為：計算GBAS算法的步驟2，設(shè)螞蟻行走路線如下表所示：表4螞蟻k路線目標(biāo)函數(shù)值第1只第2只第3只第4只當(dāng)前最優(yōu)解為：這個解是截止到當(dāng)前的最優(yōu)解，碰巧是實際最優(yōu)解.根據(jù)信息素更新規(guī)則，得到更新矩陣

26、這是第一次外循環(huán)結(jié)束的狀態(tài).重復(fù)外循環(huán)步驟，由于上一次得到的已經(jīng)是全局最優(yōu)解，因此按照信息素更新規(guī)則，無論螞蟻如何搜尋，都只對路線上的城市信息素進行加強，其它路線上的信息素進行揮發(fā).得到更新矩陣為：這是第二次外循環(huán)結(jié)束的狀態(tài).繼續(xù)重復(fù)外循環(huán)步驟，因為路線為全局最優(yōu)解.GBAS只記錄第一個最優(yōu)解，信息素的更新也將不再依賴于群的行走路線，而是不斷增強最優(yōu)路徑的信息素濃度，同時進行揮發(fā).第三次外循環(huán)得到的矩陣為：螞蟻以一定的概率從城市到城市進行轉(zhuǎn)移，信息素的更新是在步驟4中完成的，并隨而變化.假設(shè)次外循環(huán)后得到了矩陣，得到了當(dāng)前最優(yōu)解.第次外循環(huán)前的信息素矩陣最優(yōu)解為經(jīng)過了次外循環(huán)后，得到.通過對蟻

27、群算法在路徑中應(yīng)用分析我們可以得出 蟻群算法具有以下幾個優(yōu)點：(1) 蟻群算法與其它啟發(fā)式算法相比，在求解性能上面具有很強的魯棒性(即基本的蟻群算法模型稍加修改，便可以應(yīng)用于其它領(lǐng)域之中.)和搜索較優(yōu)解的能力.(2) 蟻群算法是一種基于種群的進化算法，具有本質(zhì)并行性，易于計算中的并行實現(xiàn).(3) 蟻群算法容易與其它多種算法相結(jié)合，用于改善算法的性能. 結(jié) 束 語 蟻群算法因為其自身尋優(yōu)能力強、在求解能力上有很強的魯棒性、優(yōu)化效率高、算法靈活易于和其它算法相結(jié)合等特點，在各個優(yōu)化領(lǐng)域中的應(yīng)用是非常廣泛的.本文首先介紹了什么是蟻群算法及其原理，在理解的基礎(chǔ)上建立了算法模型，并且列舉了幾例基于蟻群算

28、法的優(yōu)化應(yīng)用.在機器人路徑規(guī)劃中重點介紹了幾種改進蟻群算法的方法，解決了傳統(tǒng)蟻群算體法在優(yōu)化中常遇到的幾個問題.最后針對蟻群算法發(fā)展現(xiàn)狀和研究方向提出了自己的見解.誠然，該論文還許多不足之處.比如蟻群算法在實際應(yīng)用的方面還沒有完全發(fā)覺其潛力，我們大多數(shù)是在仿真實驗中來研究該算法的，在參數(shù)選擇中我們也是往往根據(jù)自己的直覺性和經(jīng)驗性來擇優(yōu)選擇.大多都是對在實際問題研究條件或約束條件進行簡化的前提下進行的，雖然簡化了計算過程，但是和實際情況的結(jié)果還是有點出入的.因此這是個長期的研究過程，只有不斷積累研究才能讓蟻群算法在路徑優(yōu)化中得到更廣泛的應(yīng)用. 參考文獻1 黃貴玲,高西全,靳松杰,談飛洋. 基于蟻

29、群算法的最短路徑問題的研究和應(yīng)用 J. 計算機工程與應(yīng)用. 2007 (13) 2 靳凱文,李春葆,秦前清. 基于蟻群算法的最短路徑搜索方法研究 J. 公路交通科技. 2006 (03) 3 陳宏,胡寧靜. 基于改進螞蟻算法的城市交通最佳路徑選擇 J. 長沙電力學(xué)院學(xué)報(自然科學(xué)版). 2006 (01) 4 溫如春,湯青波,楊國亮. 基于改進蟻群算法的移動機器人路徑規(guī)劃 J. 兵工自動化. 2010 (08) 5 陳偉,趙德安,平向意. 基于蟻群算法的噴涂機器人噴槍路徑規(guī)劃 J. 機械設(shè)計與制造. 2011 (07) 6 牛治永,李炎,李曉嵐. 基于改進蟻群算法的機器人路徑規(guī)劃 J. 自動化

30、技術(shù)與應(yīng)用. 2011 (07) 7 劉雄,雷勇,涂國強. 基于蟻群算法的移動機器人路徑規(guī)劃 J. 計算機仿真. 2011 (11) 8 崔麗群，許堃. 改進蟻群算法求解兩地是間最優(yōu)路徑J. 計算機仿真. 2012（06）9 A Colorni，M Dorigo，V Maniezzo Distributed optimization by antcoloniesC Proc of the First European Conf On Artificial Life，Paris，F(xiàn)rance Elsevier Publishing，1991: 134 142Ant colony optimiza

31、tion algorithm is applied in the path Auhuor: Sun Yang Yang Supervisor: Liu ChongAbstract: How to choose the optimal in multifarious road system path is an important issue in ant colony algorithm in path optimization. Understand the concept and principle of ant colony algorithm is presented in this paper, on the