許能闖

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

關鍵詞：蟻群算法；正反饋；信息素；收斂速度；TSP問題

DOIDOI：10.11907/rjdk.173024

中圖分類號：TP312

文獻標識碼：A 文章編號：1672-7800（2018）002-0056-04

0 引言

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

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

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

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

1 算法簡介

1.1 蟻群算法工作原理

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

1.2 路徑選擇概率機制

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

1.3 信息素更新機制

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

1.4 算法流程

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

2 蟻群算法改進

2.1 蟻群算法缺點

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

2.2 改進的蟻群算法

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

2.2.1 路徑選擇概率改進endprint

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

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

2.2.2 信息素更新的改進

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

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

3 實驗結果

3.1 仿真環(huán)境

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

3.2 仿真結果對比

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

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

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

為進一步論證本文算法性能，再以CH150TSP問題為例，如圖8所示。

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

4 結語

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

參考文獻：

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

[2] 林冬梅，王東，李婭.一種求解多旅行商問題雙層降解混合算法[J].計算機應用研究，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].中國科學技術大學學報，2005，35（1）：59-65.

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

[6] 張開碧，張洋川，萬素波，等.一種改進的競爭型蟻群算法在TSP問題中的應用[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問題的改進蟻群算法[J].電子測試，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