1、蟻群算法簡述及實現1蟻群算法的原理分析蟻群算法是受自然界中真實蟻群算法的集體覓食行為的啟發而發展起來的一種基于群 體的模擬進化算法，屬于隨機搜索算法，所以它更恰當的名字應該叫人工蟻群算法”我們一般簡稱為蟻群算法。M.Dorigo等人充分的利用了蟻群搜索食物的過程與著名的TSP問題的相似性，通過人工模擬蟻群搜索食物的行為來求解TSP問題。螞蟻這種社會性動物，雖然個體行為及其簡單，但是由這些簡單個體所組成的群體卻表現 出及其復雜的行為特征。這是因為螞蟻在尋找食物時，能在其經過的路徑上釋放一種叫做信息素的物質，使得一定范圍內的其他螞蟻能夠感覺到這種物質，且傾向于朝著該物質強度高的方向移動。蟻群的集體

2、行為表現為一種正反饋現象，蟻群這種選擇路徑的行為過程稱之為自催化行為。由于其原理是一種正反饋機制，因此也可以把蟻群的行為理解成所謂的增強型學習系統(Reinforcement Learning System)。引用M.Dorigo所舉的例子來說明蟻群發現最短路徑的原理和機制，見圖1所示。假設D和H之間、B和H之間以及B和D之間(通過C)的距離為1,C位于D和B的中央(見圖1 (a)。 現在我們考慮在等間隔等離散世界時間點(t=0,1,2的蟻群系統情況。假設每單位時間有30只螞蟻從A到B,另三十只螞蟻從 E到D,其行走速度都為1(一個單位時間所走距離為1),在行走時，一只螞蟻可在時刻t留下濃度為

3、1的信息素。為簡單起見，設信息素在時間區間(t+1 , t+2)的中點(t+1.5)時刻瞬時完全揮發。在t=0時刻無任何信息素，但分別有30只螞蟻在B、30只螞蟻在D等待出發。它們選擇走哪一條路徑是完全隨機的，因此在兩個節點上蟻群可各自一分為二，走兩個方向。但在t=1時刻，從A到B的30只螞蟻在通向H的路徑上(見 圖1 (b)發現一條濃度為15的信息素，這是由15只從B走向H的先行螞蟻留下來的；而在通 向C的路徑上它們可以發現一條濃度為30的信息素路徑，這是由15只走向BC的路徑的螞蟻所留下的氣息與 15只從D經C到達B留下的氣息之和(圖1 (c)。這時，選擇路徑的概率 就有了偏差，向C走的螞

4、蟻數將是向 H走的螞蟻數的2倍。對于從E到D來的螞蟻也是如此。E(a)(b)(c)圖1蟻群路徑搜索實例這個過程一直會持續到所有的螞蟻最終都選擇了最短的路徑為止。這樣,我們就可以理解蟻群算法的基本思想：如果在給定點，一只螞蟻要在不同的路徑中選擇,那么，那些被先行螞蟻大量選擇的路徑 (也就是信息素留存較濃的路徑 )被選中的概率就 更大，較多的信息素意味著較短的路徑，也就意味著較好的問題回答。2人工蟻群算法描述蟻群算法可以看作為一種基于解空間參數化概率分布模型（Parameterized ProbabilisticModel）的搜索算法框架 （Model-based search algorithm

5、s）。在蟻群算法中，解空間參數化概率 模型的參數就是信息素，因而這種參數化概率分布模型就是信息素模型。在基于模型的搜索 算法框架中，可行解通過在一個解空間參數化概率分布模型上的搜索產生，此模型的參數用以前產生的解來更新，使得在新模型上的搜索能夠集中在高質量的解搜索空間內。這種方法的 有效性建立在高質量的解總是包含好的解構成元素的假設前提下。通過學習這種解構成元素對解的質量的影響有助于找到一種機制，并通過解構成元素的最佳組合來構造出高質量的解。一般來說，一個記憶模型的搜索算法通常使用以下兩步迭代來解決優化問題：1）可行解通過在解空間參數化概率分布模型上的搜索產生。2）用搜索產生的解來更新參數化概

6、率模型，即更新解空間參數化概率分布的參數，使得在新模型上的參數搜索能夠集中在高質量的解搜索空間內。在蟻群算法中，基于信息素的解空間參數化概率模型（信息素模型）以解構造圖的形式給出。在解構造圖上，定義了一種作為隨機搜索機制的人工蟻群，螞蟻通過一種分布在解構造圖上被稱為信息素的局部信息的指引，在解構造圖上移動，從而逐步的構造出問題的可行。信息 素與解構造圖上的節點或弧相關聯，作為解空間參數化概率分布模型的參數。由于TSP問題可以直接的映射為解構造圖（城市為節點，城市間的路徑為弧，信息素分布在弧上），加之TSP問題也是個NP難題，所以，蟻群算法的大部分應用都集中在TSP問題上。一般而言，用于求解TS

7、P問題、生產調度問題等優化問題的蟻群算法都遵循下面的統一算法 框架。算法1 :求解組合優化問題的蟻群算法設置參數，初始化信息素蹤跡While（不滿足條件時）dofor蟻群中的每只螞蟻for每個解構造步（直到構造出完整的可行解）1）螞蟻按照信息素及啟發式信息的指引構造一步問題的解；2）進行信息素局部更新。（可選）en dforendfor1）以某些已獲得的解為起點進行鄰域（局部）搜索;（可選）2）根據某些已獲得的解的質量進行全局信息素更新。en dwhileend在算法1中，螞蟻逐步的構造問題的可行解，在一步解的構造過程中，螞蟻以概率方式選擇 信息素強且啟發式因子高的弧到達下一個節點，直到不能繼

8、續移動為止。此時螞蟻所走過的路徑對應求解問題的一個可行解。局部信息素更新針對螞蟻當前走過的一步路徑上的信息素進行，全局信息素更新是在所有螞蟻找到可行解之后，根據發現解的質量或當前算法找到的最好解對路徑上的信息素進行更新。3蟻群算法與其他搜索算法比較3.1蟻群算法與進化算法比較近年來，遺傳算法（GA）、進 化規劃（Evoluti on ary Pla nnin g）、進化策 略（Evolutio nary Strategies）在理論和應用上發展迅速、效果顯著并逐漸走向了融合，形成了一種新穎的模擬進 化的計算理論 ,統稱為進化計算 (Evolutionary Computation) 。因此我們

9、可以用進化計算作為代 表與蟻群算法進行比較 ,從另一個角度來認識蟻群算法 ,加深對蟻群算法的理解。蟻群算法與進化計算的相似之處有兩點：首先 ,兩種算法均采用群體表示問題的解 ;其次,新群體通過包含在群體中與問題相關的知識來生成。 兩者的主要區別在于進化計算中所有問 題的的知識都包含在當前群體中,而蟻群算法中代表過去所學的知識保存在信息素的蹤跡中。3.2 蟻群算法與模擬退火算法比較從模擬退火算法的搜索策略可以看出蟻群算法和模擬退火算法(SA) 從本質上來講是一致的。SA 對某個 “固體的 ”一個微觀狀態 i 計算其能量 Ei 的過程與螞蟻的一次 “周游 ”一樣,都是 對解空間的一次采樣 ;“退火

10、 ”與“分泌信息素 ”都是利用積累信息來增強對子空間的搜索;而“ Metropolis準則”和 隨機狀態轉移規則”類似，都是使算法能夠跳出局部最優 ，在一定范圍內 接受惡化解 ,搜索新的子空間。因此 ，SA 已經非常成熟的收斂性研究對分析設置螞蟻規模參數和信息素分布策略對最 終解質量的影響有很大的借鑒意義。 對于 SA 的收斂性分析一般分兩種情況 ，齊次 Markov 鏈 和非齊次 Markov 鏈。齊次 Markov 鏈的分析結果告訴我們 ，在任意溫度 t，SA 都達到平衡分布 的情況下，當t T0時,SA將收斂于全局最優。也就是說,在任意溫度t,SA都要遍歷整個解空間。 那么，如果我們保留

11、sA采樣后的當前全局最優解，則即使在任何溫度t,SA都會收斂于全局最 優。換句話說 ,對于蟻群算法 ,如果螞蟻數量 (規模)足夠多 ,能夠保證對解空間的遍歷 ,那么即使 不用信息素 ,也能保證全局收斂。不過這種方法顯然就是一種盲目隨機搜索,沒有任何實際的應用價值。對于非其次 Markov鏈的SA,即在某個固定溫度t,采樣次數有限，而 t將無限趨近于0的 情況下，結論告訴我們當控制參數序列滿足一定條件時,SA才收斂于整體最優解集。其更直接的表述方式是：控制參數t的衰減量與在溫度t下的采樣數之間存在一種均衡 :t的衰減量越大， 則在溫度藝下的采樣數就必須越多；反之，若t的衰減量緩慢，則在每個溫度下

12、 SA只需進行少量采樣。那么。從蟻群算法的角度可以看到 ：因為螞蟻的規模實際上影響的只是信息素更新的頻 率，所以當規模設置較大時 ，每次更新信息素時 ，可以以較快的速度拉大不同狀態上的信息素 差距 ；當規模較小時 ，每次只對信息素進行少量更新 ，以免算法早熟。由此可見，對蟻群算法的參數設置可以直接利用SA中對冷卻進度表”的研究成果。此外 ，既然兩者在本質上一致 ，那么 SA 的一些改進和變異可以直接用在蟻群算法上以改 進其性能。3.3 蟻群算法與神經網絡比較由許多并發、局部交互的單元 (人工螞蟻 )組成的蟻群 ，可以看成是一種 “連接”系統。 “連 接系統最具代表性的例子是神經網絡 (Neur

13、al Network,簡稱NN)。從結構上看，蟻群算法與通 常的神經網絡具有類似的并行機制。 螞蟻訪問過的每一個狀態 i 對應于神經網絡中的神經元 i,與問題相關的狀態i的鄰域結構與神經元i中的突觸連接相對應。螞蟻本身可以看成是通 過神經網絡的并發輸入信號 ，以修改突觸與神經元之間的連接強度。信號經過隨機轉換函數 的局部反傳 ，使用的突觸越多 ，兩個神經元之間的連接越強。蟻群算法中的學習規則可以解釋 為一種后天性的規則 ，即質量較好的解包含連接信號的強度高于質量較差的解。4 基本蟻群算法及其實現4.1 引言蟻群在覓食過程中總能找到蟻巢和食物源之間的最短路徑。受螞蟻的這種行為啟發，意大利學者M.

14、Dorigo、V.Maniezzo以及A.Colorni首先提出了一種新型的隨機搜索模擬進化算 法一螞蟻系統(Ant System,簡稱As)。AS算法是第一個蟻群算法的模型，被稱為基本蟻群算法。AS算法首先被用來求解 TSP問題,并取得了巨大成功。 實驗結果顯示 AS算法具有很強的發 現較好解的能力，但同時也存在一些缺點，如收斂速度較慢、易出現停滯現象等等。針對AS算法的不足之處，許多學者對其進行了深入的研究，提出了一些改進的蟻群算法，如帶精英策略的螞蟻系統(Ant System With elitist strategy，簡稱 ASeiitist、蟻群系統(Ant Colorni Syst

15、em，簡稱 ACS)、基于優化排序的螞蟻系統(Rank-Based Version of Ant System,簡稱AS rank)、最大-最小螞蟻系統(Max-Min Ant System,簡稱MMAS)以及最優-最差螞蟻系統(Best-Worst Ant System, 簡稱BWAS)等等。4.2螞蟻系統的模型描述為了說明螞蟻系統的模型，首先引入TSP問題。一般地來說，旅行商問題(Traveling Salesman Problem,簡稱TSP問題)可以描述如下：設C=Ci,q,6為n個城市的集合 丄=L j|Ciy C 是c中元素兩兩連接的集合，G=(C丄) 是一個圖，已知各城市之間的距

16、離,TSP問題的求解目的是從 G中找出長度最短的Hamiltonian 圈,即找出對C=Cl,c2,，碼中n個城市訪問且只訪問一次的最短的一條封閉曲線。TSP問題分為對稱型和非對稱型。在對稱型TSP問題中，有dj=dji, ci, cj C1,2，n, dij是lij的長度;在非對稱型TSP問題中，至少存在一對Ci, ci C，使 dij工”。為了模擬實際螞蟻的行為，我們首先引入如下記號：m蟻群中螞蟻的數量；bi (t) t時刻位于城市i的螞蟻數,m=;dij 兩城市i和j之間的距離；n邊(i,j)的能見度，反映由城市i轉移到城市j的啟發程度，這個量在螞蟻的運行中不改 變；ij (t) t時刻

17、邊(i,j)上的信息素量； j 本次迭代中邊ij上的信息素增量；(t)在t時刻螞蟻k從城市i轉移到城市j的概率；每只螞蟻都具有以下特性：(1) 完成一次循環后，螞蟻在其訪問過的每條邊上留下相應的信息素；(2) 螞蟻依據概率選擇下一個將要訪問的城市，這個概率是兩城市間距離及連接兩個城市的邊上信息量的函數；(3) 為了滿足問題的約束條件 ，在完成一次循環之前，不允許螞蟻選擇己經訪問過的城市，該過程由螞蟻的禁忌表來控制。 設tabuk為螞蟻k的禁忌表,則螞蟻在經過城市i以后,就將城 市i加入到自己的禁忌表 tabuk、中，表示下次不能再選擇城市 i。用tabuk(s)表示禁忌表中第s個元素，也即螞蟻

18、走過的第 s個城市。于是AS算法可以表述如下：在算法的初始時刻，將m只螞蟻隨機的放到 n座城市，同時, 將每只螞蟻的禁忌表的第一個元素設置為當前它所在的城市。初始時刻，各條路徑上的信息素量相等，設ij (0) =C (C為一較小的常數)。然后每只螞蟻按照各條路徑上的信息素量和啟 發式信息(兩城市間的距離)獨立的選擇下一座城市，螞蟻系統所用的狀態轉移規則稱為隨機 比例規則。在t時刻，螞蟻k在城市i選擇城市j的轉移概率 (t)為：,j allowed,0.(4.1)其中allowed k =1,2,ntuk表示螞蟻下一步允許選擇的城市。列表tabuk記錄了螞蟻k當前走過的城市。當所有n座城市都加入

19、到tabuk中時，螞蟻k便完成了一次周游，此時螞蟻k 所走過的路徑便是 TSP問題的一個可行解。式（4.1）中的n通常取城市i和城市j之間距離的 倒數。a和B分別表示信息素和啟發式因子的相對重要程度。當所有螞蟻完成一次周游以后，各路徑上的信息素根據下式更新。(4.2)Ty(t + n) = p Ty(t) +AT|；呵=s云k =1（4.3）其中匕（0|l）表示信息殘留系數，用1-表示信息素的揮發系數。I k關于 的計算方法，M.Dorigo曾給出三種不同的實現方法，分別對應三種不同的螞蟻系 統模型 ant-cycle system、ant-density system 以及 ant- qua

20、ntity system。它們的區另U在于表達式 ki的不同。在 ant-cycle system 模型中:.若螞巖k在本次管幵中經過邊ij0, oth(4.4)在 ant-density system 模型中:扇=伶若媽斷在松拠中経過刪(4.5)0. otherwise在 ant- quantity system 模型中：亠&若螞蟻比在本次循殲中經過邊耳Tij - （0, niherwLSC（ 46）上面公式中，Q為一正常數，表示螞蟻循環一周或者一個過程在經過的路徑上所釋放的信 息素總量。Lk表示第k只螞蟻在本次循環中所經過的路徑的長度。以上三種模型的區別在于：第一種模型利用的是蟻群的整體信息 ，即走完一個循環以后才 進行殘留信息量的全局調整 ；而后兩種模型中螞蟻每走一步 （即從時間t到t+1）都要更新殘留 的信息量，而不是等到所有的螞蟻完成對所有的城市訪問以后。4.3螞蟻系統模型的實現從上面的螞蟻系統模型來看，其尋找最優解的