融合動態層次聚類和鄰域區間重組的蟻群算法

摘要：針對蟻群算法搜索速度過慢以及解質量不足等問題，提出一種融合動態層次聚類和鄰域區間重組的蟻群算法。在初始階段，調整層次聚類閾值并按照類間距離最小合并的原則迭代至目標簇集，根據預合并系數進行簇間合并，通過蟻群系統得到小類路徑并斷開重組以加快算法整體收斂速度；接著使用蟻群系統對解空間進行優化，同時并行處理簇集與簇集鄰域區間擴散重組，增加解的多樣性，進一步固定迭代次數進行比較，若鄰域區間重組解質量優于當前優化解則進行推薦處理，提高解的精度；當算法停滯時，引入調整因子降低各路徑信息素之間差異以增強螞蟻搜索能力，有助于算法跳出局部最優。實驗結果表明，在面對大規模問題時，算法的精度在3%左右，該方法相比傳統方法可以有效提高解的精度和收斂速度。

關鍵詞：蟻群算法； 動態層次聚類； 鄰域重組； 推薦處理

中圖分類號：TP18文獻標志碼：A文章編號：1001-3695（2023）06-010-1666-08

doi：10.19734/j.issn.1001-3695.2022.11.0556

Ant colony algorithm based on dynamic hierarchical clustering and

neighborhood recombination

Zhang Peia， You Xiaominga" Liu Shengb

（a.School of Electronic amp; Electrical Engineering， b.School of Management， Shanghai University of Engineering Science， Shanghai 201620， China）

Abstract：Aiming at the problem of slow search speed and insufficient solution quality of ant colony algorithm， this paper proposed an ant colony algorithm combining dynamic hierarchical clustering and neighborhood interval reorganization. In the ini-tial stage， the algorithm adjusted the hierarchical clustering threshold and iterated to the target cluster based on the principle of minimum inter-cluster distance merging， and then merged the clusters according to the pre-merging coefficient. In the next place it used ant colony system to generate subclass paths， disconnected and reorganized the initial paths to improve the overall convergence speed of the algorithm. Then the algorithm used ant colony system to optimize the solution space， and at the same time， carried out neighborhood interval diffusion reorganization between clusters to increase the diversity of solutions. Furthermore， if the quality of the reconstructed solution was better than the current optimization solution at a fixed number of iterations， the recommendation process would be carried out to improve the accuracy of the solution. When the algorithm stagnated， it introduced an adjustment factor to reduce the differences between pheromones of each path to enhance the ant search ability， which could help the algorithm jump out of the local optimal. The experiment result shows that the accuracy of the algorithm is about 3% when facing large-scale problems， which can effectively improve the accuracy and convergence rate of the solution.

Key words：ant colony algorithm; dynamic hierarchical clustering; neighborhood reorganization; recommendation process

0引言

旅行商問題（traveling salesman problem，TSP）［1］是經典的組合優化問題，具體描述為：一位旅行商從某一個城市出發，需要途經所有的城市且僅能訪問一次，最后回到出發點，歸劃其路線使其行走的路程最短。該問題的所有解是將其所有城市進行全排列，當城市點數較少時可實行，但隨著城市數量的增加，會產生組合爆炸。它是一個完全NP問題，且使用確定性算法來獲得TSP問題解的困難呈指數倍增長。由于其具有重要的實際應用和工程背景，越來越多的學者開始借用啟發式算法來降低最優解的精度以換取效率的提升。眾多啟發式算法中，遺傳算法［2］、蟻群算法［3］、粒子群算法［4］等均有良好特性，為解決該問題提供了新思路。其中蟻群算法（ant colony optimization，ACO）以極強的魯棒性和正反饋機制等特點脫穎而出。

蟻群系統（ant system，AS）最早于1991年由Dorigo等人［5］觀察發現螞蟻在尋找食物時，通過在路徑上分泌信息素來進行溝通交流從而快速找到尋找食物最短的路徑，基于此信息素正反饋原理提出該算法。但該算法自身存在收斂速度慢、易陷入局部最優等問題，因此Dorigo等人［6］引入了全局更新策略，加快算法收斂并提出了蟻群系統（ant colony system，ACS）。Stützle等人［7］通過設置局部信息素的最大最小閾值，來避免由于信息素過大而陷入局部最優，也避免其過小而錯失該路徑，提出最大最小螞蟻系統（min max ant system，MMAS）。

隨著城市規模的不斷擴大，上述問題仍然存在，因此許多學者對蟻群算法在不同方面進行改進。文獻［8］對初始信息素進行非均勻分配使優質解信息素濃度較高，使用定向鄰域擴展策略增加算法多樣性，借助雙層精英策略來更新信息素避免其陷入收斂振蕩。文獻［9］針對過度局部最優問題，提出基于多樣化搜索的帝國競爭算法，通過區塊機制將每個部分的優勢解片段進行保留，使用人造解組合的方式增強對不同解空間的有效可行解信息的搜索，增加算法的多樣性。文獻［8，9］注重提高多樣性，其求解速度有待進一步提高。

文獻［10］提出暴力破壞路徑上信息素堆積的策略，對陷入局部最優的道路采取區域破壞重建的方式跳出局部最優，根據優勝劣汰原則更新信息素以加快算法整體收斂速度。文獻［11］提出路徑方案歸檔更新策略，將蟻群每次尋優路線信息進行存儲，對選擇的路徑方案進行更新和篩選，增加新解的同時刪除檔案中差解并對解的優劣進行排序，提高算法整體的收斂速度。文獻［10，11］收斂速度較為優秀，但在平衡速度和精度方面有待提升。

文獻［12］根據人工蜂群分級思想，提出動態分級的雙蟻態蟻群算法，將螞蟻分為尋優蟻和偵查蟻，尋優蟻負責探索較優路線而偵查蟻負責探索其他新路徑，每次迭代結束后進行優良解的交換，有效平衡解的精度和收斂速度。文獻［13］借用了異構雙種群蟻群的差異化相互協作并借助遺傳算法交叉算子進行最優解融合，在每個種群中根據社會群體搜索理論，將螞蟻劃分為首領、中堅群體和追隨者，使得多樣性、解的精度和收斂速度達到平衡。文獻［12，13］有效地平衡收斂速度與求解精度，但面對大規模問題時解的精度有待進一步提升。

文獻［14］利用改進密度峰聚類確定了聚類的中心點，將TSP劃分為若干二類TSP，并根據粒子群算法得到合適參數，將大規模TSP轉換為多個小規模問題以提升求解速度。文獻［15］提出一種帶有過濾推薦回溯機制的動態密度聚類策略，通過初級聚類與動態聚類將城市點合理劃分合并，基于協同過濾的推薦回溯增加算法多樣性，增強算法跳出局部最優能力。文獻［14，15］表明，聚類在解決大規模TSP時有著明顯優勢。

因此本文提出了一種融合動態層次聚類和鄰域區間重組的蟻群算法（HNACO）。首先通過設立層次聚類閾值對初始城市進行劃分，按照類間距離最小合并原則迭代至目標簇集，根據預合并系數將其合并，并通過蟻群系統得到每個小類的最短路徑，尋找簇集與簇集之間最近點以及前后點進行重組連接，并增加該路徑上的信息素濃度，使得其在蟻群初期階段就能發揮一定的指導作用，讓螞蟻能更好地趨向于最優解附近；其次使用蟻群算法對TSP進行優化處理，與此同時并行處理簇集與簇集鄰域區間重組，每個周期進行一次比較，若鄰域區間重組解質量優于當前蟻群解則進行推薦處理，并自適應地更新信息素；最后當算法進入到停滯狀態時，借助調整因子降低各路徑信息素之間差異，增強搜索能力以跳出局部最優。

研究結果表明，本文提出的融合動態層次聚類和鄰域區間重組的蟻群算法（HNACO）分而治之的方法較為有效，能很好地提升求解速度與精度，尤其是面對大規模問題時。通過標準TSP數據集進行仿真模擬，還發現不同的城市擁有不同的城市規模和聚類特性，若聚類特性較好且初始路徑精度較低，通過后續優化能大幅提升解的精度，反之若聚類特性較差且初始路徑精度較高，通過后續優化的空間較小，但總之本文改進蟻群算法HNACO在面對不同規模、不同聚類特性時均能獲得一定質量較高的解。

1相關工作

1.1ACS蟻群系統

Dorigo等人于1997年提出了蟻群系統（ACS），螞蟻通過式（1）的偽隨機規則選擇開發當前路徑或探索周邊，當qgt;q₀時，螞蟻根據式（2）狀態轉移公式獲得選擇下一個即將要到達的城市的概率。

1.2 層次聚類

1.3 2-opt

2-opt算子，也稱為2-exchange，是一種局部搜索算法，能有效解決組合優化問題。通過對螞蟻走過路徑進行局部優化，從而提升解的精度。2-opt路徑重組圖如圖2所示，隨機選取兩點D、G將整條路徑進行斷開，D前路徑和G后路徑順序不變，D至G之間的路徑順序進行顛倒，使得變換后路徑總長小于原路徑總長。

2.1動態層次聚類

為提升算法精度及收斂速度，通過動態層次聚類以及合并規則將大規模TSP劃分為M個子類問題，運用蟻群算法對每個子類問題進行路徑尋優操作，將簇與簇最近距離點斷開重組連接，形成優質初始解。

為獲取優質初始解，首先對城市坐標進行合理聚類，分而治之。初期采用層次聚合方法將每個樣本均單獨屬于一個類，根據類間距離最小合并的原則，迭代合并類且查看劃分后的每類簇集城市個數，若每簇城市個數在閾值內則停止初始簇集劃分。圖3以Pr226為例繪制其層次聚類樹狀圖，圖3中用一條平行于水平軸的直線，從根節點（上）往枝節點（下）平移，將樹狀圖分割開，圖中將坐標點劃分為三類時，每個子簇集個數均小于閾值，此時停止劃分。

當層次聚類劃分停止，坐標點表現情況為幾個密集性簇集及若干零散的孤立簇集。為了減少孤立簇集存在，以降低簇集與簇集之間的連接消耗，對簇集進行預合并處理。

2.2鄰域區間重組

在2.1節動態層次聚類完成后，將每個簇集中心城市作為簡易城市點，借助蟻群算法迅速得到一條連接各簇集的最短路徑，從而確定簇與簇之間的重組順序。圖4中以Pr226為例，通過動態層次聚類得到下面三個簇，使用蟻群算法得到這三個簇的最短路徑以及對應的連接順序為1-2-3-1。

確定簇與簇之間連接次序并尋找較近距離點，對每對點及其前后兩點（共6個點）進行斷開重組，其中的八種排列組合方式如圖5所示。

為了進一步增加解的多樣性，選出排列組合中最小值對應的連接方法作為該簇與簇之間的連接方式，剔除最長解作為起止合并簇集，采用鄰域區間重組策略將簇與簇之間的較近距離點全部列出進行排列組合，對其鄰域進行擴散重組處理并使用2-opt精準去除簇與簇之間連接產生的交叉，以尋找更多的解。

圖6展示簇i與j之間的鄰域區間擴散圖，建立簇與簇之間距離矩陣并選取一定比例的最短長度作為核心斷開城市，將其前后兩點作為附屬點進行上述六點斷開重組，以獲取更短連接距離，提高解空間精度。line1是簇i與j之間的最短距離，初始路徑為此處的斷開重組，但對點c、n及其各自前后兩點b、d、m、o這六點進行上述重組距離較大。通過鄰域擴散發現，下方line2、line3、line4等對應的路徑質量并不差，對每組點進行上述六點重組，相比之下，下方line3對應的點g、h、i、q、r、s進行重組后距離更近，故保留更優解。

每次迭代時，螞蟻在初始路徑增強的信息素指引下，通過蟻群算法不斷優化解的質量，同時并行處理簇與簇之間多樣擴散重組，當到達一定周期，將此階段內蟻群優化后的最短路徑解A與鄰域擴散重組的最短路徑解B進行比較，若解B質量優于解A則將解B信息傳遞至蟻群算法，并在周期結束時按式（7）對最優路徑信息素進行更新，增加跳出局部最優的可能。

引入調整因子ε主要在于對全局更新信息素進行調整，若到達迭代周期時需要推薦處理，則需要同時更新該推薦路徑上的信息素值，從而給予后續尋優一定的指導作用，若未進行推薦則仍按當前最優路徑更新路徑上的信息素，兩者均設置調整因子1lt;εlt;2，使其最優路徑上信息素進行正優化處理；若算法在整體迭代過程中陷入局部最優，則降低最優路徑與其他路徑上的信息素差異，減少該最優路徑的信息素累積，增加其跳出局部最優的可能性，設置0lt;εlt;1對最優路徑上的信息素實行負優化，即削弱處理。

2.3改進算法流程圖

改進算法流程如圖7所示。

3仿真實驗與結果分析

為驗證HNACO算法的性能，在Windows 10操作系統中使用MATLAB R2017a對TSPLIB標準庫不同規模的城市集進行仿真實驗，并與傳統的算法、當今最優算法進行比較。

3.1實驗參數設置

本文在ACS算法的基礎上進行深入研究，根據文獻［17］以及多組參數對實驗測試結果，發現其參數取值為表1時效果更好，其中α為信息啟發因子，其值越小，螞蟻傾向于走之前的路徑的可能性越小;β為期望啟發因子，其值越大，螞蟻更容易選擇局部最優路線;ξ為局部信息素蒸發率;ρ為全局信息素蒸發率;m為螞蟻數量;Tmax為迭代次數;q0為設定的參數，取值為（0，1）。

為了使初始凝聚型層次聚類擁有良好的劃分，本文建立分段函數來動態設置劃分簇集閾值，當城市規模較小，城市數小于300設置其閾值為100；若其為中大規模時城市數在1 000以內，通過相關文獻［15］和對比小規模TSP結果，發現在解決較小規模（200以內）TSP時，算法求解精度較高且運行時間短，擁有較好的性能，故設置每個簇集閾值取值大小在200左右，此時子類簇集劃分更為合理；當其為超大規模時城市數大于1 000，則對城市簇集個數以及每個簇集閾值進行雙重限制，在保證簇集數量較為精簡的情況下，降低各簇集之間冗余連接，設置其簇集閾值隨城市數動態擴大且固定最大簇集數量上限。由于本文實驗最大規模為1 000左右，故對于超大規模城市閾值劃分尚未進行合理驗證。

較好的初始路徑能為蟻群提供良好指引，HNACO算法初期在簇集與簇集之間進行斷開連接并得到一條較優路徑，根據初始解情況對該路徑進行激勵，在一定程度上增加初始較優路徑上的信息素值大小，激勵倍數E與城市數量n之間關系為E=n/k，根據圖8可知，當k取100時解的情況較好，故本文選取k=100。

3.2算法性能分析

3.2.1動態層次聚類有效性分析

1）目標簇集迭代情況分析

在算法初始階段，調整層次聚類閾值并按照類間距離最小合并的原則迭代至目標簇集，類間距離最小合并原則是層次簇類合并的基本原則，其本質是由下而上選擇簇與簇之間最近簇集進行不斷迭代合并，最終合并一類。本文關于距離的概念是物理距離，求解TSP也是求解物理距離上的最短路徑，因此保證聚類時簇與簇之間聚類距離最小十分重要。以Pr226、Fl417和U724代表小、中、大型城市，其目標簇集迭代情況如圖9所示。

圖9中（a）（d）（g）為三個城市的層次聚類圖，可以觀察到任意兩個樣本不斷聚類的過程;（b）（e）（h）為各城市某次迭代時對應樣本聚類的情況，Pr226和Fl417聚類情況更好，U724由于點分布較為均勻，聚類情況較差;（c）（f）（i）為目標簇集迭代圖，是各城市通過層次聚類聚類個數隨著迭代次數不斷減少的柱狀圖。從圖9中可看出，Pr226和Fl417的聚類特性較好，在迭代初期就已經很好地進行聚類，而U724迭代初期僅部分近距離的點相互進行了合并處理，隨著迭代次數的增加才加快合并的步伐。

由于調整動態層次聚類閾值迭代至目標簇集時解表現為幾個較大簇集與一些零散的點，故后續仍需根據預合并系數進行簇間合并從而獲得最終聚類結果。

2）初始路徑結果分析

通過2.1節動態層次聚類以及預合并將大規模TSP問題劃分為若干子區域，并依據2.2節進行路徑的斷開重組，其部分城市初始路徑精度如表2所示。

通過對比TSP標準庫中各種規模下坐標點情況易知，當坐標點分布越均勻，簇集與簇集之間距離越近，其初始解精度越高；與之相反，當簇集與簇集之間連接過于冗余，簇內密集的優勢往往不被體現，故初始解精度較低。

例如表2中Pr226初始精度并不高，坐標點呈現簇集與簇集之間較為分散而簇內較為聚集的狀態，圖10（a）為借助動態層次聚類劃分好的子類簇集最優路徑，此時通過簇集與簇集之間斷開連接獲得初始路徑解質量較低如圖10（b）所示，隨著后續鄰域區間重組與蟻群系統不斷優化解的質量，最終得到圖10（c），其精度為0.08%。Rat575城市集情況與Pr226相反，如圖11所示城市分布均勻且通過動態層次聚類劃分的簇集與簇集之間連接幾乎無冗余，此時通過連接獲得的初始路徑精度較高，后續優化解空間小，圖11（c）表明其精度控制在2.23%。由此可見，無論城市聚類特性好壞，均可找到優化解，區別僅在于其初始路徑精度以及后續優化解能提升的空間大小。

3）增強動態層次聚類策略有效性分析

為探究HNACO算法中動態層次聚類路徑性能，本節將增強動態層次聚類初始路徑信息素、增強貪婪路徑信息素以及不增強初始路徑信息素三類情況進行對比。以Pr226、Lin318、Pr439為例，其對比結果如圖12（a）～（c）所示，其中實線為增強動態層次聚類初始路徑信息素的解的情況，虛線為增強貪婪路徑信息素的解情況，點畫線為不增強初始路徑信息素的解結果。

通過對比分析可見，初始路徑的選取對算法有較大影響，好的初始路徑能夠使算法在初始階段就趨向于優質解附近，保證一定解的質量的同時加快算法整體收斂速度。圖12（a）～（c）三個圖中均表明增強貪婪形成路徑的信息素時表現的解的質量較差，采取增強動態層次聚類初始路徑信息素時，解的質量較高且能繼續尋找其他優質解，而不增強初始路徑信息素的解的質量一般，尤其在圖11（b）Lin318中直接陷入局部最優，解跳出局部最優的能力差。

在圖12（a）迭代初期，增強動態層次聚類初始路徑信息素的解的質量就已經迅速降低，但是由于其初始路徑解的精度一般，其解仍高于初始無激勵的解的大小，但隨著后續的優化，其解一直處于三者中最低位置，且在1 450代、1 980代左右仍尋找到更優解;在圖12（b）（c）中，增強動態層次聚類初始路徑信息素的解的質量較好，且隨著迭代次數的增加，其解一直處于三者中最低的位置，直觀地表明了本文策略的有效性。

3.2.2鄰域區間重組有效性分析

為驗證鄰域區間重組策略的有效性，在蟻群的每次迭代中并行進行鄰域區間擴散重組操作，在固定迭代周期內挑選最優解與蟻群優化解進行比較，若區間擴散擁有更優質的解則進行推薦處理，并通過式（7）動態更新信息素。此策略的目標在于增加算法多樣性從而提升解的精度，以Rat575城市集為例。

如圖13所示，初始迭代時，進行推薦處理的蟻群與未進行推薦處理的蟻群在迭代時刻尋優能力稍有差異，兩者在500代左右時能尋找到質量較為一致的解，均在7 330左右，但當區間擴散形成更好的解，此解質量高于當前迭代尋優所獲得的解時，進行推薦處理。當推薦完畢后，螞蟻隨著迭代次數的增加而快速獲得鄰域區間擴散重組后的優質解，并在優質解附近進行尋優，從而提高解的精度。在圖13中可清晰直觀地看出本文算法在500代時進行推薦處理，且推薦的解的質量較高，將優質解傳遞至蟻群系統并更新最優路徑以及借助信息素調整因子對此路徑上的信息素進行更新調整，為算法后續尋優提供一定的優質路徑的指引，在后續的1 000代、1 500代中未進行推薦處理則說明此時解的精度優于鄰域區間重組的解，借助調整因子對路徑上的信息素進行改動并繼續迭代尋優，固定迭代周期在后續仿真中選取的值會進行調整，但間接反映解空間在指引下一直不斷地進行優化處理，故采用的鄰域區間重組策略有效。

3.3與傳統蟻群算法進行對比分析

為驗證HNACO性能特性，本文將其與傳統ACS和MMAS進行對比，每種算法對應每個數據集均進行獨立的20次實驗，從最優解、誤差率、平均解、平均誤差率、迭代次數等方面進行對比分析，結果如表3和圖13所示，其中best為算法運行20次中最優解，Er為最優解精度，mean為獨立運行20次的平均解，Mr為平均解精度。

依據表3，從整體性能來看，HNACO求解質量在最優解、平均解、誤差率等方面均優于傳統ACS和MMAS算法。MMAS運行速度非常迅速，在小規模中解的精度較優，但在大規模城市中精度在三者中較低；ACS運行速度慢但其在大規模時精度優于MMAS。結合表4可知，當城市規模較小時（lt;300），HNACO算法精度在1%以內且運行時間較短，其求解能力優越；當城市規模為中型城市時，HNACO算法精度在2%左右。在平均解及其平均誤差率方面，HNACO算法也優于傳統ACS、MMAS，平均精度均在5%以內。

圖14為HNACO、ACS和MMAS的收斂對比，由圖可知，三種算法均在不斷尋找最優解，其圖案呈下降趨勢。在迭代初期，由于HNACO算法初始解由動態層次聚類與預合并獲得，其初始解的精度較好，故圖14（a）～（d）在迭代開始的初期就已經降低至一個優質解附近，隨著迭代次數的增加，三種算法均在尋找更優質解，在400代之后，HNACO的收斂曲線均在ACS和MMAS的下方，圖14（a）Fl417的迭代表明其經歷了一次推薦過程，鄰域區間擴散重組的解優于蟻群算法蟻群優化解，并對其重組路徑進行推薦處理，并對重組解路徑上的信息素進行增強。在迭代中后期，HNACO的迭代曲線均在ACS和MMAS迭代曲線的下方，表明本文算法可以更好地尋找高質量解。當其陷入局部最優時，設置ε值更改調整因子，對信息素進行削弱，降低路徑上信息素的差異幫助算法更好地跳出局部最優。在圖14（a）中，算法在1 650代左右找到了更優解；在圖14（c）中，算法在1 900代左右仍在優化；圖14（d）中，算法下降幅度較大，且在1 800代左右仍能尋找到更為優質的解。部分TSP實例最優解如圖15所示。

快速收斂至優質解附近，其根本原因是采取的動態層次聚類與預合并策略，得到子類簇集的最優路徑后進行連接操作并提升初始解激勵，增強其指引作用；在算法中期，當其與區間擴散解進行交互，若擴散解更優質則進行推薦處理，并加強推薦路徑的信息素值，增加解的多樣性的同時獲取更優質的解；當其陷入局部最優時通過對ε的修改從而增加算法跳出局部最優的可能性，避免陷入局部最優。圖14HNACO、ACS和MMAS收斂對比

接著將改進算法HNACO與傳統ACS在多樣性方面進行對比，選取Pr226、Fl417、Pr1002三個城市集代表小、中、大型規模。圖16表示各城市的多樣性對比。圖16（a）（b）表示Pr226的多樣性，圖中可看出HNACO的標準差值較大，且隨著迭代次數的增加其標準差值逐漸上升；圖16（c）（d）為Fl417的多樣性圖，HNACO標準差變化大且多樣性圖較ACS更為密集，說明前者的多樣性更好；圖16（e）（f）為Pr1002多樣性圖，HNACO標準差較ACS波動更大，ACS在490代左右標準差波動過小而HNACO無此問題。綜上表明HNACO多樣性更好。由此可知，HNACO算法在精度、平均解、收斂速度、多樣性等方面均得到有效提升。

3.4與其他最新改進算法進行對比分析

為進一步驗證本文算法性能，將HNACO算法與近些年最新改進算法進行對比，在小規模城市中，與DSMO算法［18］、PCCACO算法［19］和MSSICA算法［9］進行對比，其結果如表4所示。在大規模城市中，與VNS算法［20］和GVNS算法［21］進行對比，其結果如表5所示。表中黑體為對比的最優解。

表4表明HNACO在小規模TSP城市實例中擁有良好的解的精度，當城市數小于閾值時直接按照蟻群初始步驟尋找解，并使用3-opt進行去交叉處理，當城市數超過閾值時采用本文HNACO可使解的精度進一步提高。例如在Pr226中，通過動態層次聚類和區間重組獲得的解精度達到了0.08%，解的質量明顯優于其他大部分解。在KroB150和KroA200這兩個城市中，本文算法和PCCACO解的精度有少許差別，這表明算法在小城市集的尋優方面仍有改善空間。

如表5所示，HNACO在中大規模TSP城市實例中所表現的性能均優于DA-GVNS和VNS，HNACO算法表現更好。在Pr226、Pr299、Fl417、Pr439這幾個城市中HNACO的精度在1%以內，隨著城市規模的擴大，解的精度在2%左右，對于Pr1002大規模城市集，其解精度為3.8%，均優于DA-GVNS、VNS算法解。

結合表2和5中數據可知，本文算法在處理不同聚類特性的城市集問題時，均可實現進一步優化。在3.2.1節中，Pr226初始路徑精度為7.00%，后續優化至0.08%，Rat575初始路徑精度為5.63%，后續優化至2.23%，這是由于改進算法在初期借助層次聚類與預合并對城市集進行處理，分而治之促使其初始路徑較優，隨著后續不斷優化，并行處理鄰域區間擴散重組，固定迭代次數進行對比推薦處理，及時對信息素進行合理調整，加快算法收斂速度的同時也增加了蟻群路徑多樣性。

綜上所述，借助TSP來驗證HNACO算法的性能，從結果看出融合動態層次聚類和鄰域區間重組的蟻群算法（HNACO）在面對大規模問題時表現較好，擁有較強的競爭力，無論城市數量大小、聚類性能好壞均可使用本文HNACO算法來處理，且解的質量較高。

4結束語

本文提出一種融合動態層次聚類和鄰域區間重組的蟻群算法（HNACO），通過動態層次聚類及預合并得到小類路徑，對其連接處理并增強初始激勵以加快收斂速度，通過增強動態層次聚類初始路徑信息素、增強貪婪路徑信息素以及不增強初始路徑信息素三類情況的對比實驗驗證其有效性。接著在蟻群尋優時并行進行簇集與簇集之間的鄰域區間重組以增加解的多樣性，在一定周期時進行最優解的推薦處理，通過2-opt精準去交叉進一步提高解的精度，通過相關實驗驗證此策略在增加多樣性的同時也提升了解的精度。最后在標準的TSP實例上進行實驗，與傳統蟻群算法和其他最新改進算法進行比較，實驗表明HNACO在解的精度、多樣性、收斂速度等方面都有一定的改善，中小規模城市集解精度在2%左右，且其在大規模TSP城市集中表現同樣良好，在3%左右。但其在收斂速度、解的精度方面仍有提升空間，下一步將嘗試改善簇集的劃分以及簇集與簇集之間的交互方式，以進一步提高算法在處理大規模TSP的求解性能。

參考文獻：

[1]Yun Xiaoyan. Research on traveling salesman problem algorithm［J］.Advanced Materials Research，2013，694-697：2901-2904.

［2]Gupta A， Khurana S. Study of traveling salesman problem using genetic algorithm［J］.International Journal of Managment， IT and Engineering，2012，2（5）：575-588.

［3]Mavrovouniotis M， Müller F M， Yang Shengxiang. Ant colony optimization with local search for dynamic traveling salesman problems［J］.IEEE Trans on Cybernetics，2016，47（7）：1743-1756.

［4]Wang Yong， Xu Ning. A hybrid particle swarm optimization method for traveling salesman problem［J］.International Journal of Applied Metaheuristic Computing，2017，8（3）：53-65.

［5]Dorigo M， Maniezzo V， Colorni A. The ant system： optimization by a colony of cooperating agents［J］.IEEE Trans on Systems， Man， and Cybernetics，1996，2（1）：29-41.

［6]Dorigo M， Gambardella L M. Ant colony system： a cooperative lear-ning approach to the traveling salesman problem［J］.IEEE Trans on Evolutionary Computation，1997，1（1）：53-66.

［7]Stützle T， Hoos H H. Max-min ant system［J］.Future Generation Computer Systems，2000，16（8）：889-914.

［8]劉雙雙，黃宜慶.多策略蟻群算法在機器人路徑規劃中的應用［J］.計算機工程與應用，2022，58（6）：278-286.（Liu Shuangshuang， Huang Yiqing. Application of multi-strategy ant colony algorithm in robot path planning［J］.Computer Engineering and Applications，2022，58（6）：278-286.）

［9]陳孟輝，劉俊麟，徐健鋒，等.求解旅行商問題的多樣化搜索帝國競爭算法［J］.計算機應用，2019，39（10）：2992-2996.（Chen Meng-hui， Liu Junlin， Xu Jianfeng， et al. Imperialist competitive algorithm based on multiple search strategy for solving traveling salesman problem［J］.Journal of Computer Applications，2019，39（10）：2992-2996.）

［10]周克良，龔達欣，張宇龍.區域破壞重建的蟻群優化算法［J］.計算機工程與應用，2020，56（14）：62-67.（Zhou Keliang， Gong Da-xin， Zhang Yulong. Ant colony optimization algorithm for regional destructive reconstruction［J］.Computer Engineering and Applications，2020，56（14）：62-67.）

［11]楊北辰，余粟.改進蟻群算法在路徑規劃中的應用［J］.計算機應用研究，2022，39（11）：3292-3297，3314.（Yang Beichen， Yu Su. Application of improved ant colony algorithm in path planning［J］.Application Research of Computers，2022，39（11）：3292-3297，3314.）

［12]李順東，游曉明，劉升.結合ABC算法動態分級的雙蟻態蟻群算法［J］.計算機工程與應用，2020，56（12）：37-46.（Li Shundong， You Xiaoming， Liu Sheng. Dynamic hierarchical dual-morphic ant colony algorithm based on artificial bee colony algorithm［J］.Computer Engineering and Applications，2020，56（12）：37-46.）

［13]馬飛宇，瞿中.基于異構雙種群全局視野蟻群算法的移動機器人路徑規劃研究［J］.計算機應用研究，2022，39（6）：1705-1709.（Ma Feiyu， Qu Zhong. Research on path planning of mobile robot based on heterogeneous dual population and global vision ant colony algorithm［J］.Application Research of Computers，2022，39（6）：1705-1709.）

［14]馮志雨，游曉明，劉升.分層遞進的改進聚類蟻群算法解決TSP問題［J］.計算機科學與探索，2019，13（8）：1280-1294.（Feng Zhiyu， You Xiaoming， Liu Sheng. Hierarchical progressive improved clustering ant colony algorithm for solving TSP problems［J］.Computer Science and Exploration，2019，13（8）：1280-1294.）

［15]Yu Jin， You Xiaoming， Liu Sheng. Dynamic density clustering ant colony algorithm with filtering recommendation backtracking mechanism［J］.IEEE Access，2020，8：154471-154484.

［16]呂琳，尉永清，任敏，等.基于蟻群優化算法的凝聚型層次聚類［J］.計算機應用研究，2017，34（1）：114-117.（Lyu Lin， Wei Yongqing， Ren Min， et al. Agglomerative hierarchical clustering based on ant colony optimization algorithm［J］.Application Research of Computers，2017，34（1）：114-117.）

［17]黃敏.基于蟻群算法參數的最優選擇問題研究［J］.瓊州學院學報，2012，19（2）：40-42.（Huang Min. The reasonable selection on paramenters of ant colony algorithm［J］.Journal of QiongZhou University，2012，19（2）：40-42.）

［18]Akhand M A H， Ayon S I， Shahriyar S A， et al. Discrete spider monkey optimization for travelling salesman problem［J］.Applied Soft Computing，2020，86：105887.

［19]Zhu Hongwei， You Xxiaoming， Liu Sheng. Multiple ant colony optimization based on pearson correlation coefficient［J］.IEEE Access，2019，7：61628-61638.

［20]Hore S， Chatterjee A， Dewanji A. Improving variable neighborhood search to solve the traveling salesman problem［J］.Applied Soft Computing，2018，68：83-91.

［21]Karakostas P， Sifaleras A. A double-adaptive general variable neighborhood search algorithm for the solution of the traveling salesman problem［J］.Applied Soft Computing，2022，121：108746.