自話蟻群演算法

知識 07-13

這算是填3年前的一個坑吧，已經懶癌晚期了，想必也還是要掙紮下，那今天先從蟻群演算法這個坑說起，如果你是要尋找怎麼優化蟻群演算法，可以直接跳過本文，如果你還不了解什麼是蟻群演算法，或許本文能夠提起你的興趣。

如果你同樣對遺傳演算法和粒子群演算法感興趣，請查看3年前我對於這兩個演算法見解的文章。

自話粒子群演算法（超簡單實例)

自話遺傳演算法（帶實例）

簡單蟻群演算法模擬實驗：

Demo

Github

這個模擬實驗比較簡單，並沒有對信息素、路徑選擇等做優化，主要是方便大家查看簡單的螞蟻系統能夠帶來一個什麼樣的效果,詳細說明見後文。

什麼是蟻群演算法

按百度百科的話來說，蟻群演算法(ant colony optimization, ACO)，又稱螞蟻演算法，是一種用來在圖中尋找優化路徑的機率型演算法。它由Marco Dorigo於1992年在他的博士論文中提出，其靈感來源於螞蟻在尋找食物過程中發現路徑的行為。蟻群演算法是一種模擬進化演算法，初步的研究表明該演算法具有許多優良的性質，並且現在已用於我們生活的方方面面。

基本原理

螞蟻在運動過程中，會留下一種稱為信息素的東西，並且會隨著移動的距離，播散的信息素越來越少，所以往往在家或者食物的周圍，信息素的濃度是最強的，而螞蟻自身會根據信息素去選擇方向，當然信息素越濃，被選擇的概率也就越大，並且信息素本身具有一定的揮發作用。螞蟻的運動過程可以簡單歸納如下：

當周圍沒有信息素指引時，螞蟻的運動具有一定的慣性，並有一定的概率選擇其他方向

當周圍有信息素的指引時，按照信息素的濃度強度概率性的選擇運動方向

找食物時，螞蟻留下家相關的A信息素，找家時，螞蟻留下食物相關的B信息素，並隨著移動距離的增加，灑播的信息素越來越少

隨著時間推移，信息素會自行揮發

一個簡單的例子，如果現在有兩條通往食物的路徑，一條較長路徑A,一條較短路徑B,雖然剛開始A,B路徑上都有螞蟻，又因為B比A短，螞蟻通過B花費的時間較短，隨著時間的推移和信息素的揮發，逐漸的B上的信息素濃度會強於A，這時候因為B的濃度比A強，越來越多多螞蟻會選擇B，而這時候B上的濃度只會越來越強。如果螞蟻一開始只在A上呢，注意螞蟻的移動具有一定小概率的隨機性，所以當一部分螞蟻找到B時，隨著時間的推移，螞蟻會收斂到B上，從而可以跳出局部最優。

實驗

上面的描述可能不是很形象，現在我們來模擬做個小實驗，實驗地址Demo，源碼已放在Github

簡單蟻群實驗環境：

滿足上面4點基本規則,信息素散播規則按照，移動距離在找到食物或者家清0(言外之意式，螞蟻最多能夠移動斜線這麼遠的距離，這個公式比較簡單)

超過一定的移動步數未找到食物或窩的螞蟻進行重置

選擇方向的計算公式採用,用輪盤賭進行概率選擇

信息素在每次迭代時，進行統一揮發

現在我們來看看螞蟻是否能夠找到最近的食物。

1.首先我們放置一個較遠的食物A，圖中的綠色為食物，白色為螞蟻，暗藍色為家相關的信息素，顏色深淺代表濃度。

自話蟻群演算法

1.png

注意：我們上面採用的信息素灑播規則，會讓家相關的信息素濃度圍繞著家呈梯形分布，這樣螞蟻在回家時，能夠根據濃度找到家，食物相關信息素也一樣。感興趣的朋友可以在源碼里修改信息素顯示參數，顯示食物相關的信息素分布圖。

2.過一會兒，我們發現螞蟻都聚集在這條路徑上，然後我們放一個離得很近的食物B

自話蟻群演算法

2.png

3.最後我們會發現這條路徑上的螞蟻越來越多，再過一會兒，A路徑上基本沒有什麼螞蟻了。

自話蟻群演算法

3.png

你有可能問，那障礙是幹嘛用的，我當時只是想干一件小時候經常乾的事情，如

1.一群螞蟻找到了食物

自話蟻群演算法

4.png

2.我攔住了他們的去路

自話蟻群演算法

5.png

3.最後他們還是找到了食物，壞笑

自話蟻群演算法

6.png

最後

如果你親自動手做實驗，你會發現，當螞蟻在一條路徑上覓食很久時，你再放置一個近的食物基本沒啥效果，你也可以理解為當一隻螞蟻找到一條路徑時，過了很久的時間，大多數螞蟻都選擇了這條路徑，就在這時候，突然有一隻螞蟻找到了較近的食物，但因為時間過得太久，兩條路徑上濃度相差太大（濃度越大，被選擇的概率就越大），整個系統基本已經停滯了，陷入了局部最優。所以簡單的螞蟻系統是存在一些問題的，如：

搜索到一定程度，會出現停滯狀態，陷入局部最優的情況

盲目的隨機搜索，搜索時間較長

而影響螞蟻是否能夠找到好的最優解，依賴這幾個關鍵因素：

信息素怎麼灑播（比如維持在一個特地範圍的值等）

信息素怎麼揮發（除了全局揮發，可以讓螞蟻自身進行局部揮發等手段）

通過怎樣的方式讓螞蟻選擇運動方向，減少盲目性和不必要性（給螞蟻一點點智能和經驗）

給螞蟻和環境一定的記憶能力能夠幫助減少搜索空間

如果你感興趣，可以去看看諸如最大最小蟻群演算法、排序蟻群演算法、基於遺傳演算法的蟻群演算法等一系列在基本蟻群系統上的優化和改進，他們對於信息素的使用、螞蟻方向選擇等都有一套成熟的數學模型和經驗優化參數。