蟻群系統

蟻群系統（Ant Colony System）是1996年Gambardella和Dorigo提出的算法，對於複雜的組合問題可以在合適的時間內確定一個較好的解，但僅限於小規模的問題。為了改善蟻群算法的性能，

基本介紹

• 中文名：蟻群系統
• 外文名：Ant Colony System
• 簡稱：ACS
• 提出時間：1996年
• 提出者：Gambardella和Dorigo
• 特點：較強的並行性、搜尋較優解能力強

蟻群算法簡介

蟻群算法是在對螞蟻種群觀察的基礎上，受到啟發後設計出來的。仿生學家的研究發現螞蟻群體通過相互協作能夠很容易在蟻穴與食物之間找到最短的路徑。它們是憑藉路徑尋優的能力而做到這一點的。原因是：螞蟻在前進的過程中，對所經過的路徑留下了一種揮發性分泌物一信息素。這種物質的存在及其強度能夠在螞蟻在覓食過程中被感知，並指導螞蟻下一步運動方向。即在待選擇路徑上，螞蟻選擇移動的方向總是朝著高濃度的信息素所對應的路徑，即路徑上的信息素強度越高，就會有越多的螞蟻去選擇它，而這樣會使得該路徑上留下的信息素變得更為強大，從而吸引更多的螞蟻，這是信息素的一種正反饋形式。通過信息素的正反饋，螞蟻最終可以尋找到最佳行動路徑。以人工螞蟻模擬真實螞蟻行為來求解組合最佳化問題的蟻群算法就是受這種行為啟發而設計出來的。它是繼遺傳算法、模擬退火算法、人工神經網路算法、禁忌搜尋算法等啟發式搜尋算法之後的一種新型的啟發式仿生類進化算法。

然而基本蟻群算法存在一些明顯的缺陷，比如搜尋時容易陷入局部最優解；收斂到全局最優的時間過長等。因此，提出了蟻群系統算法，它可以有效的克服基本蟻群算法的缺陷，利於實際套用。

蟻群系統對蟻群算法的改進

在蟻群算法的基礎上蟻群系統主要做了三方面的改進：

(1) 以偽隨機比例規則進行狀態轉移。

這使關於問題的先驗知識得到了更好利用，也為新路徑的選擇提供了更合理的方法。蟻群系統中引入了參數 ，可以對螞蟻探索新路徑的程度進行調節，有效增強螞蟻在集中於最優解的範圍空間內的探尋能力。

(2) 只在最優的螞蟻路徑上套用全局更新規則。

在蟻群算法中全局更新規則對系統中所有螞蟻信息素都進行更新，這使得螞蟻的搜尋行為不能很快的集中在最優路徑領域內，降低了螞蟻搜尋最優路徑的效率。蟻群系統則不同，每次循環後只對選擇的最優路徑上的信息素進行增強，而其他路徑上的信息素由於揮發而逐漸減弱，這樣一來便加大了最優路徑和最差路徑上的信息素差異。在後續螞蟻選擇路徑過程中，螞蟻則便更傾向於選擇信息素大的最優路徑所對應的邊，這樣螞蟻的搜尋行為快速集中到最優路徑的附近，搜尋效率大大提高。

(3) 將局部信息素更新規則套用在建立問題解決方案的過程中。

蟻群算法只對信息素進行一次全局更新。然而，在蟻群系統中，螞蟻不僅在每次循環後再對路徑進行一次全局的更新，而且在構造路徑的同時也進行局部更新。

蟻群系統的工作過程表述

在初始時刻，n個城市上隨機放置了m只螞蟻，螞蟻則多次利用狀態轉移規則建立一條路徑(即TSP的一個可行解)。在建立路徑的過程中，螞蟻受激素信息(信息素強度高的邊對螞蟻更有吸引力)和啟發信息(傾向於選擇最短路徑)的指導。同時，對於在已經訪問過路徑上的信息素螞蟻通過套用局部更新規則進行修改。當所有螞蟻都建立了完整的路徑時，就套用全局更新規則對路徑上的信息軌跡量再次進行修改。這樣直至整個搜尋過程結束。

蟻群系統的實現過程

圖1為蟻群系統流程圖，蟻群系統的實現過程如下：

圖1 蟻群系統流程圖

(1) 初始化，設定參數，初始化蟻群A(t)；

(2) 疊代循環：將每隻螞蟻都置於一個起始節點上；

(3) 步循環：每隻螞蟻在建立完整路徑的過程中都重複套用狀態轉移規則，並對信息素進行局部更新，一直持續到所有的螞蟻都建立了完整的路徑；

(4) 將新信息素進行全局更新；

(5) 滿足終止條件後結束。

蟻群系統的狀態轉移規則

在蟻群系統一隻位於節點r的螞蟻通過偽隨機比例規則，即式(1)，選擇下一個將要移動到的城市k。

式1

其中，如果 ，則按先驗知識選擇路徑；否則，按式(2)進行機率搜尋。

式2

式(3)

其中， 表示相鄰兩個城市i、j之間的距離；η_ij為能見度因數； 表示在t時刻，處於城市i的螞蟻k(k=1，2，3，…，m)選擇城市j的機率； 表示允許螞蟻k下一步要選擇的城市； 為信息素因數；常數 為信息啟發式因子，反映了螞蟻在運動過程中所積累的信息素的相對重要性。反映了螞蟻在運動過程中所積累的信息在螞蟻運動時所起的作用，其值越大，則該螞蟻越傾向於選擇其他螞蟻經過的路徑，螞蟻之間協作性越強；參數 為期望啟發式因子，反映了啟發信息在路徑選擇中的相對重要性。即啟發信息在螞蟻選擇路徑中的受重視程度，其值越大，則該狀態轉移機率越接近於貪心規則。

這個狀態轉移規則傾向於選擇短的且有著大量信息素的邊作為移動方向。當一隻螞蟻將要從城市r移動到城市k時，首先，它要選取一個隨機數q(0≤q≤1)。當q≤ ，時，則依據先驗知識(根據式子(1))選擇最好的邊，當q>qo時，按式3機率地選擇一條邊。其中，K即為根據方程式3給出的機率分布產生出來的隨機變數；q是在[0，1]區間均勻分布的隨機變數，參數 (0≤ ≤1)，是螞蟻選擇當前最優移動方式的機率。可以通過調整 的值進而改變算法對新路徑的探索能力，從而決定算法下一步做法是應該探索新區域，還是在目前最優路徑附近。即參數 的大小決定了利用先驗知識與探索新路徑之間的相對重要性。

信息素全局更新規則

在蟻群系統中，信息素全局更新規則是在每次循環之後進行，而且只允許全局最優的那隻螞蟻釋放信息素。更新規則如式子4、5所示。該規則增強了螞蟻搜尋過程的指向性。使得搜尋結果主要集中於最好路徑的周邊範圍內。

式子4：

式子5

其中，為到當前所能找到的全局最優的路徑；參數(0<<1)為信息素揮發因數。由上式看出，信息素的增強(全局更新)只作用那些屬於全局最優路徑的邊上。

信息素的局部更新規則

在確定一個解決方案的過程中，需要採用信息素的局部更新規則，即螞蟻每經過一條邊都套用式6的局部更新規則對該邊信息素進行更新。

式6：

其中，參數的取值範圍為(0，1)。

通過實驗得出，設定，可以產生好的搜尋結果，這裡的n代表城市的數目，Lnn是受到最近的鄰域的啟發而產生的一個路徑長度。當一隻螞蟻走過路徑i，j時，局部更新規則的套用可導致相應的信息素軌跡量慢慢減少。進而降低其他螞蟻選中該邊的機率，可見，局部更新規則可以使得螞蟻探索未用路徑的機率大幅度提高，避免螞蟻收斂於同一搜尋路徑。

蟻群系統算法的特點

(1) 蟻群系統算法具有比較強的並行性。

(2) 蟻群系統算法搜尋較優解的能力很強，該算法將分散式計算、正反饋機制與貪婪式搜尋結合在了一起。

(3) 蟻群系統算法不是通過個體之間直接通信，而是通過信息素進行路徑的確定，這樣的系統可擴充性更好。系統通信開銷不會隨系統中個體增加而明顯增加。

蟻群系統算法存在的缺點

該算法搜尋時間一般較長。在行動中蟻群個體具有運動的隨機性，依靠信息的交換逐漸進化到最優路徑，由於在進化的初級階段上各個路徑的信息素量差別不大，所以群體規模越大，系統越難在較短時間內找出最優路徑。也就是說，雖然通過的信息正反饋，逐漸增大較好路徑上的信息量，但要使得較好路徑上的信息量明顯高於其他路徑上的信息量，而最終收斂於較好的路徑，還需要較長一段時間。