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

在審

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

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

步驟1.設定鳥巢數(shù)量、鳥巢被發(fā)現(xiàn)的概率和總的迭代次數(shù)；

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

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

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

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

步驟6.將當前最優(yōu)解與當前全局最優(yōu)解進行比較：

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

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

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

6.2.1.1.如果在范圍內(nèi)，則繼續(xù)檢查當前最優(yōu)解是否存在于禁忌表中：

6.2.1.1.1.如果存在于禁忌表，則選擇候選集的剩余解中適應度最小的解作為當前最優(yōu)解，并將該解從候選集中刪除后，返回步驟6，直到候選集內(nèi)的無解；

6.2.1.1.2.如果不存在于禁忌表中，則將鳥巢的解替換為當前最優(yōu)解，并將其加入禁忌表；

6.2.1.2.如果不在范圍內(nèi)，則將鳥巢的解替換為當前最優(yōu)解；

6.2.2.如果當前最優(yōu)解的適應度大于等于鳥巢的解的適應度，則進行步驟7；

步驟7.隨機生成1個概率，并將其與步驟1所設定的鳥巢被發(fā)現(xiàn)的概率進行比較：

步驟7.1.如果生成的概率大于等于鳥巢被發(fā)現(xiàn)的概率，則首先對當前全局最優(yōu)解執(zhí)行一次雙橋移動產(chǎn)生1個新解；然后將新解與當前全局最優(yōu)解進行比較：若新解的適應度小于當前全局最優(yōu)解的適應度，則將新解作為當前全局最優(yōu)解；否則，當前全局最優(yōu)解不變；最后，讓迭代次數(shù)加1，并進行步驟8；

步驟7.2.如果生成的概率小于鳥巢被發(fā)現(xiàn)的概率，則讓迭代次數(shù)加1，并進行步驟8；

步驟8.判斷迭代次數(shù)是否達到步驟1所設定的總的迭代次數(shù)：如果達到，則輸出全局最優(yōu)解；否則，返回步驟4。

2.根據(jù)權利要求1所述的一種基于離散布谷鳥算法求解旅行商問題的方法，其特征是，步驟2中，需要對每個鳥巢的解執(zhí)行一次2-opt優(yōu)化算法后再進入步驟3。