基于信息素矩陣優化蟻群算法求解城市建模的旅行商問題

Travelling salesman of urban modeling based on pheromone matrix optimization ant colony algorithm

Liu Daia，Zhang Yaming?，Wang Kaib，Cui Haiqingh? （a.EngineegnCteFlfocftoutoatoltionUsitof 300000，China）

Abstract：This paper proposedanoptimizedantcolonyalgorithm toaddressthe traveling salesman problem（TSP）inurban modeling.Thealgorithmintegratedrandomaveragingofthepheromone matrix，adaptiveperturbation，anddynamicproportional resetingstrategies tooptimizethepath search intheprocessof acquiringurban modeling materials.Aftereachroundof path selection，thealgorithmgloballyupdatedthelocalpheromonebasedonthequalityof thepathsandacceleratedconvergence through2-optoptimization.Initialy，itappliedtherandomaveraging strategy.When theoptimalpathhadnotbeenupdated formultiple iterations，thepheromoneofrandom nodes wasaveraged toavoidlocaloptima.Whenmultipleatemptsattherandomaveraging strategyproveinefective，itintroducedtheadaptiveperturbationstrategy.Thisstrategyperturbedtheperomone matrix toselectpaths，therebyreducing theriskoflocal optima.This strategyperturbedthepheromonematrix toselect paths，reducingtheriskoflocaloptima.Whenthequalityof theoptimalpathdecreases byacertain proportion，itusedthe dynamicproportionalresetingstrategytoincreasethediferencebetweenhighandlowpheromonevaluesinthematrix，further accelerating convergence.Theresultsshowthatthealgorithm efectivelyimprovesglobal search capability，acelerates the convergence process，and provides a solution to the TSP in urban modeling.

Key words：antcolonyalgorithm；traveler’ssalesmanproblem；combinatorial optimization；2-optalgorithm；urban 3D modeling

0 引言

隨著城市場景豐富和城市系統擴大，城市管理進人新階段。城市模型在規劃設計[1]、交通管理[2]和應急管理[3]等領域發揮重要作用，作為數字化城市的視覺表現。其通過模擬城市空間、結構和功能，為決策者提供關鍵信息和可視化參考。

現有高精度城市建模方法包括：基于多數據源的人工交互建模、基于影像和激光掃描點云的半自動建模，以及傾斜攝影建模[4]。這三種建模方法的共同特點是需對物體進行完整拍攝，覆蓋所有最佳拍攝點并確保每個點至少拍攝一次，最終返回初始點，構成組合優化中的經典問題—旅行商問題（trave-ling salesmanproblem，TSP）[5]。其中，文獻[6＼～8]完成城市建模拍攝視點規劃后，分別采用隨機重啟的2-opt算法、改進快速隨機探索樹算法和改進 A^* 算法進行TSP路徑規劃。但是這些方法仍具有一定的局限性，未能深人開發優化路徑規劃的潛力。為此，提出新的方法進行補充開發，以提高城市建模中TSP的優化性能。

當前求解TSP的算法主要分為精確算法和近似算法。盡管精確算法能夠提供最優解，但由于其計算量龐大[9，往往無法在實際問題中實現理想效率。因此，在大多數實際應用中，近似算法通常被優先選擇，作為TSP的解決方案[10]。

近似算法中，蟻群算法（antcolonyoptimization，ACO）是一種受自然界螞蟻覓食行為啟發的元啟發式近似算法，自20世紀90年代提出以來，因其良好的性能和靈活性被廣泛應用于TSP的求解，進而被廣泛應用于物流配送[11]、印刷電路板設計[12]和網絡路由[13]等領域。蟻群算法通過模擬螞蟻在路徑上釋放和追蹤信息素（pheromone），逐步優化路徑選擇[14]。然而，蟻群算法在解決大規模TSP問題時仍存在收斂速度慢、易陷入局部最優等問題[15]。

針對上述不足，Dorigo等人[16]指出，近年來研究蟻群算法的主要方向是將其與其他元啟發優化算法進行融合。例如，Rokbani等人[17]提出一種引力粒子群算法（PSOGSA）與蟻群算法相結合的方法，通過PSOGSA用于優化蟻群算法設置，提高了算法的搜索能力并加速收斂。Dewantoro等人[18]提出蟻群算法得出初始解，后用禁忌搜索算法進行局部搜索的組合方式來解決TSP問題，并確實得到了比單一蟻群算法更好的結果。Omar等人[19]提出了一種結合洗牌交叉和部分映射交叉的新型混合交叉遺傳算法與蟻群算法進行結合，來求解TSP。Farisi等人[20]提出了一種螢火蟲算法與蟻群算法的混合算法來求解多站點多旅行商問題。Dai等人[21]將生物地理學優化算法（BBO）和蟻群算法進行混合，先用BBO算法進行初期探索，然后用蟻群算法進行最終探索，求解TSP。

針對上述不足，少部分學者通過給出一定策略來解決蟻群算法收斂速度慢且容易陷入局部最優的問題。Ebadinezhad[22]通過引入新信息素矩陣智能選擇起始節點，并動態調整算法參數，以平衡收斂速度和精度。 Gao^[23] 通過采用組合成對搜索螞蟻策略，增強了解空間多樣性，并引入閾值常數加速算法以提升收斂速度。Li等人[24]應用HPA方法增強種群多樣性，結合平滑法優化2-opt解，并通過差分更新平衡收斂性與精度。Shahadat等人[25]不僅考慮到降低回程成本的問題，還引入3-opt局部搜索，優化求解質量和計算效率。Liu等人[26]基于凸包和K-means的初始化策略，適應不同規模實例，增加多樣性，避免局部最優，同時混合局部選擇策略提升解質量并縮短優化時間。以上改進算法，雖取得了一定成果，但不一定適配于城市建模路徑選取中，此類問題著重于提高算法所求得的平均解和標準方差，以確保每次求解結果的可靠性，從而實現算法的快速部署和高效應用[6]。為解決此類問題，提出了一種基于三種信息素矩陣優化策略的蟻群優化算法，旨在優化城市建模素材獲取過程中的路徑搜索。因此，該算法被命名為面向城市建模的蟻群優化算法（ant colonyoptimization algorithmfor urbanmodeling，UMACO）。

1 蟻群系統（ACS）

1.1 路徑構建規則

偽隨機狀態轉移策略作為ACS（antcolonysystem）中大部分被采用的路徑構建規則。其中，螞蟻 k 在節點 i 時，遵循以下兩種規則之一，來選擇下一個待訪問節點 j ，該轉移策略為

其中： τ_ij 是節點 i，j 之間的信息素濃度。 η_ij 是節點 i 和 j 之間的啟發信息（在旅行商問題中一般是距離的倒數）。 α 和 β 分別控制信息素和期望的啟發因子，代表了信息素和期望在路徑選擇中的重要性。 C_k 為螞蟻 k 可以選擇的節點集合。 q₀ 是算法中的一個關鍵參數，它控制螞蟻在開發和探索之間的權衡。當q₀ 較大時（接近1），螞蟻更傾向于根據信息素和期望這兩種啟發因子選擇最優路徑。在這種情況下，螞蟻主要在已知的路徑上進行強化，從而更快地收斂到局部最優解。而當 q₀ 較小時，螞蟻在大多數情況下會做出隨機決策，依據概率公式選擇節點，這增加了螞蟻選擇尚未充分探索路徑的可能性，促進了更多的探索行為，從而使螞蟻更多地進行探索。 s 為根據式（2），按輪盤賭規則選擇的一個隨機變量。

其中： P_ij^k 為螞蟻 k 在節點 i 通過輪盤賭方式選擇節點 j 的概率。

1.2信息素更新規則

1）局部信息素更新

在螞蟻種群構建路徑的過程中，每只螞蟻完成路徑選擇后，立即更新信息素矩陣。此舉旨在增強算法的探索性，防止螞蟻群體過早地集中于同一條路徑，從而確保在解空間內進行廣泛的搜索。局部信息素更新公式為

其中：δ為局部信息素揮發系數，取值為 [0，1];τ₀ 為初始信息素濃度。

2）全局信息素更新

在每輪螞蟻種群完成路徑選擇后，依據路徑質量對優質路徑的信息素進行強化，以引導螞蟻逐步聚集到最優路徑上，從而加速算法的收斂過程。全局信息素更新公式為

其中 _：ρ 為全局信息素揮發因子； Δτ_ij 為最優路徑上的信息素增量； L_gb 為全局最優路徑的長度。

1.3 局限性

以下將分析ACS算法中可能導致缺陷的三大因素。

原因1在ACS算法的路徑選擇過程中，由于算法初期信息素濃度較低，路徑選擇主要依賴于 η_ij ，所以容易出現如圖1（b）所示的情況。例如，節點5的最優路徑應如圖1（a）所示，為其最近的兩個節點6和7，但由于初期這兩個節點已被優先選擇，節點5不得不選擇節點4和1，進而在這些次優路徑上積累過多的信息素。即使在后續迭代中節點4和1未被選擇，過量的信息素積累仍可能導致節點5難以找到最優路徑。此外，對于節點14而言，盡管節點8和12本應具有相同的選擇概率，但由于信息素的偏向性積累，使得節點8被選擇的概率顯著降低。這種現象反映了信息素積累過程對路徑優化結果的顯著影響。

原因2對于大規模TSP，往往會出現即便算法對數據集優化不足，信息素卻已過早積累，進而陷入局部最優解[27]

原因3ACS是一種基于信息素積累的優化算法，通過正反饋改進解的搜索過程。盡管引入了輪盤賭選擇策略進行擾動，但擾動強度低，主要用于保留信息素矩陣并提供少量的跳出局部最優機會。然而，這樣的擾動機制有效性有限。但擾動概率調高就會影響ACS的核心信息素更新機制，降低算法性能。

2 UMACO描述

該算法是在ACS的基礎上提出的一種多信息素矩陣優化策略融合的協同蟻群算法。首先，為了加速ACS的收斂性，改進了原有的局部更新規則，具體做法是：在每只螞蟻構建完路徑后，立即進行局部信息素更新，將其改為在所有螞蟻完成路徑選擇后再根據所有螞蟻的路徑信息進行整體更新。并將局部信息素更新公式改為

τ_ij（t+1）=（1-δ）τ_ij（t）+δ/L_kl

其中：δ為局部信息素揮發系數，取值為 [0，1] L_kl 是螞蟻 k 完成路徑選擇后的路徑長度。

盡管該策略在一定程度上減少了種群的多樣性，但其保證了每只螞蟻均可以基于原始信息素矩陣進行路徑選擇。這種機制能夠使原始信息素矩陣中信息素濃度較高的路徑吸引更多螞蟻進行選擇，進一步強化其信息素的積累。此外，根據式（6），對每條路徑段進行統一的 （1-δ）τ_ij（t） 蒸發操作后，不是增加固定量的 δτ₀ 信息素，而是根據路徑質量動態調整，使高質量路徑獲得更多的 δ/L_kl 信息素。兩項改進結合有效提升了高質量路徑的信息素積累速度，從而顯著加快算法收斂。同時，該算法將2-opt策略引入ACS，增強算法的局部搜索能力。為避免運行時間過長，僅對種群中的最優路徑進行2-opt優化，以進一步加快算法收斂速度。然而，這兩種優化策略也增加了算法陷入局部最優解的風險。接下來的三種信息素矩陣優化策略均是在上述兩項改進的基礎上進行的。下文中所提到的“正常算法運行”也指的是基于上述兩種修改后的ACS機制。

2.1隨機平均信息素矩陣策略

為了減少本文1.3節中的原因1導致的局部最優問題，本文設計了一種新的信息素矩陣平均策略即隨機平均信息素矩陣策略。

該策略的設計思想是在執行過程中，為每個節點生成一個位于（0，1）的隨機數，并與預設的閾值 θ 進行比較。如果隨機數小于θ，則將該節點與其他節點之間的信息素濃度調整為平均值。該策略不會在每次迭代中執行，而是僅在算法出現停滯次數達到COUNT1后才觸發。其創新之處在于引入信息素“平均化”的思想，而非簡單地重置信息素為固定值。具體來說，策略通過隨機選擇節點并平均分配信息素，消除部分錯誤積累，同時保持原始信息素總量不變，增加了隨機性。該策略在算法陷入局部最優解一定次數后觸發，既保留了信息素平衡策略的優點，又避免了過度平均化的負面影響，從而有效降低了局部最優解的風險，同時增強了算法的全局搜索能力。其中θ 和COUNT1將在3.1.1節中詳細闡述。算法偽代碼如算法1所示。

算法1隨機平均信息素矩陣策略

輸入：局部最優路徑 L_lb ；全局最優路徑 L_gb ；1號計數器count1；信息素矩陣pheromoneMatrix。輸出：1號計數器count1；信息素矩陣pheromoneMatrix。a）如果 L_lb 大于或等于 L_gb ，將count1加一，否則，將當前 L_gb 設置為L_lb ，countl歸零。執行步驟b）。b）如果count1等于COUNT1，執行步驟c）。否則，正常算法運行。c）count1歸零；根據閾值θ，隨機選擇節點并對其信息素進行平均，從而得到新pheromoneMatrix后正常算法運行。

2.2動態比例信息素矩陣重置策略

為了減少本文1.3節中的原因2導致的局部最優問題，本文設計了一種新的信息素矩陣重置策略即動態比例信息素矩陣重置策略。

該策略的設計思想是：當全局最優路徑低于歷史函數最優適應值基準的某一特定比例 （1-γ） 時，啟動重置策略，并將最優適應值基準更新為當前全局最優路徑。由于每個數據集的大小不同，歷史函數最優適應值基準的初始值設為第一次迭代時的全局最優路徑。在每次重置時，信息素矩陣中大于 η 倍初始信息素的元素將被重置為初始信息素乘以重置次數，其余信息素則設為初始信息素的一半，從而實現信息素重置。該策略的創新性在于引入了比例啟動與重置機制，實現了全局搜索能力與局部搜索能力的有效平衡，提升了綜合搜索能力。比例啟動避免了過度重置對信息素積累的負面影響，保留了局部搜索成果；信息素重置則通過將較高信息素統一至同一水平，有助于跳出次優解為全局最優解的局部最優現象，增強全局搜索能力。重置過程中信息素值與重置次數相乘，既促進了信息素積累，又加速了算法收斂。其中 γ 和 η 為可設定的參數，都將在3.1.2節中詳細闡述。算法偽代碼如算法2所示。

算法2比例信息素矩陣重置策略

輸入：全局最優路徑 L_gb ;歷史函數最優適應值基準 L_rb ;1號計數器count1;信息素矩陣pheromoneMatrix;2號計數器count2，重置標志位 Flag_r 。輸出：1號計數器count1;2號計數器count2；最優適應值基準值L_rb ；信息素矩陣pheromoneMatrix；重置標志位 Flag_r 。a）如果 L_gb 小于等于 L_rb×（1-γ） ，那么將 Flag_r 設為 設為當前的 L_gb ，進入步驟b）。否則，正常算法運行。b）如果count1等于COUNT1，且 Flag_r 等于1。則執行步驟c）；否則，正常算法運行。c）根據 tau0 的 η 倍進行劃分，高于其值的重置為 tau0×count2 ，低于其值的為tauO的一半，得出新pheromoneMatrix；后將count2加一，Flag_r 設為0，countl清零。之后正常算法運行。

2.3自適應信息素矩陣擾動策略

為了減少本文1.3節中的原因3導致的局部最優問題，提出了自適應信息素矩陣擾動機制。

該策略的設計思想為：在算法經過COUNT3倍數次平均策略仍未跳出局部最優時啟動（其中COUNT3將在3.1.3節中詳細闡述）。根據式（7），通過現有信息素矩陣生成擾動信息素矩陣。其中參數 A 是參考河馬算法中的擾動規則所提出的算子，推導過程如式（8）＼～（10）所示。

pheromoneMatrix_p=A×pheromoneMatrix

A=M×C+1

M=（2-（（t-1）/（iteration-1））²）

C=rand（numberOfCities，numberOfCities-1）

在接下來的COUNT1次迭代中，算法基于擾動信息素矩陣進行路徑選擇，暫停局部信息素更新，保持全局信息素更新正常進行。之后，算法將恢復使用原始信息素矩陣，并繼續按照正常算法運行。該策略的創新在于，擾動僅在多次平均策略無效時啟用，再次提高算法的全局搜索能力，并隨著迭代增加逐漸減小擾動幅度以保證穩定收斂，提高收斂速度。大規模擾動只在找到更好全局最優路徑時影響原始信息素矩陣，否則沿用原始全局最優路徑更新信息素矩陣。算法偽代碼如算法3所示。

算法3自適應信息素擾動策略輸入：1號計數器count1;信息素矩陣pheromoneMatrix;3號計數器count3；擾動標志位 Flag_d 。輸出：1號計數器count1;3號計數器count3；擾動信息素矩陣phero-moneMatrix;擾動標志位 Flag_d 信息素矩陣pheromoneMatrix。a）每進行一次隨機平均信息素矩陣策略，就將count3加一；b）如果 count1=COUNT1 且count3為COUNT3的倍數，就將擾動標志位 Flag_d 置為 1 之后執行步驟c）。c）接下來的COUNT1次迭代都根據式（8）得出 A ，根據式（7）得到pheromoneMatrix，，執行步驟d）。d）正常蟻群算法運行，但去除了局部信息素的更新，并且在路徑構建中使用對應的pheromoneMatrixp。當 count1=COUNT1 時，執行步驟e）。e） Flag_d 置為0，且count1清零，之后正常算法運行。

2.4 UMACO流程

提出的改進算法，通過結合隨機信息素平均、自適應信息素矩陣擾動策略和動態比例信息素矩陣重置策略，對蟻群算法的綜合搜索能力進行了優化。修改后的ACS算法在收斂速度和局部搜索能力上顯著提升，但也增加了陷入局部最優解的可能性。隨機信息素平均策略幫助算法有效地規避局部最優，提升算法的全局搜索能力；自適應信息素擾動策略作為補充，進一步增強了算法跳出局部最優解的能力以及全局搜索能力；而動態比例信息素矩陣重置策略在進一步改善算法規避局部最優能力的基礎上，確保了信息素資源的高效利用，使算法的全局和局部搜索能力達到平衡，從而提升了算法在大規模TSP中的綜合搜索能力，并加速了算法收斂速度。總算法偽代碼如下：

a）初始化參數，計算節點間距離；

b）首先將節點按照貪婪算法求的路徑長度， tau0 為1/貪婪路徑長度。

c）進行正常蟻群算法前，判斷 Flag_d 是否為1，若否，進入驟d），若是，進入步驟e）。

d）螞蟻根據正常的信息素矩陣生成解和局部整體更新，其中最優解進行 2-opt 優化得到 L_lb 。在第一次迭代時的 L_gb 設置為 L_rb ，作為比例信息素矩陣重置策略的參數。

e）根據式（8）得出A，根據式（7）得到pheromoneMatrixp。螞蟻根據pheromoneMatrix，生成解，但不進行局部整體更新，其中最優解進行也2-opt 優化得到 L_lb 。

f）每次迭代后，都將 L_lb 與 L_gb 進行比較，如果 L_lb 小于 L_gb ，就將countl清零， .L_lb 賦值給 L_gb ;否則，countl加 1 但當 Flag_d 為1時，無論L_lb 與 L_gb 比較情況如何，countl都加1。

g） 進行全局信息素更新。

h）將更新后的 L_gb 與 L_rb×（1-γ） 進行比較，如果 L_gb 小于 L_rb× （1-γ） ，將 L_rb 設置為當前的 L_gb，Flag_r 記為1，否則，不會產生任何效果。之后執行步驟i）。

i）將 count1與 covavm 進行比較，若 count1=COUNT1 ，先將 Flag_d 設為0，再看 Flag_r 是否為1，若為1，進入步驟j），若不為1，進入步驟k）。

j）根據 tau0 的 η 倍進行劃分，高于其值的重置為 tau0×count2 ，低于其值的為tauO的一半，得出新pheromoneMatrix; count2=count2+1 后執行步驟 k ）；

k）判斷count3是否為COUNT3的倍數，如果不是，進入步驟1），若是，進人步驟 ?_m ）；

1）根據閾值 θ 隨機選擇節點的信息素進行平均，得出新phero-moneMatrix;count1置為0，count3加1。執行步驟m）

m）設置 Flag_p 為1，count1置為 0 執行步驟 m ；

n）判斷是否達到最大迭代次數 N_max ;若是，則進入步驟o），否則，返回步驟c）。o）輸出全局最優解。

3 實驗分析

該算法使用MATLAB2022b進行代碼編寫和仿真。為了驗證UMACO算法的有效性，選取了TSPLIB數據庫中不同規模的數據集對算法性能進行了評估。

3.1實驗參數設置

該算法使用文獻[28]的公共參數，使ACS最終獲得了較為理想的整體優化結果，如表1所示。后續的仿真實驗中，保持公共參數不變。

3.1.1隨機平均信息素矩陣策略中參數 θ 和COUNT1的確定

本節通過實驗仿真確定了 θ 和COUNT1的最優取值，以期獲得更加優質的解。為了綜合評估不同組合設置對算法性能的影響，本文采用了平均值（AVG）標準方差（SD）最優解（ ∣L_best? 和迭代次數（CT）四個指標。對這四個指標進行歸一化處理，并根據各指標的重要性分配權重，從而計算出一個綜合性能分數（score），該分數越小，表示算法性能越優。具體計算公式如式（11）所示。

score=AVG×w₁+SD×w₂+L_best×w₃+CT×w₄

其中：權重因子 w₁=0.4，w₂=0.3，w₃=0.2，w₄=0.1， 0

選取規模不同的3組TSP數據集eil51 ΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩ 和 tsp225 進行15次仿真實驗來對參數設置進行選取（下文中的實驗次數皆為15次）。通過表2設置 θ 與 covarm 的不同組合方案。圖2展示了不同方案針對不同數據集時，所對應的綜合性能分數的變化情況，其中三個軸分別表示參數值 θ 參數值COUNT1和綜合性能分數（score）。

從整體來看，當 θ 值一致時，COUNT1取值為10較為合適。在三個數據集的綜合性能分數中，隨著COUNT1從50逐漸減小至10，綜合性能分數呈下降趨勢。對于COUNT1取值為10，為了平衡不同規模的數據集，選擇 θ=0.2 作為合適的參數。對于小規模數據集eil51，當 θ 設為0.3時，綜合性能分數最小，這主要是因為較大的擾動有助于跳出局部最優解，并且小規模數據集能迅速收斂。對于中大型數據集 ch150 和tsp225，θ=0.2 時表現最佳，說明該擾動程度適合中大規模數據集。而對于更大規模的數據集， 數據集中有趨勢表明最優參數趨向于 θ=0.1 。

3.1.2動態比例信息素矩陣重置策略中參數 γ 和 η 的確定

本節選取eil76、kroB150和 pr299 規模不同的TSP數據集進行仿真實驗來對γ和 η 進行設置。通過表3設置 γ 和 η 的不同組合方案。圖3展示了不同方案針對不同數據集時，所對應的綜合性能分數的變化情況，其中三個軸分別表示參數值γ、η 和綜合性能分數（score）。

從圖中可明顯看出 γ 取值為 0.006，η 取值 2/3 為最優設置。當 γ=0.003 時，動態比例重置策略過早觸發，導致算法在充分優化前陷入局部最優，無論 η 的取值如何，綜合性能分數（score）變化幅度較小且表現不佳。當 γ=0.006 或0.009時，η=2/3 能在全局搜索與局部搜索之間實現良好的平衡，既為次優解提供探索機會，又避免選擇較差解，使綜合性能分數（score）達到最優。而當 η=1 時，次優解的探索能力受限，導致綜合性能分數（score）降低；當 η=1/2 時，較差解的納入增大了計算成本并減緩收斂速度，進一步影響性能。當 γ= 0.009時，由于觸發條件較嚴格，策略難以充分發揮作用，綜合性能分數（score）表現較差。

3.1.3自適應信息素擾動策略中參數COUNT3的確定

本節選取規模不同的三組TSP數據集kroA100、kroB200和 a280 進行仿真實驗來對參數設置進行選取。表4展示COUNT3取不同值時所對應的性能。其中算法最小誤差率的計算式為

Mr=（L_best-BKS）/BKS×100%

其中： L_best 為算法得到的最優解；BKS為TSPLIB標準最優解。

如表4所示，從整體表現來看，當COUNT3的取值為10時，平均解、標準差及誤差率均為最低。盡管該取值下的迭代次數未必能達到最優，但從所需平均值和標準差最小化為主要目標來看，1O為COUNT3的最優設置。

3.2UMACO改進策略的有效性分析

為了驗證該算法三種信息素矩陣優化策略的有效性，將這三種策略（隨機平均信息素矩陣策略、自適應信息素矩陣擾動機制和動態比例信息素矩陣重置策略）分別組合成四種不同的優化方案進行實驗仿真。選取rat99、kroA150和 lin318 這三個不同規模的數據集分別按照表5的四種方案各自進行仿真實驗，實驗結果如表6所示。

由表6分析可知，方案D在平均解、標準方差和最優解上均優于其他三個方案。在迭代次數方面，方案C在kroA150和lin318 數據集上表現更優，但主要是由于過早陷人局部最優導致的。方案A通過包含動態比例信息素矩陣重置策略，能夠在獲得較好結果的同時，表現出較小的標準方差和較少的迭代次數。然而，在小規模數據集rat99上，動態比例信息素矩陣重置策略的效果有限，難以充分發揮其優勢。且由于缺乏自適應信息素擾動機制，在大規模數據集 lin318 上最優解表現較差。相比之下，方案B由于引入了自適應信息素擾動機制，在此類小規模數據集上表現出更低的標準方差，但由于缺乏動態比例信息素矩陣重置策略，收斂速度較慢且標準差較大，隨著數據集規模的增加，平均解質量逐漸下降。方案C僅包含保持和擾動功能，未引入隨機信息素平均機制，所以其求解效率較低，整體性能較弱，表現不如其他方案。

3.3 UMACO與其他算法相比

3.3.1 UMACO與經典蟻群算法 ACS+2 -opt算法相比

選取不同的TSP數據集，將改進算法UMACO與經典蟻群算法 ACS+2-opt 的實驗結果進行比較分析。性能對比結果如表7所示。多樣性對比如圖4＼～6中（a）所示。收斂性如圖4＼～6中（b）所示。穩定性如圖6所示。

表7UMACO與經典算法 ACS+2-opt 算法

在不同數據集下的性能對比

從表7的結果可見，對于小規模數據集，經典算法ACS結合2-opt策略已能較好地接近最優解，而改進算法UMACO不僅能確保找到最優解，且迭代次數明顯減少，其優越性得益于自適應信息素平均機制和自適應擾動策略，有效避免了局部最優，提升了算法的全局搜索能力。對于中規模數據集，ACS僅依賴2-opt時精度較難保持，而UMACO除kroB200數據集誤差率都能控制在 0.1% 左右。對于大規模數據集，UMACO在平均解和標準方差方面表現出優勢，誤差率除 lin318 和u724數據集已降至 1% 左右。盡管在部分數據集如lin318和fl417上，UMACO的迭代次數稍高，但這主要是由于其動態比例信息素矩陣重置策略有效避免，經典算法ACS結合2-opt策略所陷入的局部最優，進一步說明動態比例信息素矩陣重置策略在大規模數據集上的作用。

為了更加全面地驗證UMACO算法的性能，從算法的收斂性和多樣性進行分析，分別選取kroA150、 a280 和fl417不同規模的數據集，分別給出它們的多樣性折線圖和收斂曲線圖，多樣性為每次迭代中種群間的方差表示。

通過分析其在圖4～6所示，UMACO在中大型數據集（kroA150和 a280 ）上比經典算法 ACS+2 -opt具有更高的多樣性和更快的收斂速度。特別是在 a280 數據集中，UMACO避免了經典算法 ACS+2 -opt的明顯下降趨勢，得益于其隨機平均信息素矩陣策略和自適應信息矩陣擾動策略。雖然UMACO在初期收斂較弱，但其動態比例信息素矩陣重置策略幫助其在總體收斂速度上優于 ACS+2-opt ，從而能夠更容易找到較優解。在超大型數據集fI417中，UMACO憑借多樣性和引導性的平衡，超越了 ACS+2 -opt的性能。其動態比例信息素矩陣重置策略通過鎖定更優的信息素矩陣，適度降低多樣性，避免過高多樣性帶來的負面影響，同時增強引導性，確保朝最優解方向進行搜索，使其在超大規模數據集中更有效地跳出局部最優。相比之下，盡管 ACS+2-opt 擁有較高多樣性，但缺乏足夠的引導性，導致其難以跳出局部最優，找到更優解。綜合來看，UMACO在多樣性和引導性之間取得了更好的適配性，實現了優異的收斂性。

圖7展示了兩種算法在15個實驗數據集上的穩定性分析結果，其中平均誤差率表示算法求解結果與標準最優解之間的誤差比率。平均誤差率越小，表明算法的平均解越接近標準最優解，算法的穩定性越強。從實驗結果可以看出，UMACO在求解不同規模的TSP時，平均誤差率始終低于經典算法 ACS+ 2-opt，證明其有更強的穩定性。特別是在節點數量小于300的情況下，改進后的UMACO將誤差率穩定控制在 1.3% 以內；在解決除 u724 數據集以外的大規模節點問題時，誤差率也能保持在 2.2% 以內。總體而言，UMACO在平均解質量和穩定性方面表現突出，且在各項性能指標上均優于經典算法 ACS+ 2-opt。

3.3.2與最新改進智能算法的對比

為了進一步驗證算法性能，將UMACO與其他最新改進算法進行對比，對比數據取自其他改進蟻群算法ENCACO[28]LFACO[29]、ICACO[30]和CEACO[31]以及其他類型的智能改進算法 HICA^[32] 、GA-SAC[33] .GPGA^[34] 和 DLSO^[35] 。以上算法均為近年來發表的改進智能算法，在求解TSP問題中表現出良好的性能，對比結果如表8所示。在10個標準數據集上，將UMACO與8種不同算法進行對比分析。其中平均解（AVG）為15次算法的出的路徑長度的平均值，最優解（ （L_best） 為15次算法得出的最優值，這兩個值都是越小越優。平均值越優說明算法可靠性越強，實用性越高；最優解越優說明算法綜合搜索能力越強，越能接近理論最短路徑。在平均解方面，UMACO在10個標準數據集中有7個數據集排名前二；而在最優解表現方面，UMACO在6個數據集中表現最優，所以在這9個不同的算法中，UMACO整體表現出最優的實用價值和理論價值。

3.3.3算法復雜度分析

表9中 n 為節點數； m 為螞蟻總數； N_max 為最大迭代次數。通過表9可知，UMACO的時間復雜度為 O（N_max×n²×m+ N_max×n³ ），由此可知隨機平均信息素矩陣策略、動態比例信息素矩陣重置策略以及自適應信息素矩陣擾動策略沒有額外增加算法復雜度，且只對最優螞蟻進行2-opt優化避免出現復雜度為 O（N_max×n³×m） 的情況。

4結束語

針對蟻群算法在求解面向城市建模的TSP收斂速度慢以及易陷入局部最優等問題，提出面向城市建模的優化蟻群算法（UMACO）。通過整體性的局部信息素更新加速收斂，修改局部信息素更新規則提升最優路徑選擇概率，并應用2-opt策略優化路徑。此外，采用隨機信息素平均策略防止停滯，自適應信息素擾動機制跳出局部最優，最終回歸原信息素矩陣。動態比例信息素矩陣重置策略在全局最優路徑低于歷史最優值時啟動，保持信息素的有效性。三種信息素矩陣優化策略協同作用，平衡收斂速度與解的多樣性。

通過仿真結果可見，UMACO在誤差率、平均解、標準差及找到更優解的迭代次數方面均優于經典算法 ACS+2-opt ，表現出更為顯著的優化效果。尤其善于解決需要更好平均解和標準方差的TSP，如城市建模素材獲取中的TSP。與其他最新改進算法相比，UMACO在平均解方面，對于大部分數據集均有一定領先。進一步證明了UMACO在解決TSP中的卓越潛力和優勢。下一步將嘗試引人動態參數調節機制，以優化算法在不同規模TSP中的適應能力，并進一步將算法應用于無人機城市建模過程中素材采集的路徑規劃任務，以驗證其在實際場景中的有效性與應用價值。

參考文獻：

[1］張源．城市三維地質建模方法研究［J]．礦山測量，2021，49 （1）： 65-68，88.（Zhang Yuan. Research on urban 3D geological modeling method[J].Mine Surveying，2021，49（1）：65-68， 88.）

[2]馮增文，李珂，李梓豪，等．低空無人機的傾斜攝影測量技術在 城市軌道交通建設中的應用［J]．測繪通報，2020（9）：42-45. （FengZengwen，LiKe，Li Zihao，etal.Theapplicationofoblique photography technologybased on low-altitude UAVinurbanrail transit construction[J]．Bulletin of Surveying and Mapping，2020 （9）： 42-45.）

[3]，劉斌，唐雅玲，馬晨燕，等．無人機傾斜攝影三維模型在城市雨 洪風險評估中的應用［J]．測繪通報，2019（10）：46-50，66. （Liu Bin，Tang Yaling，Ma Chenyan，et al．Application of 3D modelingof UAV tiltphotography in urban rain flood risk assessment [J].Bulletin of Surveying and Mapping，2019（10）：46-50， 66.）

[4］李存文，肖天豪，呂寶奇．人工建模技術在地鐵三維圖中的應用 [J]．地理空間信息，2021，19（3）：92-95，8.（LiCunwen，Xiao Tianhao，Lyu Baoqi.Research on application of artificial modeling technologyin 3Dmap of subway[J].Geospatial Information， 2021，19（3）：92-95，8.）

[5]Reinelt G. The traveling salesman：computational solutions for TSP applications[M].Berlin：Springer，2003.

[6]SmithN，MoehrleN，GoeseleM，etal.Aerial path planningfor urban scene reconstruction：a continuous optimization method and benchmark[J].ACMTrans on Graphics，2018，37（6）：183.

[7]Zhang Han，Yao Yucong，Xie Ke，et al.Continuous aerial path planning for 3D urban scene reconstruction[J].ACM Trans on Graphics，2021，40（6）：225.

[8]Sui Haigang，ZhangHao，Gou Guohua，et al.Multi-UAVcooperative and continuous path planning for high-resolution 3D scene reconstruction[J].Drones，2023，7（9）：544.

[9]Laporte G. The traveling salesman problem：an overview of exact and approximate algorithms [J]. European Journal of Operational Research，1992，59（2）：231-247.

[10]Toaza B，Esztergár-Kiss D.A review of metaheuristic algorithms for solving TSP-based scheduling optimization problems image 1[J]. Applied Soft Computing，2023，148：110908.

[11]Gomes D E， Iglésias M ID，Proenéa A P，et al. Applying a genetic algorithm to a m-TSP：case study of a decision support system for optimizinga beverage logisticsvehicles routing problem[J].Electronics，2021，10（18）： 2298.

[12]Hsu HP.Printed circuit board assemblyplanning for multi-head gantry SMT machine using multi-swarm and discrete firefly algorithm [J].IEEE Access，2020，9：1642-1654.

[13]Dash Y. Nature inspired routing in mobile ad hoc network [C]//Proc of the 3rd International Conference on Advances in Computing，Communication Control and Networking.Piscataway，NJ：IEEE Press， 2021：1299-1303.

[14] Styutzle T，Dorigo M. ACO algorithms for the traveling salesman problem[J].Evolutionary Algorithms in Engineering and Computer Science，1999，4：163-183.

[15]Skinderowicz R. Improving ant colony optimization eficiency for solving large TSP instances [J]. Applied Soft Computing，2022， 120：108653.

[16]Dorigo M，Stutzle T.Ant colony optimization：overview and recent advances[M]//Gendreau M，PotrinJY.Handbook of Metaheuristics.Cham：Springer，2018：311-351.

[17]Rokbani N，Kromer P，TwirI，et al. A new hybrid gravitational particle swarm optimisation-ACO with local search mechanism，PSOGSAACO-Ls for TSP[J]. International Journal of Intelligent Engineering lnformatics，2019，7（4）：384-398.

[18]Dewantoro R W，Sihombing P. The combination of ant colony optimization（ACO）and Tabu search（TS）algorithm to solve the traveling salesman problem（TSP）[C]//Proc of the 3rd International Conference on Electrical，Telecommunication and Computer Engineering. Piscataway，NJ： IEEE Press，2019：160-164.

[19]Omar AH，Naim AA.New crossover via hybrid ant colony system with genetic algorithm and making study of different crossover for TSP [J].Journal of Theoretical and Applied Information Technology，2021，99（20）：4824-4836.

[20]Farisi O IR，Setiyono B，Danandjojo RI.A hybrid approach to multi-depot multiple traveling salesman problembased on firefly algorithm and ant colony optimization[J]. IAES International Journal of Artificial Intelligence，2021，10（4）：910.

[21]Dai Zhuo，Ma Qian，Zhao Dongdong，et al.Anovel hybrid optimization algorithmcombined with BBO and ACO[C]//Proc of the 39th Chinese Control Conference.Piscataway，NJ：IEEE Press，2020： 1581-1586.

[22]Ebadinezhad S. DEACO：adopting dynamic evaporation strategy to enhance ACO algorithm for the traveling salesman problem[J].EngineeringApplicationsofArtificialIntelligence，2020，92： 103649.

[23]Gao Wei. New ant colony optimization algorithm for the traveling salesman problem[J]. International Journal of Computational Intelligence Systems，2020，13（1）：44-55.

[24]Li Wei，Wang Cancan，Huang Ying，et al.Heuristic smoothing ant colony optimization with differential information for the traveling salesman problem[J].Applied Soft Computing，2023，133：109943.

[25]Shahadat ASB，AkhandMAH，Kamal MA S. Visibility adaptationinantcolony optimization for solving traveling salesman problem [26]Liu Huijun，Lee A，Lee Wenshi，et al.DAACO：adaptive dynamic quantity of ant ACO algorithm to solve the traveling salesman problem [J].Complexamp; Intelligent Systems，2023，9（4）：4317-4330. [27]Tang Kezong，Wei Xiongfei， Jiang Yuanhao，et al. Anadaptive ant colony optimization for solving large-scale traveling salesman problem [J].Mathematics，2023，11（21）：4439. [28］王育潔，游曉明，劉升．結合評估獎懲機制和鄰域動態退化的協 同蟻群算法[J]．系統仿真學報，2024，36（6）：1475-1492. （Wang Yujie，You Xiaoming，Liu Sheng. Cooperative ant colony algorithm combining evaluation reward and punishment mechanism and neighborhood dynamic degradation[J]. Journal of System Simulation，2024，36（6）：1475-1492.） [29]丁增良，陳玨，邱禧荷．一種應用于旅行商問題的萊維飛行轉移 規則蟻群優化算法［J]．計算機應用研究，2024，41（5）：1420-

1427.（Ding Zengliang，Chen Jue，Qiu Xihe.Ant colony optimization algorithm based onLevy flight transfer rule for solving traveling salesman problem [J]. Application Research of Computers，

2024，41（5）：1420-1427.） [30］禹博文，游曉明，劉升．引入動態分化和鄰域誘導機制的雙蟻群 優化算法［J]．計算機應用研究，2023，40（10）：3000-3006. （YuBowen，You Xiaoming，Liu Sheng.Dual-ant colony optimization algorithmwith dynamic diffrentiation and neighborhood induction mechanism[J].Application Research of Computers，2023，40 （10）：3000-3006.） [31］馮晨，游曉明，劉升．結合競爭交互策略和淘汰重組機制的異構 多蟻群算法［J]．系統仿真學報，2024，36（1）：232-248.（Feng Chen，You Xiaoming，Liu Sheng.Heterogeneous multi-ant colony algorithmcombining competitiveinteractionstrategyand eliminatingreconstructing mechanism [J]. Journal of System Simulation，

2024，36（1）：232-248.） [32]裴小兵，于秀燕，王尚磊．混合帝國競爭算法求解旅行商問題 [J]．浙江大學學報：工學版，2019，53（10）：2003-2012.（Pei Xiaobing，Yu Xiuyan，Wang Shanglei. Solution of traveling salesman problem by hybrid imperialist competitive algorithm[J].Journal of Zhejiang University：Engineering Science，2019，53（10）：

2003-2012.） [33]陳斌，劉衛國．基于SAC模型的改進遺傳算法求解TSP問題 [J]．計算機科學與探索，2021，15（9）：1680-1693．（Chen Bin， Liu Weiguo.SAC model based improved genetic algorithm for solving TSP[J].Journal of Frontiers of Computer Science and Technology，2021，15（9）：1680-1693.） [34]王永，呂致為．基于基因庫求解旅行商問題的遺傳算法［J]．計 算機應用研究，2023，40（11）：3262-3268．（WangYong，Lyu Zhiwei.Novel genetic algorithm basedongenes pool for traveling salesman problem [J]. Application Research of Computers，

2023，40（11） ：3262-3268.） [35]Zhang Daoqing，Jiang Mingyan. Parallel discrete lion swarm optimizationalgorithm for solving traveling salesman problem[J].Journal of Systems Engineering and Electronics，2020，31（4）： 751-760.