複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/蟻羣算法/9646604
複製
複製成功

蟻羣算法

鎖定
蟻羣算法是一種用來尋找優化路徑的概率型算法。它由Marco Dorigo於1992年在他的博士論文中提出，其靈感來源於螞蟻在尋找食物過程中發現路徑的行為。 [1] 
這種算法具有分佈計算、信息正反饋和啓發式搜索的特徵，本質上是進化算法中的一種啓發式全局優化算法。 [2] 
中文名
蟻羣算法
外文名
ant colony optimization
簡    稱
ACO
提出人
Marco Dorigo
提出時間
1992年
所屬學科
計算機

目錄

  1. 1 背景
  2. 2 思想
  1. 3 實現
  2. 4 規則
  1. 5 特點
  2. 6 應用

蟻羣算法背景

蟻羣系統(Ant System或Ant Colony System)是由意大利學者Dorigo、Maniezzo等人於20世紀90年代首先提出來的。他們在研究螞蟻覓食的過程中，發現單個螞蟻的行為比較簡單，但是蟻羣整體卻可以體現一些智能的行為。例如蟻羣可以在不同的環境下，尋找最短到達食物源的路徑。這是因為蟻羣內的螞蟻可以通過某種信息機制實現信息的傳遞。後又經進一步研究發現，螞蟻會在其經過的路徑上釋放一種可以稱之為“信息素”的物質，蟻羣內的螞蟻對“信息素”具有感知能力，它們會沿着“信息素”濃度較高路徑行走，而每隻路過的螞蟻都會在路上留下“信息素”，這就形成一種類似正反饋的機制，這樣經過一段時間後，整個蟻羣就會沿着最短路徑到達食物源了。 [3] 

蟻羣算法思想

將蟻羣算法應用於解決優化問題的基本思路為：用螞蟻的行走路徑表示待優化問題的可行解，整個螞蟻羣體的所有路徑構成待優化問題的解空間。路徑較短的螞蟻釋放的信息素量較多，隨着時間的推進，較短的路徑上累積的信息素濃度逐漸增高，選擇該路徑的螞蟻個數也愈來愈多。最終，整個螞蟻會在正反饋的作用下集中到最佳的路徑上，此時對應的便是待優化問題的最優解。 [4] 

蟻羣算法實現

螞蟻找到最短路徑要歸功於信息素和環境，假設有兩條路可從蟻窩通向食物，開始時兩條路上的螞蟻數量差不多：當螞蟻到達終點之後會立即返回，距離短的路上的螞蟻往返一次時間短，重複頻率快，在單位時間裏往返螞蟻的數目就多，留下的信息素也多，會吸引更多螞蟻過來，會留下更多信息素。而距離長的路正相反，因此越來越多的螞蟻聚集到最短路徑上來。
螞蟻具有的智能行為得益於其簡單行為規則，該規則讓其具有多樣性和正反饋。在覓食時，多樣性使螞蟻不會走進死衚衕而無限循環，是一種創新能力；正反饋使優良信息保存下來，是一種學習強化能力。兩者的巧妙結合使智能行為湧現，如果多樣性過剩，系統過於活躍，會導致過多的隨機運動，陷入混沌狀態；如果多樣性不夠，正反饋過強，會導致僵化，當環境變化時蟻羣不能相應調整。 [5] 
Python 代碼實現
step1：在GitHub上下載常用的 scikit-opt [6]  庫。
step2：設立目標函數並執行蟻羣算法
aca = ACA_TSP(func=cal_total_distance, n_dim=8,
              size_pop=10, max_iter=20,
              distance_matrix=distance_matrix)

best_x, best_y = aca.fit()
圖示 圖示

蟻羣算法規則

(1)感知範圍
螞蟻觀察到的範圍是一個方格世界，相關參數為速度半徑，一般為3，可觀察和移動的範圍為3x3方格。
(2)環境信息
螞蟻所在環境中有障礙物、其他螞蟻、信息素，其中信息素包括食物信息素(找到食物的螞蟻留下的)、窩信息素(找到窩的螞蟻留下的)，信息素以一定速率消失。
(3)覓食規則
螞蟻在感知範圍內尋找食物，如果感知到就會過去；否則朝信息素多的地方走，每隻螞蟻會以小概率犯錯誤，並非都往信息素最多的方向移動。螞蟻找窩的規則類似，僅對窩信息素有反應。
(4)移動規則
螞蟻朝信息素最多的方向移動，當週圍沒有信息素指引時，會按照原來運動方向慣性移動。而且會記住最近走過的點，防止原地轉圈。
(5)避障規則
當螞蟻待移動方向有障礙物時，將隨機選擇其他方向；當有信息素指引時，將按照覓食規則移動。
(6)散發信息素規則
在剛找到食物或者窩時，螞蟻散發的信息素最多；當隨着走遠時，散發的信息素將逐漸減少。 [5] 

蟻羣算法特點

與其他優化算法相比，蟻羣算法具有以下幾個特點：
(1)採用正反饋機制，使得搜索過程不斷收斂，最終逼近最優解。
(2)每個個體可以通過釋放信息素來改變周圍的環境，且每個個體能夠感知周圍環境的實時變化，個體間通過環境進行間接地通訊。
(3)搜索過程採用分佈式計算方式，多個個體同時進行並行計算，大大提高了算法的計算能力和運行效率。
(4)啓發式的概率搜索方式不容易陷入局部最優，易於尋找到全局最優解。 [4] 

蟻羣算法應用

該算法應用於其他組合優化問題，如旅行商問題、指派問題、Job—shop調度問題、車輛路由問題、圖着色問題和網絡路由問題等。最近幾年，該算法在網絡路由中的應用受到越來越多學者的關注，並提出了一些新的基於螞蟻算法的路由算法。同傳統的路由算法相比較，該算法在網絡路由中具有信息分佈式性、動態性、隨機性和異步性等特點，而這些特點正好能滿足網絡路由的需要。 [7] 
參考資料
  • 1.    耿振餘，陳治湘，黃路煒，李德龍，劉思彤，周宏升，王立華編著．軟計算方法及其軍事應用：國防工業出版社，2015.12
  • 2.    沈顯君著．自適應粒子羣優化算法及其應用：清華大學出版社，2015.06
  • 3.    康與雲著．元功能鏈驅動的機電產品矩陣式創新設計方法：山東人民出版社，2015.11
  • 4.    鬱磊，史峯，王輝，胡斐編著．MATLAB智能算法30個案例分析（第2版）：北京航空航天大學出版社，2015.09
  • 5.    謝劍斌，興軍亮，張立寧，方宇強，李沛秦，劉通，閆瑋，王勇，沈傑，張政，譚筠，胡俊編著．視覺機器學習20講：清華大學出版社，2015.06
  • 6.    scikit-opt  ．GitHub．2019-08-01[引用日期2019-09-19]
  • 7.    劉騰紅主編．信息與經濟學：中國財政經濟出版社，2005年04月