求解旅行商問題的探索—開發—跳躍策略單親遺傳算法

摘要：針對遺傳算法求解旅行商問題（TSP）時容易早熟、收斂速度慢等問題，提出一種基于探索—開發—跳躍策略的單親遺傳算法（EDJS-PGA）。該算法將基因移位、倒序、交換三種算子組合構成探索策略，用于擴展解的搜索空間，增強算法全局搜索能力；再將logistic混沌映射和改良圈操作融合為一種混沌映射改良圈算子，用于增強算法的局部搜索能力，構成開發策略；最后針對種群中的同優個體設計了近鄰變異算子，構成跳躍策略，增強了算法跳出局部最優解的能力，使其兼具個體變異、局部優化、防止早熟等多重作用。通過對18個TSP實例進行仿真實驗，結果表明EDJS-PGA相較于傳統單親遺傳算法具有更高的求解精度和收斂速度，且最優解偏差率和平均誤差率均處于較低水平；與其他文獻對比，EDJS-PGA具有更強的魯棒性和求解效率。

關鍵詞：旅行商問題；單親遺傳算法；logistic混沌映射；改良圈操作；近鄰變異

中圖分類號：TP391文獻標志碼：A文章編號：1001-3695（2023）05-014-1375-06doi：10.19734/j.issn.1001-3695.2022.10.0483

0引言

旅行商問題［1］是數學領域中經典的組合優化問題，最早出現在1759年歐拉研究的騎士周游問題中，即對于國際象棋棋盤中的64個方格，騎士按“馬走日”的規則，走訪棋盤中的每個方格一次且僅一次，最終回到起始點。如今，很多實際生產生活問題都可以歸結為TSP，如無人機運送服務［2］、物流配送［3］、滾動調度問題［4］等，因此如何高效地解決TSP具有很強的實用價值。

目前，TSP已有比較完整的數學模型，人們的研究重點主要集中在求解算法上。以分支定界法［5］、動態規劃法［6］等為代表的精確算法只適用于小規模情形，對中大規模的TSP則廣泛使用啟發式算法和智能優化算法，其中遺傳算法（geneticalgorithm，GA）［7］因其良好的全局性、并行性、魯棒性、普適性等特點，在組合優化、函數優化、自動控制等領域得到廣泛的應用。但是，傳統遺傳算法在求解TSP時存在收斂速度慢、易陷入局部最優而早熟等現象，為此國內外學者對其進行了大量的改進。1998年由李茂軍［8］提出的單親遺傳算法（partheno-geneticalgorithm，PGA）獨具特色，它舍棄了傳統遺傳算法的交叉操作，只采用變異和選擇來完成遺傳進化過程，使得算法具有框架簡單、不易早熟等優點。此后，PGA被許多學者應用于組合優化問題中。例如nal等人［9］將單親遺傳算法用于求解動態0-1多維背包問題，PGA表現出了明顯的優越性；Zhou等人［10］將單親遺傳算法的選擇算子和變異算子結合在一起并消除了進化概率，將改進后的算法求解多起點多旅行商問題，實驗結果證明該算法具有較強的穩定性和計算效率；Wang等人［11］在單親遺傳算法基礎上融合入侵雜草優化算法中的繁殖機制，使得算法具有較好的全局搜索能力；Wang等人［12］采用改進的單親遺傳算法解決具有最大等待時間約束的置換流水車間調度問題，實驗結果表明所提算法是可行且有效的；唐非等人［13］使用雙重變異策略改進單親遺傳算法并用于求解地勤服務優化問題，驗證了所提算法的有效性；Zhang等人［14］將單親遺傳算法與模擬退火算法結合以提高單親遺傳算法求解與時間相關的主題公園路徑規劃問題的優化能力。

本文以PGA為基本框架，對單親遺傳算法的變異策略進行重新設計，提出了基于探索—開發—跳躍策略的PGA。其中，組合運用移位、倒序、交換三種算子，作為探索策略，以增強對解空間中新個體的發現能力；設計了混沌映射改良圈算子作為開發策略，以保持對優勢個體的精細搜索能力；設計了對同優個體的近鄰搜索算子，以增強算法跳出局部最優的能力。仿真實驗表明，本文算法在尋優能力和計算穩定性等方面優于其他同類算法。

2EDJS-PGA的探索—開發—跳躍策略設計

傳統PGA在舍棄遺傳交叉操作時，未對變異和選擇操作具體規定，允許使用者在遵循遺傳算法基本原理的基礎上進行改進。綜合已有文獻中的一些典型策略，本文為PGA設計了具有探索—開發—跳躍能力的遺傳變異策略。

2.1基于移位—倒序—交換組合算子的探索策略

基因移位、倒序、交換算子是遺傳算法求解TSP中常用的變異算子，三種算子對染色體基因的變異程度各不相同。本文將這三種算子進行組合運用，構成探索策略，使其擴展解空間的搜索范圍，種群多樣性更豐富，算法全局搜索能力得到增強，起到了探索作用。本文中，三種算子的含義如下：

a）雙側移位算子。隨機產生兩個基因點，將染色體分為左、中、右三個片段，保持中間的基因片段不變，對左右兩個基因片段內的基因分別進行循環左移或右移一次，稱為雙側移位算子。傳統的移位算子通常是對中間片段的基因進行循環左移或右移，相比而言，雙側移位算子能獲得更明顯的變異效果。

b）倒序算子。隨機產生兩個基因點，將介于兩個基因點之間的基因片段進行顛倒順序處理。對旅行商路徑而言，倒序算子只是對路徑片段作截斷和斷點處的重連，因此染色體的變異程度相對較小。

c）片段交換算子。隨機產生兩個基因點，將染色體基因分為左、中、右三個片段；保持左邊片段不變，將中間片段和右邊片段進行整體交換。傳統的交換算子通常是對兩個或多個隨機的基因點進行交換，相比而言，片段交換能適當增強變異效果。

根據單親遺傳的基本思想，由一個父代個體根據上述三種算子遺傳生成三個子代個體，即為本文算法的組合運用方法。例如，設父代個體為a=（1，5，8，3，7，2，9，6，4），隨機基因點為3和6，組合算子的單親遺傳變異結果如圖1所示。

在4.1節，將利用種群多樣性指標具體分析上述探索策略對種群的改善效果。

2.2基于混沌映射改良圈算子的開發策略

在圖論知識中，改良圈算法（improvedcirclealgorithm，ICA）是求解TSP的一種常用的啟發式近似解法，對小規模的TSP能獲得較好的近似最優解［15］。

ICA的基本思想是對任給的初始Hamilton圈，不斷消除圈中路徑相交的項，直到無法再改進為止，其原理如圖2所示。ICA有較高的求解效率，但只適合于求解小規模問題。

近鄰變異算子的局部優化能力也容易引起算法早熟，為此將近鄰變異算子操作限定在同優個體范圍內，既可嘗試進一步優化同優個體又可以有效避免同優個體積聚過多。基于同優個體近鄰變異的跳躍策略如下：

a）對當前種群作同優個體的分組統計，記錄組數及組內個體數；若總組數低于預設閾值U，則轉入步驟b），否則結束本策略。

b）對每一組同優個體，保留組內一個個體不變，其余每一個個體隨機產生基因片段，執行近鄰變異算子。

可以看到，跳躍策略兼具變異、局部優化和避免早熟的多重作用，對加速算法收斂、避免算法早熟有重要作用。

3EDJS-PGA的總體步驟與流程

將上述探索—開發—跳躍策略與PGA框架相結合，得到EDJS-PGA。

3.1算法步驟

a）設置算法參數，包括編碼方案、染色體基因長度N、種群規模NP、迭代次數G。本文算法采用自然數序列編碼，基因長度N為TSP的城市數量，種群規模和迭代次數根據TSP實例的規模相應設定。

b）種群初始化，即按設定的基因長度產生每個個體的自然數隨機序列的基因編碼，構成初始種群p0。

c）計算個體適應度，對TSP，旅行商路徑越短則種群中個體越優秀。為利于遺傳優選，本文算法的適應度函數取式（1）的倒數1/f（V）。

d）作錦標賽分組優選，設定分組規模k（通常取值2～5，本文取k=4），將種群的NP個個體隨機分成NP/k個規模為k的小組；對每個組，根據適應度值選擇組內的最優個體作為單親遺傳的臨時個體，共得到NP/4個個體構成臨時種群p1。

e）執行基于探索—開發策略的單親遺傳變異，依次取臨時種群p1的每一個個體，分別按2.1節的探索策略和2.2節的開發策略進行單親遺傳變異操作，每個個體可變異生成四個子代個體，當所有個體完成操作時共獲得種群規模NP個變異個體，構成臨時子代種群p2。

f）對子代種群p2，執行2.3節的跳躍策略。

g）判斷算法是否達到終止條件；若迭代次數t達到預設值G，則算法結束并輸出最優解；否則返回步驟c）。

3.2算法流程

根據上述算法步驟，EDJS-PGA的流程如圖3所示。

在圖3中，探索策略使個體變異性更強，增強了種群多樣性，擴展了解的搜索空間；開發策略對個體有局部優化作用，增強了優質解出現的幾率，提高了算法的全局尋優能力。探索策略和開發策略并行執行則可以加速算法收斂，再執行跳躍策略可以有效避免算法早熟。

3.3運算復雜度分析

根據上述算法步驟和流程可知，EDJS-PGA的計算量主要包括初始化階段的城市距離矩陣計算、種群初始化和遺傳迭代的執行錦標賽分組優選、探索策略、開發策略和跳躍策略。其中，計算城市的距離矩陣和種群初始化，運算復雜度分別為O（N2）和O（NP）；錦標賽分組優選的復雜度為O（NP/k），k為分組規模；探索策略中需要執行組合算子移位—倒序—交換，按隨機數的均勻分布特性，其運算復雜度為O（3N/2）；開發策略的核心是混沌映射改良圈算子，運算時其內層循環會隨外層循環次數增加而減小，且僅在區間上執行，因此其最大運算復雜度為O（N2/2）；跳躍策略的核心是同優個體近鄰變異算子，所參與變異的同優個體數理論最大為NP－1，但實際數量并不會超過NP/3，故其運算復雜度為O（NP×N/3）。初始化操作是在迭代之前完成，三種策略則是在迭代過程中執行，因此EDJS-PGA算法的運算復雜度為

綜上所述，EDJS-PGA的理論最大運算復雜度為O（G×NP×N）。

4仿真實驗與結果分析

為測試本文構建的三種策略和EDJS-PGA的性能，本章將基于求解旅行商問題（TSP），對其作仿真實驗分析。實驗在IntelCorei7-8550U1.80GHz處理器的計算機上進行，選用MATLAB2021b作為編程環境，選取TSPLIB數據集中的標準對稱TSP實例進行仿真計算。

4.1探索策略對種群的改善效果

將基因移位、倒序、交換三種基本算子組合運用，有利于擴展搜索范圍，獲得更多新個體，增強種群多樣性。采用文獻［17］的多樣性評價指標進行分析。

其中：fi為種群中個體適應度值。選取TSPLIB數據集Kroa100實例，算法參數設置G=2000、NP=300、k=4，對三種基本算子的組合運用與每種算子的單獨使用時的種群多樣性進行測試和對比分析，結果如圖4所示。

從圖4可以看到，組合算子的種群多樣性較為穩定且隨著迭代次數增加呈現上升趨勢；而倒序算子的種群多樣性較低；雙側移位算子具有較強的變異能力但存在斷崖式的種群多樣性缺失，難以保持種群的多樣性；片段交換算子對種群的多樣性提升比較好，有微弱的上升趨勢。因此，三種算子的組合可以有效地保持和改善種群的多樣性，且兼具其他算子的優點。

4.2開發策略的性能分析

4.2.1logistic混沌映射對改良區間的改進作用

在開發策略中，logistic混沌映射主要用于增強改良區間的穩定性，其使區間長度處于相對穩定的范圍，以保證被選定個體總有一定長度的片段基因被改良。現有文獻尚無類似做法，因此下面將其與按普通隨機數生成改良區間進行實驗對比分析。算法參數取N=200，G=100，分別按式（2）和普通隨機數方法生成改良區間，如圖5所示。

可以看到，圖5（a）所對應的改良區間通過調節參量，可以將改良區間控制在預期的范圍內，使每個個體基因能得到一定程度的改良，并且其取值能穩定在一定范圍內；而在圖5（b）中，改良區間波動范圍太大，有時無法對個體基因進行有效改良，導致路徑的局部改良效果不穩定。綜上所述，按logistic混沌映射公式產生區間是必要的，且通過下一節的測試證明對于求解TSP是適用的。

4.2.2CMICO算子的性能分析

CMICO算子是本文算法的獨特之處，對算法的全局尋優和加速收斂均有重要作用，下面單獨測試和分析其性能。

測試實例選取TSPLIB數據集中的Att48、Pr76、Ch150、Tsp225四個。測試方法是基于標準PGA在加入該算子和不加入該算子兩種情形下分別求解，并對比分析。算法參數設置G=500、NP=300、k=4、U=290，獨立運行30次統計分析，分析指標包括最優解（best）、平均值（mean）、收斂次數（numberofconvergence，NC）、最優解誤差率（besterrorrate，BER）、平均解誤差率（meanerrorrate，MER）。收斂次數為尋找到最優解所需要的次數，BER和MER的計算公式為

其中：fbest為算法30次所求得的最好最優解；fave為算法30次所求得的最優解的平均值；fopt為已知最優解。

對上述四個TSP實例，用不加入CMICO算子的PGA和加入CMICO算子的PGA分別求解，結果如表1所示。

可以看到，CMICO算子對PGA的尋優能力、收斂性、穩定性都有明顯的提升。加入CMICO算子后求解四個實例的最優解誤差率為0.08%，平均解誤差率為0.22%，而不加入CMICO算子求解時，平均最優解誤差率和平均解誤差率為1882%和35%，并且當城市數量增多時求解效果仍保持良好，表明CMICO算子是有效和實用的。

圖6為采用和不采用CMICO算子的PGA分別求解實例Pr144、Tsp225時的進化曲線。

從圖6可以看到，當采用CMICO算子后，PGA的進化曲線能很快下降并趨于平穩，具有明顯的快速收斂能力。

4.3跳躍策略的性能分析

跳躍策略是對種群的同優個體進行近鄰變異，這使得其具有避免早熟、變異、局部優化等多重作用。下面分析其局部跳躍尋優能力及其變異幅度。

選取TSPLIB庫的Pr76案例，基于本文算法分別使用和不使用跳躍策略求解Pr76，繪制適應度進化曲線，如圖7所示。

從圖7可以看到，在求解案例Pr76過程中，到第32次迭代時，與不使用跳躍策略相比，發生了比較明顯的跳躍，最優個體的適應度值從108866下降到108202；在后續迭代中，類似的跳躍還會繼續發生，從而使得EDJS-PGA的局部尋優能力得到增強，對其他TSP案例進行求解，也發現會有多次跳躍尋優的特征，因此跳躍策略具有較強的跳出局部最優解的能力。

對跳躍策略引起同優個體的變異幅度，下面選取TSPLIB庫的8個案例，將使用跳躍策略的本文算法獨立運行30次進行統計分析。記錄每次運行期間同優個體中適應度的最大變異幅度（maximumrangeofvariation，MRV），且計算30次運行所得MRV的均值，記為平均最大變異幅度（averagemaximumrangeofvariation，AMRV），結果如表2所示。

從表2可以看出，跳躍策略對各案例均有不同程度的優化作用，能使種群中堆積的同優個體進行變異的同時并進一步優化。特別是對于小規模案例Att48、Pr76、Lin105，最大變異幅度較為明顯，其中最高為25.86%，最低為9.66%，平均最大變異幅度最大為13.48%，最低為6.46%，說明跳躍策略可有效地改變同優個體，變成更優質的解。對于中大型規模案例Ch130、U159、Kroa200、Tsp225、Lin318，跳躍策略的優化幅度有一定降低，但是均對同優個體進行了進一步的改善，這對算法進一步搜索更優質的解提供了新的方案。綜上所述，跳躍策略可以搜索同優個體的鄰域內的優質解，幫助算法跳出局部最優解的同時為算法提供更優質的解。

4.4EDJS-PGA算法的求解能力與收斂性

4.4.1EDJS-PGA算法求解TSP的能力

下面選取TSPLIB數據集的18個案例，用EDJS-PGA分別求解。對城市數量300以下的案例，迭代次數G=500，否則設置G=1000，其他算法參數與4.1節相同，實驗結果如表3所示。

從表3可以看到，EDJS-PGA求得的最優解都非常接近已知最優解。特別地，對于案例Dantzig42、Pr136、Pr144、U159、D198、Tsp225，求得的結果可以優于已知最優解；表中最優解誤差率（BER）最大為0.59%，BER均值約為0.06%；平均解誤差率（MER）最大為1.05%，MER均值約為0.19%。總體上看，EDJS-PGA對不同規模的城市都具有較強的全局尋優能力，驗證了探索、開發、跳躍策略可有效平衡算法的局部搜索能力與全局探索能力的矛盾。從表的BER、MER值可以看到，算法的求解結果具有很強的穩定性。不管是對于中小型規模城市Att48、Pr76、Pr144等案例，還是中大型城市Kroa200、Tsp225、Pr299，MER值都控制在很小的范圍，驗證了EDJS-PGA中三種策略的融合是有效的，同時三種策略各自在算法中的作用，兼顧了算法的全局搜索能力、局部搜索能力以及跳出局部最優解的能力，這使得算法每次的求解結果都能獲得比較理想的最優解。

4.4.2EDJS-PGA的收斂性

為進一步分析算法的尋優能力隨迭代次數的變化情況及收斂速度。本節選取三種算法進行對比：單親遺傳算法（PGA）、模擬退火算法（simulatedannealing，SA）、改進的蟻群算法（improvedantcolonyoptimization，IACO）。選取TSPLIB數據集中的Att48、kroa100、Ch150、Tsp225四個案例。各算法求解TSP案例的收斂曲線如圖8所示。

根據圖8可以看出，對于案例Att48，SA與IACO算法收斂精度較低，PGA收斂精度較高，但收斂速度緩慢，在迭代400次以后才接近最優解，而EDJS-PGA在迭代開始時收斂曲線便迅速下降，在迭代50次以內便收斂到最優解。對于案例Kroa100和Ch150，EDJS-PGA相較于其他算法仍然表現出卓越的收斂速度，驗證了算法具有較強的局部搜索能力，且兩個案例均在迭代次數150之內收斂到最優解，證明探索策略和開發策略有效地平衡了算法的局部搜索能力與全局搜索能力。對于大規模城市案例Tsp225，EDJS-PGA算法的收斂速度略微下降，但仍然在迭代次數400次以內達到最優解，且在迭代過程中多次快速跳出局部最優解，證明了本文設計的跳躍策略的有效性。

通過分析EDJS-PGA求解TSP的精度和收斂曲線可以證明，基于探索—開發—跳躍策略的單親遺傳算法，相較于原始PGA全局搜索能力、局部搜索能力以及跳出局部最優解的能力均得到加強。在求解TSP時表現出優秀的求解精度、收斂速度以及穩定性，證明了所設計的三種策略的融合是有效的，算法的全局搜索能力和局部搜索能力得到較好的平衡。

5EDJS-PGA與其他文獻算法的比較

為進一步驗證EDJS-PGA的有效性，本章將它與改進的遺傳算法（improvedgeneticalgorithm，IGA）［17］、優勢點蜜蜂算法（vantagepointbeesalgorithm，VPBA）［18］、混合遺傳多主體強化學習算法（hybridgeneticandmultiagentreinforcementlearningalgorithm，GA+MARL）［19］、混合細胞遺傳算法（hybridcellulargeneticalgorithm，SCGA）［20］、自適應繼承策略的帝國競爭算法（imperialistcompetitivealgorithmbasedonadaptiveinheritancestrategy，AISICA）［21］、迭代局部搜索算法（iteratedlocalsearch，ILS）［22］等近期國內外文獻中的算法進行對比測試，算法參數及實驗環境與上述相同，結果如表4所示。

在表4中，EDJS-PGA求得的最優解平均值都優于其他文獻算法的結果，驗證了本文算法的魯棒性優于其他算法。雖然對St70和Kroa100案例，EDJS-PGA求得的最優解略次于GA+MARL和ILS算法，但對Kroa200、Tsp225、Lin318案例，EDJS-PGA能夠求解出其他算法無法求得的最短路徑。因此，總體上EDJS-PGA相較于其他文獻算法更穩定且整體求解效果更好。圖9為EDJS-PGA求解四個實例所獲得的最優路徑圖。

6結束語

針對TSP特性以及傳統算法求解TSP時易出現的問題，本文基于單親遺傳算法（PGA）設計了探索策略、開發策略、跳躍策略。其中，探索策略將多種隨機變異算子相組合，主要作用是豐富種群的多樣性；開發策略將logistic混沌映射與改良圈操作相融合，構成混沌映射改良圈算子，增強算法的全局尋優能力；為防止算法早熟，針對種群的同優個體組，設計了基于最近鄰變異的跳躍策略，兼具局部優化和避免早熟等多重作用。上述三種策略使得EDJS-PGA具有良好的尋優能力和穩定性。

仿真實驗結果表明，EDJS-PGA在求解TSP時，對于中小型和中大型城市能夠取得較好的結果，且求解結果具有較好的穩定性，但對于少數案例求解精度上略微有些偏差。從數據上可以看出，EDJS-PGA具有求解大型TSP的潛力，未來將對算法的求解精度做進一步的研究改進，并將其應用于更大規模的TSP中。

參考文獻：

［1］ParkerRG，RardinRL.Thetravelingsalesmanproblem：anupdateofresearch［J］.NavalResearchLogisticsQuarterly，1983，30（1）：69-96.

［2］KimS，MoonI.Travelingsalesmanproblemwithadronestation［J］.IEEETransonSystems，Man，andCybernetics：Systems，2019，49（1）：42-52.

［3］LiuShaokun.Researchonlogisticsdistributionpathplanningbasedongeneticalgorithm［J］.JournalofPhysics：ConferenceSeries，2021，2083（3）：032013.

［4］SuFuyong，KongLinglu，WangHui，etal.ModelingandapplicationforrollingschedulingproblembasedonTSP［J］.AppliedMathematicsandComputation，2021，407（3）：126333.

［5］CarpenetoG，TothP.Somenewbranchingandboundingcriteriafortheasymmetrictravellingsalesmanproblem［J］.ManagementScience，1980，26（7）：736-743.

［6］BellmanR.Dynamicprogrammingtreatmentofthetravellingsalesmanproblem［J］.JournaloftheACM，1962，9（1）：61-63.

［7］LiepinsGE，HilliardMR.Geneticalgorithms：foundationsandapplications［J］.AnnalsofOperationsResearch，1989，21（1）：31-57.

［8］李茂軍.單親遺傳算法理論及應用［D］.長沙：湖南大學，2002.（LiMaojun.Theoryandapplicationofpartheno-geneticalgorithm［D］.Changsha：HunanUniversity，2002.）

［9］nalAN，KayakutluG.Apartheno-geneticalgorithmfordynamic0-1multidimensionalknapsackproblem［J］.RairoOperationsResearch，2016，50（1）：47-66.

［10］ZhouHonglu，SongMingli，PedryczW.AcomparativestudyofimprovedGAandPSOinsolvingmultipletravelingsalesmenproblem［J］.AppliedSoftComputing，2018，64：564-580.

［11］WangZijian，FangXi，LiHao，etal.Animprovedpartheno-geneticalgorithmwithreproductionmechanismforthemultipletravelingsalespersonproblem［J］.IEEEAccess，2020，8：102607-102615.

［12］WangBailin，LiTieke，WangHaifeng，etal.Partheno-geneticalgorithmforthepermutationflowshopschedulingproblemwithmaximumwaitingtimes［J］.AppliedMechanicsandMaterials，2014，631：66-69.

［13］唐非，劉樹安.機場地勤服務優化問題的雙重變異單親遺傳算法［J］.東北大學學報：自然科學版，2018，39（10）：1369-1374.（TangFei，LiuShu’an.Double-mutationpartheno-geneticalgorithmforairportgroundserviceoptimization［J］.JournalofNortheasternUniversity：NaturalScience，2018，39（10）：1369-1374.）

［14］ZhangYang，LiJiacheng，LiLei.Time-dependentthemeparkroutingproblembypartheno-geneticalgorithm［J］.Mathematics，2020，8（12）：2193.

［15］王海英，黃強，李傳濤，等.圖論算法及其MATLAB實現［M］北京：北京航空航天大學出版社，2010：88-89.（WangHaiying，HuangQiang，LiChuantao，etal.GraphtheoryalgorithmanditsMATLABimplementation［M］.Beijing：BeihangUniversityPress，2010：88-89.）

［16］LiuHao，ZhangXuewei，TuLiangping.Amodifiedparticleswarmoptimizationusingadaptivestrategy［J］.ExpertSystemswithApplications，2020，152（3）：113353.

［17］徐偉華，魏傳祥，張根瑞，等.基于K-近鄰域搜索的遺傳算法求解旅行商問題［J］.昆明理工大學學報：自然科學版，2022，47（1）：139-146.（XuWeihua，WeiChuanxiang，ZhangGenrui，etal.GeneticalgorithmfortravelingsalesmanproblembasedonK-nearestneighborssearch［J］.JournalofKunmingUniversityofScienceandTechnology：NaturalSciences，2022，47（1）：139-146.）

［18］ZeybekS，IsmailAH，HartonoN，etal.AnimprovedvantagepointbeesalgorithmtosolvecombinatorialoptimizationproblemsfromTSPLIB［J］.MacromolecularSymposia，2021，396（1）：2000299.

［19］MohammadAM，NaserRS，RezaFDM，etal.Ahybridalgorithmusingageneticalgorithmandmultiagentreinforcementlearningheuristictosolvethetravelingsalesmanproblem［J］.NeuralComputingandApplications，2018，30（9）：2935-2951.

［20］DengYanlan，XiongJuxia，WangQiuhong.Ahybridcellulargeneticalgorithmforthetravelingsalesmanproblem［J］.MathematicalProblemsinEngineering，2021，2021：articleID6697598.

［21］徐偉華，張根瑞，魏傳祥，等.基于自適應繼承策略的帝國競爭算法求解旅行商問題［J］.計算機應用研究，2021，38（11）：3349-3353.（XuWeihua，ZhangGenrui，WeiChuanxiang，etal.Imperialistcompetitivealgorithmbasedonadaptiveinheritancestrategytosolvetravelingsalesmanproblem［J］.ApplicationResearchofCompu-ters，2021，38（11）：3349-3353.）

［22］王若愚，陳勇全.基于強化學習的旅行商問題解構造方法［J］.計算機工程，2020，46（11）：293-300.（WangRuoyu，ChenYongquan.Solutionconstructionmethodsbasedonreinforcementlearningforthetravelingsalesmanproblem［J］.ComputerEngineering，2020，46（11）：293-300.）