群智能蟻群算法及其改進策略研究

摘要：本文首先介紹了群智能理論的產生、蟻群的覓食行為以及螞蟻的信息系統，其次介紹了蟻群算法的基本原理以及基本模型。最后對蟻群算法的改進策略和未來的發展方向進行了探討。

關鍵詞：蟻群算法；螞蟻系統；信息素；改進算法

中圖分類號：TP183文獻標識碼：A文章編號：1009-3044(2008)15-20ppp-0c

Research on Ant Colony Algorithm Based on Swam Intelligence and its' Improve Algorithm

BAO Dan-dan，WANG Hong

(College of Computer Science，South-central University for Nationalities，Wuhan 430074，China)

Abstract:A survey of origin of swam intelligence are presented in this paper.At first ant colonies foraging behavior and their communication system are briefly introduced.then the basic principle and the basic model of artificial ant colony algorithm is presented.Finally the improve algorithm about ACA and the future works are discussed.

Key words:Ant Colony Algorithm;ant system;pheromone;Improve algorithm

1 引言

群智能(Swarm Intelligence，SI)的概念最早由Beni，Hack-wood和wang在分子自動機系統中提出。群智能的一種定義是：任何一種由昆蟲群體或其它動物社會行為機制而激發設計出的算法或分布式解決問題的策略均屬于群智能。這里，Swarm可被描述為一些相互作用相鄰個體的集合體，蜂群、蟻群、鳥群都是Swarm的典型例子。每只螞蟻的智能并不高，但它們卻能協同工作，依靠群體能力發揮出超出個體的智能，且這種能力不是多個個體之間的能力通過簡單疊加所獲得的，其根本原因在于個體之間存在著信息交互能力。信息的交互過程不僅僅在群體內傳播了信息，而且群內個體還能處理信息，這樣就使得群體涌現出一些單個個體所不具備的能力和特性尤其是對環境的適應能力。這種對環境變化所具有的適應能力可以被認為是一種智能，也就是說動物個體通過聚集成群而涌現出了智能。

生物學家和仿生學家觀察研究發現，螞蟻在覓食走過的路徑上釋放一種特有的分泌物—信息素(Pheromone)，螞蟻個體之間正是通過這種信息素傳遞信息，從而相互協作，完成從蟻穴到食物源尋找最短路徑的復雜任務。從螞蟻群體尋找最短路徑覓食行為受到啟發，意大利學者Dorigo等人1991年提出了一種模擬自然界蟻群行為的模擬進化算法—人工蟻群算法，簡稱蟻群算法。蟻群算法(ant colony algorithm，ACA)是最新發展起來的模擬昆蟲王國中螞蟻群體智能行為的仿生優化算法，它具有較強的魯棒性、優良的分布式計算機制、易于與其它方法相結合等優點。

2 蟻群算法的基本原理

蟻群算法不需要任何先驗知識，最初只是隨機選擇搜索路徑，隨著對解空間的“了解”，搜索變得有規律，并逐漸逼近直至最終達到全局最優解。蟻群算法對搜索空間的“了解”機制主要包括三個方面[1]：

⑴螞蟻的記憶。一只螞蟻搜索過的路徑在下次搜索時候不會再被選擇，由此在蟻群算法中建立tabu（禁忌）列表來進行模擬。

⑵螞蟻利用信息素(pheromone)進行相互通信。螞蟻在所選擇的路徑上會釋放一種叫做信息素的物質，當同伴進行路徑選擇時，會根據路徑上的信息素進行選擇，這樣信息素就成為螞蟻之間進行通訊的媒介。

⑶螞蟻的集群活動。通過一只螞蟻的運動很難到達食物源，但整個蟻群進行搜索就完全不同，當某些路徑上通過的螞蟻越來越多時，在路徑上留下的信息素數量也越來越多，導致信息素強度增大，螞蟻選擇該路徑的概率隨之增加，從而進一步增加該路徑的信息素強度，而某些路徑上通過的螞蟻較少時，路徑上的信息素就會隨時間的推移而蒸發，因此，模擬這種現象即可利用群體智能建立路徑選擇機制，使蟻群算法的搜索向最優解推進。

蟻群算法所利用的搜索機制呈現出一種自催化或正反饋的特征，因此，可將蟻群算法模型理解成增強型學習系統，圖1說明了螞蟻群體的路徑搜索原理和機制。假定障礙物的周圍有兩條路可以從蟻巢到達食物，即（蟻巢-ABD-食物）和（蟻巢-ACD-食物），路徑的長度分別為4和6 。每只螞蟻在單位時間內移動一個單位長的距離，并在走過的路徑上遺留一個單位的信息素。開始時所有道路上未留有任何信息素，假設在t=0時刻，有20只螞蟻從蟻巢出發移動到A。它們以相同概率選擇左側或右側的路徑，因此有10只螞蟻走左側，10只走右側。在t=4時刻，第一批找到食物的螞蟻將返回，在t=5時刻，兩批螞蟻將在D點相遇，此時BD上的信息素數量與CD上的相同，因為各有10只螞蟻選擇了相應的道路。從而有5只返回的螞蟻將選擇DB而另5只選擇DC。在t=9時刻，前5只螞蟻又返回A并且再次進行往左還是往右的選擇。這時，AB上的信息素數量是20而AC上是15，因此將有較多的螞蟻選擇往左，從而增加了該路徑的信息素數量。隨著這種過程的不斷進行，兩條路徑上的信息素數量的差距將越來越大，直到絕大多數螞蟻都選擇了最短的路徑，正是由于一條路要比另一條路短，因此，在相同的時間區間內，短的路線會有更多的機會被選中。

3蟻群算法

3.1基本蟻群算法模型

為模擬實際螞蟻的行為，首先引進如下記號[2]：

設：m——蟻群中螞蟻的數量；

ηij——邊弧（i，j）的能見度；

τij——t時刻在ij之間路徑上的信息量；

Δτkij——螞蟻本次遍歷中信息素濃度的增量;

Pkij(t)——表示在t時刻螞蟻k從城市i移動到城市j的概率，j是此次遍歷中還未訪問的城市;

α——軌跡的相對重要性（α≥0）；

β——能見度的相對重要性（β≥0）；

ρ——軌跡的持久性（0≤ρ≤1），1－ρ理解為軌跡衰減度；

Q——體現螞蟻所留軌跡數量的一個常數。

現以求解n個城市的TSP問題為例，說明蟻群系統模型。

旅行商問題是指，給定n個城市和每個城市之間的距離，要求確定一條經過每個城市一次且只有一次的最短路徑。初始時刻，各條路徑上信息量相等，設τij（0）=C（C為常數），螞蟻k（k=1，2，3…，m）在運動過程中，根據各條路徑上的信息量決定轉移方向，移動概率為

bdd02.tif

其中，allowedk ={0，1，…，n-1}－tabuk表示螞蟻k下一步允許選擇的城市，與實際蟻群不同，人工蟻群系統具有記憶功能，tabuk(k=0，1，…，m)用以記錄螞蟻K當前所走過的城市，集合tabuk 隨著進化過程做動態調整。隨著時間的推移，以前留下的信息逐漸消逝，用參數1-ρ表示信息消逝程度，經過n個時刻，螞蟻完成一次循環，各路徑上信息量要根據下式進行調整：

τij（t+n）=ρ?τij（t）+（1-ρ）?Δτij

Δτij=∑Δτkij

其中，Δτkij 表示第k只螞蟻在本次循環中留在路徑（i，j）上的信息量，Δτij表示本次循環中路徑（i，j）上的信息量的增量。在初始時刻，τij（0）=C（C為常數），Δτij=0

（i ，j =0，1，…，n-1）。ηij 表示從城市i轉移到城市j的期望程度，可根據某種啟發式算法具體確定。根據具體算法的不同，τij（t），Δτij 及Pkij的表達式可以不同，要視具體問題而定。

基本蟻群算法的主要步驟敘述如下：

步驟1：nc=0（nc為迭代步數或搜索次數），各τij 和Δτij 的初始化，將m個螞蟻置于n個頂點上；

步驟2：將各螞蟻的初始出發點置于當前解集中，對螞蟻k(k=1，…，m)，按概率Pkij 移至下一頂點j，將頂點j置于當前解集；

步驟3：計算各螞蟻的目標函數值Zk (k=1，…，m)，記錄當前的最好解；

步驟4：按更新方程修改軌跡強度；

步驟5：對各邊弧（i ， j），置Δτij =0，nc = nc＋1；

步驟6：若nc<預定的迭代次數，則轉步驟2。

3.2 對基本蟻群算法的改進策略

3.2.1 對選擇策略的改進

在蟻群算法中，在螞蟻搜索過程的起始階段，有的路徑上有螞蟻走過，有的路徑還未來的及被走過，而螞蟻選路的策略是一旦有路徑上的信息素，即信息量多于其他路徑，它就以較大的概率選擇該路徑，這使得螞蟻從搜索的一開始就以較大的概率集中在幾條當前局部長度較短的路徑上。為了避免螞蟻一開始就失去解的多樣性，在路徑上信息量的刺激量未達到螞蟻的絕對感覺閾限時，讓螞蟻忽視該刺激物的存在，只有當信息量的刺激趨于閾限為ρ0

時，螞蟻才在信息量的刺激下趨于信息量較大的路徑。這樣螞蟻在初始階段可選擇較多不同路徑，以獲得多樣性的解。

3.2.2 蟻群信息量的全局修正

信息量的全局修正規則如下

τij（t+n）=ρ?τij（t）＋（1-ρ）?Δτij

其中Δτij=Δτkij ，第K只螞蟻是發現本次循環中最短路徑的螞蟻。

全局修正規則只是讓實現最好環游的螞蟻釋放信息素。它和改進的狀態轉移規則結合的搜索，保證了螞蟻在優秀父輩完成的環游領域內進行更多搜索，這使得求解速度大大提高。

4 蟻群算法改進的思路和應用前景

由于基本蟻群算法利用隨機選擇策略，使得進化速度較慢；同時蟻群算法旨在利用正反饋原理和分布式計算的模式，卻未能較好地加快進化過程及避免過早收斂，反而容易出現停滯現象。針對蟻群算法加速收斂與早熟、停滯 現象等的矛盾和尋找最優解的時間過長等缺點，可以從以下方向改進蟻群算法。

（1）算法的自適應性。①從選擇概率來看，可以采用不同的階段使用不同的選擇概率，在尋路的過程中動態地調整選擇概率，并且可以使用選擇概率的不同方法。②信息素更新策略的自適應，應該能對信息素進行動態更新和自適應調節。③如果把尋路過程優化為幾個不同的階段，并且在不同階段采用不同的方法，則應該自適應地分析蟻群個體進行的程度已經到哪個階段了，選擇應該執行什么樣的策略等。④蟻群算法的公式中各個參數的自適應選擇。

（2）初始解的優化。由于各個路徑上的初始信息素是相同的，初始解即第一次選擇的路徑很可能對整個蟻群的進化過程產生誤導，必須提高初始解的質量，盡量擴大在初始階段可以選擇路徑的數目，以增加解的多樣性。

（3）信息素動態更新策略。信息素的濃度強弱直接關系到螞蟻個體的尋優過程。如何讓信息素動態、自適應地更新，如何通過信息素作用的擴散和信息素種類的增加等方法來達到螞蟻間的協作，以及如何調整信息素的更新公式，都是非常重要的。

⑷路徑選擇概率的適應性調整。①應該實現選擇概率的自適應；②按照不同的應用，不同的實際環境等合理設計和調整選擇概率公式等。

（4）門檻值的設計。定義信息素、選擇概率等發揮作用的區間或臨界點，把蟻群算法分為不同的階段，不同的策略來實施等，也輔助了自適應的實現。

（5）螞蟻的協作。已經有較多研究提到了螞蟻間的協作，并且有研究者提出要把螞蟻分成多類，不同的類別實現不同的策略、完成不同的工作，然后再通過螞蟻間的協作達到更優的策略。正如在真實的蟻群世界中，螞蟻也是被分了類的，不同類別的螞蟻完成不同的工作。螞蟻的協作在一定程度上優化了算法，但也增加了算法的復雜性。

以上是蟻群算法中最重要的改進和優化的主要方向，當然還有蟻群算法中參數的優化，如信息素揮發系數的優化等。

5 結語

蟻群算法的理論研究和實際應用表明，它是一種很有前途的仿生優化算法。隨著人類認識的進步和社會發展的加速，仿生智能及最優化系統理論將越來越成為科學認識和工程時間的有力工具，蟻群算法理論及其應用的研究必將是一個長期的研究課題。蟻群算法這一新興的仿生優化算法必將展現出更加廣闊、更加引人注目的發展前景。

參考文獻：

[1] M Dorigo，V Maniezzo A， Colomi ColomiA， DorigoM， ManiezzoV. Distributed optimization by ant colonies [A] .proc 1 European conf art ificial Life[C] .Pans，Francer:Elsevier，1991.134- 142.

[2] 熊偉清，余舜杰，趙杰煜.具有分工的蟻群算法及應用[J].模式識別與人工智能，2003，16(3).

[3] M Dorigo，LMG ambardella. Ant Colonies for the Traverling Salesman Problem .BioSystems，1997(43):73-81.

[4] 陳永強，人工蟻群算法及其在組合優化中的應用[D].哈爾濱：哈爾濱工業大學，2003.

[5] 馬良，項培軍.螞蟻算法在組合優化中的應用[J].管理科學學報，2001，4(2):32-36.

[6] 候立文，蔣馥.一種基于螞蟻算法的交通分配方法及其應用[J].上海交通大學學報，2001，35(6).

收稿日期：2008-03-12