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 引言

隨著城市場景豐富和城市系統(tǒng)擴大，城市管理進人新階段。城市模型在規(guī)劃設(shè)計[1]、交通管理[2]和應(yīng)急管理[3]等領(lǐng)域發(fā)揮重要作用，作為數(shù)字化城市的視覺表現(xiàn)。其通過模擬城市空間、結(jié)構(gòu)和功能，為決策者提供關(guān)鍵信息和可視化參考。

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

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

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

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

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

1 蟻群系統(tǒng)（ACS）

1.1 路徑構(gòu)建規(guī)則

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

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

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

1.2信息素更新規(guī)則

1）局部信息素更新

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

其中：δ為局部信息素?fù)]發(fā)系數(shù)，取值為 [0，1];τ₀ 為初始信息素濃度。

2）全局信息素更新

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

其中 _：ρ 為全局信息素?fù)]發(fā)因子； Δτ_ij 為最優(yōu)路徑上的信息素增量； L_gb 為全局最優(yōu)路徑的長度。

1.3 局限性

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

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

原因2對于大規(guī)模TSP，往往會出現(xiàn)即便算法對數(shù)據(jù)集優(yōu)化不足，信息素卻已過早積累，進而陷入局部最優(yōu)解[27]

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

2 UMACO描述

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

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

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

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

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

為了減少本文1.3節(jié)中的原因1導(dǎo)致的局部最優(yōu)問題，本文設(shè)計了一種新的信息素矩陣平均策略即隨機平均信息素矩陣策略。

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

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

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

2.2動態(tài)比例信息素矩陣重置策略

為了減少本文1.3節(jié)中的原因2導(dǎo)致的局部最優(yōu)問題，本文設(shè)計了一種新的信息素矩陣重置策略即動態(tài)比例信息素矩陣重置策略。

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

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

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

2.3自適應(yīng)信息素矩陣擾動策略

為了減少本文1.3節(jié)中的原因3導(dǎo)致的局部最優(yōu)問題，提出了自適應(yīng)信息素矩陣擾動機制。

該策略的設(shè)計思想為：在算法經(jīng)過COUNT3倍數(shù)次平均策略仍未跳出局部最優(yōu)時啟動（其中COUNT3將在3.1.3節(jié)中詳細(xì)闡述）。根據(jù)式（7），通過現(xiàn)有信息素矩陣生成擾動信息素矩陣。其中參數(shù) A 是參考河馬算法中的擾動規(guī)則所提出的算子，推導(dǎo)過程如式（8）＼～（10）所示。

pheromoneMatrix_p=A×pheromoneMatrix

A=M×C+1

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

C=rand（numberOfCities，numberOfCities-1）

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

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

2.4 UMACO流程

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

a）初始化參數(shù)，計算節(jié)點間距離；

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

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

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

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

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

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

h）將更新后的 L_gb 與 L_rb×（1-γ） 進行比較，如果 L_gb 小于 L_rb× （1-γ） ，將 L_rb 設(shè)置為當(dāng)前的 L_gb，F(xiàn)lag_r 記為1，否則，不會產(chǎn)生任何效果。之后執(zhí)行步驟i）。

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

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

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

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

m）設(shè)置 Flag_p 為1，count1置為 0 執(zhí)行步驟 m ；

n）判斷是否達(dá)到最大迭代次數(shù) N_max ;若是，則進入步驟o），否則，返回步驟c）。o）輸出全局最優(yōu)解。

3 實驗分析

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

3.1實驗參數(shù)設(shè)置

該算法使用文獻(xiàn)[28]的公共參數(shù)，使ACS最終獲得了較為理想的整體優(yōu)化結(jié)果，如表1所示。后續(xù)的仿真實驗中，保持公共參數(shù)不變。

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

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

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

其中：權(quán)重因子 w₁=0.4，w₂=0.3，w₃=0.2，w₄=0.1， 0

選取規(guī)模不同的3組TSP數(shù)據(jù)集eil51 ΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩ 和 tsp225 進行15次仿真實驗來對參數(shù)設(shè)置進行選?。ㄏ挛闹械膶嶒灤螖?shù)皆為15次）。通過表2設(shè)置 θ 與 covarm 的不同組合方案。圖2展示了不同方案針對不同數(shù)據(jù)集時，所對應(yīng)的綜合性能分?jǐn)?shù)的變化情況，其中三個軸分別表示參數(shù)值 θ 參數(shù)值COUNT1和綜合性能分?jǐn)?shù)（score）。

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

3.1.2動態(tài)比例信息素矩陣重置策略中參數(shù) γ 和 η 的確定

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

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

3.1.3自適應(yīng)信息素擾動策略中參數(shù)COUNT3的確定

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

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

其中： L_best 為算法得到的最優(yōu)解；BKS為TSPLIB標(biāo)準(zhǔn)最優(yōu)解。

如表4所示，從整體表現(xiàn)來看，當(dāng)COUNT3的取值為10時，平均解、標(biāo)準(zhǔn)差及誤差率均為最低。盡管該取值下的迭代次數(shù)未必能達(dá)到最優(yōu)，但從所需平均值和標(biāo)準(zhǔn)差最小化為主要目標(biāo)來看，1O為COUNT3的最優(yōu)設(shè)置。

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

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

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

3.3 UMACO與其他算法相比

3.3.1 UMACO與經(jīng)典蟻群算法 ACS+2 -opt算法相比

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

表7UMACO與經(jīng)典算法 ACS+2-opt 算法

在不同數(shù)據(jù)集下的性能對比

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

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

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

圖7展示了兩種算法在15個實驗數(shù)據(jù)集上的穩(wěn)定性分析結(jié)果，其中平均誤差率表示算法求解結(jié)果與標(biāo)準(zhǔn)最優(yōu)解之間的誤差比率。平均誤差率越小，表明算法的平均解越接近標(biāo)準(zhǔn)最優(yōu)解，算法的穩(wěn)定性越強。從實驗結(jié)果可以看出，UMACO在求解不同規(guī)模的TSP時，平均誤差率始終低于經(jīng)典算法 ACS+ 2-opt，證明其有更強的穩(wěn)定性。特別是在節(jié)點數(shù)量小于300的情況下，改進后的UMACO將誤差率穩(wěn)定控制在 1.3% 以內(nèi)；在解決除 u724 數(shù)據(jù)集以外的大規(guī)模節(jié)點問題時，誤差率也能保持在 2.2% 以內(nèi)?？傮w而言，UMACO在平均解質(zhì)量和穩(wěn)定性方面表現(xiàn)突出，且在各項性能指標(biāo)上均優(yōu)于經(jīng)典算法 ACS+ 2-opt。

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

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

3.3.3算法復(fù)雜度分析

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

4結(jié)束語

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

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

參考文獻(xiàn)：

[1］張源．城市三維地質(zhì)建模方法研究［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]馮增文，李珂，李梓豪，等．低空無人機的傾斜攝影測量技術(shù)在 城市軌道交通建設(shè)中的應(yīng)用［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]，劉斌，唐雅玲，馬晨燕，等．無人機傾斜攝影三維模型在城市雨 洪風(fēng)險評估中的應(yīng)用［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］李存文，肖天豪，呂寶奇．人工建模技術(shù)在地鐵三維圖中的應(yīng)用 [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］王育潔，游曉明，劉升．結(jié)合評估獎懲機制和鄰域動態(tài)退化的協(xié) 同蟻群算法[J]．系統(tǒng)仿真學(xué)報，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]丁增良，陳玨，邱禧荷．一種應(yīng)用于旅行商問題的萊維飛行轉(zhuǎn)移 規(guī)則蟻群優(yōu)化算法［J]．計算機應(yīng)用研究，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］禹博文，游曉明，劉升．引入動態(tài)分化和鄰域誘導(dǎo)機制的雙蟻群 優(yōu)化算法［J]．計算機應(yīng)用研究，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］馮晨，游曉明，劉升．結(jié)合競爭交互策略和淘汰重組機制的異構(gòu) 多蟻群算法［J]．系統(tǒng)仿真學(xué)報，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]．浙江大學(xué)學(xué)報：工學(xué)版，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]陳斌，劉衛(wèi)國．基于SAC模型的改進遺傳算法求解TSP問題 [J]．計算機科學(xué)與探索，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]．計 算機應(yīng)用研究，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.