許能闖

摘 要：蟻群算法作為解決TSP中組合優(yōu)化問(wèn)題方案，其搜索路徑能力較其它算法優(yōu)異，但傳統(tǒng)蟻群算法的選取策略較隨機(jī)，導(dǎo)致進(jìn)化速度慢。為了優(yōu)化傳統(tǒng)蟻群算法速度較慢、過(guò)早收斂以致停滯現(xiàn)象，針對(duì)概率選取公式隨機(jī)搜索下一節(jié)點(diǎn)，以延緩其收斂速度。對(duì)信息素調(diào)節(jié)公式進(jìn)行更新以提高蟻群的搜索能力。實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法在最短路徑、平均路徑和搜索最短路徑時(shí)間上較蟻群算法提高很大，改進(jìn)的蟻群算法能有效提高算法的收斂速度和搜索能力。

關(guān)鍵詞：蟻群算法；正反饋；信息素；收斂速度；TSP問(wèn)題

DOIDOI：10.11907/rjdk.173024

中圖分類(lèi)號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2018）002-0056-04

0 引言

TSP問(wèn)題[1]即旅行商問(wèn)題，其含義是某商人要訪問(wèn)n個(gè)城市后再回到出發(fā)城市，前提是各城市只能訪問(wèn)一遍，從而確定最短路徑[2]。

目前，針對(duì)該問(wèn)題的解決方案較多，如動(dòng)態(tài)規(guī)劃法、遺傳算法、模擬退火算法等，但這些算法的實(shí)現(xiàn)很復(fù)雜，由此蟻群算法應(yīng)運(yùn)而生。蟻群算法是一種新型的優(yōu)化算法，其模擬螞蟻覓食過(guò)程。在食物尋找過(guò)程中，螞蟻會(huì)分泌信息素記錄所走路徑，其它螞蟻根據(jù)信息素的濃密程度，選擇其中較短路徑去尋覓食物，該算法最早于20世紀(jì)90年代初由意大利學(xué)者Dorigo M[3]提出。蟻群算法中，當(dāng)越多的螞蟻分布在路徑上，其信息素釋放也越多，此時(shí)更多螞蟻將選擇信息素濃度大的路徑去尋覓食物，由此體現(xiàn)其算法具備好的魯棒性和協(xié)作性。該算法廣泛應(yīng)用在網(wǎng)絡(luò)優(yōu)化和路徑尋優(yōu)問(wèn)題上，是解決組合優(yōu)化問(wèn)題的有效算法之一[4]。

文獻(xiàn)[5]中，針對(duì)TSP容易陷入局部最優(yōu)和收斂速度慢的問(wèn)題，提出了一種博弈論的量子蟻群算法。該算法采用博弈模型產(chǎn)生博弈序列，使產(chǎn)生的效益最大，能有效解決蟻群算法的收斂速度和穩(wěn)定性問(wèn)題。文獻(xiàn)[6]中，針對(duì)路徑優(yōu)化問(wèn)題，提出一種競(jìng)爭(zhēng)方式以更改信息素的更新機(jī)制，使算法的搜索結(jié)果更優(yōu)，精度更高。文獻(xiàn)[7]針對(duì)蟻群算法求解聚類(lèi)特征TSP的收斂速度慢的問(wèn)題，提出新的蟻群算法，將TSP問(wèn)題從數(shù)據(jù)域分解為多個(gè)子問(wèn)題，從而分別求解以提高算法的收斂速度。

作為典型的NP問(wèn)題，已將TSP用作測(cè)試和比較算法性能方法[8]。本文在考慮蟻群算法的搜索能力和收斂速度基礎(chǔ)上，依據(jù)現(xiàn)有算法特點(diǎn)和不足，提出改進(jìn)蟻群算法的概率選取方式和信息素的更新方式。引入新的參數(shù)，改變概率選取方式以延緩收斂速度。與此同時(shí)，在信息素更新過(guò)程中采用新的更新機(jī)制，使螞蟻尋優(yōu)效果更好，以提高算法的搜索能力及搜索結(jié)果。

1 算法簡(jiǎn)介

1.1 蟻群算法工作原理

蟻群算法是由許多螞蟻組成的集體行為構(gòu)成的一種信息學(xué)習(xí)正反饋算法[9]：當(dāng)某條路徑上螞蟻越多，其釋放的信息素就越多，信息濃度隨之越高，其后選擇該路徑的可能性越大，個(gè)體間通過(guò)交流信息以尋找通向食物的最短路徑，正反饋現(xiàn)象如圖1所示。螞蟻剛開(kāi)始覓食時(shí)，假設(shè)各路徑上初始時(shí)刻信息素都相同，40只螞蟻等概率從A結(jié)點(diǎn)出發(fā)去尋找食物（D結(jié)點(diǎn)），有兩條路徑可以到達(dá)，故螞蟻平均分配20只到路徑A-B-D和A-C-D上。因A-B-D和A-C-D的距離分別為20m和30m，故單位時(shí)間內(nèi)在路徑A-B-D上通過(guò)的螞蟻數(shù)量較多，其釋放的信息素也多，導(dǎo)致該路徑被其它螞蟻選擇的概率就大。一段時(shí)間過(guò)后，A-B-D上的螞蟻為30只，A-C-D上的螞蟻只有10只，如圖2所示。由此可見(jiàn)，隨著螞蟻正反饋現(xiàn)象的持續(xù)，A-B-D上螞蟻會(huì)繼續(xù)增多，最終螞蟻覓食可找到最佳路徑。

1.2 路徑選擇概率機(jī)制

螞蟻覓食過(guò)程分析可有效幫助TSP問(wèn)題的求解。在TSP問(wèn)題中，螞蟻隨機(jī)分配到各個(gè)節(jié)點(diǎn)（即城市），因各節(jié)點(diǎn)只能被訪問(wèn)一次，故螞蟻k（k=1，2，3…，m）在節(jié)點(diǎn)i訪問(wèn)下一節(jié)點(diǎn)j的概率為：

1.3 信息素更新機(jī)制

因螞蟻在訪問(wèn)節(jié)點(diǎn)過(guò)程中會(huì)在經(jīng)過(guò)的路徑上釋放信息素，為避免殘留的信息素過(guò)多掩蓋啟發(fā)信息，故當(dāng)螞蟻訪問(wèn)完某個(gè)節(jié)點(diǎn)或完成對(duì)所有節(jié)點(diǎn)的訪問(wèn)后，必須更新遺留的信息素，故（i，j）上的信息素τij的更新公式為：

1.4 算法流程

求解TSP問(wèn)題的蟻群算法步驟如下：①初始化算法所需參數(shù)。設(shè)置循環(huán)次數(shù)Nc=0，最大迭代次數(shù)NC_Max，路徑初始化信息量Δτij（t）=C，C為常數(shù)，Δτij（0）=0；②將m只螞蟻置于n個(gè)城市，對(duì)每只螞蟻按路徑選擇概率pkij訪問(wèn)下一節(jié)點(diǎn)j，j∈allowedk；③對(duì)各螞蟻搜索的路徑長(zhǎng)度進(jìn)行計(jì)算，記錄當(dāng)前搜索的最優(yōu)解；④依據(jù)更新公式修改信息素；⑤將各條路徑上的信息素增量Δτij，循環(huán)次數(shù)Nc分別設(shè)置為Δτij=0，Nc=Nc+1；⑥若NC_Max>Nc，則跳轉(zhuǎn)至第②步；⑦若滿足條件，則輸出當(dāng)前的最優(yōu)解。算法流程見(jiàn)圖3。

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

2.1 蟻群算法缺點(diǎn)

對(duì)TSP問(wèn)題進(jìn)行求解時(shí)，蟻群算法常有以下不足之處：①在首次循環(huán)中，螞蟻經(jīng)過(guò)的路徑上釋放的信息素并不全是路徑最優(yōu)的方向；②因算法的全局搜索能力不足，當(dāng)一段時(shí)間搜索后，會(huì)發(fā)現(xiàn)幾乎一致的解，故局部最優(yōu)解容易產(chǎn)生；③計(jì)算時(shí)間相對(duì)較長(zhǎng)，容易產(chǎn)生停滯現(xiàn)象；④搜索時(shí)間較長(zhǎng)；⑤傳統(tǒng)蟻群算法對(duì)所有搜索路徑都要更新信息素，故搜索最優(yōu)路徑效率降低。

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

蟻群算法依據(jù)螞蟻路徑上釋放的信息素搜索最優(yōu)解，其將優(yōu)先選擇信息素濃度大的路徑。但當(dāng)?shù)螖?shù)一定時(shí)，因較優(yōu)解的頻率不斷刷新使許多螞蟻在較少蟻群的路徑上聚集，從而出現(xiàn)停滯、早熟現(xiàn)象，導(dǎo)致局部最優(yōu)解。本文依據(jù)算法在優(yōu)化過(guò)程中的路徑搜索和收斂速度情況，對(duì)路徑選擇概率和信息素進(jìn)行更新，避免算法出現(xiàn)上述現(xiàn)象，從而提高算法的收斂速度及精確性。

2.2.1 路徑選擇概率改進(jìn)endprint

傳統(tǒng)蟻群算法中，各螞蟻選擇路徑的概率主要由當(dāng)前節(jié)點(diǎn)i訪問(wèn)下一節(jié)點(diǎn)j的信息素濃度τij和啟發(fā)信息ηij兩者共同決定，這在一定程度上誤導(dǎo)螞蟻選擇最佳路徑的機(jī)率，從而陷入局部最優(yōu)解的窘境。為避免上述情況產(chǎn)生，對(duì)路徑選擇概率公式進(jìn)行改進(jìn)。螞蟻由節(jié)點(diǎn)i訪問(wèn)下一節(jié)點(diǎn)j的概率為：

其中，q0是給定的參數(shù)值，范圍為（0，1）之間，q是0～1之間的隨機(jī)數(shù)，引入α/β參數(shù)，表示信息啟發(fā)因子與期望啟發(fā)因子的比值。通過(guò)參數(shù)引入影響算法的概率選取，以延緩算法收斂速度。當(dāng)q>q0時(shí)，將采用q0的搜索方式；當(dāng)q≤q0時(shí)，將采用q的搜索方式，其目的是保持概率選取在合理范圍。q0的選取調(diào)節(jié)了隨機(jī)搜索和確定性搜索的平衡，且q0的大小決定算法的優(yōu)劣。q0過(guò)大會(huì)導(dǎo)致算法陷入局部最優(yōu)解，q0過(guò)小將影響算法的搜索程度，使算法收斂速度過(guò)慢。

2.2.2 信息素更新的改進(jìn)

傳統(tǒng)的蟻群算法中，單一的信息素更新導(dǎo)致算法并未充分利用上次循環(huán)所得的最短路徑，故影響算法的精確搜索。為改善這種情況，將之前的信息素公式加以改進(jìn)，防止螞蟻過(guò)早經(jīng)過(guò)同路徑而產(chǎn)生局部最優(yōu)解。

其中L′表示當(dāng)前搜索的總路徑長(zhǎng)度，Lt表示搜索最長(zhǎng)路徑的集合。信息素調(diào)整公式是避免降低算法的收斂速度，提高蟻群對(duì)新發(fā)現(xiàn)的最短路徑的敏感程度，從而快速對(duì)附近新的最短路徑進(jìn)行搜索。改進(jìn)算法流程如圖4所示。

3 實(shí)驗(yàn)結(jié)果

3.1 仿真環(huán)境

本文實(shí)驗(yàn)環(huán)境為Win10系統(tǒng)下的仿真軟件平臺(tái)。針對(duì)蟻群算法求解TSP問(wèn)題，將本文提出的改進(jìn)算法與原算法進(jìn)行對(duì)比分析，從而檢測(cè)改進(jìn)的算法性能。以ACO52TSP和CH150TSP問(wèn)題為例說(shuō)明算法的可執(zhí)行性，其數(shù)據(jù)均來(lái)自TSP標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)[10]。仿真參數(shù)設(shè)置為：城市數(shù)n=52或150，m=30，α=1，β=5，ρ=0.3，Q=100，q=0.6。對(duì)兩種算法進(jìn)行對(duì)比試驗(yàn)，算法迭代次數(shù)為200次。

3.2 仿真結(jié)果對(duì)比

在仿真軟件平臺(tái)環(huán)境下，選取最短路徑和平均路徑因素，將改進(jìn)算法與蟻群算法性能進(jìn)行對(duì)比。針對(duì)ACO52TSP問(wèn)題，仿真效果如圖5和圖6所示。

圖5中，程序剛開(kāi)始運(yùn)行時(shí)，改進(jìn)算法和原算法都用較少的循環(huán)次數(shù)獲得不錯(cuò)的解。隨著程序的繼續(xù)執(zhí)行，原算法在循環(huán)17次左右出現(xiàn)停滯現(xiàn)象，而改進(jìn)算法在18次左右表現(xiàn)很強(qiáng)的搜索能力，不斷搜索最短路徑。當(dāng)程序運(yùn)行到45次左右時(shí)就找到了最優(yōu)解，即最短路徑為7 033m。而原算法在循環(huán)18次才搜索到最優(yōu)解，最短路徑為7 179m。與原始算法相比，改進(jìn)算法尋找路徑最優(yōu)。圖6為ACO52最短路徑線路，圖7代表原算法和改進(jìn)算法的搜索路徑平均距離。

從圖7可以很明顯地看出，在0～15次循環(huán)期間，原算法和改進(jìn)算法都以相同的速度尋找路徑。隨著算法循環(huán)至18次后，兩者的平均路徑出現(xiàn)差異。經(jīng)過(guò)200次循環(huán)后，原算法平均路徑最小為9 248m，改進(jìn)算法為8 704m，改進(jìn)算法在平均路徑上明顯優(yōu)于原算法。改進(jìn)算法性能得以提升，算法的可靠性和有效性得到了印證。

為進(jìn)一步論證本文算法性能，再以CH150TSP問(wèn)題為例，如圖8所示。

在圖8中，當(dāng)程序剛開(kāi)始運(yùn)行時(shí)，改進(jìn)算法的抖動(dòng)程度較原算法大，表明改進(jìn)算法有較大的搜索空間；隨著程序的不斷運(yùn)行，在算法經(jīng)過(guò)7次循環(huán)后，原算法已陷入停滯狀態(tài)，而改進(jìn)算法一直保持穩(wěn)定的向下不斷搜索路徑；在程序的最后階段，改進(jìn)算法的最優(yōu)解為6 835m，明顯優(yōu)于原算法的7 152m。這得益于參數(shù)的引入以及信息素的更新，改進(jìn)算法花費(fèi)更多的時(shí)間將信息素分泌在較優(yōu)路徑上，增加了算法的搜索能力，降低了收斂速度，使其演化速度更快、更穩(wěn)定，結(jié)果最優(yōu)。圖9表示CH150最短路徑線路。

4 結(jié)語(yǔ)

本文采用新的路徑概率選取公式及信息素更新方法，提高了蟻群節(jié)點(diǎn)的收斂速度及搜索能力。本文提出的改進(jìn)算法主要體現(xiàn)在節(jié)點(diǎn)路徑選擇概率和信息素的更新上。仿真結(jié)果表明，改進(jìn)算法可有效地提高算法的收斂速度和搜索能力，達(dá)到精度更高和結(jié)果最優(yōu)的目的。

參考文獻(xiàn)：

[1] 孫文彬，王江.一種基于遺傳算法的TSP問(wèn)題多策略優(yōu)化求解方法[J].地理與地理信息科學(xué)，2016，32（4）：1-4.

[2] 林冬梅，王東，李婭.一種求解多旅行商問(wèn)題雙層降解混合算法[J].計(jì)算機(jī)應(yīng)用研究，2011，28（8）：2876-2879.

[3] DORIGO M， MANIEZZO V， COLORNI A. Ant system： optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics A Publication of the IEEE Systems Man & Cybernetics Society，1996，26（1）：29-41.

[4] 徐精明，曹先彬，王煦法.多態(tài)蟻群算法[J].中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào)，2005，35（1）：59-65.

[5] 王啟明，李瑋瑤.基于改進(jìn)量子蟻群算法的TSP求解問(wèn)題研究[J].微處理機(jī)，2015（3）：31-33.

[6] 張開(kāi)碧，張洋川，萬(wàn)素波，等.一種改進(jìn)的競(jìng)爭(zhēng)型蟻群算法在TSP問(wèn)題中的應(yīng)用[J].計(jì)算機(jī)與數(shù)字工程，2016，44（3）：396-399.

[7] GAMBARDELLA L M， DORIGO M Q. A Reinforcement learning approach to the traveling salesman problem-machine learning proceedings 1995-ant[J]. Machine Learning Proceedings，2000，170（3）：252-260.

[8] ROSENKRANTZ D J， STEARNS R E， II P M L. An analysis of several heuristics for thetraveling salesman problem[J]. Siam Journal on Computing，1977，6（3）：563-581.

[9] 馮月華.一種求解TSP問(wèn)題的改進(jìn)蟻群算法[J].電子測(cè)試，2014（8）：38-40.

[10] YOSHIKAWA M，TERAI H.Architecture for high-speed ant colony optimization[C].IEEE International Conference on Information Reuse and Integration. IEEE，2007：1-5.endprint