陳 雷，張紅梅，張向利

桂林電子科技大學 廣西高校云計算與復雜系統(tǒng)重點實驗室，廣西 桂林 541004

1 引言

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

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

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

2 研究基礎

2.1 旅行商問題的圖論描述

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

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

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

2.2 布谷鳥搜索算法

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

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

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

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

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

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

（1）初始化種群P，計算各個個體x的適應值 f(x)

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

（3） 對種群中的每一個個體x，重復執(zhí)行：

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

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

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

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

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

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

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

3.1 布谷鳥算法的離散化

3.1.1 適應度函數(shù)

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

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

3.1.2 表示方式

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

3.1.3 鄰域結構

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

（1）2-opt鄰域結構

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

（2）3-opt鄰域結構

即首先刪除路徑中的3條子路徑，再嘗試重新連接路徑的所有其他可能形式，這個過程會產(chǎn)生3種新的路徑，如圖1所示，切斷子路徑1-2，3-4，5-6之后重組，可以得到3個候選項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鄰域結構

（3）雙橋鄰域結構

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

圖2 雙橋鄰域結構

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

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

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

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

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

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

3.2 動態(tài)鄰域結構

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

圖3 2-opt隨機移動造成路程增加

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

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

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

3.3 禁忌搜索的結合

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

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

（2）計算候選集Y中各候選項的適應度，并按適應度 f(Yi)升序排列

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

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

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

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

3.4 算法描述

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

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

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

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

（4） 對于每個Si：

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

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

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

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

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

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

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

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

（4）Else

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

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

4 實驗結果

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

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

4.2 對比分析

4.2.1 ADNHCS與DCS和ADCS算法的比較

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

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

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

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

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

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

本節(jié)ADNHCS算法將會與HDCS算法和兩個基于經(jīng)典智能優(yōu)化算法的混合算法進行比較，分別是四點三線遺傳算法（Four Vertices and Three Lines Genetic Algorithm，4V3LGA）[2]和基于圓周定向突變的動態(tài)鄰域結構自適應混合模擬退火禁忌搜索算法（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算法的比較結果。

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

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

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

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

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

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

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

4.2.4 ADNHCS收斂效果圖

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

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

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

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

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

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

5 結束語

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