改進(jìn)二進(jìn)制布谷鳥(niǎo)搜索算法求解TSP問(wèn)題

姜保強(qiáng)

摘 要：針對(duì)TSP問(wèn)題的特點(diǎn)，設(shè)計(jì)了一種求解TSP問(wèn)題的改進(jìn)的二進(jìn)制布谷鳥(niǎo)算法。該算法采用二進(jìn)制編碼串表示鳥(niǎo)巢的位置，對(duì)布谷鳥(niǎo)尋找新鳥(niǎo)巢的萊維飛行路徑進(jìn)行了二進(jìn)制代碼變換，引入了二進(jìn)制編碼控制系數(shù)對(duì)變換得到的二進(jìn)制編碼進(jìn)行混合更新，保留了布谷鳥(niǎo)蛋被淘汰的機(jī)制等方法，并且引入了貪心思想，將新型高效的布谷鳥(niǎo)搜索（CS）算法改進(jìn)為二進(jìn)制布谷鳥(niǎo)搜索（BCS）算法。將BCS算法用于求解TSP問(wèn)題。通過(guò)多組數(shù)據(jù)的測(cè)試，對(duì)比"TSP問(wèn)題數(shù)據(jù)集合目錄（標(biāo)準(zhǔn)測(cè)試集）"結(jié)果表明，要好于禁忌搜索算法，遺傳算法，蟻群算法，粒子群算法。

關(guān)鍵詞：二進(jìn)制；布谷鳥(niǎo)搜索算法；旅行商問(wèn)題；貪心算法

ABSTRACT：According to the characteristics TSP problem， we design an improved TSP problem solving binary cuckoo algorithm. The algorithm uses a binary code string showing the location of the nest， the nest of the cuckoo to find a new flight path of Levi binary code conversion， this paper introduces the binary coded control coefficient transform binary coding mixed update， the paper retains the cuckoo egg method being eliminated mechanisms， and introduces greedy thought， this article will search for new and efficient cuckoo （CS） algorithm to improve a binary search cuckoo （BCS） algorithm. The BCS algorithm for solving TSP. By testing multiple sets of data， compared to "TSP problem of data collection catalog （standard test set），" The results show that better than tabu search algorithm， genetic algorithm， ant colony algorithm， particle swarm optimization.

Keywords： Binary； Cuckoo search algorithm； traveling salesman problem； greedy algorithm

1 引言

TSP（旅行商）問(wèn)題是指已知n個(gè)城市之間的相互距離，尋找一條遍訪n個(gè)城市，每個(gè)城市只訪問(wèn)一次。最終又回到出發(fā)城市的最短旅行路線。這是一個(gè)典型的組合優(yōu)化問(wèn)題，被證明是NP完全問(wèn)題，其所有的路線數(shù)為n，搜索空間隨著城市數(shù)n的增大而迅猛增大，這就產(chǎn)生了所謂的“組合爆炸”問(wèn)題。目前還沒(méi)有一種完全有效的算法解決TSP問(wèn)題。由于TSP問(wèn)題有很高的理論價(jià)值和實(shí)際應(yīng)用背景，如何以用來(lái)解決分配、調(diào)度和網(wǎng)絡(luò)優(yōu)化問(wèn)題等，所以人們一直致力于研究新的算法達(dá)到高效求解TSP問(wèn)題。求解TSP問(wèn)題傳統(tǒng)的方法有窮舉搜索法、貪心法、動(dòng)態(tài)規(guī)劃法等，這些方法都面臨著這樣一個(gè)共同的問(wèn)題，即當(dāng)問(wèn)題的規(guī)模 N 大到一定程度時(shí)，問(wèn)題的計(jì)算量極大地超出了機(jī)器所能允許的極限。現(xiàn)代流行的智能算法主要有遺傳算法、郭濤算法、蟻群算法、粒子群優(yōu)化算法。

英國(guó)劍橋大學(xué)的Yang等在研究了布谷鳥(niǎo)的繁殖行為和萊維飛行特性之后于2009年創(chuàng)立了布谷鳥(niǎo)搜索（ Cuckoo Search， CS）算法，并用大量的函數(shù)對(duì)其性能進(jìn)行了測(cè)試，結(jié)果表明該算法在許多方面的性能已經(jīng)超過(guò)了微粒群算法和遺傳算法：CS算法具有全局搜索能力強(qiáng)、選用參數(shù)少、搜索路徑優(yōu)、多目標(biāo)問(wèn)題求解能力強(qiáng)等優(yōu)點(diǎn)。然而，原始的CS算法只能用于求解連續(xù)型的優(yōu)化問(wèn)題，不能用于求解離散型的優(yōu)化問(wèn)題如NP完全問(wèn)題。本文將原始的CS算法改進(jìn)成為二進(jìn)制布谷鳥(niǎo)搜索（Binary Cuckoo Search，BCS）算法，并應(yīng)用旅行商問(wèn)題（TSP）。

2 TSP問(wèn)題數(shù)學(xué)描述

TSP問(wèn)題（Traveling Salesman Problem），又稱旅行商問(wèn)題，每?jī)蓚€(gè)城市i和j之間的距離為Dij，城市行走的排列順序用數(shù)學(xué)符號(hào)表示為： X=（C1，C2，……Cn），目標(biāo)函數(shù) 。

3 求解TSP問(wèn)題的改進(jìn)的二進(jìn)制布谷鳥(niǎo)算法

3. 1 編碼方法

本文提采用的解碼方案如下：采用二進(jìn)制編碼，設(shè)TSP問(wèn)題有n個(gè)城市，則用長(zhǎng)度為r=n*[log2n ]個(gè)二進(jìn)制位代表一個(gè)染色體。設(shè)有一染色體的二進(jìn)制編碼為T={t1， t2，... tr}，其中ti=0或ti=1。解碼時(shí)，把T平均分成n段，然后把分別每一段看成一個(gè)二進(jìn)制數(shù)還原成相應(yīng)的整數(shù)，再對(duì)這n個(gè)整數(shù)從小到大排序，用相應(yīng)的位置當(dāng)成一條路徑中的城市編號(hào)。例如，設(shè)TSP問(wèn)題有5個(gè)城市，則染色體編碼的長(zhǎng)度為15，設(shè)其中一個(gè)染色體的編碼為[011010001010100]，解碼時(shí)，每3個(gè)二進(jìn)制編碼為一段，可化為有重復(fù)整數(shù)序列[3 2 1 2 4]，從小到大排序后，其相應(yīng)的位置為[4 2 1 3 5]，可看作無(wú)重復(fù)的城市編號(hào)解釋為一條回路。在此編碼方案下，采用二進(jìn)制的兩點(diǎn)交叉及均勻變異，不僅可以避免產(chǎn)生重復(fù)城市編號(hào)的問(wèn)題，而且產(chǎn)生的子代很好的繼承了父代的優(yōu)良路徑，使得種群得以進(jìn)化，并擴(kuò)大了搜索的空間。

3. 2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)設(shè)置為路徑的長(zhǎng)度，函數(shù)值越小，也就表示個(gè)體的適應(yīng)度越好。

3. 3 CS算法

布谷鳥(niǎo)搜索算法是由布谷鳥(niǎo)的寄宿孵生的繁殖行為和levy飛行機(jī)制演化而來(lái)的。在大自然中布谷鳥(niǎo)是一種會(huì)將自己的鳥(niǎo)蛋產(chǎn)在別的鳥(niǎo)類的巢穴里，讓別的鳥(niǎo)來(lái)幫助它孵化它的后代的寄宿繁殖的鳥(niǎo)類。布谷鳥(niǎo)產(chǎn)的蛋在別的鳥(niǎo)巢時(shí)很有可能會(huì)被發(fā)現(xiàn)，那么寄宿其他鳥(niǎo)巢孵化自己后代的計(jì)劃就失敗，只能另尋更好的鳥(niǎo)巢，如果宿主鳥(niǎo)沒(méi)有發(fā)現(xiàn)這個(gè)計(jì)劃的實(shí)施，就會(huì)幫布谷鳥(niǎo)孵化鳥(niǎo)蛋，并且布谷鳥(niǎo)幼雛會(huì)比宿主鳥(niǎo)先被孵化出來(lái)，只要布谷鳥(niǎo)幼鳥(niǎo)被孵化出來(lái)它就會(huì)將其他的鳥(niǎo)蛋從鳥(niǎo)巢里推出去，以助其加快成長(zhǎng)。Levy飛行在自然界中很多動(dòng)物和昆蟲(chóng)的飛行行為中普遍存在，比如在飛行過(guò)程中可能會(huì)突然轉(zhuǎn)一個(gè)90度的彎接著飛行。

布谷鳥(niǎo)搜索算法是在以下三個(gè)理想的假定前提下提出的：

（1）一只布谷鳥(niǎo)只產(chǎn)一個(gè)蛋，而且隨機(jī)的寄宿在某個(gè)被選中的鳥(niǎo)巢中；

（2）最好的鳥(niǎo)巢位置將被保留到下一代；

（3）布谷鳥(niǎo)能夠利用的多樣性的鳥(niǎo)巢數(shù)量是固定的n個(gè)，布谷鳥(niǎo)蛋被發(fā)現(xiàn)的概率為pa，pa∈[0，1]。

萊維飛行取決于由公式（3）和公式（5）產(chǎn)生的兩個(gè)正態(tài)分布的隨機(jī)數(shù)v，u，v，u可大可小，可正可負(fù)，故布谷鳥(niǎo)每次按Levy飛行機(jī)制隨機(jī)搜索的路徑長(zhǎng)短和方向都是高度隨機(jī)改變的，很容易從一個(gè)區(qū)域躍入到另一個(gè)區(qū)域，是個(gè)CS算法的全局多樣性特別強(qiáng)。另一方面，CS算法借鑒了布谷鳥(niǎo)的繁殖行為，定義布谷鳥(niǎo)蛋被宿主鳥(niǎo)發(fā)現(xiàn)的概率pm=0.25，不適應(yīng)環(huán)境的較差的布谷鳥(niǎo)蛋被淘汰，適應(yīng)環(huán)境的優(yōu)秀的布谷鳥(niǎo)蛋被孵化，保證新生的布谷鳥(niǎo)都是優(yōu)秀個(gè)體組成，使得CS算法具有較強(qiáng)的收斂性。

3. 4 BCS算法

原始的CS算法用于求解連續(xù)空間的優(yōu)化問(wèn)題，取得了很好的效果。欲將CS算法用于求解離散型的優(yōu)化問(wèn)題，須對(duì)其進(jìn)行二進(jìn)制改進(jìn)，已得到二進(jìn)制布谷鳥(niǎo)搜索（BCS）算法。

首先，用一個(gè)長(zhǎng)度為nc的二進(jìn)制編碼串來(lái)表示的m代第i個(gè)鳥(niǎo)巢第j維變量的值，那么 就表示第m代第i個(gè)鳥(niǎo)巢第j維變量的第k個(gè)二進(jìn)制編碼，其中k=1，2，..，nc。

其次，對(duì)Levy飛行每次位置更新的跳躍路徑step進(jìn)行二進(jìn)制代碼變換。按照Kennedy和Eberha 公式[1]變換得到Levy飛行的二進(jìn)制代碼變換公式為：

按照劉建華[2] 進(jìn)行變換則得到Levy飛行的二進(jìn)制代碼變換公式，當(dāng)Step<=0時(shí)為：

當(dāng)Step>0時(shí)為：

然后，采用二進(jìn)制編碼的混合更新方法。按照文獻(xiàn)[2]的分析可知，的分析可知，若只用式（5）和式（6）進(jìn)行二進(jìn)制編碼的更新，其全局多樣性很強(qiáng)，而幾乎沒(méi)有收斂性；而只用式（7）～式（11）進(jìn)行更新，其收斂性很強(qiáng)，但全局多樣性較弱。為使BCS算法的性能更好，在BCS算法中引人二進(jìn)制編碼控制系數(shù)pr ∈[0，1]，在算法的每一代均使用上述兩類公式對(duì)二進(jìn)制編碼進(jìn)行混合更新，得到BCS算法中Levy飛行的二進(jìn)制編碼混合更新方法為：

If rand（）<=pr

利用公式（5）和（6）對(duì)二進(jìn)制編碼進(jìn)行更新

Else

If Step<=0

利用公式（7）和（8）對(duì)二進(jìn)制編碼進(jìn)行更新

Else

利用公式（9）和（10）對(duì)二進(jìn)制編碼進(jìn)行更新

Endif

Endif

在混合更新時(shí)：若pr越大，則BCS算法的全局多樣性就越強(qiáng)；若pr越小，則BCS算法的收斂性越強(qiáng)。

最后保留布谷鳥(niǎo)蛋被淘汰的機(jī)制，即設(shè)定布谷鳥(niǎo)蛋被宿主鳥(niǎo)發(fā)現(xiàn)而淘汰的概率為pa，以保證BCS算法的收斂性。

3.5 貪心算法求解TSP問(wèn)題

貪心算法通常包含用來(lái)尋找具備最優(yōu)的迭代過(guò)程，在很少的計(jì)算基礎(chǔ)上作出相對(duì)正確的猜想而不著急去考慮后面的情況，這樣一步一步的來(lái)構(gòu)造解，每一步都是找到局部最優(yōu)解的后，在最優(yōu)解的基礎(chǔ)上，并且每走一步都會(huì)擴(kuò)大部分解的規(guī)模，每次的選擇都能產(chǎn)生最大的直接收益，同時(shí)還能保持穩(wěn)定性可行性。

在求解最短路徑時(shí)，設(shè)G（V，E）是以一個(gè)每條邊有非負(fù)長(zhǎng)度的有向圖，有一個(gè)源點(diǎn)v，要確定從v到V中每個(gè)其他頂點(diǎn)的距離，這里從頂點(diǎn)v到頂點(diǎn)x的距離定義為從v到x的路徑長(zhǎng)度。假設(shè)V={1，2，3，...，n}，并且v=1。首先將頂點(diǎn)分為兩個(gè)集合X={1}和Y={2，3，4，...，n}。從源點(diǎn)到這些點(diǎn)的距離都是確定的，在接下來(lái)的每一步中，將選定源點(diǎn)到它的距離已經(jīng)獲得的一個(gè)頂點(diǎn)y，y屬于Y，并將y移動(dòng)到X中。

在實(shí)際生活中的最短路徑問(wèn)題認(rèn)為兩兩城市之間都有通路且沒(méi)有方向，根據(jù)三角形定理，兩邊之和必然會(huì)大于第三邊，因此不會(huì)出現(xiàn)更新在Y中與y相鄰的頂點(diǎn)的邊的權(quán)值。因此引入在該算法中的貪心思想為：確定一個(gè)城市坐標(biāo)為源點(diǎn)放在s中，然后從剩下的城市中找到與源點(diǎn)城市距離最小的城市移入s中。再將剛放入到s中的頂點(diǎn)去剩下的城市中搜索跟它距離最短的城市，并將找到的城市放入s中，以此類推將所有的城市都移入到s中。

原始貪心算法的流程如下。

Step1：將源點(diǎn)1移入X中，Y中的頂點(diǎn)個(gè)數(shù)為V-1，λ [1]=0。

Step2：對(duì)于每個(gè)屬于Y的頂點(diǎn)v，如果存在從1到頂點(diǎn)v的邊，則令λ [v]為邊的長(zhǎng)度；否則令λ [v]為無(wú)窮大，并設(shè)λ [1]=0。

Step3：while Y ≠{}

Step4： 令y Y，使得λ [y]為最小

Step5： 將y從Y移動(dòng)到X

Step6： 更新那些在Y中與y相鄰的頂點(diǎn)的標(biāo)記

For每條邊（y，w）

If w ∈Y and λ[y]+length[y，w]< λ [w] then

λ [w]=λ [y]+length[y，w]

End for

Step7：end while

在實(shí)際生活中，經(jīng)過(guò)的城市存放在s中，初始化是讓所有城市都不在s中即s[x]=0，表示編號(hào)為x的城市不在s中，若s[x]=1，表示編號(hào)為x的城市在s中。D是存儲(chǔ)最短路徑的城市順序的編號(hào)。

設(shè)源點(diǎn)為v，流程如下。

Step1：s[v]=1，D[0]=v； m=v； //m是存儲(chǔ)將要移入s中的城市的編號(hào)。

Step2：for n從1到CityNum

Step3： 從其他剩余的城市里找到與源點(diǎn)城市距離最小的城市d

Step4： D[n]=d；m=d；s[m]=1； //將編號(hào)為m的城市放入s中

Step5：end for

Step6：輸出D。

3. 6 BCS結(jié)合貪心算法解決TSP的算法流程

Step1：給定參數(shù)pa和pr，隨機(jī)產(chǎn)生n個(gè)染色體作為初始種群。（同樣也是當(dāng)前最優(yōu)群體）染色體為二進(jìn)制編碼，編碼長(zhǎng)度如上所述。

Step2 ：對(duì)染色體進(jìn)行解碼，方法如上所述，進(jìn)行適應(yīng)度評(píng)估。得到初始群體的最優(yōu)值作為全局最優(yōu)解（bestindividual）。

Step3 ：在給定的pr下，將Levy飛行的路徑Step按公式（5）～（10）進(jìn)行二進(jìn)制代碼變換后，采用二進(jìn)制編碼混合更新。產(chǎn)生新的種群規(guī)模為n的布谷鳥(niǎo)群體，對(duì)新找到的n個(gè)鳥(niǎo)巢進(jìn)行解碼，之后進(jìn)行適應(yīng)度評(píng)價(jià)，并同當(dāng)前的群體的每個(gè)個(gè)體比較，得到當(dāng)前最優(yōu)解（bestindividual），和最優(yōu)群體。

Step4：產(chǎn)生服從均勻分布的隨機(jī)數(shù)rand（）∈[0，1]，與布谷鳥(niǎo)蛋被發(fā)現(xiàn)的概率pa進(jìn)行比較，若rand（）>pa，則應(yīng)用這個(gè)個(gè)體與當(dāng)前最優(yōu)個(gè)體進(jìn)行多點(diǎn)交叉，并且進(jìn)行換位變異的方法（為了保證進(jìn)化前期的穩(wěn)定性和防止后期進(jìn)化的陷入局部最優(yōu)解，所以前期變異概率小，后期變異概率適當(dāng)增大），得到新的位置，否則不變。

Step5：為了增強(qiáng)算法的收斂性，在算法的后期每隔100代，對(duì)群體的10%進(jìn)行一次貪心算法，優(yōu)化一下群體。這樣即增強(qiáng)的收斂性，也不影響算法搜索的全局多樣性。

Step6：回到步驟2 重復(fù)迭代，直到達(dá)到最大迭代次數(shù)。即算法結(jié)束，輸出最優(yōu)解bestindividual。

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

4.1 實(shí)驗(yàn)條件和測(cè)試集

（1）實(shí)驗(yàn)條件

實(shí)驗(yàn)條件如表4-1所示。

（2）測(cè)試集

為了最好地說(shuō)明本文算法的有效性，本文選用了國(guó)際上最通用的 TSP 測(cè)試庫(kù) TSPLIB（http：//elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html）中的多個(gè)問(wèn)題實(shí)例進(jìn)行測(cè)試，每個(gè)問(wèn)題的求解均運(yùn)行本算法10 次。以下給出了每個(gè)問(wèn)題求解時(shí)的參數(shù)設(shè)置，以及10次運(yùn)行每次所得的最優(yōu)值，10次運(yùn)行的平均路徑，并和TSPLIB中公布的最短路徑進(jìn)行了對(duì)比。

4.2 試驗(yàn)參數(shù)和結(jié)果

（1）試驗(yàn)參數(shù)的設(shè)置

實(shí)驗(yàn)參數(shù)的設(shè)置如表4-2所示。

（2）實(shí)驗(yàn)結(jié)果

先對(duì)pr76進(jìn)行將問(wèn)題執(zhí)行十次的結(jié)果進(jìn)行羅列，并與其他算法進(jìn)行比較。

表4-2 eil76運(yùn)行10的結(jié)果及平均值、最優(yōu)值及與其他算法和tsplib公布的最優(yōu)值的對(duì)比

（3）與其他算法比較

將本文算法中的得到的結(jié)果跟其他算法求解TSP問(wèn)題的結(jié)果以及TSPLIB公布的最優(yōu)的結(jié)果進(jìn)行比較。

對(duì)于文中用到比較數(shù)據(jù)進(jìn)行如下說(shuō)明：

在下表中MPSO、MFFA、FFA和GN算法得出的結(jié)果出自參考文獻(xiàn)[3]。在此文獻(xiàn)中，GA，TS，PSO算法來(lái)自于TSP問(wèn)題數(shù)據(jù)集合目錄（標(biāo)準(zhǔn)測(cè)試集）。為了排除隨機(jī)性每個(gè)算法都運(yùn)行了25次，本文取其最優(yōu)值進(jìn)行比較；MACO算法出自于參考文獻(xiàn)[8]，TSPLIB最有解來(lái)自于TSPLIB最新公布的最優(yōu)解。

改進(jìn)后的BCS算法在經(jīng)過(guò)上一節(jié)中測(cè)試后與原始的布谷鳥(niǎo)搜索算法、其他的比較新穎的算法以及TSPLIB公布的數(shù)據(jù)比較的結(jié)果如表4- 3所示。

5 結(jié)論

經(jīng)過(guò)以上各表的分析我們發(fā)現(xiàn)在解決中TSP問(wèn)題時(shí)，本算法表現(xiàn)出優(yōu)越的性能，其收斂速度和收斂精度都有不小的提高。雖然和tsplib公布的最優(yōu)解還有些差距，但是比起GA，POS等算法，還是有很大的優(yōu)勢(shì)的。進(jìn)而證實(shí)了改進(jìn)的二進(jìn)制布谷鳥(niǎo)搜索算法具有一定的可行性和有效性。

參考文獻(xiàn)：

[1]KENNEDY J，EBERHARTR.Particle swarm optimization[C]//Proceedings of the IEEE International Conference on Neural Networks.Pisalaway：IEEE，1995：1942-1948

[2]劉建華.粒子群算法的基本理論及其改進(jìn)研究[D].長(zhǎng)沙：中南大學(xué)，2009：77-98

[3]王忠英，白艷萍，岳利霞.經(jīng)過(guò)改進(jìn)的求解TSP問(wèn)題的蟻群算法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2012，2