長(zhǎng)江大學(xué)學(xué)報(bào)(自然科學(xué)版) 2009年9月第6卷第3期: 理工Journal of Yangtze University (Nat Sci Edit) Sep. 2009，Vol.6 No.3: Sei & Eng，221●蟻群優(yōu)化算法研究王同喜(長(zhǎng)江大學(xué)計(jì)算機(jī)科學(xué)學(xué)院， 湖北荊州434023)[摘要] 由傳統(tǒng)的蟻群優(yōu)化算法入手， 介紹了蟻群優(yōu)化算法的基本原理以及在TSP問(wèn)題中的應(yīng)用，分析并總結(jié)了蟻群算法在信息素更新、路徑構(gòu)造等方面的改進(jìn)方法。[關(guān)鍵詞]蟻群算法;組合優(yōu)化; TSP[中圈分類(lèi)號(hào)] TP301. 6.[文獻(xiàn)標(biāo)識(shí)碼] A [文章編號(hào)] 1673- 1409 (2009) 03- N221 -02蟻群優(yōu)化算法是一種源于大自然中生物世界的新的仿生類(lèi)算法。它吸收了螞蟻的行為特性，通過(guò)其內(nèi)在的搜索機(jī)制，在一系列的組合優(yōu)化問(wèn)題求解中取得了成效。意大利學(xué)者Dorigo 在1991年至1992年間提出螞蟻密度(ant-density)、 螞蟻數(shù)量(ant-quantity)、 螞蟻周期(ant-cycle) 3種算法模型1。其中前2個(gè)算法模型因?yàn)槠涞土拥男阅芤呀?jīng)淘汰，現(xiàn)在的蟻群優(yōu)化算法由螞蟻周期演變而來(lái)。蟻群優(yōu)化算法的一般步驟如下:①將待解問(wèn)題抽象成以成分和狀態(tài)變換的集合形式，或者以帶權(quán)圖的形式，蟻群將利用這些形式建立問(wèn)題的解;②定義信息素r的合適含義;③定義一個(gè)合理的啟發(fā)信息素η; ④在條件允許的情況下，使用合適有效的局部搜索算法;⑤選擇某種具體的蟻群優(yōu)化算法;⑥調(diào)整算法參數(shù)，跳轉(zhuǎn)到第4步直到滿(mǎn)足某種結(jié)束條件,算法結(jié)束。1 TSP 中的蟻群優(yōu)化算法以求解n個(gè)城市的對(duì)稱(chēng)TSP問(wèn)題為例，建立基本螞蟻算法模型。首先，對(duì)算法中的參數(shù)和變量進(jìn)行說(shuō)明。記M為蟻群中螞蟻的數(shù)量,c。為城市ivj間的距離的權(quán)值,ty(I)為t時(shí)刻城市i、j間路徑的軌跡強(qiáng)度,即殘留的信息素濃度,物為城市i、j間路徑的能見(jiàn)度，即啟發(fā)信息素,在TSP問(wèn)題中一般取值1/cg，a表示軌跡的相對(duì)重要性(a≥0),β表示能見(jiàn)度的相對(duì)重要性(β≥0),帕(t)為I時(shí)刻螞蟻k選擇j作為下一個(gè)訪(fǎng)問(wèn)城市的轉(zhuǎn)移概率,定義為:。[r,]°[n衛(wèi)如果j∈N;p()=ScxJ[P否則其中,Nt為位于城市i的螞蟻k可以直接到達(dá)的相鄰城市的集合。采用蟻群算法求解TSP問(wèn)題的主要步驟如下:步1初始化:n.← 0;(n.為迭代次數(shù)),對(duì)各路徑(i,j),置τ=劃= m/c"(c"為最鄰近啟發(fā)算法構(gòu)造的路徑長(zhǎng)度,一般為估計(jì)值),Org←0 ,將m只螞蟻隨機(jī)分布于城市的m個(gè)頂點(diǎn)上。步2將各螞蟻的初始 出發(fā)點(diǎn)置于當(dāng)前解集中,對(duì)每個(gè)螞蟻k(k = 1,2..m)，按慨率p(t)移至下一頂點(diǎn)j,將頂點(diǎn)j置于當(dāng)前解集中;重復(fù)n-1次該過(guò)程,完成一個(gè)解的構(gòu)造。步3計(jì)算各螞蟻的目標(biāo)函數(shù)值T*(k= 1,2,.. ,m)。步4進(jìn)行解的評(píng) 價(jià),并由解決定反饋給環(huán)境的軌跡更新量。按更新方程修改最好解路徑上的軌跡強(qiáng)度。步5對(duì)各路徑(i,),置t←r+ 二0嗜,即:如果(i,j)在路徑T*上;n.←ne +1到←q+中國(guó)煤化工[收稿日期] 2009 -05 -25CNMH G_[作者簡(jiǎn)介們]王同喜(1971-), 男，1994年大學(xué)畢業(yè)，碩士,講師，現(xiàn)主要從事數(shù)據(jù)庫(kù)、典法刀們刀通的我子=研究工作。，222●長(zhǎng)江大學(xué)學(xué)報(bào)(自然科學(xué)版)2009年9月步6若n 小于預(yù)定的迭代次數(shù)，則轉(zhuǎn)步2,否則結(jié)束。2幾種改進(jìn)的蟻群算法隨著TSP問(wèn)題規(guī)模n的擴(kuò)大，相比其他的啟發(fā)式算法，蟻群算法的性能將嚴(yán)重下降。目前，對(duì)蟻群算法的研究工作都集中在優(yōu)化其參數(shù)配置，改進(jìn)信息素更新規(guī)則，或者與其他啟發(fā)式算法結(jié)合。1)精華螞蟻系統(tǒng) 精華螞蟻系統(tǒng)(elitist strategy for ant system, EAS)是Dorigol2]在 1992年提出，是對(duì)基本蟻群算法的首次改進(jìn)。其改進(jìn)思想是對(duì)m只螞蟻從算法開(kāi)始到目前為止找到的最優(yōu)路徑T"實(shí)施-種強(qiáng)化。信息素釋放規(guī)則改進(jìn)為的←q+ 2st +eO你(e為一常數(shù))。適當(dāng)?shù)膃不但可以得到更好的解,而且可以再更少迭代次數(shù)的情況下得到更好的解，即只有最優(yōu)的螞蟻可以向該路徑T*.2)最大最小螞蟻系統(tǒng)Stuzle & HoosC3] 在對(duì)蟻群算法進(jìn)行深人研究后提出了4點(diǎn)改進(jìn)，產(chǎn)生了最大最小螞蟻系統(tǒng)(max -min ant system, MMAS)。首先,在m只螞蟻的一次迭代過(guò)程中,獲得當(dāng)前迭代最優(yōu)路徑Then的螞蟻釋放信息素,即r←τ +Or5*。其次,將信息素的取值范圍限制在區(qū)間[mn,Tma],這.樣避免了某些邊信息索增長(zhǎng)過(guò)快,導(dǎo)致算法停滯。再次,信息素的初始值為T(mén)max.最后，當(dāng)算法出現(xiàn)停滯或者在達(dá)到一定的迭代次數(shù)后，信息素值重新初始化。3)蟻群系統(tǒng)蟻群系統(tǒng) . (ant colony system, ACS)4I與上述算法的不同主要表現(xiàn)在3個(gè)方面:首先，蟻群系統(tǒng)采用了一種更積極的行為來(lái)構(gòu)建路徑。在ACS中,位于城市i的螞蟻k ,根據(jù)偽隨機(jī)比例規(guī)則選擇城市j作為下一個(gè)訪(fǎng)問(wèn),即:(arg max(re[n]}如果q≤qo否則其中,q是在區(qū)間[0,1]中均勻分布的- -個(gè)隨機(jī)變量,0≤qo≤1;J根據(jù)公式:(_ [ry]°[y]°如果j∈Nt幬(t) =.乙[tv]°[η]°IEN給出的概率分布產(chǎn)生。根據(jù)這個(gè)改進(jìn)的路徑產(chǎn)生規(guī)則,能更好的利用螞蟻所積累的搜索經(jīng)驗(yàn).第二,信息索的揮發(fā)和釋放只在至今最優(yōu)的路徑上執(zhí)行。第三,對(duì)螞蟻每次路徑的邊(i,j),算法主動(dòng)去掉一定的信息素,這樣增加了搜索其他路徑的機(jī)會(huì)。信息素的更新表示τ + (1- p)t; + pQ諧,(p為信息素?fù)]發(fā)速率)。3結(jié)語(yǔ)蟻群優(yōu)化算法作為一種通用型隨機(jī)優(yōu)化算法，自問(wèn)世以來(lái)表現(xiàn)出了強(qiáng)大的生命力，較以往的啟發(fā)式算法在搜索效率和算法的時(shí)間復(fù)雜度方面都取得了令人滿(mǎn)意的效果?，F(xiàn)已陸續(xù)應(yīng)用到組合優(yōu)化、人工智能等多個(gè)領(lǐng)域。螞蟻算法的正反饋性和協(xié)同性使其可用于分布式系統(tǒng)，隱含的并行性更使之具有極強(qiáng)的發(fā)展?jié)摿Α參考文獻(xiàn)][1] Colormi A, Dorigo M, Maniezo V. Distributed optimization by ant colonies [M] . Boston; PWS Publishing, 1991.[2] Dorigo M, Maniezzo V , Colorni A. Ant System: Optimization by a coloay of cooperationg agents [J] . IEEE Transactions on System,1992, 26 (1): 29~41.[3] Stutle T, Hoos H H. The MAX-MIN Ant System and local search for the traveling sales man problem [A] . Proceedings of the 1997IEEE International Conference on Evolutionary Computation (ICEC'97) [C1 : NI: IEEE Press, 1997. 309~314.[4] DorigoM. 蟻群優(yōu)化[M].張軍，胡曉敏,羅旭耀等譯.北京:清華中國(guó)煤化工MHCNMHG輛] 洪云飛