基于改進蟻群算法的TSP問題研究

許能闖

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

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

DOIDOI：10.11907/rjdk.173024

中圖分類號：TP312

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

0 引言

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

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

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

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

1 算法簡介

1.1 蟻群算法工作原理

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

1.2 路徑選擇概率機制

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

1.3 信息素更新機制

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

1.4 算法流程

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

2 蟻群算法改進

2.1 蟻群算法缺點

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

2.2 改進的蟻群算法

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

2.2.1 路徑選擇概率改進endprint

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

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

2.2.2 信息素更新的改進

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

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

3 實驗結果

3.1 仿真環境

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

3.2 仿真結果對比

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

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

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

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

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

4 結語

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

參考文獻：

[1] 孫文彬，王江.一種基于遺傳算法的TSP問題多策略優化求解方法[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] 徐精明，曹先彬，王煦法.多態蟻群算法[J].中國科學技術大學學報，2005，35（1）：59-65.

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

[6] 張開碧，張洋川，萬素波，等.一種改進的競爭型蟻群算法在TSP問題中的應用[J].計算機與數字工程，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