蟻群優(yōu)化算法研究

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