Discrete cuckoo search algorithm for the travelling salesman problem
摘要
本文提出了一種改進的離散杜鵑搜尋（CS）算法，用于求解著名的旅行商問題（TSP），這是一個NP難的組合優化問題。CS是一種元啟發式搜尋算法，最近由楊欣社（Xin She Yang）和蘇亞什德（Suash Deb）在2009年受杜鵑繁殖行為啟發而開發。事實證明，這種新算法在解決連續優化問題時非常有效。現在，我們通過重建CS種群并引入一類新的杜鵑來擴充和改進CS，以便它能夠解決組合問題以及連續問題。提出的離散布谷鳥搜尋（DCS）的性能是根據著名TSPLIB庫中的一組對稱TSP基準測試的。測試結果表明，分布式控制系統優于其他一些元啟發式算法。
介紹
優化問題，無論是單目标還是多目标，通常都很難解決。其中許多問題被稱為NP難問題，在實際可接受的時間範圍内，任何已知算法都無法有效解決。事實上，許多看似簡單的問題都很難解決，因為組合的數量随着感興趣問題的規模呈指數級增長；搜尋每一種可能的組合都是極其複雜且不現實的。最著名的例子可能是旅行推銷員問題（TSP），其中推銷員打算隻通路一次多個城市，然後傳回起點，同時最小化總旅行距離或旅行總成本。TSP是組合優化中研究最廣泛的問題之一。它屬于NP難優化問題[2]，其計算複雜性随城市數量呈指數級增加。它通常用于測試優化算法。此外，TSP及其變體有幾個重要的應用[19,25]，例如印刷電路闆鑽孔、X射線結晶學、計算機布線、車輛路線和排程、機器人控制等。是以，解決這類問題不僅具有學術意義，而且具有現實意義，是以，它一直是積極研究的重要課題。
對于TSP及其所有相關變體或同類問題，不存在有效的算法。快速找到這些問題的好（不一定是最優）解決方案的需要導緻了各種近似算法的發展，如元啟發式[3,14]。另一方面，元啟發式算法已經證明了它們在解決問題方面的潛力和有效性，與傳統算法相比具有許多優勢。兩個優點是簡單性和靈活性。元啟發式算法通常易于實作，但它們通常可以解決複雜的問題，是以可以适用于解決許多實際優化問題，從運籌學、工程到人工智能等領域[10、11、12、36]。此外，這些算法非常靈活，可以處理具有不同目标函數性質的問題，無論是連續的、離散的還是混合的。這種靈活性還使它們能夠同時處理大量參數。
元啟發式算法使用搜尋政策來更有效地探索搜尋空間，通常關注搜尋空間中一些有前途的區域。這些方法從一組初始解或初始總體開始，然後逐漸檢查一系列解決方案，以達到或希望接近感興趣問題的最佳解決方案。在最流行的元啟發式算法中，我們可以列出一長串，舉幾個例子，遺傳算法（GA）、禁忌搜尋（TS）、模拟退火（SA）、格洛弗和科欽伯格[14]中提出的蟻群優化（ACO）以及粒子群優化（PSO）[16]。蜂群優化（BCO）[30]、猴子搜尋算法（MS）[22]、和諧搜尋算法（HS）[13]、螢火蟲算法（FA）[32]、智能水滴（IWD）[26]、蝙蝠啟發算法（BA）[33]、杜鵑搜尋（CS）[34]和磷蝦群（KH）[9]是最近提出的元啟發式算法。這些元啟發式大多是受自然啟發的，模仿了潛在生物、實體或社會系統的成功特征。這些方法在解決各種問題（如組合優化問題）方面的成功來自于相對容易的實作、對實際應用的良好适應和對其限制的适當考慮，以及産生高品質的解決方案[29]。然而，有些算法可以比其他算法更好地解決某些特定問題。是以，沒有特定的算法來解決所有優化問題。是以，開發新的元啟發式仍然是一個巨大的挑戰，特别是對于難處理的NP難問題[31]。
各種研究人員已經将許多元啟發式算法應用于求解TSP，如SA[4]、TS[20]、GA[17]、ACO[8]、離散粒子群優化（DPSO）[27]、，遺傳-模拟退火蟻群系統與粒子群優化技術（GSAACS-PSOT）[6]和模糊粒子群優化與模拟退火和鄰域資訊（PSO-NIC-SA）[1]。本文介紹了一種新的杜鵑搜尋變體（CS），以改進和有效解決對稱TSP問題。CS是一種元啟發式搜尋算法，最近由Yang和Deb于2009年開發[34,35]。這種新算法已被證明在解決連續優化問題時非常有效。受一些杜鵑物種專性繁殖寄生行為的啟發，再加上描述許多動物和昆蟲采食模式的勒維飛行，CS是自然啟發的元啟發式的一個很好的例子。與遺傳算法（GA）和粒子群優化（PSO）相比，CS的特點還在于減少了參數的數量，并為多峰函數提供了有效的結果[35]。
本文結構如下：。2首先簡要介紹了标準CS，然後描述了對CS靈感來源進行的改進。第3節簡要介紹TSP。第4節描述了求解對稱TSP的離散CS。第5節詳細介紹了TSPLIB庫中所謂對稱TSP的一組基準的數值實驗結果[24]。最後，Sect。6最後進行了一些讨論。
2布谷鳥搜尋算法（CS）
2.1基本CS
在杜鵑物種的許多有趣特征中，杜鵑的一個顯著特征是一些物種參與所謂的卵寄生。雌性杜鵑在另一物種的巢穴中産卵，以讓寄主鳥孵化和孵化幼小的杜鵑雛鳥。為了增加新杜鵑的機率，降低寄主鳥放棄卵的機率，杜鵑（雌鳥、雄鳥和幼鳥）使用了幾種政策[23]。在标準杜鵑搜尋算法（CS）[34]中，杜鵑通過Leövy航班搜尋新的巢穴。法國數學家保羅·勒維裡（Paul Leövy）命名的勒維裡飛行代表了一種随機行走模型，其特征是步長服從幂律分布。幾項科學研究表明，獵人尋找獵物的過程通常遵循勒維飛行的相同特征。機動飛行廣泛用于優化和許多科學領域。
istic搜尋算法是最近由楊欣社（Xin She Yang）和Suash Deb于2009年開發的，最初是為求解多峰函數而設計的。算法1所示的CS是圍繞以下理想規則[34]進行總結的：（1）每隻杜鵑每次産一個卵，随機選擇一個巢；（2） 最好的巢和最高品質的蛋可以傳給新一代；（3） 寄主巢的數量是固定的，寄主鳥可以發現杜鵑産卵的機率為p a 2[0,1]。以下等式（1）用于産生杜鵑i的新解x i（t？1），byaLeívy航班：xðtþ1Þi¼x \240；t \222»i \254»a Levy \240；s；kð1Þ其中a（a[0）是步長。在一般情況下，a應該與感興趣的問題的尺度相關聯，盡管a=O（1）可以在許多情況下使用。步長遵循Leövy分布Levy \240；s；k \222；s k；०1\k3 \2406\k2 \222；，它具有無窮方差和無窮平均值[34]。這裡，s是從Le´中得出的步長。
2.2改進的CS
CS成功地證明了其優越的性能，與PSO和GA（求解多峰函數）相比，它在探索解空間方面具有更好的政策。勒維航班加強了這一戰略，它在控制集約化和多樣化之間的平衡方面發揮着重要作用。參數數量的減少使CS更加通用[34]。從靈感來源和算法本身來看，CS仍有一些改進的空間。CS的優勢在于如何通過布谷鳥開發和探索解決方案空間。這種杜鵑可以有一些“智慧”，以便找到更好的解決方案。是以，我們可以通過杜鵑在搜尋空間中的移動來控制強化和多樣化。拟議的改進将布谷鳥視為控制強化和多樣化的第一級，由于這種布谷鳥是種群中的一個個體，我們可以将種群限定為第二級控制，可以通過添加一種新的布谷鳥類别，使其搜尋更智能、更高效來進行重組。
研究表明，杜鵑還可以對可能成為宿主的巢穴進行某種監測[23]。這種行為可以作為一種靈感，創造出一種新的杜鵑種類，這種杜鵑能夠在孵化期間改變寄主巢，以避免蛋被遺棄。這些杜鵑在育雛前後都會使用一些機制，例如觀察寄主巢穴，以決定巢穴是否是最佳選擇（是以，它為ase尋找一個更好的新巢，我們可以談論一種由目前解決方案周圍的一小部分杜鵑執行的本地搜尋。為了簡單起見，我們可以将這一新的杜鵑部分在我們建議的方法中采用的機制分為兩個主要步驟：（1）杜鵑，最初由Leövy航班移動到一個新的解決方案（代表一個新領域）；（2） 從目前的解決方案來看，同一地區的杜鵑鳥尋求一種新的、更好的解決方案。根據這兩個步驟，我們可以看到，在CS的标準算法中可以直接引入帶有新分數pc的搜尋機制。是以，改進的CS算法（算法2）的總體可以用三個方面來構造。
1.可以在人群中随機選擇可能包含比個人解決方案好得多的新解決方案的區域；
2.一小部分杜鵑鳥尋求新的解決方案，而不是最好的解決方案；
3.杜鵑鳥中的一小部分人從目前位置尋找解決方案，并試圖加以改進。他們通過勒維航班從一個地區移動到另一個地區，以在每個地區找到最佳解決方案，而不會被困。
這一改進的目标是加強圍繞人群最佳解決方案的密集搜尋，同時，應适當使用随機化來探索使用Leövy航班的新領域。是以，标準CS的擴充是添加了一個處理智能杜鵑的分數“pc”的方法。我們可以預期，新的布谷鳥種類使CS能夠以更少的疊代來更高效地執行。在TSP的情況下，它可以更好地抵抗任何潛在陷阱和局部最優停滞。這使得CS适應TSP能夠以較少的參數對集約化和多樣化進行更多的控制。CS用于求解對稱TSP的适應性在第4節中進行了描述。
4. 用CS解決TSP
我們目前工作的主要思想是，改進後的CS尋求在Leövy航班指定的區域使用本地搜尋找到的好的解決方案。我們可以說，改進的CS和本地搜尋這兩種方法在尋找高品質的解決方案方面構成了一個單一的實體。局部搜尋的缺點是很可能陷入局部最優。這可以通過使用我們改進的CS很容易地得到加強，該CS需要按區域而不是按解決方案進行位移，進而将陷入局部最優的可能性降至最低。擴充CS以解決旅行商問題（TSP）的目标之一是保持其主要優勢，并将這些優勢內建到改進CS的離散版本中。将CS改編為TSP的過程主要側重于重新解釋基本CS中使*用的術語。CS及其靈感來源可以用以下五個主要元素來建構和解釋：蛋、巢、目标函數、搜尋空間和Leívy航班。這些關鍵要素對組合問題具有重要意義。
4.1雞蛋
如果我們假設布谷鳥在一個巢中隻産一個蛋，我們可以賦予蛋以下特性：
–巢中的蛋是由種群中的一個個體代表的解決方案；
杜鵑鳥蛋是人口中某個地方/地點的一種新的解決方案候選。
我們可以說雞蛋相當于哈密頓循環。在這裡，我們忽略了所有線路的出發城市，也忽略了推銷員的旅行方向。
4.2巢穴
在CS中，可以對嵌套施加以下特征：
–巢數是固定的；
–巢是種群中的一個個體，巢的數量等于種群的大小；
–廢棄巢穴是指用新巢穴替換種群中的一個個體。
通過這些特征在TSP上的投影，我們可以說巢穴在種群中表現為具有自己哈密頓循環的個體。顯然，一個巢可以有多個蛋，以備将來擴充。在本論文中，為了簡單起見，每個巢隻有一個蛋。
4.3目标函數
搜尋空間中的每個解決方案都與一個數字目标值相關聯。是以，解的品質與目标函數的值成正比。在CS中，一個品質更好的雞蛋将造就新一代。這意味着杜鵑卵的品質與它産生新杜鵑的能力直接相關。對于旅行商問題，解的品質與哈密頓環的長度有關。最佳解是哈密頓環最短的解。
4.4搜尋空間
在二維情況下，搜尋空間表示潛在巢穴的位置。這些位置是ðx；yࢮ2R R。要更改嵌套的位置，隻需修改其坐标的實際值。很明顯，移動巢穴或巢穴位置并不會施加真正的限制。大多數連續優化問題都是這種情況，這可以被視為一種優勢，可以避免許多技術障礙，例如TSP解空間中的坐标表示，特别是在将解從一個鄰域移動到另一鄰域的機制中。城市坐标是被訪城市的固定坐标；然而，城市之間的參觀順序可以改變
4.4.1在搜尋空間内移動
由于城市的坐标是固定的，是以移動基于通路城市的順序。有幾種方法、運算符或擾動可以通過更改通路城市的順序，從另一個現有解決方案生成新的解決方案。在CS适應TSP的過程中，我們有一個離散的CS，其中用于改變通路城市順序的擾動是2-opt移動[7]和雙橋移動[21]。2-opt移動方法用于小擾動，而大擾動則通過雙橋移動來實作。如圖1所示，2-opt移動從巡更中移除兩條邊（解或哈密頓循環），并重新連接配接建立的兩條路徑。雙橋移動切割四條邊并引入四條新邊，如圖2所示。
4.4.2鄰裡
在連續問題中，鄰裡的含義是顯而易見的。然而，對于組合問題，鄰域的概念要求給定解的鄰域必須由最小擾動産生。這種擾動必須使解的變化最小，我們可以删除的非連續邊的最小數目是兩條。是以，2-opt移動是這種擾動的一個很好的候選者。
.4.3步長移動的步長是兩個溶液之間的距離。它基于空間拓撲和鄰域概念。步長與解決方案上連續2-opt移動的次數成正比。一個大的進步表現為雙橋移動
4.5勒維航班勒維航班的特點是圍繞解決方案進行密集搜尋，然後從長遠來看，偶爾會有重大進展。根據Yang和Deb[34]的說法，在一些優化問題中，通過Leövy航班尋找新的最佳解決方案更有效。為了提高搜尋品質，我們将步長與标準CS中概述的Leívy航班生成的值相關聯。
5實驗結果
提出的基本和改進的離散布谷鳥搜尋（DCS）算法在TSP的一些執行個體（基準）上進行了測試，這些執行個體取自公共電子圖書館TSPLIB中的TSP問題[24]。TSPLIB中包含的大多數執行個體已經在文獻中解決，其優化結果可用于比較算法。41個執行個體的規模從51到1379個城市不等。在Reinelt[24]中，所有這些TSP執行個體都屬于歐氏距離類型。TSP執行個體為城市提供坐标。實*、例名稱中的數值表示提供的城市數，例如，名為eil51的執行個體有51個城市。
首先對基本DCS和改進的DCS這兩種算法進行了比較。然後，将改進的DCS算法與其他一些最近的方法（帶有粒子群優化技術的遺傳模拟退火蟻群系統（GSAACS-PSOT）[6]和離散粒子群優化（DPSO）[27]）進行了比較。注意，在Chen和Chien[6]中，作者将他們提出的方法與文獻中用于求解TSP的其他元啟發式算法進行了比較。
我們已經在32位Vista作業系統下使用Java實作了基本/标準和改進的DCS算法。實驗在一台配備Intel（R）CoreTM 2 Duo 2.00 GHz CPU和3 GB RAM的筆記本電腦上進行。在一些初步試驗的基礎上，選擇了該算法的參數值。這兩種算法（基本和改進DCS）中選擇的參數是在解決方案品質和計算時間方面提供最佳結果的值。實驗中使用的參數設定如表1所示。在每個案例研究中，使用這些參數進行30次獨立的算法運作。圖3顯示，兩種算法的最大疊代次數（MaxGeneration）都可以設定為500。
表2和表3總結了實驗結果，其中第一列顯示執行個體名稱，“opt”列顯示從TSPLIB中提取的最佳解長度，“best”列顯示每個算法找到的最佳解的長度，“average”列給出每個算法30次獨立運作的平均解長度，“最差”列顯示了每種算法找到的最差解的長度，“PDav（%）”清單示平均解長度與30次最優解長度的偏差百分比，“PDbest（%））”列給出了最佳解長度與三十次最優解長的偏差百分比，“time”列顯示30次跑步的平均時間（以秒為機關）。溶液與最佳已知溶液（或最佳溶液，如果已知）的偏差百分比由以下公式給出：
表2中給出了基本DCS算法與改進DCS算法的比較實驗結果。從表3和圖4中可以看出，改進後的DCS在PDav（%）和PDbest（%）方面均優于基本DCS。改進後的DCS獲得14個TSP執行個體的最小值。改進後的DCS相對于基本DCS的高性能可能是由于新型杜鵑鳥對基本DCS的改進，這種杜鵑有一種有效的方法，可以通過從一個區域移動到另一個區域來尋找每個區域的最佳解決方案。
表3給出了改進的DCS算法在41個TSPLIB執行個體上的計算結果。“SD”清單示标準偏差，當發現的所有解決方案在30次運作中具有相同長度時，該标準偏差采用以粗體顯示的值0.00，而“C 1%/C opt”列給出了在1%最佳性（超過30次運作）範圍内的解決方案數/最佳解決方案數。關于PDbest（%），我們可以說90.24%的PDbest值（%）小于0.5%，這意味着在30次試驗中，找到的最佳解決方案大約小于最佳已知解決方案的0.5%，而PDav（%）列中以粗體顯示的0.00值表示在30次試驗中找到的所有解決方案與最佳已知解決辦法的長度相同。表3中的數值表明，改進後的DCS确實可以在合理的時間内提供良好的解決方案。
在表4和表5中，将改進的DCS算法與GSA-ACS-PSOT和DPSO兩種方法的實驗結果進行了比較。這兩種方法的結果直接總結自原始論文6,27]。從表4和表5可以清楚地看出，在解決所有十八/五個測試的TSP執行個體時，DCS優于其他兩種算法（GSA-ACS-PSOT和DPSO）。所提出的DCS算法獲得了十五/五個最佳解，而GSA-ACS-PSOT/DPSO在十八/五個TSP執行個體中僅獲得十一/二個最佳解。此外，我們發現表4/5中GSA-ACS-PSOT/DPSO算法的SDs/PDav（%）s平均值等于161.55/3.54，而我們提出的DCS算法的SDs/PDav平均值等于31.28/0.00。圖5顯示了18個不同大小的執行個體的兩種算法改進的DCS和GSA-ACS-PSOT的PDav的百分比。從圖5可以看出，我們提出的DCS算法的SDs/PDav（%）s的下曲線ge等于31.28/0.00。圖5顯示了18個不同大小執行個體的兩種算法改進的DCS和GSA-ACS-PSOT的PDav值（%）。從圖5可以看出，就解決方案品質而言，與改進的DCS算法相關的較低曲線更好。這基本上可以用CS的優勢來解釋：集約化和多樣化之間的良好平衡，Leívy航班的智能使用以及參數數量的減少。它可以證明種群的結構，使用各種杜鵑進行搜尋和生成新的解。改進後的DCS的優點之一是在尋找最佳位置的過程中相對獨立于杜鵑鳥。是以，它更有可能在元啟發式尚未探索的領域找到好的解決方案，而元啟發式以迄今為止找到的最佳位置為起點.
6結論
在本文中，我們通過重建其種群并引入一個更智能的新布谷鳥類别，擴充并改進了通過勒維航班進行的标準/基本布谷鳥搜尋（CS）。改進後的CS被離散化，然後用于求解對稱旅行商問題（TSP）。此改編基于對CS及其靈感來源中使用的術語解釋的研究。已實作離散CS（改進的适應TSP的CS），并在41個基準TSP執行個體上測試了其性能。其性能與GSA-ACS-PSOT[6]和DPSO[27]進行了比較。比較結果表明，離散CS法求解TSP的性能優于其他兩種方法。這可以通過勒維航班的集約化和多樣化管理以及使用多種研究方法的杜鵑種群結構來解釋。是以，我們的布谷鳥新類别在尋找新解決方案時相對于最佳解決方案的獨立性，可能比簡單使用一個目前最佳解決方案提供更好的生成新解決方案的政策，進而産生更高效的算法。我們提出的離散CS中引入的局部擾動可以為解決其他組合優化問題提供更大的靈活性。離散CS的目标是為設計新一代更有效的元啟發式算法提供好的思路。進一步關注DCS的參數研究和應用到其他組合問題，如排程和路由
我們想模仿自然，這樣我們就可以設計新的算法來更有效地解決非常複雜的問題。我們還想開發真正智能化的新算法。與當代的元啟發式算法相比，新算法應該更可控、更簡單。可以預期，智能算法應該能夠調整其算法相關參數，以便自動優化其性能。最後，可能會出現一些真正高效和智能的算法，以越來越高效的方式解決NP難題。至少，一些看似棘手的問題可以解決