張開碧　張洋川　萬素波　白　銀

(重慶郵電大學(xué)自動(dòng)化學(xué)院　重慶　400065)

?

一種改進(jìn)的競(jìng)爭(zhēng)型蟻群算法在TSP問題中的應(yīng)用*

張開碧張洋川萬素波白銀

(重慶郵電大學(xué)自動(dòng)化學(xué)院重慶400065)

摘要路徑優(yōu)化問題在配送成本中是一個(gè)至關(guān)重要的因素。隨著社會(huì)的不斷進(jìn)步和經(jīng)濟(jì)的快速發(fā)展,路徑優(yōu)化問題得到了大力發(fā)展,其中通過優(yōu)化配送路徑的方法可以大大節(jié)約運(yùn)輸成本從而對(duì)成本進(jìn)行有效控制。在分析常規(guī)蟻群算法的基礎(chǔ)上,采用競(jìng)爭(zhēng)的方式讓蟻群釋放信息素來改變信息素的更新機(jī)制從而進(jìn)一步優(yōu)化配送路徑。最終使整個(gè)算法收斂速度更快、搜索能力更強(qiáng)、精度更高,結(jié)果更優(yōu)。

關(guān)鍵詞蟻群算法; TSP; 信息素競(jìng)爭(zhēng)機(jī)制; 路徑優(yōu)化

Application of An Improved Competitive Ant Colony Algorithm in TSP

ZHANG KaibiZHANG YangchuanWAN SuboBAI Yin

(College of Automation, Chongqing University of Posts and Telecommunications, Chongqing400065)

AbstractThe path optimization problem has been a crucial factor in the transportation costs. With the continuous progress of the society and the rapid development of economy, the path optimization problem has been greatly developed. The method of optimizing the distribution route can save the transportation costs and control the cost effectively. On the basis of analyzing the conventional ant colony algorithm, this way of competition is used to let the ant colony release information, and the pheromone update mechanism is changed to further optimize the distribution route. Finally, the result can be gotten that the algorithm converges faster, is more powerful and more accurate, and has better result.

Key Wordsant colony algorithm, TSP, pheromone competition mechanism, route optimization

Class NumberTP301

1引言

路徑優(yōu)化中最為典型的是旅行商問題(Traveling Saleman Problem,TSP)是最基本的路線問題。現(xiàn)在主流的路徑優(yōu)化算法有遺傳算法、節(jié)約算法、粒子群算法和蟻群算法等[1~2]。其中比較重要的蟻群算法是一種仿生物智能算法,其模型是螞蟻群體尋找食物的過程。它的魯棒性較強(qiáng),分布式特征使得算法可靠和全局搜索能力都比較強(qiáng),同時(shí)也可以有效地和其他算法進(jìn)行結(jié)合。但是也存在不足:搜索時(shí)間長(zhǎng),過快地收斂于局部最優(yōu)解。為了解決上述問題,本文提出了一種改進(jìn)的競(jìng)爭(zhēng)型蟻群算法,更加有效地對(duì)路徑進(jìn)行控制以求得更優(yōu)的路徑結(jié)果,更大限度地節(jié)約成本。

2常規(guī)蟻群算法

2.1常規(guī)蟻群算法的基本原理

蟻群算法(Ant Colony Optimization,ACO)又稱螞蟻算法,是一種用來尋找優(yōu)化路徑的機(jī)率型算法。它由Marco Dorigo于1992年在博士論文中提出[3],其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為:蟻群在尋找食物時(shí),它們總能找到一條從食物到巢穴之間的最短路徑,并且能隨環(huán)境變化而變化的搜索到新的最短路徑。

蟻群是通過何種方式尋找到最優(yōu)路徑的呢？其實(shí),螞蟻在尋找食物時(shí),能在其走過的路上釋放一種特殊的分泌物—信息素,而且信息素會(huì)隨著時(shí)間的推移而逐漸揮發(fā)。螞蟻在選擇該路徑的概率與當(dāng)時(shí)這條路徑上信息素的強(qiáng)度成正比。某條路徑上通過的螞蟻越來越多,其留下的信息素濃度就越來越高,后面的螞蟻選擇這條路徑的概率也就越來越大,將會(huì)進(jìn)一步增加該路徑的信息素強(qiáng)度,吸引更多的螞蟻,從而形成一種正反饋機(jī)制[4]。蟻群正反饋機(jī)制如圖1所示,剛開始時(shí),各條路徑上的信息素相同,30只螞蟻等概率地選擇下一個(gè)節(jié)點(diǎn),A-C-B和A-D-B上的螞蟻都是15只。但是螞蟻通過較短路徑的時(shí)間會(huì)更短,那么在單位時(shí)間內(nèi),通過較短路徑的螞蟻就越多,留下的信息素越多,信息素越大,那么這條路徑被選擇的概率也就越大,就會(huì)被更多的螞蟻所選擇[5]。圖中A-C-B的距離小于A-D-B,所以經(jīng)過一段時(shí)間后,A-C-B上的螞蟻逐漸增加到20,A-D-B減少到10。由于這種正反饋機(jī)制的持續(xù)作用,將會(huì)有更多的螞蟻選擇A-C-B這條較短的路徑,蟻群最終就找到了它們的最佳覓食路徑。

圖1　蟻群正反饋機(jī)制

目前,人們已經(jīng)從蟻群的這種覓食過程中總結(jié)出了一些基本的規(guī)則[6]。在TSP問題中,螞蟻一開始被隨機(jī)放置到各個(gè)節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)只能被訪問一次,在每一步的路徑構(gòu)建中,螞蟻k按照概率選擇下一個(gè)訪問節(jié)點(diǎn)。例如,螞蟻k在節(jié)點(diǎn)i選擇節(jié)點(diǎn)j作為下一個(gè)訪問點(diǎn)的概率為

(1)

式(1)中τij代表(i,j)上的信息素濃度,ηij=1/dij代表一個(gè)最初給定的啟發(fā)式信息,dij代表i~j的距離,α和β這兩個(gè)參數(shù)表示信息素和啟發(fā)式信息的相對(duì)影響力,allowedk代表一個(gè)集合,這個(gè)集合包含了那些還可以被訪問的所有節(jié)點(diǎn)。所以在這種選擇規(guī)則下,路徑(i,j)的選擇概率就由信息素τij和啟發(fā)式信息ηij的大小共同決定。

(i,j)上的信息素τij(t)的更新方程為

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

(2)

(3)

(4)

式(2)~式(4)共同決定(i,j)路徑上信息素的更新。式(2)中參數(shù)ρ表示信息素的揮發(fā)系數(shù)(0<ρ<1),τij(t-1)表示上次搜索后(i,j)上的信息素,Δτij表示當(dāng)前這次搜索過程中,蟻群釋放的信息素。式(3)表示第k只螞蟻會(huì)經(jīng)過(i,j),Lk表示第k只螞蟻的搜索路徑,第k只螞蟻在(i,j)上的信息素增量為Q/Lc,Q為信息素增加系數(shù),Lc為此次搜索的最優(yōu)解,即蟻群此次搜索到的最短路徑。式(4)表示此次搜索后,i~j上增加的信息素等于所有由i~j的螞蟻釋放的信息素相加。

2.2用常規(guī)蟻群算法來求解TSP問題

TSP問題是數(shù)學(xué)領(lǐng)域中著名的N-P問題。假設(shè)有一個(gè)旅行商人要訪問n個(gè)城市,但是他所訪問城市要滿足一定要求,每個(gè)城市只能訪問一次;從一個(gè)城市出發(fā),在訪問完其他城市后,最后回到開始的那個(gè)城市。目標(biāo)路徑為經(jīng)過所有n個(gè)城市路徑距離最小的那一條路徑。

用蟻群算法求解TSP問題的步驟如下[7~8]:

1) 變量初始化;

2) 螞蟻構(gòu)造路徑,按概率選擇路徑,每只螞蟻完成各自的周游;

3) 計(jì)算本次搜索的最佳路線;

4) 信息素的更新;

5) 禁忌表清零;

6) 判斷是否達(dá)到最大搜索次數(shù)？如果未達(dá)到最大搜索次數(shù),跳入步驟2),如果達(dá)到最大搜索次數(shù),輸出結(jié)果。

TSP問題的本質(zhì)是求滿足要求的最短路徑,即給定一個(gè)帶權(quán)圖G=(N,d),其中N是圖中的各個(gè)節(jié)點(diǎn)的集合,d是各個(gè)節(jié)點(diǎn)之間連線的集合。

TSP問題的求解模型為

(5)

約束條件公式:

(6)

式(6)中,約束(a)表示路徑只能從一條邊出,約束(b)表示路徑只能從一條邊進(jìn),約束(c)表示回路中不含任何子回路,滿足以上三個(gè)約束條件的解就構(gòu)成了一條Hamilton回路[9]。

蟻群算法在TSP問題中取得了不錯(cuò)的效果,但是也存在以下不足之處:

1) 參數(shù)設(shè)置得不準(zhǔn)確,就會(huì)導(dǎo)致求解速度慢且所得解質(zhì)量不高;

2) 常規(guī)蟻群算法計(jì)算量大,信息素更新容易求得局部最優(yōu)解,從而造成算法停滯;

3) 常規(guī)蟻群算法從理論上要求所有螞蟻在最后都選擇最短那條路徑,但實(shí)際上是不可能的,因?yàn)樗惴ㄔ谝欢ǖ乃阉鞔螖?shù)內(nèi)可能無法找到最優(yōu)解。

為了提高算法的合理性和精確性,本文對(duì)常規(guī)蟻群算法做出了一些改進(jìn)。

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

通過以往學(xué)者在TSP問題對(duì)蟻群算法做出的研究,可以將蟻群算法做出以下幾個(gè)方面的改進(jìn)[10]:

1) 選擇概率中各個(gè)參數(shù)的設(shè)置;

2) 改變信息素的更新規(guī)則;

3) 與其他優(yōu)秀算法相結(jié)合。

改進(jìn)的主要目標(biāo)如下:

1) 提高搜索結(jié)果的精確性,加快收斂速度的同時(shí)避免過早的局部收斂,從而避免算法過早停滯。

2) 加強(qiáng)算法的自我搜索能力。

本文提出的改進(jìn)蟻群算法中,主要是更改了信息素的跟新規(guī)則。并不是所有螞蟻在每次搜索結(jié)束后都進(jìn)行信息素更新,而是只對(duì)每次搜索到最短路徑的那只螞蟻的信息素進(jìn)行更新。

改進(jìn)蟻群算法的信息素更新規(guī)則如式(7)~式(10):

(7)

(8)

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

(9)

τij(t)∈[τmin,τmax]

(10)

信息素?fù)]發(fā)系數(shù)ρ體現(xiàn)了路徑上信息素的保留能力,在常規(guī)蟻群算法中,信息素?fù)]發(fā)系數(shù)ρ為一個(gè)常系數(shù),但是這樣會(huì)導(dǎo)致算法在初始階段尋優(yōu)能力不足,得到較優(yōu)化結(jié)果的同時(shí)陷入局部最優(yōu)導(dǎo)致算法停滯,所以在改進(jìn)的蟻群算法中將信息素?fù)]發(fā)系數(shù)與搜索次數(shù)相結(jié)合,隨著搜索次數(shù)的增加,信息素?fù)]發(fā)系數(shù)也發(fā)生改變。從式(7)可以看到,改進(jìn)蟻群算法在搜索前期采用較小的揮發(fā)系數(shù),中后期加大揮發(fā)系數(shù),這種隨搜索次數(shù)變化的信息素?fù)]發(fā)系數(shù)有助于加強(qiáng)算法在前期的搜索能力,也能避免算法在中后期的停滯。

在常規(guī)蟻群算法中,知道路徑(i,j)上的信息素增量為蟻群中所有從i~j的螞蟻釋放的信息素相加,但是經(jīng)過(i,j)的大部分螞蟻,它們的周游路徑并不是最優(yōu)值,這就會(huì)對(duì)后面的搜索產(chǎn)生一定的干擾。而在改進(jìn)蟻群算法中,每次搜索完成后,蟻群通過競(jìng)爭(zhēng)的方式來釋放信息素。

競(jìng)爭(zhēng)規(guī)則如下:

1) 每次搜索完成后,有且僅有一只螞蟻能釋放信息素;

2) 釋放信息素的螞蟻必須是當(dāng)前這次搜索中的最優(yōu)螞蟻;

3) 如果當(dāng)前這次搜索中的這只最優(yōu)螞蟻尋得的路徑比前一次搜索的最優(yōu)螞蟻尋得的路徑更短,將釋放大小為1/Lc的信息素,Lc為螞蟻尋得路徑的距離;

4) 如果當(dāng)前這次搜索中的這只最優(yōu)螞蟻尋得的路徑和前一次搜索的最優(yōu)螞蟻尋得的路徑相同,將釋放大小為1/Nc-maxLc的信息素,Nc-max為總的搜索次數(shù);

5) 如果當(dāng)前這次搜索中的這只最優(yōu)螞蟻尋得的路徑比上一次搜索的最優(yōu)螞蟻尋得的路徑更長(zhǎng),將不會(huì)釋放信息素。

根據(jù)這種新的競(jìng)爭(zhēng)規(guī)則可以看出,能夠釋放信息素的螞蟻會(huì)經(jīng)歷兩次篩選,第一次與本次搜索中的其他螞蟻進(jìn)行比較,第二次則是與前一次搜索的最優(yōu)螞蟻進(jìn)行比較。而且尋得路徑越短的螞蟻,能釋放更多的信息素,按照這樣的規(guī)則,一直循環(huán)下去,能夠有效地保留那些優(yōu)秀螞蟻,淘汰那些結(jié)果不夠優(yōu)化的螞蟻,這樣大大地提高了蟻群搜尋結(jié)果的精確性。

從式(9)可以知道,與常規(guī)蟻群算法不同的是,改進(jìn)蟻群算法中不論上一次搜索后保留的信息素,還是當(dāng)前這次搜索后釋放的信息素都跟信息素?fù)]發(fā)系數(shù)ρ相關(guān),這樣就大大加強(qiáng)了算法的搜索能力,避免了算法因找到局部最優(yōu)解而導(dǎo)致停滯的可能。

式(10)作為信息素限制條件,主要是為了防止某條路徑上的信息素表現(xiàn)過大或過小的情況[11]。通過這種方法可以有效控制信息素,避免信息素超過最大值或小于最小值,以此提高算法的有效性。

4改進(jìn)蟻群算法的應(yīng)用

本文用改進(jìn)的蟻群算法和常規(guī)蟻群算法同時(shí)對(duì)TSP問題進(jìn)行了求解,并對(duì)比和分析了改進(jìn)的新算法的優(yōu)點(diǎn)。

設(shè)定20個(gè)節(jié)點(diǎn)坐標(biāo):(5,5)、(25,12)、(8,23)、(11,8)、(30,2)、(21,4)、(20,20)、(8,10)、(3,13)、(30,9)、(25,26)、(15,16)、(20,6)、(33,10)、(23,0)、(0,17)、(36,3)、(18,23)、(34,15)、(28,14)。

下面是常規(guī)蟻群算法和改進(jìn)蟻群算法的結(jié)果。其中常規(guī)蟻群算法的結(jié)果如圖2,改進(jìn)蟻群算法的結(jié)果如圖3。

圖2　常規(guī)蟻群算法結(jié)果

從實(shí)驗(yàn)圖形結(jié)果中可以看出,改進(jìn)蟻群算法的最短路徑距離為130.007,常規(guī)蟻群算法的最短路徑距離為134.283,改進(jìn)蟻群算法的結(jié)果明顯更加精確。對(duì)比圖2和圖3,常規(guī)蟻群算法的搜索次數(shù)少,收斂速度過快,還無法找到最短路徑,而改進(jìn)蟻群算法則是一次一次的優(yōu)化去搜索最短路徑,說明改進(jìn)蟻群算法尋找最優(yōu)解的能力加強(qiáng)了。而且改進(jìn)蟻群算法中,每次搜索后,蟻群搜索路徑的平均值也是逐漸變小的,說明新的信息素更新機(jī)制效果十分明顯。

圖3　改進(jìn)蟻群算法結(jié)果

5結(jié)語(yǔ)

本文首先介紹了常規(guī)蟻群算法的原理和對(duì)TSP問題的求解方法,發(fā)現(xiàn)了常規(guī)蟻群算法存在的不足,然后通過改進(jìn)信息素更新機(jī)制,加強(qiáng)算法的自我搜索能力,避免局部收斂過早。最后通過實(shí)驗(yàn),將常規(guī)蟻群算法和改進(jìn)蟻群算法進(jìn)行了對(duì)比,證明了改進(jìn)蟻群算法能提高精確度,加強(qiáng)自我搜索能力。

參 考 文 獻(xiàn)

[1] 朱獻(xiàn)文,李福榮.求解旅行商問題的幾種智能算法[J].計(jì)算機(jī)與數(shù)字工程,2010,38(1):32-35.

ZHU Xianwen, LI Furong. Several intelligent algorithms for solving traveling salesman problem[J]. Computer and Digital Engineering,2010,38(1):32-35.

[2] 李擎,張超.一種基于粒子群參數(shù)優(yōu)化的改進(jìn)蟻群算法[J].控制與決策,2013,28(6):873-878.

LI Qing, ZHANG Chao. An improved ant colony algorithm based on particle swarm optimization[J]. Control and Decision,2013,28(6):873-878.

[3] Dorigo M, Maniezzo V. Ant system: Optimization by a colony cooperating Agents[J]. IEEE Transactions on Systems, Man and Cybernetics part B,1996,26(1):29-41.

[4] WANG L, ZHU Q. An efficient approach for solving TSP: the rapidly Convergen-t ant colony algorithm[C]//Fourth International Conference on Natural Computation, IEEE,2008,186(4):448-452.

[5] 吳華鋒,陳信強(qiáng).基于自然選擇策略的蟻群算法求解TSP問題[J].通信學(xué)報(bào),2013,34(4):165-170.

WU Huafeng, CHEN Xinqiang. Ant colony algorithm based on natural selection strategy to solve[J]. Problem TSP Journal of Communication,2013,34(4):165-170.

[6] 段愛民,陳澤琳.基于改進(jìn)蟻群算法的物流配送路徑優(yōu)化[J].計(jì)算機(jī)技術(shù)與發(fā)展,2011,21(12):178-181.

DUAN Aimin, CHEN Zelin. Optimization of logistics distribution routing based on improved ant colony algorithm[J]. Computer Technology and Development,2011,21(12):178-181.

[7] 楊再甫,黃友銳.TSP的改進(jìn)蟻群算法求解及其仿真研究[J].合肥工業(yè)大學(xué)學(xué)報(bào),2014,37(8):928-932.

YANG Zaifu, HUANG Yourui. The improved ant colony algorithm for TSP and its simulation[J]. Journal of Hefei University of Technology,2014,37(8):928-932.

[8] 張偉娟,張紅梅.基于蟻群算法的基因路徑預(yù)測(cè)[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2015,24(3):280-283.

ZHANG Weijuan, ZHANG Hongmei. Genetic algorithm based on ant colony algorithm to predict the[J]. Computer System Applications,2015,24(3):280-283.

[9] 柳寅,馬良.模糊蟻群算法及其在TSP中的應(yīng)用[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2011,41(6):150-154.

LIU Yin, MA Liang. Fuzzy ant colony algorithm and its application in TSP[J]. Practice and Cognition of Mathematics,2011,41(6):150-154.

[10] Valdez F, Chaparro I. Ant Colony Optimization for solving the TSP symmetric with parallel processing[C]//IFSA World Congress and NAFIPS Annual Meeting(IFSA/NAFIPS),2013:1192-1196.

[11] 姚艷.一種最大最小螞蟻系統(tǒng)的改進(jìn)算法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2014,44(15):242-247.

YAO Yan. An improved algorithm for the maximum and minimum ant system[J]. Practice and Cognition of Mathematics,2014,44(15):242-247.

中圖分類號(hào)TP301

DOI:10.3969/j.issn.1672-9722.2016.03.003

作者簡(jiǎn)介:張開碧,女,碩士,副教授,研究方向:人工智能、數(shù)據(jù)采集。張洋川,男,碩士研究生,研究方向:路徑優(yōu)化、人工智能。

收稿日期:2015年9月4日,修回日期:2015年10月26日