一、柵格地圖介紹

柵格地圖有兩種表示方法，直角坐標系法和序號法，序號法比直角坐標法節(jié)省內(nèi)存

室內(nèi)環(huán)境柵格法建模步驟

1.柵格粒大小的選取

柵格的大小是個關鍵因素，柵格選的小，環(huán)境分辨率較大，環(huán)境信息存儲量大，決策速度慢。

柵格選的大，環(huán)境分辨率較小，環(huán)境信息存儲量小，決策速度快，但在密集障礙物環(huán)境中發(fā)現(xiàn)路徑的能力較弱。

2.障礙物柵格確定

當機器人新進入一個環(huán)境時，它是不知道室內(nèi)障礙物信息的，這就需要機器人能夠遍歷整個環(huán)境，檢測障礙物的位置，并根據(jù)障礙物位置找到對應柵格地圖中的序號值，并對相應的柵格值進行修改。自由柵格為不包含障礙物的柵格賦值為0，障礙物柵格為包含障礙物的柵格賦值為1.

3.未知環(huán)境的柵格地圖的建立

通常把終點設置為一個不能到達的點，比如（-1，-1），同時機器人在尋路過程中遵循“下右上左”的原則，即機器人先向下行走，當機器人前方遇到障礙物時，機器人轉(zhuǎn)向右走，遵循這樣的規(guī)則，機器人最終可以搜索出所有的可行路徑，并且機器人最終將返回起始點。

備注：在柵格地圖上，有這么一條原則，障礙物的大小永遠等于n個柵格的大小，不會出現(xiàn)半個柵格這樣的情況。

二.蟻群算法基本原理

2.1 算法綜述

　　對于VRP問題,求解算法大致可分為精確算法和人工智能算法兩大類。精確性算法基于嚴格的數(shù)學手段,在可以求解的情況下,解的質(zhì)量較好。但是由于算法嚴格,運算量大,特別是大規(guī)模的問題幾乎無法求解。所以其應用只能是小規(guī)模的確定性問題，面對中小規(guī)模問題,人工智能算法在精度上不占優(yōu)勢。但規(guī)模變大時,人工智能方法基本能在可接受時間里,找到可接受的滿意解,這是精確算法難以做到的。由于的實際問題,各種約束錯綜復雜,人工智能算法顯示出了巨大的優(yōu)越性,也正因為如此,實際應用中,人工智能算法要更廣泛。求解車輛路徑調(diào)度問題的精確算法有動態(tài)規(guī)劃法、分枝定界法等。并開始尋求所得結果可接受的啟發(fā)式算法,以處理大規(guī)模實際問題，一些其他學科的新一代優(yōu)化算法相繼出現(xiàn),如禁忌搜索算法,遺傳算法,人工神經(jīng)網(wǎng)絡算法,以及現(xiàn)在研究較多的蟻群算法等。

2.2 蟻群算法的原理

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

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

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

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

c圖是t=1時刻螞蟻經(jīng)過后的狀態(tài)，各個邊的信息素濃度，有變化；因為大量螞蟻的選擇概率會不一樣，而選擇概率是和路徑長度相關的。所以越短路徑的濃度會越來越大，經(jīng)過此短路徑達到目的地的螞蟻也會比其他路徑多。這樣大量的螞蟻實踐之后就找到了最短路徑。所以這個過程本質(zhì)可以概括為以下幾點：

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

2.信息素更新機制路徑越短,路徑上的信息素蹤跡增長得越快

3.協(xié)同工作機制螞蟻個體通過信息素進行信息交流。

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

　　上述例子如果不好理解，我在這里貼幾張PPT，個人感覺非常不錯，也是我找了很多資料覺得最好理解的【來源是大連理工大學谷俊峰】，點擊這里提供下載：蟻群算法基本知識.rar。

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

回到目錄

三.蟻群算法的基本流程

　　我們還是采用大連理工大學谷俊峰的PPT來說明問題，重要公式進行截圖計算和解釋，對PPT難以理解的地方進行單獨解釋：

3.1 基本數(shù)學模型

　　首先看看基本TSP問題的基本數(shù)學模型：

　　問題其實很簡單，目標函數(shù)就是各個走過路徑的總長度，注意的就是距離矩陣根據(jù)實際的問題不一樣，長度是不一樣的。

3.2 蟻群算法說明

　　在說明群蟻算法流程之前，我們對算法原理和幾個注意點進行描述：

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

3.3 蟻群算法核心步驟

　　更加我們前面的原理和上述說明，群蟻算法的2個核心步驟是 路徑構建 和 信息素更新。我們將重點對這2個步驟進行說明。

3.3.1 路徑構建

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

　　上述公式就是計算 當前點 到 每一個可能的下一個節(jié)點 的概率。分子是 信息素強度 和 能見度 的冪乘積，而分母則是所有 分子的和值。這個剛開始是很不容易理解的，我們在最后實例計算的時候，可以看得很清楚，再反過來理解公式。注意每次選擇好節(jié)點后，就要從可用節(jié)點中移除選擇的節(jié)點。

3.3.2 信息素更新

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

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

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

　　信息素更新的作用： 1.信息素揮發(fā)(evaporation)信息素痕跡的揮發(fā)過程是每個連接上的 信息素痕跡的濃度自動逐漸減弱的過程，這個揮發(fā)過程主要用于避 免算法過快地向局部最優(yōu)區(qū)域集中，有助于搜索區(qū)域的擴展。 2.信息素增強(reinforcement)增強過程是蟻群優(yōu)化算法中可選的部 分，稱為離線更新方式（還有在線更新方式）。這種方式可以實現(xiàn) 由單個螞蟻無法實現(xiàn)的集中行動。基本蟻群算法的離線更新方式是 在蟻群中的m只螞蟻全部完成n城市的訪問后，統(tǒng)一對殘留信息進行 更新處理。

3.3.3 迭代與停止

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

回到目錄

?