基于ICS算法的旅行商問(wèn)題研究

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

關(guān)鍵詞：TSP；混沌；正交交叉

中圖分類號(hào)：TP18? 文獻(xiàn)標(biāo)識(shí)碼：A? 文章編號(hào)：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? 引? 言

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

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

1? 旅行商問(wèn)題簡(jiǎn)介

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

以上公式中，式（1）表示求解TSP的目標(biāo)函數(shù)，其中xi，j表示兩個(gè)城市，di，j表示2個(gè)城市之間的權(quán)重值。式（2）（3）表示旅行者只能走過(guò)一個(gè)城市，式（4）表示旅行商走過(guò)的任何城市中子集中不能形成循環(huán)。

2? 基本CS算法簡(jiǎn)述

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

1）算法隨機(jī)產(chǎn)生N個(gè)鳥(niǎo)窩的位置表達(dá)為 ，任意選擇其中一個(gè)最佳的鳥(niǎo)窩傳遞給下一代。

2）算法的位置更新主要依靠Levy飛行進(jìn)行迭代，將新獲得鳥(niǎo)窩中下一代個(gè)體位置對(duì)比上一代的鳥(niǎo)窩位置，從中尋找位置最好的個(gè)體。

3）將隨機(jī)數(shù)r ∈ [0，1]對(duì)比宿主鳥(niǎo)發(fā)現(xiàn)外來(lái)鳥(niǎo)蛋概率Pa。當(dāng)r＞Pa，則將該鳥(niǎo)窩的位置進(jìn)行改變，否則不變，然后對(duì)比上一代鳥(niǎo)窩的位置，從中選擇出位置更好的鳥(niǎo)窩即 。

4）計(jì)算獲得最新的鳥(niǎo)窩位置是否達(dá)到精度或者迭代條件，則該鳥(niǎo)窩為算法的全局最優(yōu)解，否則繼續(xù)轉(zhuǎn)2）執(zhí)行。

布谷鳥(niǎo)算法中每一個(gè)巢中的卵代表算法的解，表達(dá)式如下：

式中， 表示第t代中的第i個(gè)鳥(niǎo)窩位置；?表示點(diǎn)對(duì)點(diǎn)乘法，α表示步長(zhǎng)，L（λ）表示隨機(jī)搜索路徑。

3? ICS算法的旅行商問(wèn)題優(yōu)化

從旅行商問(wèn)題的求解中發(fā)現(xiàn)，該問(wèn)題是一個(gè)典型的NP問(wèn)題，而采用元啟發(fā)式算法是求解該問(wèn)題關(guān)鍵。本文采用CS算法進(jìn)行求解旅行社問(wèn)題。CS算法憑借實(shí)現(xiàn)原理簡(jiǎn)單，容易操作等優(yōu)點(diǎn)而被廣泛地進(jìn)行應(yīng)用，但是它像大部分元啟發(fā)式算法一樣存在陷入局部最優(yōu)，收斂速度慢等缺點(diǎn)。本文從種群初始化和個(gè)體篩選兩個(gè)方面對(duì)算法進(jìn)行優(yōu)化，一方面使用混沌對(duì)種群進(jìn)行初始化提高多樣性，另一方面通過(guò)正交交叉算子進(jìn)行個(gè)體篩選，提高解的質(zhì)量。

3.1? 種群初始化

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

式中，xi表示布谷鳥(niǎo)個(gè)體，xi+1表示混沌后的布谷鳥(niǎo)個(gè)體。rand（0，1）表示0和1之間的隨機(jī)函數(shù)。我們將混沌后的布谷鳥(niǎo)個(gè)體和原始個(gè)體進(jìn)行適應(yīng)度比較，選擇兩者中最優(yōu)的個(gè)體組成初始化種群。

3.2? 個(gè)體篩選

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

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

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

將每一個(gè)元素量化為Q個(gè)分區(qū)，因此第i個(gè)因素個(gè)體適應(yīng)度值fi的Q個(gè)分區(qū)如式（9）：

通過(guò)上述的方法能夠有效地消除冗余解，從而提高解的質(zhì)量，同時(shí)根據(jù)正交表的處理獲得候選解的個(gè)體，對(duì)這些候選解進(jìn)行一一評(píng)價(jià)后獲得最優(yōu)個(gè)體。該方法能夠保證算法在不斷優(yōu)化迭代的過(guò)程中，降低每個(gè)候選解之間的差異，使得這些候選解的父體所在解的空間逐漸減少，從而獲得質(zhì)量最好的個(gè)體。

3.3? 算法步驟

算法步驟如下：

1）將設(shè)定城市數(shù)目以及相應(yīng)位置的坐標(biāo)數(shù)據(jù)，建立所有城市矩陣，并設(shè)置CS算法相關(guān)參數(shù)，設(shè)定最大迭次次數(shù)，種群規(guī)模。

2）對(duì)CS算法的種群采用混沌算法。

3）對(duì)個(gè)體篩選采用正交交叉算子。

4）對(duì)每次更新的個(gè)體比較適應(yīng)度值，如果由于當(dāng)前最優(yōu)個(gè)體的適應(yīng)度值，則直接取代，否則轉(zhuǎn)步驟3）。

5）迭次次數(shù)加1。

6）當(dāng)?shù)螖?shù)達(dá)到設(shè)定最大迭代次數(shù)，則輸出最優(yōu)路結(jié)果，否則轉(zhuǎn)步驟3）執(zhí)行。

4? 仿真實(shí)驗(yàn)

為了更好地說(shuō)明本文算法的效果，將本文的算法與ACO、PSO和CS算法進(jìn)行對(duì)比，對(duì)比算法涉及的參數(shù)以各自參數(shù)為主。根據(jù)TSP模型的計(jì)算要求，對(duì)于模擬城市的遍歷設(shè)定相同的速度。對(duì)比的指標(biāo)是最優(yōu)路徑的長(zhǎng)度和所花費(fèi)的單位時(shí)間。將模擬城市的數(shù)量分為兩種情況，即為對(duì)比模擬數(shù)量少的城市和模擬數(shù)量多的城市。

4.1? 算法性能

為了更好地說(shuō)明本文算法具有的優(yōu)勢(shì)，將CS和本文的ICS在3個(gè)經(jīng)典測(cè)試函數(shù)中借助MATLAB 2012仿真平臺(tái)進(jìn)行對(duì)比。設(shè)置相同的初始化鳥(niǎo)巢的數(shù)目，Pa選擇0.5，β設(shè)為0.5，對(duì)于兩種算法運(yùn)行100次，結(jié)果如表1至表3所示。

4.2? TSP問(wèn)題效果對(duì)比

構(gòu)建5個(gè)模擬城市的坐標(biāo)分別是（13，13）、（17，35）、（20，20）、（35，15）、（30，40），分布如圖1所示。圖2和圖3分別展示了4種算法的在城市中的最優(yōu)路徑的長(zhǎng)度和所花費(fèi)的單位時(shí)間。從圖2中發(fā)現(xiàn)4種算法在城市最優(yōu)路徑長(zhǎng)度比較方面相差不大，雖然本文算法相比于其他算法具有一定的優(yōu)勢(shì)，但是這種優(yōu)勢(shì)并不是十分明顯，這主要是由于模擬城市的數(shù)量較少，算法的性能可能好沒(méi)有得到充分的體現(xiàn)。從圖3中發(fā)現(xiàn)4種算法在尋找最優(yōu)路徑時(shí)候的花費(fèi)時(shí)間的對(duì)比，從圖中發(fā)現(xiàn)4種算法所消耗的單位時(shí)間都比較少，這主要是由于模擬城市數(shù)量較少的原因，但是總體上本文算法的時(shí)間具有一定的優(yōu)勢(shì)，這主要是因?yàn)楸疚乃惴ㄔ诜N群初始化，位置更新和個(gè)體篩選方面進(jìn)行了優(yōu)化，使得算法的性能得到了提升，因此降低了算法的運(yùn)行時(shí)間。

5? 結(jié)? 論

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

參考文獻(xiàn)：

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

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

[3] 李想，董玉民.一種優(yōu)化的量子蟻群算法在旅行商問(wèn)題上的應(yīng)用 [J].重慶師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2022，39（5）：127-133.

[4] 趙鑫，楊雄飛，錢育蓉.改進(jìn)的蟻群優(yōu)化算法求解旅行商問(wèn)題 [J].計(jì)算機(jī)工程與設(shè)計(jì)，2022，43（4）：962-968.

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

[6] 謝聰.求解TSP問(wèn)題的改進(jìn)離散蝴蝶優(yōu)化算法 [J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2020，50（1）：173-182.

[7] 陳斌，劉衛(wèi)國(guó).基于SAC模型的改進(jìn)遺傳算法求解TSP問(wèn)題 [J].計(jì)算機(jī)科學(xué)與探索，2021，15（9）：1680-1693.

[8] 熊文瑞，陶繼平.自適應(yīng)對(duì)抗學(xué)習(xí)求解旅行商問(wèn)題 [J].計(jì)算機(jī)工程與應(yīng)用，2022，58（17）：224-229.

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

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

收稿日期：2023-02-27