技術篇:蟻群算法實例解析

在我們做研究的的時候會用到很多群智能算法用於尋優，比如遺傳算法、魚群算法、粒子群算法、還有咱們今天要講的蟻群算法。將蟻群算法應用於解決尋優問題的基本思路為：用螞蟻的行走路徑表示待優化問題的可行解，整個螞蟻群體的所有路徑構成待優化問題的解空間。路徑較短的螞蟻釋放的信息素量較多，隨著時間的推進，較短的路徑上累積的信息素濃度逐漸增高，選擇該路徑的螞蟻個數也愈來愈多。最終，整個螞蟻會在正反饋的作用下集中到最佳的路徑上，此時對應的便是待優化問題的最優解。

螞蟻找到最短路徑要歸功於信息素和環境，假設有兩條路可從蟻窩通向食物，開始時兩條路上的螞蟻數量差不多，當螞蟻到達終點之後會立即返回，距離短的路上的螞蟻往返一次時間短，重複頻率快，在單位時間裡往返螞蟻的數目就多，留下的信息素也多，會吸引更多螞蟻過來，會留下更多信息素。而距離長的路正相反，因此越來越多的螞蟻聚集到最短路徑上來，我們下圖可以形象的表示蟻群算法的中心思想。

在蟻群算法中，螞蟻的眼睛觀察到的範圍是一個方格世界，相關參數為速度半徑，一般為3，可觀察和移動的範圍為3x3方格。螞蟻在感知範圍內尋找食物，如果感知到就會過去，否則朝信息素多的地方走，每隻螞蟻會以很小的可能性犯錯，並非都往信息素最多的方向移動。螞蟻朝信息最多的方向爬行，當周圍沒有指引時，會按照原來預設的規則行走。而且聰明的螞蟻會記住最近走過的地方，防止原地轉圈。當螞蟻遇到障礙物時，將按照設定隨機選擇其行走的方向。當有指引時，將按照覓食規則移動。在剛找到食物或者窩時，螞蟻散發的信息素最多，當隨著走遠時，散發的信息素將逐漸減少。在使用蟻群算法進行尋優時，蟻群算法基本工作流程是：

接下來我們舉一個實例進行蟻群算法的功能測試，我們做一個城市之間最優旅行方式的計算，為了體現算法強大，我們選擇31個城市的坐標，隨機選擇一個城市作為始發地。我們先看看31個城市的坐標，呈現無規則狀態，這為計算增加了不少難度。

在這31所城市中，我們會有31×30×29×28×…×2×1種選擇，如果靠人工計算幾乎是不可能的事情，就算是計算機也不是一時半刻就可以完成的，但是我們利用魚群算法，不用挨個計算，可以迅速的找到最合適的旅行路線。我們設置螞蟻的數量為50個，信息素重要因子為1，啟發函數重要因子為5，初次迭代次數為1，最大迭代次數為200。接下來隨機產生各個螞蟻的起點城市，逐個螞蟻路徑選擇，逐個城市路徑選擇，將已訪問的城市和沒訪問的城市以及待訪問城市找出來，並採用輪盤賭法選擇下一個城市。然後計算各個螞蟻的路徑距離，取出每個螞蟻的路徑，計算最短路徑距離和平均距離，更新信息素，逐個螞蟻計算，逐個城市計算，我們採用MATLAB編程去實現。

通過編輯程序得出運算結果：

我們可以看出計算出來的最短路徑為15601.9195km，隨機選擇第14個編號作為初始位置：14、12、13、11、23、16、5、6、7、2、4、8、9、10、3、18、17、19、24、25、20、21、22、26、28、27、30、31、29、1、15、14。旅行的路線圖如下圖所示：

從上面的迭代圖可以看出，第一代蟻群計算的距離約為1.8萬km，大約經過80代循環之後，基本上找到了最優旅行路線。除了本文的應用，蟻群算法應用廣泛，也可以應用於其他組合優化問題，如線性最優解問題、指派問題、Job—shop調度問題、車輛路由問題、圖著色問題和網絡路由問題等。最近幾年，該算法在網絡路由中的應用受到越來越多學者的關注，並提出了一些新的基於蟻群算法的路由算法。同傳統的路由算法相比較，該算法在網絡路由中具有信息分布式性、動態性、隨機性和異步性等特點，而這些特點正好能滿足網絡路由的需要。