蟻群算法
這算是填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點基本規則,資訊素散播規則按照
螢幕斜線距離/螞蟻移動距離
- 超過一定的移動步數未找到食物或窩的螞蟻進行重置
- 選擇方向的計算公式采用
單元格濃度/8個方向單元格濃度總和
- 資訊素在每次疊代時，進行統一揮發
一個常量值
現在我們來看看螞蟻是否能夠找到最近的食物。
1.首先我們放置一個較遠的食物A，圖中的綠色為食物，白色為螞蟻，暗藍色為家相關的資訊素，顔色深淺代表濃度。
注意：我們上面采用的資訊素灑播規則，會讓家相關的資訊素濃度圍繞着家呈梯形分布，這樣螞蟻在回家時，能夠根據濃度找到家，食物相關資訊素也一樣。感興趣的朋友可以在源碼裡修改資訊素顯示參數，顯示食物相關的資訊素分布圖。
2.過一會兒，我們發現螞蟻都聚集在這條路徑上，然後我們放一個離得很近的食物B
3.最後我們會發現這條路徑上的螞蟻越來越多，再過一會兒，A路徑上基本沒有什麼螞蟻了。
你有可能問，那障礙是幹嘛用的，我當時隻是想幹一件小時候經常幹的事情，如
1.一群螞蟻找到了食物
2.我攔住了他們的去路
3.最後他們還是找到了食物，壞笑
最後
如果你親自動手做實驗，你會發現，當螞蟻在一條路徑上覓食很久時，你再放置一個近的食物基本沒啥效果，你也可以了解為當一隻螞蟻找到一條路徑時，過了很久的時間，大多數螞蟻都選擇了這條路徑，就在這時候，突然有一隻螞蟻找到了較近的食物，但因為時間過得太久，兩條路徑上濃度相差太大（濃度越大，被選擇的機率就越大），整個系統基本已經停滞了，陷入了局部最優。是以簡單的螞蟻系統是存在一些問題的，如：
- 搜尋到一定程度，會出現停滞狀态，陷入局部最優的情況
- 盲目的随機搜尋，搜尋時間較長
而影響螞蟻是否能夠找到好的最優解，依賴這幾個關鍵因素：
- 資訊素怎麼灑播（比如維持在一個特地範圍的值等）
- 資訊素怎麼揮發（除了全局揮發，可以讓螞蟻自身進行局部揮發等手段）
- 通過怎樣的方式讓螞蟻選擇運動方向，減少盲目性和不必要性（給螞蟻一點點智能和經驗）
- 給螞蟻和環境一定的記憶能力能夠幫助減少搜尋空間
如果你感興趣，可以去看看諸如最大最小蟻群算法、排序蟻群算法、基于遺傳算法的蟻群算法等一系列在基本蟻群系統上的優化和改進，他們對于資訊素的使用、螞蟻方向選擇等都有一套成熟的數學模型和經驗優化參數。
posted on
2016-07-13 09:26
HackerVirus
閱讀(51228)
評論(3)
編輯
收藏
舉報