易正俊，李勇霞，易校石

(1.重慶大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，重慶 401331;2.重慶師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，重慶 401131)

自適應(yīng)蟻群算法求解最短路徑和TSP問(wèn)題

易正俊1，李勇霞1，易校石2

(1.重慶大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，重慶 401331;2.重慶師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，重慶 401131)

對(duì)傳統(tǒng)蟻群算法的初始化信息素濃度加入方向引導(dǎo)，避免蟻群在初始階段盲目地隨機(jī)搜索浪費(fèi)較多的時(shí)間；在全局信息素更新過(guò)程中加入雙曲正切函數(shù)作為動(dòng)態(tài)因子，自適應(yīng)地更新每次迭代較優(yōu)解路徑的信息素濃度，增大算法獲取全局最優(yōu)解的可能性。兩個(gè)算例采用改進(jìn)的蟻群算法進(jìn)行優(yōu)化，優(yōu)化的結(jié)果與實(shí)際情形具有良好的一致性，說(shuō)明了改進(jìn)算法的有效性和實(shí)用性。

蟻群算法；最短路徑；方向引導(dǎo)；動(dòng)態(tài)因子：旅行商問(wèn)題

0 引 言

蟻群算法(Ant Colony System,ACS)是由意大利學(xué)者Dorigo等于20世紀(jì)90年代初期提出的一種基于種群的啟發(fā)式隨機(jī)搜索算法[1-4]。蟻群算法具有正反饋、魯棒性、并行性等優(yōu)點(diǎn),有很多文獻(xiàn)采用蟻群算法計(jì)算最短路徑的問(wèn)題。最短路徑問(wèn)題在交通運(yùn)輸、物流配送、網(wǎng)絡(luò)分析、管道鋪設(shè)、廠區(qū)選取等領(lǐng)域有廣泛的應(yīng)用。如交通運(yùn)輸往往需要盡可能降低運(yùn)輸成本,等價(jià)于搜索運(yùn)輸網(wǎng)中兩節(jié)點(diǎn)的最短路徑；但傳統(tǒng)的蟻群算法在計(jì)算較復(fù)雜的網(wǎng)絡(luò)圖中兩節(jié)點(diǎn)間的最短距離時(shí)容易陷入局部最優(yōu)，且隨著網(wǎng)絡(luò)圖的復(fù)雜程度的增加其收斂速度慢,還有可能出現(xiàn)停滯現(xiàn)象[5-6]。針對(duì)這些問(wèn)題，有學(xué)者對(duì)傳統(tǒng)的蟻群算法做了一些相應(yīng)改進(jìn)。有的將信息素濃度控制在一定范圍內(nèi)變化，避免螞蟻都選擇同一條路徑，避免算法中的停滯現(xiàn)象。Stuzle等[7]提出“最大最小蟻群系統(tǒng)”(Max-Min Ant System);Clornei等[8]將蟻群算法和遺傳算法相結(jié)合,增強(qiáng)了算法的尋優(yōu)能力；鄭衛(wèi)國(guó)等[9]提出帶獎(jiǎng)罰的蟻群算法，對(duì)較優(yōu)信息素濃度進(jìn)行獎(jiǎng)勵(lì)，對(duì)較差信息素濃度進(jìn)行懲罰。這些改進(jìn)的蟻群算法雖然獲得了較好的最優(yōu)解，但初始搜索時(shí)間較長(zhǎng)，全局更新規(guī)則中沒(méi)有考慮較優(yōu)解。

文中對(duì)初始信息素濃度進(jìn)行方向的改進(jìn)：距離目標(biāo)方向越近的路徑，就提高此路徑上信息素濃度比例，這樣就會(huì)促進(jìn)螞蟻在尋找食物源時(shí)以最大概率沿著信息素濃度高的路徑，用最短時(shí)間接近最優(yōu)食物源的快速通道，避免初始搜索時(shí)間較長(zhǎng)的缺陷；由于傳統(tǒng)蟻群算法的動(dòng)態(tài)因子在調(diào)節(jié)全局信息素濃度時(shí)不具有自適應(yīng)性，因此引入雙曲線正切函數(shù)在全局的信息素濃度更新中作為其自適應(yīng)動(dòng)態(tài)因子，每次迭代最優(yōu)解路徑的信息素濃度時(shí)具有一定的自適應(yīng)性，使最優(yōu)路徑的信息素增大，從而增大了算法獲取最優(yōu)解的可能性，縮短了算法的收斂時(shí)間。

1 最短路徑問(wèn)題的描述

設(shè)一個(gè)帶權(quán)重的有向圖G=(V,{L}),其中V是含有n個(gè)節(jié)點(diǎn)的集合，L是邊的集合，每條邊(i,j)∈L都賦予一個(gè)非負(fù)權(quán)重dij，表示節(jié)點(diǎn)i到節(jié)點(diǎn)j間的距離大小，i,j∈V。設(shè)B，E分別為V中的任意兩點(diǎn)，最優(yōu)路徑問(wèn)題就是在帶有權(quán)重的有向圖中，尋找從點(diǎn)B到E的一條具有最小權(quán)重總和的路徑。

2 蟻群算法的改進(jìn)

一種仿生算法—蟻群算法，是模擬自然界螞蟻尋找食物過(guò)程而得出。在此過(guò)程中，它們總能找到從巢穴到食物源之間的一條最短路徑。其原因在于螞蟻在路徑上會(huì)釋放一種信息激素(pheromone)進(jìn)行信息傳遞，螞蟻在運(yùn)動(dòng)過(guò)程中能夠感知這種物質(zhì)，由它來(lái)指導(dǎo)運(yùn)動(dòng)方向。當(dāng)它們碰到一個(gè)陌生路口時(shí)，就會(huì)隨機(jī)地選出一條路徑進(jìn)行前行，同時(shí)螞蟻會(huì)在這條路徑上釋放一定量的信息素，此時(shí)路徑上的信息素濃度增大，后來(lái)的螞蟻再次碰到這個(gè)路口時(shí)，就會(huì)選擇信息素濃度高的路徑,這樣就形成一種正反饋。最優(yōu)路徑上的激素濃度越來(lái)越大，最終整個(gè)蟻群就會(huì)搜索出一條最短路徑。

2.1 算法初始時(shí)刻濃度改進(jìn)

傳統(tǒng)的蟻群算法在初始迭代時(shí)給每條路徑上的濃度是一個(gè)常數(shù)，那時(shí)螞蟻不知道每條路徑的長(zhǎng)度，它只能隨機(jī)選擇，產(chǎn)生了大量無(wú)關(guān)緊要的路徑，阻礙最優(yōu)路徑搜索過(guò)程，同時(shí)對(duì)信息素濃度局部更新也會(huì)產(chǎn)生影響。但在求最短路徑時(shí)，節(jié)點(diǎn)與節(jié)點(diǎn)之間的距離是已知的，因此在用蟻群算法求最短路徑時(shí)，沒(méi)有必要進(jìn)行盲目選擇，可以對(duì)迭代開(kāi)始時(shí)的初始濃度進(jìn)行精確賦值。

設(shè)在網(wǎng)絡(luò)圖中需要求出從點(diǎn)B到E的一條最短路徑。其中節(jié)點(diǎn)i和節(jié)點(diǎn)j之間路徑上的初始信息素濃度為τij(0)，反映靠近最短距離的程度,越靠近最短距離,濃度應(yīng)該越大。用dBE表示起點(diǎn)B到終點(diǎn)E的直線距離,dBj表示節(jié)點(diǎn)B與節(jié)點(diǎn)j的直線距離，djE表示節(jié)點(diǎn)j到終點(diǎn)E的直線距離,dBj+djE表示B→j→E的曲線距離,dBE/(dBj+djE)中dBj+djE越趨向于dBE，dBE/(dBj+djE)越接近于1,此條路徑上的濃度越大,螞蟻就越偏向選擇這些節(jié)點(diǎn)作為移動(dòng)方向。因此節(jié)點(diǎn)i和節(jié)點(diǎn)j之間路徑上的初始信息素濃度為τij(0)定義為:

(1)

算法的這種改進(jìn)使得螞蟻在搜索過(guò)程產(chǎn)生了比較合理的方向引導(dǎo)，進(jìn)而對(duì)無(wú)關(guān)路徑起到抑制作用，避免螞蟻的盲目搜索,提高了搜索全局最優(yōu)解的速率。

2.2 全局更新規(guī)則的改進(jìn)

傳統(tǒng)蟻群算法在全局更新規(guī)則中只更新每次迭代的最優(yōu)路徑上的信息素濃度。這樣就導(dǎo)致某些較短路徑信息素濃度過(guò)分增加，全局最優(yōu)路徑與單次迭代的最優(yōu)路徑相關(guān)性較大[10-12]，易陷入局部最優(yōu)。在全局更新規(guī)則中，引入自適應(yīng)動(dòng)態(tài)因子σ(σ∈(0,1))，這樣不僅可以實(shí)時(shí)動(dòng)態(tài)更新每次迭代最優(yōu)路徑的全局信息素濃度，而且也要?jiǎng)討B(tài)更新較優(yōu)的局部最優(yōu)解。經(jīng)過(guò)自適應(yīng)控制單次迭代最優(yōu)解的信息素濃度在當(dāng)前最優(yōu)解中的比重，從而較優(yōu)路徑信息素濃度發(fā)揮了更大的作用，更好地反映了路徑信息，最優(yōu)解逐漸凸現(xiàn)，加快了全局最優(yōu)解的收斂速度。

τij(t+1)=τij(t)+σμΔτij

(2)

(3)

對(duì)于自適應(yīng)因子σ，當(dāng)Llocalmin越大，即搜索路徑越長(zhǎng)時(shí)，動(dòng)態(tài)因子σ越趨于0；而當(dāng)Llocalmin越小，搜索路徑越短時(shí)，動(dòng)態(tài)因子σ越趨于1。所以搜索到的路徑長(zhǎng)度越短，全局更新時(shí)它所遍歷的路徑信息素濃度越強(qiáng)，信息量增加就會(huì)較快。當(dāng)ω取不同值時(shí)，雙曲正切函數(shù)曲線以及與傳統(tǒng)蟻群算法動(dòng)態(tài)因子的對(duì)比圖如圖1所示。

圖1 動(dòng)態(tài)因子函數(shù)曲線圖

對(duì)于雙曲正切函數(shù)f(x)，當(dāng)x∈(-1,1)時(shí)，可以看到f(x)變化率最大，那么敏感度就較高，這樣有效區(qū)分了不同迭代最優(yōu)解對(duì)信息素加成的影響，加強(qiáng)局部最優(yōu)解中路徑更短的信息素濃度，加快收斂的全局最優(yōu)解的速度；當(dāng)x<-1時(shí)，f(x)緩慢趨向于0，這樣不但對(duì)不利解對(duì)信息素加成起到抑制作用，同時(shí)保留了其部分影響，進(jìn)而也增加了解空間的多樣性；當(dāng)x>-1時(shí)，f(x)緩慢趨于定值1，這樣更好地避免部分較短但不是全局最優(yōu)路徑被過(guò)度增強(qiáng)，有效地防止算法陷入局部最優(yōu)解。與此同時(shí)，對(duì)于自適應(yīng)動(dòng)態(tài)因子σ是平滑過(guò)渡，故不會(huì)對(duì)信息素濃度造成波動(dòng)影響。從圖中可以看出ω越大，f(x)對(duì)x的靈敏度就越高。

3 自適應(yīng)蟻群算法的步驟

以上是對(duì)傳統(tǒng)蟻群算法的改進(jìn)，改進(jìn)后的算法實(shí)現(xiàn)步驟如下：

步驟1:初始化信息啟發(fā)因子α(軌跡的相對(duì)重要性)，期望啟發(fā)因子β，路徑啟發(fā)因子ηij,ηij=1/dij。其中,dij為i→j的歐氏距離；q0為螞蟻狀態(tài)轉(zhuǎn)移的閾值。設(shè)最大迭代次數(shù)N,選定螞蟻數(shù)m。

步驟2：計(jì)算節(jié)點(diǎn)距離矩陣，初始化信息素濃度τij(0)，將m只螞蟻放在起點(diǎn)B，將各螞蟻的初始節(jié)點(diǎn)B置于當(dāng)前解集tabuk中，第k只螞蟻從節(jié)點(diǎn)i轉(zhuǎn)移到下一個(gè)節(jié)點(diǎn)j的規(guī)則：在0與1之間隨機(jī)生成一個(gè)實(shí)數(shù)q，把它與事先給定的閾值q0∈(0,1)進(jìn)行比較：

當(dāng)q>q0時(shí)，以輪盤(pán)賭的方式計(jì)算第k只螞蟻由i轉(zhuǎn)移到下一個(gè)節(jié)點(diǎn)l的概率：

(4)

步驟3:信息素濃度的局部更新。在螞蟻完成一次搜索后，信息素一方面要揮發(fā)掉一部分，另一方面螞蟻在走過(guò)的路徑上要釋放一定量的信息素。設(shè)揮發(fā)和增加信息素的系數(shù)均為ρ，更新規(guī)則如下：

τij(t+1)=(1-ρ)τij(t)+ρΔτij(t)

(5)

(6)

步驟4：重復(fù)步驟2和3，直到所有螞蟻都到達(dá)終點(diǎn)E，此時(shí)得到m條由初始節(jié)點(diǎn)到終點(diǎn)E的路徑{l1,l2,…,lm}。

步驟6：再將m只螞蟻放置于起點(diǎn)B，按照步驟2～4進(jìn)行搜索，這樣一直重復(fù)進(jìn)行，直到迭代N次，此時(shí)可以得到全局最優(yōu)解。

4 算法仿真

4.1 最短路徑問(wèn)題求解

為檢驗(yàn)文中自適應(yīng)蟻群算法的有效性，以哈爾濱市區(qū)部分交通路線圖為例，以道路交通事故現(xiàn)場(chǎng)作為起點(diǎn)，以哈爾濱市人民醫(yī)院作為終點(diǎn)，在事故和醫(yī)院之間尋找一條最短路徑，其目的是快速將傷員送往醫(yī)院，最大可能地減少人員傷亡和財(cái)產(chǎn)損失。

選取的參數(shù)如表1所示，分別采用文中的自適應(yīng)蟻群算法(M-ACO)、傳統(tǒng)蟻群算法(Ant Colony Optimization，ACO)、最大最小蟻群算法(Max-Min Ant System，MMAS)，節(jié)點(diǎn)與節(jié)點(diǎn)間的距離數(shù)據(jù)來(lái)源于文獻(xiàn)[13]。

表1 3種算法的公共參數(shù)設(shè)置

選取交通事故點(diǎn)離醫(yī)院有20個(gè)路口即對(duì)20個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)進(jìn)行仿真實(shí)驗(yàn)，實(shí)際最短路徑長(zhǎng)度為3 186.25 km，用三種方法搜索的最短距離結(jié)果如表2所示。

表2 20路口網(wǎng)絡(luò)實(shí)驗(yàn)數(shù)據(jù)統(tǒng)計(jì)結(jié)果

從表2可以看出：ACS經(jīng)歷21次迭代后迅速陷入局部最優(yōu)，并且在100次中只有8次搜索到最優(yōu)路徑；而搜索結(jié)果在平均解意義上有所提高的是MMAS，但平均迭代次數(shù)明顯升高，并且搜索到的最優(yōu)解的幾率只有19%；文中改進(jìn)的蟻群算法的搜索結(jié)果在最優(yōu)解和平均最優(yōu)解上都有顯著改善，搜索到最優(yōu)解的幾率為96%，基本上每次都能找到最優(yōu)解。

為進(jìn)一步驗(yàn)證文中算法對(duì)路口數(shù)量多的適用性，現(xiàn)擴(kuò)大交通事故點(diǎn)與醫(yī)院的距離，路口增加即研究的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)增加，使得研究的網(wǎng)絡(luò)圖變得更復(fù)雜。分別對(duì)20、30、40、50、60個(gè)路口進(jìn)行仿真，如表3和表4所示。

表3 最優(yōu)解搜索率統(tǒng)計(jì)結(jié)果 %

由表3可知，當(dāng)路口數(shù)增加時(shí)，改進(jìn)的M-ACS算法仍然具有較好的路徑搜索效果，30路口時(shí)最優(yōu)路徑搜索率為89%，遠(yuǎn)遠(yuǎn)優(yōu)于其他兩種算法。當(dāng)路口數(shù)為60時(shí)，由于研究網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)較為復(fù)雜，計(jì)算量較大，參考算法搜索率較低，而文中仍然有51%的搜索率。表4中，M-ACS算法平均迭代次數(shù)略大于其他算法，并且在路口數(shù)較少時(shí)，迭代數(shù)增加并不明顯，但帶來(lái)的搜索性能提升較大。

表4 平均迭代次數(shù)統(tǒng)計(jì)結(jié)果

3種算法對(duì)不同節(jié)點(diǎn)的收斂時(shí)間對(duì)比如圖2所示。

圖2 收斂時(shí)間對(duì)比圖

從圖2可以看出：在不同復(fù)雜程度的網(wǎng)絡(luò)圖中，3種算法中收斂時(shí)間最短的是文中提出的自適應(yīng)蟻群算法，主要因?yàn)镸-ACS在迭代初期，對(duì)路徑的信息素濃度進(jìn)行了重新分配，并給予了一定的方向指導(dǎo)，節(jié)約了蟻群盲目的隨機(jī)搜索時(shí)間。在迭代后期全局信息素濃度更新時(shí)加入了自適應(yīng)動(dòng)態(tài)因子，動(dòng)態(tài)更新每次迭代最優(yōu)路徑的全局信息素濃度，使其最優(yōu)路徑上的信息素濃度進(jìn)一步加強(qiáng)，從而提高了算法的收斂速度。因此，在不同節(jié)點(diǎn)的收斂時(shí)間均小于其他2種算法。

4.2 TSP問(wèn)題求解

旅游線路的優(yōu)化問(wèn)題是旅行商問(wèn)題(TSP)的一種典型代表。近幾年來(lái)對(duì)于TSP的求解提出了許多優(yōu)化算法，仿生算法是研究熱點(diǎn)，它有傳統(tǒng)算法不可替代的優(yōu)勢(shì)。文中引用文獻(xiàn)[14]中設(shè)計(jì)旅行線路為例，直觀地反映自適應(yīng)蟻群算法與其他算法的優(yōu)劣。為驗(yàn)證文中算法的性能，引入遺傳算法和傳統(tǒng)的蟻群算法進(jìn)行求解。選取參數(shù)如表1，設(shè)置出發(fā)點(diǎn)都為重慶，且必須經(jīng)過(guò)每一個(gè)城市且只有一次，最后回到重慶。

由文獻(xiàn)[14]可知，利用遺傳算法得出的最優(yōu)路線如圖3所示，對(duì)應(yīng)最優(yōu)值為18 997.8 km。圖4為傳統(tǒng)蟻群算法得出旅行路徑的結(jié)果，其對(duì)應(yīng)的最優(yōu)值為18 696.1 km。從優(yōu)化效果來(lái)看，傳統(tǒng)蟻群算法的尋優(yōu)效果比遺傳算法的效果更好。

圖3 遺傳算法運(yùn)行結(jié)果

圖4 傳統(tǒng)蟻群算法運(yùn)行結(jié)果

圖5為采用自適應(yīng)蟻群算法設(shè)計(jì)旅行路徑的結(jié)果。對(duì)應(yīng)的線路如下：重慶→貴州→南寧→?？凇拈T(mén)→香港→廣州→長(zhǎng)沙→合肥→南京→上海→杭州→臺(tái)北→福州→南昌→武漢→鄭州→太原→石家莊→濟(jì)南→哈爾濱→長(zhǎng)春→沈陽(yáng)→天津→北京→呼和浩特→西安→銀川→蘭州→西寧→烏魯木齊→拉薩→昆明→成都→重慶；所對(duì)應(yīng)的最優(yōu)值為17 887.4 km。從效果來(lái)看，自適應(yīng)蟻群算法的尋優(yōu)效果比遺傳算法和傳統(tǒng)的蟻群算法的效果更好。

通過(guò)三種算法的比較可以得出：文中在迭代過(guò)程中采用自適應(yīng)蟻群算法，在實(shí)際應(yīng)用中能夠得到更佳的效果且求解精度更高。

圖5 自適應(yīng)蟻群算法運(yùn)行結(jié)果

5 結(jié)束語(yǔ)

針對(duì)傳統(tǒng)蟻群算法存在容易陷入局部最優(yōu)解且收斂速度慢的缺陷，提出了自適應(yīng)蟻群算法。通過(guò)在初始化信息素濃度時(shí)加入方向引導(dǎo)，在全局信息素更新過(guò)程中加入雙曲正切函數(shù)作為動(dòng)態(tài)因子，自適應(yīng)地調(diào)整每次迭代最優(yōu)解的信息素更新的改進(jìn)策略。實(shí)驗(yàn)結(jié)果表明：自適應(yīng)蟻群算法提高了求解最短路徑的收斂速度和精度，增強(qiáng)了算法的尋優(yōu)能力。為驗(yàn)證文中算法的有效性，將其用于34個(gè)城市旅游線路的優(yōu)化，并與傳統(tǒng)的蟻群算法和遺傳算法進(jìn)行比較。結(jié)果表明：文中算法尋優(yōu)精度高，得到的線路最優(yōu)。

[1] Colomi A,Dorigo M,Maniezzo V.Distributed optimization by ant colonies[C]//Proceeding of the first European conference of artificial life.Paris:Elsevier Publishing,1991.

[2] Dorigo M,Ganbardella L M.Ant colony system:a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation,1997,1(1):53-66.

[3] Colomi A,Dorigo M,Maniezzo V.Ant system for job-shop scheduling[J].Belgian Journal of Operations Research Statistics and Computer Science,1994,34(1):39-53.

[4] Dorigo M,Maniezzo V,Colomi A.Ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on System Man and Cybernetics -Part B,1996,26(1):29-41.

[5] 王 健,劉衍珩,朱建啟.全局自適應(yīng)蟻群優(yōu)化算法[J].小型微型計(jì)算機(jī)系統(tǒng),2008,29(6)：1083-1087.

[6] 付 宇,肖健梅.動(dòng)態(tài)自適應(yīng)蟻群算法求解TSP問(wèn)題[J].計(jì)算機(jī)輔助工程，2008,15(4)：10-13.

[7] Stuzle H.MAX-MIN ant system[J].Future Generation Computer System,2000,16:889-914.

[8] Clornei I,Kyriakides E.Hybrid ant colony-genetic algorithm (GAAPI) for global continuous optimization[J].IEEE Transactions on Systems Man and Cybernetics-Part B,Cybernetics,2012,42(1):234-245.

[9] 鄭衛(wèi)國(guó),田其沖,張 磊.基于信息素強(qiáng)度的改進(jìn)蟻群算法[J].計(jì)算機(jī)仿真,2010,27(7):191-193.

[10] Shah S,Kothari R,Chandra S.Debugging ants:how ants find the shortest routs[C]//8th international conference on information,communications and signal processing.[s.l.]:IEEE,2011:1-5.

[11] 吳虎發(fā),李學(xué)俊,章玉龍.改進(jìn)的蟻群算法求解最短路徑問(wèn)題[J].計(jì)算機(jī)仿真,2012,29(8):215-218.

[12] 張學(xué)敏,張 航.基于改進(jìn)蟻群算法的最短路徑問(wèn)題研究[J].自動(dòng)化技術(shù)與研究,2009(6):4-7.

[13] 哈爾濱市統(tǒng)計(jì)年鑒[R].哈爾濱:哈爾濱市統(tǒng)計(jì)局,2014.

[14] 走遍全中國(guó)方案的研究[EB/OL].2014-05-30.http://www.docin.com/p-105402921.html.

Solving of Shortest Path Problem and TSP with Adaptive Ant Colony Algorithm

YI Zheng-jun1,LI Yong-xia1,YI Xiao-shi2

(1.College of Mathematics and Statistics,Chongqing University，Chongqing 401331,China;2.College of Mathematics and Statistics,Chongqing Normal University,Chongqing 401131,China)

Direction guiding is utilized in the initial pheromone avoiding ant colony in the initial stage to blindly random search and to waste more time.Moreover,a dynamic factor (hyperbolic tangent function) is invited in the global renewal process to update adaptively the pheromone concentration on the optimal path,in which way the possibility of obtaining the global optimal solution is increased.Then two examples are optimized with the improved algorithm,and the optimization results are in step with the actual,illustrating the effectiveness and practicability of the improved algorithm.

ant colony algorithm;shortest path;direction guiding;dynamic factor;TSP

2016-01-27

2016-05-11

時(shí)間：2016-11-21

國(guó)家自然科學(xué)基金資助項(xiàng)目(69674012)；重慶市科技攻關(guān)計(jì)劃(CSTC2009AC3037)

易正俊(1963-)，男，博士，教授，全國(guó)專(zhuān)業(yè)學(xué)位研究生教育教指委專(zhuān)家,研究方向?yàn)槿斯ぶ悄?、仿真系統(tǒng)、數(shù)據(jù)挖掘；李勇霞(1988-)，女，碩士生，研究方向?yàn)橹悄芩惴ā?/p>

http://www.cnki.net/kcms/detail/61.1450.TP.20161121.1641.026.html

TP301

A

1673-629X(2016)12-0001-05

10.3969/j.issn.1673-629X.2016.12.001