自適應(yīng)動(dòng)態(tài)鄰域布谷鳥混合算法求解TSP問題

陳 雷，張紅梅，張向利

桂林電子科技大學(xué) 廣西高校云計(jì)算與復(fù)雜系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004

1 引言

旅行商問題（Traveling Salesman Problem，TSP）是經(jīng)典的NP困難組合優(yōu)化問題[1]，該問題可描述為給定一組城市及城市之間的距離，求只經(jīng)過每座城市一次并返回出發(fā)地的最短路線。TSP問題具有廣泛的應(yīng)用背景，如物流配送、航線設(shè)計(jì)等，是組合優(yōu)化領(lǐng)域研究的熱點(diǎn)。近年來，啟發(fā)式算法已成為解決TSP問題的一種思路，如經(jīng)典的遺傳算法[2-3]、蟻群算法[4]、粒子群算法[5-7]和一些混合算法[8-9]，以及新型群智能優(yōu)化算法如蝙蝠算法[10-11]、帝國(guó)競(jìng)爭(zhēng)算法[12]和布谷鳥搜索算法[13-17]等。這些算法為解決旅行商問題提供了優(yōu)秀的方案。

布谷鳥搜索算法（Cuckoo Search，CS）是Yang于2009年提出的一種群智能優(yōu)化算法[18]，它通過結(jié)合列維飛行機(jī)制與偏好隨機(jī)游走策略，在求解連續(xù)空間優(yōu)化問題方面具有優(yōu)良的性能[19]。同時(shí)也有一些學(xué)者將其改進(jìn)并應(yīng)用于求解組合優(yōu)化問題，如TSP問題，其中Ouaarab等人設(shè)計(jì)了離散布谷鳥算法（Discrete Cuckoo Search Algorithm，DCS）[13]和基于隨機(jī)鍵的布谷鳥算法（Random-Key Cuckoo Search，RKCS）[14]，DCS 算法使用2-opt和雙橋移動(dòng)方式產(chǎn)生符合列維飛行機(jī)制的鄰域，以此離散化布谷鳥算法，但DCS算法在遍歷鄰域時(shí)未進(jìn)行篩選，且設(shè)置的步長(zhǎng)概率是相同的，減緩了收斂速度，同時(shí)產(chǎn)生鄰域的方式太過單一，不利于快速找到最優(yōu)解；而RKCS算法引入了隨機(jī)鍵表示法，利用列維飛行后的鍵值排序產(chǎn)生結(jié)果，但此方案不僅增加了額外的解碼過程，也沒有發(fā)揮列維飛行的特點(diǎn)，全隨機(jī)排序增加了計(jì)算的復(fù)雜程度，降低了收斂效果。針對(duì)DCS算法的不足，張子成等人設(shè)計(jì)了一種自適應(yīng)離散型布谷鳥算法（Adaptive Discrete Cuckoo Search，ADCS）[15]，使用針對(duì)路徑的自適應(yīng)型局部調(diào)整算子和全局隨機(jī)擾動(dòng)策略，并引入2-opt優(yōu)化算子來提升收斂速度，該方案相較DCS解的質(zhì)量有了提升，但2-opt優(yōu)化算子的運(yùn)算時(shí)間復(fù)雜度為O(n3)，若每一步都應(yīng)用該優(yōu)化算子，不僅會(huì)極大程度地拖延運(yùn)算速度，而且該優(yōu)化算子在大圖中有時(shí)會(huì)破壞更優(yōu)的解，導(dǎo)致無法收斂至全局最優(yōu)解。林敏等人結(jié)合基于學(xué)習(xí)的混合鄰域結(jié)構(gòu)和概率接受準(zhǔn)則，提出了混合離散布谷鳥（Hybrid Discrete Cuckoo Search，HDCS）算法[16]，通過列維飛行選擇相應(yīng)的鄰域結(jié)構(gòu)進(jìn)行尋優(yōu)，并引入模擬退火算法的Metropolis接受準(zhǔn)則，使算法不易陷入局部最優(yōu)，一定程度上提升了解的質(zhì)量，但該算法的學(xué)習(xí)規(guī)則是以當(dāng)前最優(yōu)解作為學(xué)習(xí)目標(biāo)，而在迭代前中期向最優(yōu)解的學(xué)習(xí)很難確保收斂，因此需要非常高的迭代次數(shù)才能獲得優(yōu)質(zhì)的解。

因此本文針對(duì)上述問題，提出了一種自適應(yīng)動(dòng)態(tài)鄰域布谷鳥混合算法（Adaptive Dynamic Neighborhood Hybrid Cuckoo Search，ADNHCS），首先對(duì)鄰域結(jié)構(gòu)進(jìn)行了擴(kuò)展，使之有可以產(chǎn)生更多富有變化的候選項(xiàng)；其次，設(shè)計(jì)了一種自適應(yīng)概率調(diào)整策略，可動(dòng)態(tài)調(diào)整離散列維飛行不同游走距離的概率，使之在不同迭代時(shí)期都具有優(yōu)質(zhì)的偏好步長(zhǎng)；同時(shí)對(duì)于高效但耗時(shí)的2-opt優(yōu)化算子采用dropout策略，保證快速收斂的同時(shí)避免大量無效計(jì)算；再次，為了提升鄰域搜索效率，設(shè)計(jì)了一種圓限定突變的動(dòng)態(tài)鄰域結(jié)構(gòu)來降低經(jīng)典算法的隨機(jī)性；最后，添加了禁忌搜索算法來擴(kuò)展局部鄰域搜索，提升了尋優(yōu)效果，使用禁忌表和藐視準(zhǔn)則防止重復(fù)搜索，降低陷入局部最優(yōu)解的可能。實(shí)驗(yàn)結(jié)果表明，ADNHCS較其他基于布谷鳥搜索的算法和一些其他群智能算法，均可獲得更接近全局最優(yōu)解的優(yōu)質(zhì)解。

2 研究基礎(chǔ)

2.1 旅行商問題的圖論描述

圖論中對(duì)于此問題的描述如下[9]：G=(V,E)，其中V={v1,v2,…,vn}表示n個(gè)城市集（頂點(diǎn)集），E={eij|vi,vj∈V}是集合V中元素（城市）兩兩連接的邊集，每一邊都存在與之對(duì)應(yīng)的權(quán)值。記城市V={v1,v2,…,vn}的一個(gè)訪問順序?yàn)門={t1,t2,…,ti,…,tn}，ti∈V(i=1,2,…,n)，且tn+1=t1，則其數(shù)學(xué)描述為：

其中eij表示城市i和城市 j之間的距離，xij表示該路徑是否在旅行商的旅行路線中的一個(gè)決策變量，若旅行商選擇此路徑，則xij=1，否則，xij=0。即：

通過公式（2）～（5）可以確保該路徑是一個(gè)合法的旅行商問題的解。

2.2 布谷鳥搜索算法

CS算法通過模擬布谷鳥的寄生育雛行為來有效地求解優(yōu)化問題，它根據(jù)Levy飛行和偏好隨機(jī)游走來獲取全局最優(yōu)解。Levy飛行是服從于Levy概率分布的，即尋優(yōu)路徑由頻繁的短跳躍與偶然出現(xiàn)的長(zhǎng)跳躍組成，這種尋優(yōu)方式可以使CS算法擁有更大的搜索空間，更容易跳出局部最優(yōu)[19]。另一方面，CS算法模擬了布谷鳥的繁殖行為，通過定義布谷鳥蛋被宿主鳥發(fā)現(xiàn)的概率，淘汰掉不適應(yīng)環(huán)境的較差鳥蛋，孵化適應(yīng)環(huán)境的優(yōu)秀的鳥蛋，確保布谷鳥的群體都是由優(yōu)秀個(gè)體組成，使得CS算法具有較強(qiáng)的收斂性[20]。在CS算法中假定遵循三條理想化的規(guī)則：

（1）每只布谷鳥每次只產(chǎn)一個(gè)卵，并隨機(jī)選擇一個(gè)鳥巢來孵化它。

（2）最好的鳥巢將被保留到下一代。

（3）布谷鳥可選擇的鳥巢數(shù)量是一定的，鳥巢宿主發(fā)現(xiàn)外來鳥蛋的概率 pa∈[0,1]。

基于上述三條理想化規(guī)則的基礎(chǔ)下布谷鳥尋窩的路徑和位置更新如下：

基本CS算法的主要實(shí)現(xiàn)步驟為：

（1）初始化種群P，計(jì)算各個(gè)個(gè)體x的適應(yīng)值 f(x)

（2）若未達(dá)到迭代終止條件，則重復(fù)執(zhí)行：

（3） 對(duì)種群中的每一個(gè)個(gè)體x，重復(fù)執(zhí)行：

（4） 使用Levy飛行生成新解y

（5） 若 f(y)＜f(x)，則用 y替代 x

（6） 按發(fā)現(xiàn)概率 pa丟棄差的解，使用偏好隨機(jī)游動(dòng)產(chǎn)生新解替代丟棄的解

（7） 記錄全局最優(yōu)解

（8）返回全局最優(yōu)解

3 自適應(yīng)動(dòng)態(tài)鄰域布谷鳥混合算法

在2.2節(jié)中介紹的CS算法主要用于解決連續(xù)優(yōu)化問題，為了解決TSP等組合優(yōu)化問題，要將連續(xù)型CS算法轉(zhuǎn)換成離散型CS算法。

3.1 布谷鳥算法的離散化

3.1.1 適應(yīng)度函數(shù)

TSP問題的目標(biāo)是找到最短的周游路徑，若用n個(gè)城市的訪問次序x來表示問題的解，則適應(yīng)度函數(shù)定義為：

其中xi表示第i個(gè)被訪問的城市，xi+1表示第i+1個(gè)被訪問的城市，Dist(xi,xi+1)表示城市xi和城市xi+1之間的距離。

3.1.2 表示方式

每個(gè)鳥巢都表示TSP問題的一個(gè)解，設(shè)第i個(gè)鳥巢的解為 Xi=(Xi1,Xi2,…,Xin)，其中 Xi1,Xi2,…,Xin代表n個(gè)城市的編號(hào)，表示從Xi1出發(fā)經(jīng)過Xi2,Xi3,…,Xin等城市，最終返回出發(fā)點(diǎn)。

3.1.3 鄰域結(jié)構(gòu)

ADNHCS采用了可以切斷2條邊的反序算子（2-opt鄰域）和可以切斷4條邊的雙橋移動(dòng)來產(chǎn)生候選集，為了豐富鄰域結(jié)構(gòu)，添加了具有多種變化形式的3-opt鄰域結(jié)構(gòu)。下面以8個(gè)城市的對(duì)稱TSP為例，假設(shè)當(dāng)前解為X=(1,2,3,4,5,6,7,8)，介紹各種鄰域結(jié)構(gòu)及其生成的路徑。

（1）2-opt鄰域結(jié)構(gòu)

又稱為“反序算子”，選擇兩個(gè)城市并逆序其中的排列，一般情況下切斷2條子路徑會(huì)產(chǎn)生這樣的效果，如切斷2-3和7-8，逆序城市2和8之間的路徑，得到候選項(xiàng)X1=(1,2,7,6,5,4,3,8)。

（2）3-opt鄰域結(jié)構(gòu)

即首先刪除路徑中的3條子路徑，再嘗試重新連接路徑的所有其他可能形式，這個(gè)過程會(huì)產(chǎn)生3種新的路徑，如圖1所示，切斷子路徑1-2，3-4，5-6之后重組，可以得到3個(gè)候選項(xiàng)X1=(1,5,4,2,3,6,7,8)、X2=(1,3,2,5,4,6,7,8)、X3=(1,4,5,3,2,6,7,8)。

圖1 3-opt鄰域結(jié)構(gòu)

（3）雙橋鄰域結(jié)構(gòu)

是4-opt的一種特殊組成形式，如圖2所示，切斷子路徑 1-2、3-4、5-6、7-8之后重組，得到候選項(xiàng) X1=(1,6,7,4,5,2,3,8)，由于此種移動(dòng)形成的結(jié)構(gòu)類似于兩座橋，故稱之為雙橋移動(dòng)，會(huì)對(duì)8個(gè)城市，4條子路徑產(chǎn)生影響。

圖2 雙橋鄰域結(jié)構(gòu)

3.1.4 自適應(yīng)概率調(diào)整策略

在上述提到的三種鄰域結(jié)構(gòu)基礎(chǔ)上，根據(jù)鄰域結(jié)構(gòu)對(duì)解的擾動(dòng)大小，將其劃分為3種步長(zhǎng)，通過Levy飛行的不同步長(zhǎng)選擇不同的鄰域結(jié)構(gòu)，短步長(zhǎng)時(shí)采用擾動(dòng)最小的2-opt鄰域結(jié)構(gòu)生成候選解集，長(zhǎng)步長(zhǎng)時(shí)則采用可以影響最多城市的雙橋鄰域結(jié)構(gòu)生成候選解集，中距離步長(zhǎng)則使用3-opt鄰域結(jié)構(gòu)生成候選解集。但由于在算法前期鳥巢中的每個(gè)解與最優(yōu)解是有一定距離的，需要以較大幅度的擾動(dòng)并結(jié)合2-opt優(yōu)化算子來縮小每個(gè)解與最優(yōu)解之間的距離，所以長(zhǎng)步長(zhǎng)在算法前期理應(yīng)獲得最大的概率，然而到了算法后期，優(yōu)質(zhì)的解都被保留了下來，鳥巢中的解只需微調(diào)就能達(dá)到最優(yōu)解，因此算法后期要以短步長(zhǎng)為主。綜上所述，步長(zhǎng)概率取值隨算法迭代次數(shù)的增加而動(dòng)態(tài)調(diào)整，是一個(gè)需要自適應(yīng)的參數(shù)，經(jīng)大量實(shí)驗(yàn)驗(yàn)證按照20%，30%，50%的區(qū)間概率設(shè)定可以達(dá)到較好的一個(gè)全局優(yōu)化效果，故設(shè)定其概率定義式如下：

其中it為剩余迭代次數(shù)，tot為迭代總次數(shù)，P2-opt表示2-opt鄰域產(chǎn)生的概率，Pdouble-bridge表示雙橋鄰域產(chǎn)生的概率，P3-opt表示3-opt鄰域產(chǎn)生的概率。

3.1.5 Dropout策略

2-opt優(yōu)化算子是一種用于解決TSP問題的路徑局部?jī)?yōu)化算法[15]，它依次交換路徑中不相鄰的兩條邊得到所有路徑的集合，保留可以改善路徑的交換。其時(shí)間復(fù)雜度高達(dá)O(n3)，但又可以提供優(yōu)質(zhì)的快速收斂效果，因此在算法早期啟動(dòng)可以獲得最大收益，而算法后期的解已經(jīng)相對(duì)穩(wěn)定，對(duì)每個(gè)候選項(xiàng)都啟用該算子不僅浪費(fèi)計(jì)算力還很難獲得更優(yōu)解。經(jīng)大量測(cè)試發(fā)現(xiàn)設(shè)定算法早期dropout啟動(dòng)率為50%，中期和后期啟動(dòng)率為20%可以在運(yùn)算時(shí)間和求解全局最優(yōu)解方面實(shí)現(xiàn)最優(yōu)策略，因此dropout概率定義式如下：

式中it表示剩余迭代次數(shù)，tot為迭代總次數(shù)，Pdropout表示2-opt優(yōu)化算子啟動(dòng)概率，上式可將啟動(dòng)概率限定為從50%到20%的遞減。

3.1.6 鳥巢被發(fā)現(xiàn)后的處理

若鳥巢被發(fā)現(xiàn)，則啟用向最優(yōu)鳥巢學(xué)習(xí)的策略，即選定被發(fā)現(xiàn)鳥巢的一個(gè)城市，在最優(yōu)解中截取該城市后面一組城市，將其移至被發(fā)現(xiàn)鳥巢對(duì)應(yīng)城市后面。假設(shè)選定的城市是3，最優(yōu)解給出的城市3后的城市段為6，7和2，則調(diào)整之后的路徑為X1=(1,3,6,7,2,4,5,8)。若該組城市路徑已存在于被發(fā)現(xiàn)鳥巢之中，則使用雙橋鄰域算子對(duì)最優(yōu)解的路徑進(jìn)行全局的擾動(dòng)并用2-opt優(yōu)化擾動(dòng)后的路徑，計(jì)算新路徑的適應(yīng)度，若比原路徑適應(yīng)度小則替換原路徑，若比原路徑適應(yīng)度大則丟棄。若當(dāng)前路徑適應(yīng)度小于全局最優(yōu)解的適應(yīng)度，則以當(dāng)前路徑為全局最優(yōu)解。

3.2 動(dòng)態(tài)鄰域結(jié)構(gòu)

為了降低在迭代后期隨機(jī)選邊帶來的劣質(zhì)候選集，ADNHCS對(duì)于2-opt鄰域和3-opt鄰域設(shè)置了一種圓限定突變的動(dòng)態(tài)鄰域結(jié)構(gòu)來降低經(jīng)典算法的隨機(jī)性。以2-opt為例，圖3（a）表示原路徑，圖3（b）表示隨機(jī)移動(dòng)后的路徑，可見b1+b2-a1-a2是一個(gè)遠(yuǎn)大于0的數(shù)字，盡管這樣的解也可以作為候選集，但其被選擇為當(dāng)前最優(yōu)解的概率幾乎為0，將在迭代后期增加許多不必要的搜索時(shí)間。

圖3 2-opt隨機(jī)移動(dòng)造成路程增加

因此本文設(shè)計(jì)了一種動(dòng)態(tài)鄰域結(jié)構(gòu)，可以在迭代后期減少無效的長(zhǎng)距離路徑交換，將2-opt鄰域和3-opt鄰域的候選范圍減小到一個(gè)近鄰域范圍內(nèi)。首先在城市集之中隨機(jī)選擇一個(gè)城市，然后根據(jù)半徑r的選定規(guī)則確定范圍內(nèi)的點(diǎn)，得到點(diǎn)集之后，隨機(jī)選擇點(diǎn)集中的某些點(diǎn)構(gòu)成的邊來組成2-opt或者3-opt切邊的候選集。半徑r的選定規(guī)則如下，其中totallen表示路程總長(zhǎng)度，citynum表示城市數(shù)：

以圖4的鄰域選擇與2-opt交換為例，圖4（a）表示原路徑，圖4（b）中隨機(jī)選擇了點(diǎn)8作為圓心，設(shè)置r為平均路徑的兩倍，以此選定的城市集合有{2，3，4，5，6，7，8，9}，隨機(jī)選擇點(diǎn)集中的邊（2，3）和（8，9），如圖4（c）所示，將其切斷并交換路徑，可得到如圖4（d）中所示的結(jié)果。

圖4 鄰域選擇與2-opt交換

3.3 禁忌搜索的結(jié)合

禁忌搜索在ADNHCS之中的作用有兩個(gè)，其一為擴(kuò)展局部鄰域搜索，通過Levy飛行產(chǎn)生基于當(dāng)前鳥巢解的候選集；其二是根據(jù)禁忌表和藐視準(zhǔn)則在候選集內(nèi)選出最適用于當(dāng)前鳥巢的解，補(bǔ)充了跳出局部最優(yōu)解的手段。具體步驟如下所述，其中Sbest代表當(dāng)前全局最優(yōu)解，Snest表示當(dāng)前鳥巢的解，tabulist表示禁忌表：

（1）采用Levy飛行生成候選集X并使用Dropout策略對(duì)候選集X執(zhí)行2-opt優(yōu)化，得到候選集Y

（2）計(jì)算候選集Y中各候選項(xiàng)的適應(yīng)度，并按適應(yīng)度 f(Yi)升序排列

（3）若 f(Y1)＜f(Sbest)，則 Sbest=Snest=Y1，并將Y1加入禁忌表，終止禁忌搜索

（4） 若候選集之中還有候選項(xiàng)，則重復(fù)執(zhí)行：

（5） 若 f(Yi)≥f(Snest)，終止禁忌搜索

（6） 若Yi∈tabulist，i=i+1，返回（3），否則Snest=Yi，并將Yi加入禁忌表，終止禁忌搜索

3.4 算法描述

綜合3.1～3.3節(jié)的步驟與結(jié)論，ADNHCS的執(zhí)行的主要流程如下：

（1）設(shè)定種群數(shù)目 pop，鳥巢被發(fā)現(xiàn)的概率 pa，迭代次數(shù)gen，禁忌表長(zhǎng)度=候選集數(shù)目candi

（2）隨機(jī)產(chǎn)生初始解集S={S1,S2,…,Spop}，并計(jì)算個(gè)體的適應(yīng)度 f(Si)，找出當(dāng)前最優(yōu)解Sbest

（3）當(dāng)沒有達(dá)到循環(huán)次數(shù)時(shí)，重復(fù)操作：

（4） 對(duì)于每個(gè)Si：

（5） Levy飛行產(chǎn)生候選集X={X1,X2,…,Xcandi}

（6） 對(duì)于候選集X使用禁忌搜索檢查是否有全局最優(yōu)解，是否優(yōu)于當(dāng)前解

（7） 隨機(jī)生成概率rand，若rand＞pa，鳥巢被發(fā)現(xiàn)，則向最優(yōu)解學(xué)習(xí)，對(duì)最優(yōu)解執(zhí)行一次雙橋移動(dòng)作為當(dāng)前解

（8）返回最優(yōu)解Sbest

其中（5）提到的Levy飛行產(chǎn)生候選集的具體實(shí)現(xiàn)方式為：

（1）隨機(jī)生成概率rand，判斷rand落在 P2-opt、Pdouble-bridge、P3-opt其中一個(gè)區(qū)間

（2）If迭代期位于迭代前中期

（3） 依據(jù)所落區(qū)間執(zhí)行各鄰域結(jié)構(gòu)的生成規(guī)則，產(chǎn)生候選集X={X1,X2,…,Xcandi}

（4）Else

（5） 2-opt，3-opt采用動(dòng)態(tài)鄰域結(jié)構(gòu)執(zhí)行各鄰域結(jié)構(gòu)的生成規(guī)則，雙橋鄰域不采用動(dòng)態(tài)鄰域結(jié)構(gòu)產(chǎn)生候選集 X={X1,X2,…,Xcandi}

（6）返回生成的候選集X

4 實(shí)驗(yàn)結(jié)果

4.1 算例與參數(shù)設(shè)置

為了驗(yàn)證ADNHCS算法的性能，本文選取了TSPLIB測(cè)試集[21]的多個(gè)不同規(guī)模的常用算例，并將ADNHCS算法與其他基于CS算法、新型群智能優(yōu)化算法和基于經(jīng)典智能優(yōu)化算法的混合算法進(jìn)行比較。程序編寫并執(zhí)行于MATLAB 2017a，Win10 1703系統(tǒng)，CPU 3.60 GHz，16 GB內(nèi)存。

4.2 對(duì)比分析

4.2.1 ADNHCS與DCS和ADCS算法的比較

基于CS的算法有DCS[13]、RKCS[14]、ADCS[15]、HDCS[16]等，由于RKCS的樣本數(shù)目太少且均運(yùn)行于小數(shù)據(jù)集，無法表現(xiàn)其完整性能，故盡管ADNHCS優(yōu)于RKCS，在此處暫不予比較；而HDCS的迭代次數(shù)遠(yuǎn)高于其他基于CS的算法，將其與移至同樣具有高迭代次數(shù)的經(jīng)典智能優(yōu)化算法部分進(jìn)行比較。

為了方便ADNHCS與DCS和ADCS算法對(duì)比，三者設(shè)置相同的參數(shù)，均為鳥巢發(fā)現(xiàn)概率Pa=0.2，集群數(shù)pop=20，迭代次數(shù)gen=500。同時(shí)，禁忌表長(zhǎng)度tabulen和候選集個(gè)數(shù)candi的設(shè)置都會(huì)影響算法全局尋優(yōu)能力。若禁忌表長(zhǎng)度和候選集個(gè)數(shù)設(shè)置較大，算法運(yùn)行時(shí)間長(zhǎng)，但可以獲得高質(zhì)量解；若設(shè)置較少的候選集個(gè)數(shù)和禁忌表長(zhǎng)，不僅會(huì)降低Levy飛行獲得優(yōu)質(zhì)解的可能性，還影響禁忌搜索跳出局部最優(yōu)解的能力。經(jīng)大量實(shí)驗(yàn)表明對(duì)于不同規(guī)模的算例，當(dāng)tabulen=candi=20時(shí)算法運(yùn)行效果可獲得性能與尋優(yōu)的平衡。比較結(jié)果列于表1中，ADNHCS對(duì)每個(gè)算例都獨(dú)立執(zhí)行30次。其中Instances表示算例名稱，Opt表示算例的理論最優(yōu)解，Best和Mean分別表示該算法的最優(yōu)解和平均解，PDb和PDav分別表示最優(yōu)解偏差和平均解偏差，計(jì)算公式分別為：

表1 ADNHCS算法與DCS和ADCS算法的比較

從表1可以看到，在城市數(shù)少于300的11個(gè)小規(guī)模問題上ADNHCS算法的優(yōu)勢(shì)已經(jīng)展現(xiàn)，其平均PDav僅為0.001%，當(dāng)城市數(shù)超過300時(shí)，ADNHCS算法的平均PDav明顯優(yōu)于ADCS和DCS算法，僅有0.82%，可見ADNHCS在各種規(guī)模TSP問題上均具有較大優(yōu)勢(shì)，當(dāng)算例少于500城市時(shí)幾乎總能找到最優(yōu)解，對(duì)于少于700城市的算例，PDav可以始終保持在1%之內(nèi)，只有對(duì)于城市數(shù)超過800的算例，受收斂次數(shù)影響，會(huì)出現(xiàn)大于1%小于2%的偏差，但平均解和最優(yōu)解差距很小，表示算法穩(wěn)定性較高，且尋優(yōu)效果較好。

從算例角度分析，以lin318算例為例，ADNHCS僅為0.16%的平均偏差率 PDav，是DCS的1/6，ADCS的1/2；對(duì)于rat575算例，ADNHCS將PDb和PDav準(zhǔn)確地限制在了0.52%和0.93%，最優(yōu)解的偏差率接近DCS和ADCS的1/4，平均解偏差率也有DCS和ADCS的1/3；對(duì)于nrw1379算例，ADNHCS依然可以保持1.19%的PDb，接近DCS和ADCS的1/3?？梢姰?dāng)算例城市數(shù)繼續(xù)增加時(shí)，ADNHCS相比DCS和ADCS依然可以保持穩(wěn)定的優(yōu)越性。

4.2.2 ADNHCS與經(jīng)典智能優(yōu)化算法比較

本節(jié)ADNHCS算法將會(huì)與HDCS算法和兩個(gè)基于經(jīng)典智能優(yōu)化算法的混合算法進(jìn)行比較，分別是四點(diǎn)三線遺傳算法（Four Vertices and Three Lines Genetic Algorithm，4V3LGA）[2]和基于圓周定向突變的動(dòng)態(tài)鄰域結(jié)構(gòu)自適應(yīng)混合模擬退火禁忌搜索算法（the Adaptive Hybrid Simulated Annealing-Tabu Search with a Dynamic neighborhood structure based on a Circle-directed Mutation，AHSATS-D-CM）[9]。表2給出了ADNHCS算法與HDCS、4V3LGA和AHSATS-D-CM算法的比較結(jié)果。

其中4V3LGA是一種改進(jìn)型遺傳算法，通過第一階段的變異算子優(yōu)化和第二階段是四點(diǎn)三線優(yōu)化，將漢密爾頓環(huán)分為多個(gè)四點(diǎn)三線的漢密爾頓路徑，并尋找最優(yōu)路徑來達(dá)到優(yōu)化的目的。AHSATS-D-CM算法是模擬退火與禁忌搜索算法結(jié)合的混合算法，并且為了提升鄰域突變的效果，設(shè)計(jì)了一種基于圓周定向突變的動(dòng)態(tài)鄰域結(jié)構(gòu)。

其中，HDCS和AHSATS-D-CM均為高迭代次數(shù)的算法。HDCS總的迭代次數(shù)不超過pop×gen×citynum，其中citynum為城市數(shù)，gen代表迭代次數(shù)，pop代表種群數(shù)，對(duì)于最簡(jiǎn)單的eil51算例，51個(gè)城市，2 000次迭代，30個(gè)種群，迭代次數(shù)就高達(dá)3.06×106，而這些迭代次數(shù)隨著城市數(shù)目增多也會(huì)隨之增加，AHSATS-D-CM也給出了2×106數(shù)量級(jí)的迭代次數(shù)，而ADNHCS的總迭代次數(shù)為 pop×candi×gen，其中candi為候選項(xiàng)個(gè)數(shù)，總迭代次數(shù)為2×105。盡管對(duì)于智能優(yōu)化算法來說迭代次數(shù)越多，找到最優(yōu)解的概率就越高，但從表3的結(jié)果來看，ADNHCS無論是在最優(yōu)解還是在均值的求解中，都表現(xiàn)出了穩(wěn)定的全局尋優(yōu)效果，在17個(gè)算例中只有3個(gè)平均解沒有達(dá)到理論最優(yōu)解，平均PDav僅有0.029%，AHSATS-D-CM在算例超過140城市時(shí)開始出現(xiàn)與理論最優(yōu)解的偏差，其平均PDav為0.1%，HDCS和4V3LGA分別只有1個(gè)和4個(gè)算例的平均解達(dá)到了理論最優(yōu)解，平均PDav分別為0.19%和0.91%。

表2 ADNHCS算法與HDCS、4V3LGA和AHSATS-D-CM算法的比較

4.2.3 ADNHCS與新型群智能優(yōu)化算法比較

為了進(jìn)一步驗(yàn)證ADNHCS算法的性能，本小節(jié)選擇了新型群智能優(yōu)化算法-離散蝙蝠算法（Discrete Bat Algorithm，DBA）[10]，參數(shù)設(shè)置與4.2.1小節(jié)相同，比較結(jié)果列于表3中，其中Worst表示該算法的最差解，C1%表示運(yùn)行結(jié)果在最優(yōu)解1%范圍內(nèi)解的個(gè)數(shù)，Copt表示運(yùn)行結(jié)果是最優(yōu)解的個(gè)數(shù)。

從表3中可以看到，無論是最優(yōu)解、平均解、最差情況的值還是的比率，ADNHCS算法均優(yōu)于DBA算法，經(jīng)計(jì)算得知DBA的平均偏差率PDav為0.515%，而ADNHCS的PDav僅為0.185%。同時(shí)ADNHCS在少于400城市的算例中可以確保穩(wěn)定的全局尋優(yōu)，在25個(gè)算例中只有3個(gè)算例的均值沒有達(dá)到理論最優(yōu)解，而DBA僅有8個(gè)算例得到了理論最優(yōu)解。

對(duì)于C1%的觀察可以發(fā)現(xiàn)，對(duì)于城市數(shù)少于500的算例，ADNHCS可以將解的值限制在最優(yōu)解1%的范圍內(nèi)，DBA則只能確保城市數(shù)少于200的算例解的值可以落入最優(yōu)解1%范圍內(nèi)。同時(shí)ADNHCS在城市規(guī)模超過1 000算例解的才超出最優(yōu)解1%范圍，表明ADNHCS在較大規(guī)模算例的運(yùn)算上面仍然具有穩(wěn)定高效的收斂效果。

4.2.4 ADNHCS收斂效果圖

為了證明ADNHCS算法在不同類型數(shù)據(jù)集的收斂效果，使用了4個(gè)屬性各異的算例進(jìn)行測(cè)試分析，分別為城市分布有規(guī)律的tsp225算例；城市分布高度規(guī)律和分散的ts225算例，以及城市分布高度集中且無規(guī)律的pr226算例和rat575算例。圖5～8為對(duì)應(yīng)的收斂曲線和路徑圖，從圖中可見由于2-opt優(yōu)化算子和dropout策略的引入，對(duì)于不同類型、不同規(guī)模的數(shù)據(jù)集，ADNHCS均可在前50次迭代中實(shí)現(xiàn)快速收斂，在求解TSP問題中展現(xiàn)出良好的搜索性能。

表3 ADNHCS算法與DBA算法的比較

圖5 tsp225的最優(yōu)路徑圖與收斂曲線

圖6 ts225的最優(yōu)路徑圖與收斂曲線

圖7 pr226的最優(yōu)路徑圖與收斂曲線

圖8 rat575的路徑圖與收斂曲線

5 結(jié)束語

本文提出了一種用來求解TSP問題的ADNHCS算法，將離散CS算法與禁忌搜索方式結(jié)合，降低陷入局部最優(yōu)解的可能，同時(shí)對(duì)鄰域結(jié)構(gòu)進(jìn)行了擴(kuò)展，可以產(chǎn)生更多富有變化的候選項(xiàng)，提高候選集的質(zhì)量。而可動(dòng)態(tài)調(diào)整離散列維飛行不同游走距離的概率的自適應(yīng)概率調(diào)整策略的引入，增強(qiáng)了算法的全局搜索能力，為高效但耗時(shí)的2-opt優(yōu)化算子使用dropout策略，平衡了快速收斂與無效計(jì)算力的矛盾，最后，圓限定突變的動(dòng)態(tài)鄰域結(jié)構(gòu)避免了遠(yuǎn)距離的無效交換，提升了鄰域搜索效率。在TSPLIB算例進(jìn)行的實(shí)驗(yàn)結(jié)果也驗(yàn)證了ADNHCS算法相較其他基于CS的算法和部分新型或經(jīng)典群智能算法，在求解TSP時(shí)有更好的收斂速度和收斂精度。