群智能蟻群算法及其改進(jìn)策略研究

摘要：本文首先介紹了群智能理論的產(chǎn)生、蟻群的覓食行為以及螞蟻的信息系統(tǒng)，其次介紹了蟻群算法的基本原理以及基本模型。最后對(duì)蟻群算法的改進(jìn)策略和未來(lái)的發(fā)展方向進(jìn)行了探討。

關(guān)鍵詞：蟻群算法；螞蟻系統(tǒng)；信息素；改進(jìn)算法

中圖分類號(hào)：TP183文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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在分子自動(dòng)機(jī)系統(tǒng)中提出。群智能的一種定義是：任何一種由昆蟲(chóng)群體或其它動(dòng)物社會(huì)行為機(jī)制而激發(fā)設(shè)計(jì)出的算法或分布式解決問(wèn)題的策略均屬于群智能。這里，Swarm可被描述為一些相互作用相鄰個(gè)體的集合體，蜂群、蟻群、鳥(niǎo)群都是Swarm的典型例子。每只螞蟻的智能并不高，但它們卻能協(xié)同工作，依靠群體能力發(fā)揮出超出個(gè)體的智能，且這種能力不是多個(gè)個(gè)體之間的能力通過(guò)簡(jiǎn)單疊加所獲得的，其根本原因在于個(gè)體之間存在著信息交互能力。信息的交互過(guò)程不僅僅在群體內(nèi)傳播了信息，而且群內(nèi)個(gè)體還能處理信息，這樣就使得群體涌現(xiàn)出一些單個(gè)個(gè)體所不具備的能力和特性尤其是對(duì)環(huán)境的適應(yīng)能力。這種對(duì)環(huán)境變化所具有的適應(yīng)能力可以被認(rèn)為是一種智能，也就是說(shuō)動(dòng)物個(gè)體通過(guò)聚集成群而涌現(xiàn)出了智能。

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

2 蟻群算法的基本原理

蟻群算法不需要任何先驗(yàn)知識(shí)，最初只是隨機(jī)選擇搜索路徑，隨著對(duì)解空間的“了解”，搜索變得有規(guī)律，并逐漸逼近直至最終達(dá)到全局最優(yōu)解。蟻群算法對(duì)搜索空間的“了解”機(jī)制主要包括三個(gè)方面[1]：

⑴螞蟻的記憶。一只螞蟻搜索過(guò)的路徑在下次搜索時(shí)候不會(huì)再被選擇，由此在蟻群算法中建立tabu（禁忌）列表來(lái)進(jìn)行模擬。

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

⑶螞蟻的集群活動(dòng)。通過(guò)一只螞蟻的運(yùn)動(dòng)很難到達(dá)食物源，但整個(gè)蟻群進(jìn)行搜索就完全不同，當(dāng)某些路徑上通過(guò)的螞蟻越來(lái)越多時(shí)，在路徑上留下的信息素?cái)?shù)量也越來(lái)越多，導(dǎo)致信息素強(qiáng)度增大，螞蟻選擇該路徑的概率隨之增加，從而進(jìn)一步增加該路徑的信息素強(qiáng)度，而某些路徑上通過(guò)的螞蟻較少時(shí)，路徑上的信息素就會(huì)隨時(shí)間的推移而蒸發(fā)，因此，模擬這種現(xiàn)象即可利用群體智能建立路徑選擇機(jī)制，使蟻群算法的搜索向最優(yōu)解推進(jìn)。

蟻群算法所利用的搜索機(jī)制呈現(xiàn)出一種自催化或正反饋的特征，因此，可將蟻群算法模型理解成增強(qiáng)型學(xué)習(xí)系統(tǒng)，圖1說(shuō)明了螞蟻群體的路徑搜索原理和機(jī)制。假定障礙物的周?chē)袃蓷l路可以從蟻巢到達(dá)食物，即（蟻巢-ABD-食物）和（蟻巢-ACD-食物），路徑的長(zhǎng)度分別為4和6 。每只螞蟻在單位時(shí)間內(nèi)移動(dòng)一個(gè)單位長(zhǎng)的距離，并在走過(guò)的路徑上遺留一個(gè)單位的信息素。開(kāi)始時(shí)所有道路上未留有任何信息素，假設(shè)在t=0時(shí)刻，有20只螞蟻從蟻巢出發(fā)移動(dòng)到A。它們以相同概率選擇左側(cè)或右側(cè)的路徑，因此有10只螞蟻?zhàn)咦髠?cè)，10只走右側(cè)。在t=4時(shí)刻，第一批找到食物的螞蟻將返回，在t=5時(shí)刻，兩批螞蟻將在D點(diǎn)相遇，此時(shí)BD上的信息素?cái)?shù)量與CD上的相同，因?yàn)楦饔?0只螞蟻選擇了相應(yīng)的道路。從而有5只返回的螞蟻將選擇DB而另5只選擇DC。在t=9時(shí)刻，前5只螞蟻又返回A并且再次進(jìn)行往左還是往右的選擇。這時(shí)，AB上的信息素?cái)?shù)量是20而AC上是15，因此將有較多的螞蟻選擇往左，從而增加了該路徑的信息素?cái)?shù)量。隨著這種過(guò)程的不斷進(jìn)行，兩條路徑上的信息素?cái)?shù)量的差距將越來(lái)越大，直到絕大多數(shù)螞蟻都選擇了最短的路徑，正是由于一條路要比另一條路短，因此，在相同的時(shí)間區(qū)間內(nèi)，短的路線會(huì)有更多的機(jī)會(huì)被選中。

3蟻群算法

3.1基本蟻群算法模型

為模擬實(shí)際螞蟻的行為，首先引進(jìn)如下記號(hào)[2]：

設(shè)：m——蟻群中螞蟻的數(shù)量；

ηij——邊弧（i，j）的能見(jiàn)度；

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

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

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

α——軌跡的相對(duì)重要性（α≥0）；

β——能見(jiàn)度的相對(duì)重要性（β≥0）；

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

Q——體現(xiàn)螞蟻所留軌跡數(shù)量的一個(gè)常數(shù)。

現(xiàn)以求解n個(gè)城市的TSP問(wèn)題為例，說(shuō)明蟻群系統(tǒng)模型。

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

bdd02.tif

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

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

Δτij=∑Δτkij

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

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

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

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

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

步驟3：計(jì)算各螞蟻的目標(biāo)函數(shù)值Zk (k=1，…，m)，記錄當(dāng)前的最好解；

步驟4：按更新方程修改軌跡強(qiáng)度；

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

步驟6：若nc<預(yù)定的迭代次數(shù)，則轉(zhuǎn)步驟2。

3.2 對(duì)基本蟻群算法的改進(jìn)策略

3.2.1 對(duì)選擇策略的改進(jìn)

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

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

3.2.2 蟻群信息量的全局修正

信息量的全局修正規(guī)則如下

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

其中Δτij=Δτkij ，第K只螞蟻是發(fā)現(xiàn)本次循環(huán)中最短路徑的螞蟻。

全局修正規(guī)則只是讓實(shí)現(xiàn)最好環(huán)游的螞蟻釋放信息素。它和改進(jìn)的狀態(tài)轉(zhuǎn)移規(guī)則結(jié)合的搜索，保證了螞蟻在優(yōu)秀父輩完成的環(huán)游領(lǐng)域內(nèi)進(jìn)行更多搜索，這使得求解速度大大提高。

4 蟻群算法改進(jìn)的思路和應(yīng)用前景

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

（1）算法的自適應(yīng)性。①?gòu)倪x擇概率來(lái)看，可以采用不同的階段使用不同的選擇概率，在尋路的過(guò)程中動(dòng)態(tài)地調(diào)整選擇概率，并且可以使用選擇概率的不同方法。②信息素更新策略的自適應(yīng)，應(yīng)該能對(duì)信息素進(jìn)行動(dòng)態(tài)更新和自適應(yīng)調(diào)節(jié)。③如果把尋路過(guò)程優(yōu)化為幾個(gè)不同的階段，并且在不同階段采用不同的方法，則應(yīng)該自適應(yīng)地分析蟻群個(gè)體進(jìn)行的程度已經(jīng)到哪個(gè)階段了，選擇應(yīng)該執(zhí)行什么樣的策略等。④蟻群算法的公式中各個(gè)參數(shù)的自適應(yīng)選擇。

（2）初始解的優(yōu)化。由于各個(gè)路徑上的初始信息素是相同的，初始解即第一次選擇的路徑很可能對(duì)整個(gè)蟻群的進(jìn)化過(guò)程產(chǎn)生誤導(dǎo)，必須提高初始解的質(zhì)量，盡量擴(kuò)大在初始階段可以選擇路徑的數(shù)目，以增加解的多樣性。

（3）信息素動(dòng)態(tài)更新策略。信息素的濃度強(qiáng)弱直接關(guān)系到螞蟻個(gè)體的尋優(yōu)過(guò)程。如何讓信息素動(dòng)態(tài)、自適應(yīng)地更新，如何通過(guò)信息素作用的擴(kuò)散和信息素種類的增加等方法來(lái)達(dá)到螞蟻間的協(xié)作，以及如何調(diào)整信息素的更新公式，都是非常重要的。

⑷路徑選擇概率的適應(yīng)性調(diào)整。①應(yīng)該實(shí)現(xiàn)選擇概率的自適應(yīng)；②按照不同的應(yīng)用，不同的實(shí)際環(huán)境等合理設(shè)計(jì)和調(diào)整選擇概率公式等。

（4）門(mén)檻值的設(shè)計(jì)。定義信息素、選擇概率等發(fā)揮作用的區(qū)間或臨界點(diǎn)，把蟻群算法分為不同的階段，不同的策略來(lái)實(shí)施等，也輔助了自適應(yīng)的實(shí)現(xiàn)。

（5）螞蟻的協(xié)作。已經(jīng)有較多研究提到了螞蟻間的協(xié)作，并且有研究者提出要把螞蟻分成多類，不同的類別實(shí)現(xiàn)不同的策略、完成不同的工作，然后再通過(guò)螞蟻間的協(xié)作達(dá)到更優(yōu)的策略。正如在真實(shí)的蟻群世界中，螞蟻也是被分了類的，不同類別的螞蟻完成不同的工作。螞蟻的協(xié)作在一定程度上優(yōu)化了算法，但也增加了算法的復(fù)雜性。

以上是蟻群算法中最重要的改進(jìn)和優(yōu)化的主要方向，當(dāng)然還有蟻群算法中參數(shù)的優(yōu)化，如信息素?fù)]發(fā)系數(shù)的優(yōu)化等。

5 結(jié)語(yǔ)

蟻群算法的理論研究和實(shí)際應(yīng)用表明，它是一種很有前途的仿生優(yōu)化算法。隨著人類認(rèn)識(shí)的進(jìn)步和社會(huì)發(fā)展的加速，仿生智能及最優(yōu)化系統(tǒng)理論將越來(lái)越成為科學(xué)認(rèn)識(shí)和工程時(shí)間的有力工具，蟻群算法理論及其應(yīng)用的研究必將是一個(gè)長(zhǎng)期的研究課題。蟻群算法這一新興的仿生優(yōu)化算法必將展現(xiàn)出更加廣闊、更加引人注目的發(fā)展前景。

參考文獻(xiàn)：

[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，F(xiàn)rancer:Elsevier，1991.134- 142.

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

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

[4] 陳永強(qiáng)，人工蟻群算法及其在組合優(yōu)化中的應(yīng)用[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2003.

[5] 馬良，項(xiàng)培軍.螞蟻算法在組合優(yōu)化中的應(yīng)用[J].管理科學(xué)學(xué)報(bào)，2001，4(2):32-36.

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

收稿日期：2008-03-12