改進二進制布谷鳥搜索算法求解TSP問題

姜保強

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

關鍵詞：二進制；布谷鳥搜索算法；旅行商問題；貪心算法

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（旅行商）問題是指已知n個城市之間的相互距離，尋找一條遍訪n個城市，每個城市只訪問一次。最終又回到出發城市的最短旅行路線。這是一個典型的組合優化問題，被證明是NP完全問題，其所有的路線數為n，搜索空間隨著城市數n的增大而迅猛增大，這就產生了所謂的“組合爆炸”問題。目前還沒有一種完全有效的算法解決TSP問題。由于TSP問題有很高的理論價值和實際應用背景，如何以用來解決分配、調度和網絡優化問題等，所以人們一直致力于研究新的算法達到高效求解TSP問題。求解TSP問題傳統的方法有窮舉搜索法、貪心法、動態規劃法等，這些方法都面臨著這樣一個共同的問題，即當問題的規模 N 大到一定程度時，問題的計算量極大地超出了機器所能允許的極限?，F代流行的智能算法主要有遺傳算法、郭濤算法、蟻群算法、粒子群優化算法。

英國劍橋大學的Yang等在研究了布谷鳥的繁殖行為和萊維飛行特性之后于2009年創立了布谷鳥搜索（ Cuckoo Search， CS）算法，并用大量的函數對其性能進行了測試，結果表明該算法在許多方面的性能已經超過了微粒群算法和遺傳算法：CS算法具有全局搜索能力強、選用參數少、搜索路徑優、多目標問題求解能力強等優點。然而，原始的CS算法只能用于求解連續型的優化問題，不能用于求解離散型的優化問題如NP完全問題。本文將原始的CS算法改進成為二進制布谷鳥搜索（Binary Cuckoo Search，BCS）算法，并應用旅行商問題（TSP）。

2 TSP問題數學描述

TSP問題（Traveling Salesman Problem），又稱旅行商問題，每兩個城市i和j之間的距離為Dij，城市行走的排列順序用數學符號表示為： X=（C1，C2，……Cn），目標函數 。

3 求解TSP問題的改進的二進制布谷鳥算法

3. 1 編碼方法

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

3. 2 適應度函數

適應度函數設置為路徑的長度，函數值越小，也就表示個體的適應度越好。

3. 3 CS算法

布谷鳥搜索算法是由布谷鳥的寄宿孵生的繁殖行為和levy飛行機制演化而來的。在大自然中布谷鳥是一種會將自己的鳥蛋產在別的鳥類的巢穴里，讓別的鳥來幫助它孵化它的后代的寄宿繁殖的鳥類。布谷鳥產的蛋在別的鳥巢時很有可能會被發現，那么寄宿其他鳥巢孵化自己后代的計劃就失敗，只能另尋更好的鳥巢，如果宿主鳥沒有發現這個計劃的實施，就會幫布谷鳥孵化鳥蛋，并且布谷鳥幼雛會比宿主鳥先被孵化出來，只要布谷鳥幼鳥被孵化出來它就會將其他的鳥蛋從鳥巢里推出去，以助其加快成長。Levy飛行在自然界中很多動物和昆蟲的飛行行為中普遍存在，比如在飛行過程中可能會突然轉一個90度的彎接著飛行。

布谷鳥搜索算法是在以下三個理想的假定前提下提出的：

（1）一只布谷鳥只產一個蛋，而且隨機的寄宿在某個被選中的鳥巢中；

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

（3）布谷鳥能夠利用的多樣性的鳥巢數量是固定的n個，布谷鳥蛋被發現的概率為pa，pa∈[0，1]。

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

3. 4 BCS算法

原始的CS算法用于求解連續空間的優化問題，取得了很好的效果。欲將CS算法用于求解離散型的優化問題，須對其進行二進制改進，已得到二進制布谷鳥搜索（BCS）算法。

首先，用一個長度為nc的二進制編碼串來表示的m代第i個鳥巢第j維變量的值，那么 就表示第m代第i個鳥巢第j維變量的第k個二進制編碼，其中k=1，2，..，nc。

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

按照劉建華[2] 進行變換則得到Levy飛行的二進制代碼變換公式，當Step<=0時為：

當Step>0時為：

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

If rand（）<=pr

利用公式（5）和（6）對二進制編碼進行更新

Else

If Step<=0

利用公式（7）和（8）對二進制編碼進行更新

Else

利用公式（9）和（10）對二進制編碼進行更新

Endif

Endif

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

最后保留布谷鳥蛋被淘汰的機制，即設定布谷鳥蛋被宿主鳥發現而淘汰的概率為pa，以保證BCS算法的收斂性。

3.5 貪心算法求解TSP問題

貪心算法通常包含用來尋找具備最優的迭代過程，在很少的計算基礎上作出相對正確的猜想而不著急去考慮后面的情況，這樣一步一步的來構造解，每一步都是找到局部最優解的后，在最優解的基礎上，并且每走一步都會擴大部分解的規模，每次的選擇都能產生最大的直接收益，同時還能保持穩定性可行性。

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

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

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

Step1：將源點1移入X中，Y中的頂點個數為V-1，λ [1]=0。

Step2：對于每個屬于Y的頂點v，如果存在從1到頂點v的邊，則令λ [v]為邊的長度；否則令λ [v]為無窮大，并設λ [1]=0。

Step3：while Y ≠{}

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

Step5： 將y從Y移動到X

Step6： 更新那些在Y中與y相鄰的頂點的標記

For每條邊（y，w）

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

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

End for

Step7：end while

在實際生活中，經過的城市存放在s中，初始化是讓所有城市都不在s中即s[x]=0，表示編號為x的城市不在s中，若s[x]=1，表示編號為x的城市在s中。D是存儲最短路徑的城市順序的編號。

設源點為v，流程如下。

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

Step2：for n從1到CityNum

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

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

Step5：end for

Step6：輸出D。

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

Step1：給定參數pa和pr，隨機產生n個染色體作為初始種群。（同樣也是當前最優群體）染色體為二進制編碼，編碼長度如上所述。

Step2 ：對染色體進行解碼，方法如上所述，進行適應度評估。得到初始群體的最優值作為全局最優解（bestindividual）。

Step3 ：在給定的pr下，將Levy飛行的路徑Step按公式（5）～（10）進行二進制代碼變換后，采用二進制編碼混合更新。產生新的種群規模為n的布谷鳥群體，對新找到的n個鳥巢進行解碼，之后進行適應度評價，并同當前的群體的每個個體比較，得到當前最優解（bestindividual），和最優群體。

Step4：產生服從均勻分布的隨機數rand（）∈[0，1]，與布谷鳥蛋被發現的概率pa進行比較，若rand（）>pa，則應用這個個體與當前最優個體進行多點交叉，并且進行換位變異的方法（為了保證進化前期的穩定性和防止后期進化的陷入局部最優解，所以前期變異概率小，后期變異概率適當增大），得到新的位置，否則不變。

Step5：為了增強算法的收斂性，在算法的后期每隔100代，對群體的10%進行一次貪心算法，優化一下群體。這樣即增強的收斂性，也不影響算法搜索的全局多樣性。

Step6：回到步驟2 重復迭代，直到達到最大迭代次數。即算法結束，輸出最優解bestindividual。

4 實驗結果

4.1 實驗條件和測試集

（1）實驗條件

實驗條件如表4-1所示。

（2）測試集

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

4.2 試驗參數和結果

（1）試驗參數的設置

實驗參數的設置如表4-2所示。

（2）實驗結果

先對pr76進行將問題執行十次的結果進行羅列，并與其他算法進行比較。

表4-2 eil76運行10的結果及平均值、最優值及與其他算法和tsplib公布的最優值的對比

（3）與其他算法比較

將本文算法中的得到的結果跟其他算法求解TSP問題的結果以及TSPLIB公布的最優的結果進行比較。

對于文中用到比較數據進行如下說明：

在下表中MPSO、MFFA、FFA和GN算法得出的結果出自參考文獻[3]。在此文獻中，GA，TS，PSO算法來自于TSP問題數據集合目錄（標準測試集）。為了排除隨機性每個算法都運行了25次，本文取其最優值進行比較；MACO算法出自于參考文獻[8]，TSPLIB最有解來自于TSPLIB最新公布的最優解。

改進后的BCS算法在經過上一節中測試后與原始的布谷鳥搜索算法、其他的比較新穎的算法以及TSPLIB公布的數據比較的結果如表4- 3所示。

5 結論

經過以上各表的分析我們發現在解決中TSP問題時，本算法表現出優越的性能，其收斂速度和收斂精度都有不小的提高。雖然和tsplib公布的最優解還有些差距，但是比起GA，POS等算法，還是有很大的優勢的。進而證實了改進的二進制布谷鳥搜索算法具有一定的可行性和有效性。

參考文獻：

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

[2]劉建華.粒子群算法的基本理論及其改進研究[D].長沙：中南大學，2009：77-98

[3]王忠英，白艷萍，岳利霞.經過改進的求解TSP問題的蟻群算法[J].數學的實踐與認識，2012，2