求解旅行商問題的人工協(xié)同搜索算法

徐小平，唐陽麗*，王峰

求解旅行商問題的人工協(xié)同搜索算法

徐小平1，唐陽麗1*，王峰2

（1.西安理工大學 理學院，西安 710054； 2.西安交通大學數(shù)學與統(tǒng)計學院，西安 710049）（*通信作者電子郵箱2461333692@qq.com）

針對傳統(tǒng)人工協(xié)同搜索（ACS）算法求解精度不高、收斂速度慢等問題，提出一種基于Sigmoid函數(shù)的反向人工協(xié)同搜索（SQACS）算法求解旅行商問題（TSP）。首先，利用Sigmoid函數(shù)構(gòu)造比例因子，增強算法的全局搜索能力；其次，在變異階段，加入差分進化（DE）算法的DE/rand/1變異策略，對當前種群進行二次變異，提高算法的計算精度和種群的多樣性；最后，在算法后期的開發(fā)階段，引入擬反向?qū)W習策略，進一步提高解的質(zhì)量。對TSP測試庫TSPLIB中的4個實例進行仿真實驗，結(jié)果顯示，SQACS算法在最短路徑與花費時間上均優(yōu)于麻雀搜索算法（SSA）、DE、阿基米德算法（AOA）等7種對比算法，并且具有良好的魯棒性；與其他求解TSP的改進算法綜合對比，SQACS算法也顯示了良好的性能。實驗結(jié)果表明，SQACS算法在求解小規(guī)模TSP時是有效的。

人工協(xié)同搜索算法；旅行商問題；Sigmoid函數(shù)；差分進化；擬反向?qū)W習

0 引言

旅行商問題（Traveling Salesman Problem， TSP）又稱推銷員問題、貨郎擔問題。它是基本的線路問題，也是典型的NP難問題和典型的組合優(yōu)化問題，是數(shù)學領(lǐng)域中非常有名的問題之一［1-2］。TSP自提出后就引起了運籌學、物流科學、應(yīng)用數(shù)學、計算機應(yīng)用、圈論與網(wǎng)絡(luò)分析、組合數(shù)學等學科的學者及管理者的極大重視，成了運籌學與組合優(yōu)化領(lǐng)域的研究熱點［3］。近年來，許多學者對TSP進行了研究，如葛海明［4］基于對原始數(shù)據(jù)進行域規(guī)則的數(shù)據(jù)預(yù)處理，提出了一種對傳統(tǒng)路徑編碼并改進各算子的遺傳算法，然后將區(qū)域化遺傳算法用于求解TSP，結(jié)果顯示所提算法有較為明顯的收斂效果。何慶等［5］對遺傳算法部分中的適應(yīng)度函數(shù)、交叉變異算子進行改進，并根據(jù)舊種群和新種群每個對應(yīng)個體的進化程度提出一種改進自適應(yīng)的Metropolis準則，使模擬退火算法部分的染色體跳變更具有自適應(yīng)性。最后將改進算法用于求解TSP的7個實例，結(jié)果表明改進算法更優(yōu)。戚遠航等［6］通過采用整數(shù)編碼的路徑表示方法來表示TSP的解，對爆炸算子、高斯變異算子進行離散化操作策略設(shè)計；并提出了一種帶固定半徑近鄰搜索3-opt的離散煙花算法解決TSP，驗證了改進算法在全局收斂能力、收斂精度、求解時間和穩(wěn)定性等方面均優(yōu)于傳統(tǒng)煙花算法。湯雅連等［7］通過3-opt策略提高蟻群優(yōu)化算法的局部搜索能力，并對3個實例進行仿真，結(jié)果表明該改進策略在求解小規(guī)模TSP時具有優(yōu)勢。陳科勝等［8］提出了一種求解TSP的自適應(yīng)升溫模擬退火算法，通過6個實例對改進算法全局尋優(yōu)效果進行測試的結(jié)果表明，改進后的算法具有全局尋優(yōu)能力、泛化強等特點。唐天兵等［9］利用量子比特、態(tài)疊加和量子干涉等量子概念，在人工蜂群算法的基礎(chǔ)上加入量子表示的解，提出了一種基于量子激勵的人工蜂群算法，求解6個TSP實例的測試結(jié)果表明，該算法性能較好。也有學者將TSP進行拓展，提出了概率旅行商問題［10］、單商品取送貨旅行商問題［11］、對稱旅行商問題［12］等。TSP的應(yīng)用非常廣泛，如互聯(lián)網(wǎng)環(huán)境、道路交通以及物流運輸?shù)龋?3］；但是，目前還沒有有效的方法解決此問題，因此對TSP的研究具有重要的理論價值和實際意義。

近年來，智能優(yōu)化算法因為參數(shù)少、結(jié)構(gòu)簡單、易實現(xiàn)而受到廣大學者的青睞，提出了麻雀搜索算法（Sparrow Search Algorithm， SSA）［14］、差分進化（Differential Evolution， DE）算法［15］、雜草優(yōu)化（Invasive Weed Optimization， IWO）算法［16］、阿基米德優(yōu)化算法（Archimedes Optimization Algorithm， AOA）［17］、人工協(xié)同搜索（Artificial Cooperative Search，ACS）算法［18］等優(yōu)化算法。其中ACS算法是一種用于求解數(shù)值優(yōu)化問題的算法，它是為了模擬在同一自然棲息地中生存的兩個具有捕食與被捕食關(guān)系的生物之間的相互作用和合作過程而提出的。在自然界，一個地區(qū)能找到的食物量對氣候變化非常敏感，因此，自然界中的許多物種都會發(fā)生遷徙行為，尋找并遷移到更高產(chǎn)的飼養(yǎng)區(qū)。ACS算法包括捕食者（predator）選擇、獵物（prey）選擇、變異和交叉等過程，先隨機產(chǎn)生捕食者種群位置，設(shè)置捕食者位置內(nèi)存，再隨機產(chǎn)生獵物種群位置，對獵物位置進行重新排序。在變異階段產(chǎn)生生物相互作用的位置。最后，進入交叉階段，通過捕食者種群中的活躍個體更新生物相互作用位置。與其他優(yōu)化算法相比，ACS算法具有控制參數(shù)少、魯棒性強等優(yōu)點，并且采用了不同的變異和交叉策略。目前，ACS算法已經(jīng)被用于解決調(diào)度問題、設(shè)計問題等各種實際問題［19-20］。這些算法雖然解決了一些實際問題，但仍存在算法收斂速度慢、精度低等不足，有進一步的改進空間。為此，本文提出了基于Sigmoid函數(shù)的反向人工協(xié)同搜索（Quasi opposition Artificial Cooperative Search algorithm based on Sigmoid function， SQACS）算法，即利用Sigmoid函數(shù)構(gòu)造比例因子后，在變異階段加入DE算法的DE/rand/1變異策略，并在算法后期的開發(fā)階段引入擬反向?qū)W習策略。最后利用TSP測試庫TSPLIB中的實例進行仿真實驗，結(jié)果表明，本文算法是可行的。

1 ACS算法

1.1 基本ACS算法

ACS算法是一種基于雙種群的全局搜索算法，用于求解數(shù)值優(yōu)化問題。該算法基于兩個人工生物之間的生物相互作用，求出當前優(yōu)化問題的全局最小值。任何具有智能的個體組成的群體，其行為在本質(zhì)上類似于一個綜合系統(tǒng)，被稱為生物。在同一自然棲息地生存的兩種群居的生物之間存在著一種智能的生物相互作用。由于生物具有全社會行為，所以生物成員無法長期遠離生物生存。具有捕食者-獵物或寄生-宿主關(guān)系的生物之間存在著一種基于封閉主義的智能相互作用，這種生物間的相互作用形成了生物間的共同滅絕、共同進化或合作過程。ACS算法是為了模擬在同一自然棲息地中生存的兩個具有捕食與被捕食關(guān)系的生物之間的相互作用和合作過程而提出的。

ACS算法控制參數(shù)單一，算法性能對控制參數(shù)初始值不太敏感；此外，ACS算法利用了兩種先進的進化算子（交叉和變異）來實現(xiàn)探索與開發(fā)階段的平衡。在ACS算法的演化過程中，還提出了一種記憶過程，以幫助探索問題的搜索空間，并有助于開發(fā)更高質(zhì)量的解。

在ACS算法中，一個由相關(guān)問題的隨機解組成的生物對應(yīng)著一個遷徙到更多產(chǎn)區(qū)域的人工生物。人工捕食者亞生物可以在人工獵物亞生物向問題的全局最小值遷徙的一段時間內(nèi)跟蹤他們。當將ACS算法的迭代過程稱為協(xié)同進化過程時，可以看出兩個生物尋找相關(guān)問題的全局最小值時，彼此之間建立了一種基于互惠的生物關(guān)系。ACS算法的概率特性使得每一代被確定為捕食者或獵物的生物發(fā)生變化，因此，ACS算法為兩個生物提供了一個協(xié)同進化的過程。ACS算法包括種群初始化、捕食者選擇、獵物選擇、變異、交叉、更新選擇等階段。

1.2 SQACS算法

ACS算法在理論和實踐上都不夠成熟和完善，針對其收斂速度慢、精度不高、易陷入局部最優(yōu)等缺點，本文提出了基于Sigmoid函數(shù)的反向人工協(xié)同搜索算法（SQACS）。具體改進方案如下：

2）二次變異策略。加入DE算法的DE/rand/1變異策略對ACS算法變異階段產(chǎn)生的種群進行二次變異［15］。研究發(fā)現(xiàn)，DE算法中參數(shù)的高斯、隨機、線性或混沌變化可以有效地防止早熟收斂，所以將DE算法的DE/rand/1變異策略加到ACS變異之后，產(chǎn)生新的變異種群，進行下一步的交叉行為，可以使算法避免陷入局部最優(yōu)并且提高計算精度。二次變異公式如式（14）：

圖1 比例因子R變化曲線

Fig. 1 Change curve of scale factor R

3）擬反向?qū)W習策略。在算法后期的開發(fā)階段，算法容易陷入局部最優(yōu)，且種群間要尋找更優(yōu)的生物相互作用位置，因為位置的變化是隨機的，沒有規(guī)律可言，阻礙了算法在局部小區(qū)域搜索最優(yōu)解。為了克服以上缺點，引入擬反向?qū)W習策略來產(chǎn)生擬反向種群，增加了種群的多樣性，這樣生物能夠在鄰近小區(qū)間內(nèi)展開精細尋找相互作用位置的行為，避免跳過最優(yōu)解，然后從當前種群和擬反向種群進行貪婪選擇，從而有效地找到最優(yōu)解［22］。SQACS算法流程如圖2所示。

圖2 SQACS算法的流程

詳細過程如下：

擬反向解和當前解的選擇如式（17）：

2 利用SQACS算法求解TSP

2.1 TSP模型

2.2 求解步驟

利用SQACS求解路徑規(guī)劃時：生物相互作用位置表示可行路徑；生物相互作用位置變動表示路徑順序變動；作用位置的適應(yīng)度表示路徑長度。

步驟 2 計算種群中各個體的適應(yīng)度值。

步驟3 隨機選擇捕食者及獵物種群，然后對獵物種群位置進行重新隨機打亂排序。

步驟7 交叉。若活躍個體映射大于0，將路徑更新為捕食者位置，否則保持原位置不變。

步驟8 重新選擇捕食者和獵物種群。

步驟9 判斷是否滿足終止條件，若滿足，停止算法更新，輸出最優(yōu)位置和最優(yōu)函數(shù)值，即TSP的最短路線和最短的路徑值；否則返回步驟2。

2.3 實驗結(jié)果與分析

首先，為了驗證三種策略的有效性，對SQACS算法做相關(guān)的消融實驗，表1為加入各改進策略的實驗結(jié)果對比。S-ACS表示用Sigmoid函數(shù)構(gòu)造比例因子后的ACS算法，D-ACS表示加入了二次變異策略的ACS算法，Q-ACS表示加入了擬反向?qū)W習策略的ACS算法。

由表1可以看出，三種策略均對ACS算法有所改進，其中二次變異策略在最優(yōu)值與平均值這兩個指標上都取得了最優(yōu)的結(jié)果，顯示了二次變異策略在提高計算精度方面有較好的性能。而在計算時間方面，加入的擬方向?qū)W習策略則取得了最佳結(jié)果。由此顯示了三種改進策略在計算精度和計算時間上的有效性。

表1 SQACS算法消融實驗結(jié)果

其次，為了驗證SQACS算法性能，將SQACS算法與SSA［14］、DE［15］、IWO［16］、AOA［17］、ACS［18］、IACS1［23］和IACS2［24］（IACS1和IACS2為基本ACS算法的兩種改進算法）就解決TSPLIB標準數(shù)據(jù)庫中Oliver30、Att48、Eil51和Eil76這4個不同規(guī)模的TSP進行實驗測試。實驗設(shè)置最大評估次數(shù)為40 000，各算法的初始種群規(guī)模都為20。ACS算法中生物相互作用概率為0.10，IACS1和IACS2參數(shù)設(shè)置與ACS算法相同，其余算法參數(shù)設(shè)置見表2。

表2 算法參數(shù)設(shè)置

利用SQACS算法和其他七種算法分別進行30次求解后，其結(jié)果的最優(yōu)值、平均值和平均計算時間見表3。為方便比較，對最小值進行加粗表示，最優(yōu)值表示30次求解結(jié)果中旅行商訪問路徑的最短距離。通過對比各算法求解TSP的最優(yōu)值與平均值可知，SQACS算法求解這四個TSP在最小值與平均值上都能取得最優(yōu)的結(jié)果，而且最優(yōu)值與平均值相差最小，說明SQACS算法的穩(wěn)定性最好。

從計算時間的指標值對比來看，SQACS算法在四個數(shù)據(jù)集上的表現(xiàn)均優(yōu)于其他對比算法。由此可見，SQACS算法在求解小規(guī)模TSP時具有良好的可行性及魯棒性。

圖3為SQACS算法求解TSP中4組實例的最優(yōu)路徑圖。從圖3可以看出，除Att48數(shù)據(jù)集有一個路徑交叉點外，其他3個圖都是一個完全閉回路，路徑?jīng)]有交叉，因此所得到的路徑可行。得到的最優(yōu)路線的解分別為：

6→5→30→23→22→16→17→12→13→4→3→9→11→7→8→25→26→29→28→27→24→15→14→10→21→20→19→18→2→1→6；

2→29→34→41→16→22→3→40→9→1→8→38→31→44→18→7→28→36→30→6→37→19→27→17→43→20→33→46→15→12→11→23→14→25→13→47→21→39→32→48→5→42→10→24→45→35→26→4→2；

40→19→42→44→37→15→45→33→39→10→30→34→50→9→49→38→11→5→46→51→27→32→1→22→2→16→21→29→20→35→36→3→28→31→26→8→48→6→23→7→43→24→14→25→18→47→12→17→4→13→41→40；

9→39→72→58→10→38→65→56→11→53→14→59→19→54→13→27→52→34→46→8→35→7→26→67→76→75→4→45→29→5→15→57→37→20→70→60→74→36→69→21→47→48→30→2→68→6→51→17→12→40→32→44→3→16→63→33→73→62→28→74→61→22→1→43→41→42→64→56→23→49→24→18→50→25→55→31→9。

為進一步驗證SQACS算法的有效性，選取文獻［5-9］中算法對TSP中Oliver30、Att48、Eil51和Eil76這4個實例的求解結(jié)果進行對比，結(jié)果見表4。通過對比表4中的數(shù)據(jù)可以發(fā)現(xiàn)，除過Att48數(shù)據(jù)集外，SQACS算法在其他3個數(shù)據(jù)集上的最優(yōu)解都優(yōu)于文獻中所提算法，且求解結(jié)果都達到了TSPLIB數(shù)據(jù)庫中的最優(yōu)值。從計算時間角度分析，SQACS算法除在Oliver30數(shù)據(jù)集上的計算時間比文獻［6］和文獻［7］要久一點，但是相差并不大，其他計算時間都要比對比算法更短。這驗證了SQACS算法對求解小規(guī)模TSP的有效性。

表3 八種算法的實驗結(jié)果對比

圖3 SQACS算法求得4個實例的最優(yōu)路徑

表4 SQACS算法與文獻［5-9］算法的計算結(jié)果對比

Tab.4 Comparison of calculation results of SQACS algorithm and algorithms in literatures ［5-9］

3 結(jié)語

本文針對人工協(xié)同搜索算法收斂速度慢、精度低等缺點，提出了基于Sigmoid函數(shù)的反向人工協(xié)同搜索算法。利用Sigmoid函數(shù)構(gòu)造了比例因子，提高算法的全局搜索能力；在變異階段，加入了差分進化算法的DE/rand/1變異策略，對當前種群進行二次變異，使算法避免陷入局部最優(yōu)并且提高計算精度；在算法后期的開發(fā)階段，引入擬反向?qū)W習策略，從而更有效地找到最優(yōu)解。最后，利用提出的SQACS算法求解TSP，用TSPLIB數(shù)據(jù)庫中實例進行測試，并與其他7個算法和近五年文獻方法進行對比實驗，仿真實驗結(jié)果表明，本文提出的方法對于求解小規(guī)模TSP具有可行性，且效果更優(yōu)，但在求解大規(guī)模TSP時取得的結(jié)果不是很好。今后工作仍需對ACS算法進行改進，加快其計算速度，并將改進算法運用于多旅行商問題的求解中。

[1] WANG K P， HUANG L， ZHOU C G， et al. Particle swarm optimization for traveling salesman problem［C］// Proceedings of the 2003 International Conference on Machine Learning and Cybernetics. Piscataway： IEEE， 2003： 1583-1585.

[2] 王建忠，唐紅. TSP問題的一種快速求解算法［J］. 微電子學與計算機，2011， 28（1）： 7-10.（WANG J Z， TANG H. A fast algorithm for TSP［J］. Microelectronics and Computer， 2011， 28（1）： 7-10.）

[3] DANTZIG G B， RAMSER J H. The truck dispatching problem［J］. Management Science， 1959， 6（1）： 80-91.

[4] 葛海明. 改進的遺傳算法求解TSP問題的應(yīng)用與研究［D］. 贛州：江西理工大學， 2016： 36-42.（GE H M. Application and research of improved genetic algorithm for TSP problem［D］. Ganzhou： Jiangxi University of Science and Technology， 2016： 36-42.）

[5] 何慶，吳意樂，徐同偉. 改進遺傳模擬退火算法在TSP優(yōu)化中的應(yīng)用［J］. 控制與決策， 2018， 33（2）： 219-225.（HE Q， WU Y L， XU T W. Application of improved genetic simulated annealing algorithm in TSP optimization［J］. Control and Decision， 2018， 33（2）： 219-225.）

[6] 戚遠航，蔡延光，黃戈文，等. 帶固定半徑近鄰搜索3-opt的離散煙花算法求解旅行商問題［J］. 計算機應(yīng)用研究， 2021， 38（6）： 1642-1647.（QI Y H， CAI Y G， HUANG G W， et al. Discrete fireworks algorithm with fixed radius nearest-neighbor search 3-opt for traveling salesman problem［J］. Application Research of Computers， 2021， 38（6）： 1632-1647.）

[7] 湯雅連，楊期江. 求解旅行商問題的蟻群優(yōu)化算法參數(shù)設(shè)計［J］. 東莞理工學院學報， 2020， 27（3）： 48-54.（TANG Y L， YANG Q J. Parameter design of ant colony optimization algorithm for traveling salesman problem［J］. Journal of Dongguan Institute of Technology， 2020， 27（3）： 48-54.）

[8] 陳科勝，鮮思東，郭鵬. 求解旅行商問題的自適應(yīng)升溫模擬退火算法［J］. 控制理論與應(yīng)用， 2021， 38（2）： 245-254.（CHEN K S， XIAN S D， GUO P. Adaptive temperature rising simulated annealing algorithm for traveling salesman problem［J］. Control Theory and Applications， 2021， 38（2）： 245-254.）

[9] 唐天兵，朱繼生，嚴毅. 基于量子優(yōu)化的人工蜂群算法求解旅行商問題［J］. 大眾科技， 2020， 22（12）： 7-9， 13.（TANG T B， ZHU J S， YAN Y. An artificial bee colony algorithm based on quantum optimization to solve the traveling salesman problem［J］. Popular Science and Technology， 2020， 22（12）： 7-9， 13.）

[10] JAILLET P. A priori solution of a traveling salesman problem in which a random subset of the customers are visited［J］. Operations Research， 1998， 36（6）： 929-936.

[11] HERNáNDEZ-PéREZ H， SALAZAR-GONZáLEZ J J. The one-commodity pickup-and-delivery traveling salesman problem［M］// JüNGER M， REINELT G， RINALDI G. Combinatorial Optimization - Eureka， You Shrink！， LNCS 2570. Berlin： Springer， 2003： 89-104.

[12] NIENDORF M， KABAMBA P T， GIRARD A R. Stability of solutions to classes of traveling salesman problems［J］. IEEE Transactions on Cybernetics， 2016， 46（4）： 973-985.

[13] 卓雪雪，苑紅星，朱蒼璐，等. 蟻群遺傳混合算法在求解旅行商問題上的應(yīng)用［J］. 價值工程， 2020， 39（2）： 188-193.（ZHUO X X， YUAN H X， ZHU C L， et al. The application of ant colony and genetic hybrid algorithm on TSP［J］. Value Engineering， 2020， 39（2）： 188-193.）

[14] XUE J K， SHEN B. A novel swarm intelligence optimization approach： sparrow search algorithm［J］. Systems Science and Control Engineering， 2020， 8（1）： 22-34.

[15] PRICE K， STORN R. Differential evolution： a simple evolution strategy for fast optimization［J］. Dr. Dobb’s Journal， 1997， 22（4）： 18-24.

[16] MEHRABIAN A R， LUCAS C. A novel numerical optimization algorithm inspired from weed colonization［J］. Ecological Informatics， 2006， 1（4）： 355-366.

[17] HASHIM F A， HUSSAIN K， HOUSSEIN E H， et al. Archimedes optimization algorithm： a new metaheuristic algorithm for solving optimization problems［J］. Applied Intelligence， 2021， 51（3）： 1531-1551.

[18] CIVICIOGLU P. Artificial cooperative search algorithm for numerical optimization problems［J］. Information Sciences， 2013， 229： 58-76.

[19] TURGUT M S， TURGUT O E. Hybrid artificial cooperative search — crow search algorithm for optimization of a counter flow wet cooling tower［J］. International Journal of Intelligent Systems and Applications in Engineering， 2017， 5（3）： 105-116.

[20] TSELVARAJU R K， SOMASKANDAN G. Artificial cooperative search algorithm based load frequency controller for multi-area deregulated power system with coordinated controlof TCPS， RFB and AC-DC parallel Tie-lines［J］. ARPN Journal of Engineering and Applied Sciences， 2015， 10（14）： 6080-6091.

[21] 張蕭，黃晞，仲偉漢，等. Sigmoid函數(shù)及其導(dǎo)函數(shù)的FPGA實現(xiàn)［J］. 福建師范大學學報（自然科學版）， 2011， 27（2）： 62-65.（ZHANG X， HUANG X， ZHONG W H， et al. Implementation of Sigmoid function and its derivative on FPGA［J］. Journal of Fujian Normal University （Natural Science Edition）， 2011， 27（2）：62-65.）

[22] MAHDAVI S， RAHNAMAYAN S， DEB K. Opposition based learning： a literature review［J］. Swarm and Evolutionary Computation， 2018， 39： 1-23.

[23] TURGUT O E. Improved artificial cooperative search algorithm for solving nonconvex economic dispatch problems with valve-point effects［J］. International Journal of Intelligent Systems and Applications in Engineering， 2018， 6（3）： 228-241.

[24] KABOLI S H A， SELVARAJ J， RAHIM N A. Long-term electric energy consumption forecasting via artificial cooperative search algorithm［J］. Energy， 2016， 115（Pt 1）： 857-871.

Artificial cooperative search algorithm for solving traveling salesman problems

XU Xiaoping1， TANG Yangli1*， WANG Feng2

（1，’，’710054，；2，’，’710049，）

Concerning low solution accuracy and slow convergence of traditional Artificial Cooperative Search （ACS） algorithm， a Quasi opposition Artificial Cooperative Search algorithm based on Sigmoid function （SQACS） algorithm was proposed to solve Traveling Salesman Problem （TSP）. Firstly， the Sigmoid function was used to construct the scale factor to enhance the global search ability of the algorithm. Then， in the mutation stage， the mutation strategy DE/rand/1 of Differential Evolution （DE） algorithm was introduced into the current population for secondary mutation， thereby improving the calculation accuracy of the algorithm and the diversity of the population. Finally， in the later development stage， the quasi opposition learning strategy was introduced to further improve the quality of the solution. Four instances in TSP test library TSPLIB were used to perform simulation experiments， and the results show that SQACS algorithm is superior to seven comparison algorithms such as Sparrow Search Algorithm （SSA）， DE and Archimedes Optimization Algorithm （AOA） in the shortest path and time consumption， and has good robustness； and compared with other improved algorithms for solving TSP comprehensively， SQACS algorithm also shows good performance. Experimental results prove that the SQACS algorithm is effective in solving small-scale TSPs.

Artificial Cooperative Search (ACS) algorithm; Traveling Salesman Problem (TSP); Sigmoid function; Differential Evolution (DE); quasi opposition learning

This work is partially supported by National Natural Science Foundation of China （61773016）， Shaanxi Provincial Innovation Capability Support Program （2020PT-023）， Shaanxi Natural Science Basic Research Program （2018JQ1089）.

XU Xiaoping， born in 1973， Ph. D.， professor. His research interests include intelligent algorithm.

TANG Yangli， born in 1995， M. S. candidate. Her research interests include intelligent algorithm.

WANG Feng， born in 1972， Ph. D.，professor. Her research interests include intelligent algorithm.

TP301.6

A

1001-9081（2022）06-1837-07

10.11772/j.issn.1001-9081.2021040567

2021?04?14；

2021?06?28；

2021?07?02。

國家自然科學基金資助項目（61773016）；陜西省創(chuàng)新能力支撐計劃項目（2020PT-023）；陜西省自然科學基礎(chǔ)研究計劃項目（2018JQ1089）。

徐小平（1973—），男，陜西藍田人，教授，博士，主要研究方向：智能算法；唐陽麗（1995—），女，甘肅慶陽人，碩士研究生，主要研究方向：智能算法；王峰（1972—），女，河南蘭考人，教授，博士，主要研究方向：智能算法。