基于ICS算法的旅行商問題研究

摘? 要：旅行商問題（Traveling Salesman Problem， TSP）是一個NP問題。為了能夠獲得最優的路徑長度以及降低運行時間，文章使用改進的布谷鳥算法（Improved Cuckoo Search， ICS）進行旅行商問題的優化。首先闡述了TSP問題的定義，其次采用布谷鳥算法（Cuckoo Search， CS）進行優化：使用混沌映射進行種群初始化，提高種群多樣性；利用量化正交交叉算子對每一次迭代后的個體進行篩選，保證了算法解的質量。仿真實驗中與ACO、PSO和CS對比，該文算法在TSP的最優路徑和最短時間方面具有一定的效果。

關鍵詞：TSP；混沌；正交交叉

中圖分類號：TP18? 文獻標識碼：A? 文章編號：2096-4706（2023）13-0092-04

Research on Traveling Salesman Problem Based on ICS Algorithm

QUAN Yu

（Science Technology Bureau of Shaoxing， Shaoxing? 312000， China）

Abstract： Traveling Salesman Problem （TSP） is a NP problem. In order to obtain the optimal path length and reduce running time， this paper uses the improved Cuckoo search （ICS） algorithm to optimize the traveling salesman problem. Firstly， the definition of the TSP problem is explained， and then the Cuckoo search （CS） algorithm is used for optimization： chaos mapping is used for population initialization to improve population diversity; the quantization orthogonal crossover operator is used to screen the individuals after each iteration， ensuring the quality of the algorithm solution. Compared with ACO， PSO， and CS in simulation experiments， the proposed algorithm in this paper has certain effectiveness in terms of optimal path and shortest time of TSP.

Keywords： TSP; chaos; orthogonal crossover

0? 引? 言

旅行商問題是一個經典的線路優化問題，如何最大程度減少TSP的時間、提高優化效率是當前學者們研究的主要方向。文獻[1]提出一種基于大規模鄰域搜索的模擬退火算法解決旅行商問題，仿真結果表明所提方法收斂效果好和魯棒性強，能夠有效求解旅行商問題；文獻[2]針對TSP問題，提出一種新的ACAG算法，實驗結果表明該算法性能明顯優于傳統的蟻群算法和遺傳算法，降低了TSP問題的求解時間；文獻[3]針對TSP問題提出一種優化的量子蟻群算法，在求解旅行商問題時，提出的算法在最優值差別不大的情況下，減少了早熟，大幅度提高了算法的收斂速度；文獻[4]在TSP問題中提出一種帶遺忘因子的蟻群優化算法，在TSP實例的仿真結果表明能夠耗時更短，路徑尋優結果更優；文獻[5]提出了一種改進的混合遺傳蟻群算法，仿真結果表明該算法在求解不同規模的旅行商問題時具有更強的全局搜索性及快速收斂性。文獻[6]在TSP問題中提出改進離散蝴蝶優化算法，該算法為了提升搜索效率，利用貪婪機制初始化種群，同時結合2-OPT算子、改進的2-OPT算子和模擬退火等策略來提高尋優能力，仿真結果表明提出的算法在尋優能力和魯棒性方面表現優越；文獻[7]利用深度強化學習模型SAC對遺傳算法進行改進，并將其應用至旅行商問題（TSP）的求解，通過對TSPLIB實例的實驗結果表明改進的遺傳算法可有效地避免陷入局部最優解，在提高種群收斂速度的同時，減少尋優過程的迭代次數；文獻[8]借鑒對抗學習的思想解決旅行商問題，核心思想是使用監督學習的方式來產生對抗樣本，并將對抗樣本加入隨機樣本中混合訓練，以改善模型對該類問題的泛化性能，仿真實現驗證了所提出方法的有效性；文獻[9]在解決TSP問題中設計了一種隨機最佳插入的煙花算法（RBIFWA），仿真表明RBIFWA算法在求解TSP問題上具有更加優秀的性能和更高的求解質量。

在以上的研究成果中發現大部分解決TSP問題的方法都是采用了元啟發式的智能算法，從實驗結果看獲得了較好的效果，本文將繼續這一思想的指導下進行研究，將ICS算法用于解決TSP問題。首先闡述了TSP問題基本概念，其次針對CS算法使用混沌映射進行種群初始化，提高種群多樣性，利用量化正交交叉算子對每一次迭代后的個體進行篩選，保證了算法的解的質量，通過仿真實驗說明該算法具有較好的效果。

1? 旅行商問題簡介

求解TSP問題的本質是求解一個NP完全問題，由于TSP問題涉及的范圍越來越廣，使得計算規模逐漸增大，從而導致規劃路徑中所需要的計算量呈現指數級的改變。而TSP問題的本質就是在具有n個頂點組成的無向閉合回路的完全圖G =（V，E，r）中利用最小的時間和最低的成本遍歷完成所有的頂點的邊之和。假設頂點集合V = {1，2，…，n}中每一個點表示需要訪問的城市，E表示這些頂點中的不同頂點組成的邊集，r設定為每一邊的權值。因TSP問題的數學模型表達如下：

以上公式中，式（1）表示求解TSP的目標函數，其中xi，j表示兩個城市，di，j表示2個城市之間的權重值。式（2）（3）表示旅行者只能走過一個城市，式（4）表示旅行商走過的任何城市中子集中不能形成循環。

2? 基本CS算法簡述

布谷鳥算法（Cuckoo Search， CS）是一種元啟發式的算法。該算法模擬布谷鳥的巢寄生行為和Levy行為。具體算法描述如下：

1）算法隨機產生N個鳥窩的位置表達為 ，任意選擇其中一個最佳的鳥窩傳遞給下一代。

2）算法的位置更新主要依靠Levy飛行進行迭代，將新獲得鳥窩中下一代個體位置對比上一代的鳥窩位置，從中尋找位置最好的個體。

3）將隨機數r ∈ [0，1]對比宿主鳥發現外來鳥蛋概率Pa。當r＞Pa，則將該鳥窩的位置進行改變，否則不變，然后對比上一代鳥窩的位置，從中選擇出位置更好的鳥窩即 。

4）計算獲得最新的鳥窩位置是否達到精度或者迭代條件，則該鳥窩為算法的全局最優解，否則繼續轉2）執行。

布谷鳥算法中每一個巢中的卵代表算法的解，表達式如下：

式中， 表示第t代中的第i個鳥窩位置；?表示點對點乘法，α表示步長，L（λ）表示隨機搜索路徑。

3? ICS算法的旅行商問題優化

從旅行商問題的求解中發現，該問題是一個典型的NP問題，而采用元啟發式算法是求解該問題關鍵。本文采用CS算法進行求解旅行社問題。CS算法憑借實現原理簡單，容易操作等優點而被廣泛地進行應用，但是它像大部分元啟發式算法一樣存在陷入局部最優，收斂速度慢等缺點。本文從種群初始化和個體篩選兩個方面對算法進行優化，一方面使用混沌對種群進行初始化提高多樣性，另一方面通過正交交叉算子進行個體篩選，提高解的質量。

3.1? 種群初始化

CS算法的種群個體初始值僅僅通過隨機方式處理，這樣容易使得算法在后期陷入局部收斂，解的多樣性受到嚴重影響。而混沌思想具有隨機性，遍歷性等優點，它能夠保證算法解獲得多樣性。它的主要思想是將解的個體映射關系某個區間中，從而產生混沌解，然后對應到個體的搜索空間中，提高了種群的解的多樣性。本文采用的混沌表達式為：

式中，xi表示布谷鳥個體，xi+1表示混沌后的布谷鳥個體。rand（0，1）表示0和1之間的隨機函數。我們將混沌后的布谷鳥個體和原始個體進行適應度比較，選擇兩者中最優的個體組成初始化種群。

3.2? 個體篩選

CS算法在每一次迭代后沒有對個體進行篩選，這樣就容易造成質量差的個體也進入了下一次迭代，從而降低了解的質量，為了避免這種情況的發生，同時提高解的效率，本文提出使用量化正交交叉算子用于個體篩選和提高個體解質量。過程闡述如下：

我們先假設x =（x1，x2，…，xD）和y =（y1，y2，…，yD）分別表示不同兩個父體的候選解，我們將這兩個候選解定義在同一個搜索空間中[llow，uup]，下限范圍即llow = [min（x1，y1），min（x2，y2），…，min（xD，yD）]，上限范圍即uup = [max（x1，y1），max（x2，y2），…，max（xD，yD）]，同時將該空間的每一個維度范圍量化為Q個分區，因此通過式（7）可以獲得第i個體在j維上的具有的Q個分區：

我們將每一個維度上的數值看成一個元素，利用正交表LM（QK）（K = D）將不同的元素變成為M個組合，利用隨機生成的F - 1個整數k1，k2，…，kF-1（1＜k1＜k2，…，＜kF-1＜D）來降低解的高維性，根據式（8）分成F個組（F遠小于D），其中每一個組設定為一個元素。

將每一個元素量化為Q個分區，因此第i個因素個體適應度值fi的Q個分區如式（9）：

通過上述的方法能夠有效地消除冗余解，從而提高解的質量，同時根據正交表的處理獲得候選解的個體，對這些候選解進行一一評價后獲得最優個體。該方法能夠保證算法在不斷優化迭代的過程中，降低每個候選解之間的差異，使得這些候選解的父體所在解的空間逐漸減少，從而獲得質量最好的個體。

3.3? 算法步驟

算法步驟如下：

1）將設定城市數目以及相應位置的坐標數據，建立所有城市矩陣，并設置CS算法相關參數，設定最大迭次次數，種群規模。

2）對CS算法的種群采用混沌算法。

3）對個體篩選采用正交交叉算子。

4）對每次更新的個體比較適應度值，如果由于當前最優個體的適應度值，則直接取代，否則轉步驟3）。

5）迭次次數加1。

6）當迭代次數達到設定最大迭代次數，則輸出最優路結果，否則轉步驟3）執行。

4? 仿真實驗

為了更好地說明本文算法的效果，將本文的算法與ACO、PSO和CS算法進行對比，對比算法涉及的參數以各自參數為主。根據TSP模型的計算要求，對于模擬城市的遍歷設定相同的速度。對比的指標是最優路徑的長度和所花費的單位時間。將模擬城市的數量分為兩種情況，即為對比模擬數量少的城市和模擬數量多的城市。

4.1? 算法性能

為了更好地說明本文算法具有的優勢，將CS和本文的ICS在3個經典測試函數中借助MATLAB 2012仿真平臺進行對比。設置相同的初始化鳥巢的數目，Pa選擇0.5，β設為0.5，對于兩種算法運行100次，結果如表1至表3所示。

4.2? TSP問題效果對比

構建5個模擬城市的坐標分別是（13，13）、（17，35）、（20，20）、（35，15）、（30，40），分布如圖1所示。圖2和圖3分別展示了4種算法的在城市中的最優路徑的長度和所花費的單位時間。從圖2中發現4種算法在城市最優路徑長度比較方面相差不大，雖然本文算法相比于其他算法具有一定的優勢，但是這種優勢并不是十分明顯，這主要是由于模擬城市的數量較少，算法的性能可能好沒有得到充分的體現。從圖3中發現4種算法在尋找最優路徑時候的花費時間的對比，從圖中發現4種算法所消耗的單位時間都比較少，這主要是由于模擬城市數量較少的原因，但是總體上本文算法的時間具有一定的優勢，這主要是因為本文算法在種群初始化，位置更新和個體篩選方面進行了優化，使得算法的性能得到了提升，因此降低了算法的運行時間。

5? 結? 論

針對TSP問題中的路徑和運行時間長的問題，本文提出了一種改進的CS算法，它使用混沌映射進行種群初始化，提高了種群多樣性，并利用量化正交交叉算子對每一次迭代后的個體進行篩選，保證了算法的解的質量，仿真實驗中在模擬城市數量少和多的情況下，本文算法相比于ACO、PSO和CS都具有較好的效果

參考文獻：

[1] 孫鑒，劉凇佐，武曉曉.基于大規模鄰域搜索的模擬退火算法求解TSP [J/OL].計算機仿真，（2023-01-02）[2023-01-23].https：//www.cnki.net/KCMS/detail/detail.aspx？dbcode=CAPJ&dbname=CAPJLAST&filename=JSJZ20221229002&v=MTQ2MDRyWTFNWk9zTll3azd2QkFTNmpoNFRBemxxMkEwZkxUN1I3cWRaT1pwRmlIbFZiM0JKVjg9THo3QmRMRzRITlBO.

[2] 圣文順，徐愛萍，徐劉晶.基于蟻群算法與遺傳算法的TSP路徑規劃仿真 [J].計算機仿真，2022，39（12）：398-402+412.

[3] 李想，董玉民.一種優化的量子蟻群算法在旅行商問題上的應用 [J].重慶師范大學學報：自然科學版，2022，39（5）：127-133.

[4] 趙鑫，楊雄飛，錢育蓉.改進的蟻群優化算法求解旅行商問題 [J].計算機工程與設計，2022，43（4）：962-968.

[5] 鄭娟毅，程秀琦，付姣姣.改進蟻群算法在TSP中的應用研究 [J].計算機仿真，2021，38（5）：126-130+167.

[6] 謝聰.求解TSP問題的改進離散蝴蝶優化算法 [J].數學的實踐與認識，2020，50（1）：173-182.

[7] 陳斌，劉衛國.基于SAC模型的改進遺傳算法求解TSP問題 [J].計算機科學與探索，2021，15（9）：1680-1693.

[8] 熊文瑞，陶繼平.自適應對抗學習求解旅行商問題 [J].計算機工程與應用，2022，58（17）：224-229.

[9] 吳俊斌，吳晟，吳興蛟.一種用于求解TSP問題的隨機最佳插入煙花算法 [J].計算機工程與科學，2020，42（11）：2080-2087.

作者簡介：全瑜（1985.01—），男，漢族，浙江紹興人，工程師，本科，研究方向：信息技術。

收稿日期：2023-02-27