-
蟻羣算法
鎖定
這種算法具有分佈計算、信息正反饋和啓發式搜索的特徵,本質上是進化算法中的一種啓發式全局優化算法。
[2]
- 中文名
- 蟻羣算法
- 外文名
- ant colony optimization
- 簡 稱
- ACO
- 提出人
- Marco Dorigo
- 提出時間
- 1992年
- 所屬學科
- 計算機
蟻羣算法背景
蟻羣系統(Ant System或Ant Colony System)是由意大利學者Dorigo、Maniezzo等人於20世紀90年代首先提出來的。他們在研究螞蟻覓食的過程中,發現單個螞蟻的行為比較簡單,但是蟻羣整體卻可以體現一些智能的行為。例如蟻羣可以在不同的環境下,尋找最短到達食物源的路徑。這是因為蟻羣內的螞蟻可以通過某種信息機制實現信息的傳遞。後又經進一步研究發現,螞蟻會在其經過的路徑上釋放一種可以稱之為“信息素”的物質,蟻羣內的螞蟻對“信息素”具有感知能力,它們會沿着“信息素”濃度較高路徑行走,而每隻路過的螞蟻都會在路上留下“信息素”,這就形成一種類似正反饋的機制,這樣經過一段時間後,整個蟻羣就會沿着最短路徑到達食物源了。
[3]
蟻羣算法思想
將蟻羣算法應用於解決優化問題的基本思路為:用螞蟻的行走路徑表示待優化問題的可行解,整個螞蟻羣體的所有路徑構成待優化問題的解空間。路徑較短的螞蟻釋放的信息素量較多,隨着時間的推進,較短的路徑上累積的信息素濃度逐漸增高,選擇該路徑的螞蟻個數也愈來愈多。最終,整個螞蟻會在正反饋的作用下集中到最佳的路徑上,此時對應的便是待優化問題的最優解。
[4]
蟻羣算法實現
螞蟻找到最短路徑要歸功於信息素和環境,假設有兩條路可從蟻窩通向食物,開始時兩條路上的螞蟻數量差不多:當螞蟻到達終點之後會立即返回,距離短的路上的螞蟻往返一次時間短,重複頻率快,在單位時間裏往返螞蟻的數目就多,留下的信息素也多,會吸引更多螞蟻過來,會留下更多信息素。而距離長的路正相反,因此越來越多的螞蟻聚集到最短路徑上來。
螞蟻具有的智能行為得益於其簡單行為規則,該規則讓其具有多樣性和正反饋。在覓食時,多樣性使螞蟻不會走進死衚衕而無限循環,是一種創新能力;正反饋使優良信息保存下來,是一種學習強化能力。兩者的巧妙結合使智能行為湧現,如果多樣性過剩,系統過於活躍,會導致過多的隨機運動,陷入混沌狀態;如果多樣性不夠,正反饋過強,會導致僵化,當環境變化時蟻羣不能相應調整。
[5]
Python 代碼實現
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)散發信息素規則
蟻羣算法特點
與其他優化算法相比,蟻羣算法具有以下幾個特點:
(1)採用正反饋機制,使得搜索過程不斷收斂,最終逼近最優解。
(2)每個個體可以通過釋放信息素來改變周圍的環境,且每個個體能夠感知周圍環境的實時變化,個體間通過環境進行間接地通訊。
(3)搜索過程採用分佈式計算方式,多個個體同時進行並行計算,大大提高了算法的計算能力和運行效率。
蟻羣算法應用
該算法應用於其他組合優化問題,如旅行商問題、指派問題、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月