[發明專利]一種基于離散布谷鳥算法求解旅行商問題的方法

在審

• 申請號: 201711227262.1
• 申請日: 2017-11-23
• 公開（公告）號: CN108009678A
• 公開（公告）日: 2018-05-08
• 發明（設計）人: 張紅梅;陳雷;張向利
• 申請（專利權）人: 桂林電子科技大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/00
• 代理公司: 桂林市持衡專利商標事務所有限公司 45107
• 代理人: 陳躍琳

本發明公開一種基于離散布谷鳥算法求解旅行商問題的方法，在離散布谷鳥算法的基礎上，添加了禁忌搜索算法，在布谷鳥搜索過程中使用禁忌搜索來控制步長，預期布谷鳥?禁忌搜索算法可以消除二者算法中存在的一些不足之處，使之可避免陷入局部最優解，并減少了算法的重復搜索；另外，由于禁忌搜索和布谷鳥搜索解的優劣在很大程度上取決于鄰域結構，而k?opt算法的隨機性使其后期很難再次快速收斂，因此本發明在迭代后期設置一個鄰域限制的結構，這種結構可以消除一定量的隨機性，即避免發生低質量的選邊，通過使用自適應動態鄰域調整k?opt算法的切邊選擇，提高了算法的局部搜索能力。

技術領域

本發明涉及旅行商問題求解技術領域，具體涉及一種基于離散布谷鳥算法求解旅行商問題的方法。

背景技術

旅行商問題是Dantzig于1959年提出的一個經典的組合優化問題。其概念可用如下的例子來說明：一位旅行商從一個城市出發，訪問列表中所有城市，且每個城市只訪問一次，最終回到首次出發的城市，其目標是旅行商訪問所有城市的總距離最小。旅行商問題可被同化為其他的組合優化問題，如車輛路徑問題、裝卸貨問題、物流配送問題、電路板鉆孔問題等。

布谷鳥搜索算法是一種通過模擬布谷鳥寄生育雛的生物學行為和列維飛行機制實現的啟發式仿生群智能優化算法，它利用布谷鳥特殊的繁殖方式和列維飛行機制來尋找問題的最優解。其中列維飛行是一種行動機制，是一種由高頻率的短距離和低頻率的長距離組成的典型的隨機游走過程，其平穩增量服從列維穩定分布。在仿生群智能優化算法中采用列維飛行機制，能夠加強算法的全局搜索能力，使算法更容易跳出局部最優點，在求解最優化問題和進行最優化搜索時表現出良好的性能。

利用布谷鳥算法解決旅行商問題，已存在幾種技術方案，但其都存在不同的問題。Ouaarab等人將列維飛行用概率離散化，用2-opt鄰域代表短距離游走，用雙橋移動代表長距離游走，取得了一定的效果，但存在有無法找到全局最優解，收斂到最優解的速度慢的問題。張子成等人設計了一種針對路徑的自適應型局部調整算子和全局隨機擾動策略，將路徑分塊交叉計算，并采用了簡單的2-opt優化算子作為局部優化算子以加快算法的收斂速度，該方案相對于Yang的方案提升了收斂速度，但其舍棄了列維飛行機制，導致其全局尋優效果較差。

發明內容

本發明所要解決的是普通布谷鳥算法在求解旅行商問題時存在難以獲取全局最優解和收斂速度慢的問題，提供一種基于離散布谷鳥算法求解旅行商問題的方法。

為解決上述問題，本發明是通過以下技術方案實現的：

一種基于離散布谷鳥算法求解旅行商問題的方法，具體包括步驟如下：

步驟1.設定鳥巢數量、鳥巢被發現的概率和總的迭代次數；

步驟2.根據步驟1所設定的鳥巢數量，為每個鳥巢設定一個旅行商問題的解，并將其作為鳥巢初始的解；

步驟3.計算每個鳥巢的解的適應度，并將適應度函數最小的解作為當前全局最優解；

步驟4.對每個鳥巢的解采用離散化的列維飛行生成預定個數的解，并將所產生的這些解集合在一起構成該鳥巢的候選集；

步驟5.對于每個鳥巢，計算其候選集中解的適應度，并從中選出適應度值最小的解作為當前最優解，并將該解從候選集中刪除后，進行步驟6；

步驟6.將當前最優解與當前全局最優解進行比較：

6.1.如果當前最優解的適應度小于當前全局最優解的適應度，則用當前最優解作為當前全局最優解，并將其加入禁忌表；

6.2.如果當前最優解的適應度大于等于當前全局最優解的適應度，則將當前最優解與每個鳥巢的解進行比較：

6.2.1.如果當前最優解的適應度小于鳥巢的解的適應度，則檢查當前最優解的適應度是否在當前全局最優解的適應度的允許范圍內：