[發明專利]一種多點位置最短路徑計算方法

在審

• 申請號: 202010812977.9
• 申請日: 2020-08-13
• 公開（公告）號: CN111985705A
• 公開（公告）日: 2020-11-24
• 發明（設計）人: 歐陽春;甘中學;甄俊杰;管宇翔;祝興
• 申請（專利權）人: 復旦大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08;G06Q50/30;G06N3/00
• 代理公司: 上海德昭知識產權代理有限公司 31204
• 代理人: 盧泓宇

1.一種多點位置最短路徑計算方法，用于求解出路過且只路過一次所有位置的最短路徑序列，其特征在于，包含如下步驟：

步驟S1，將由若干個預定位置隨機排成的隨機序列設定為蜜源；

步驟S2，根據公式(1)隨機創建Popsize/2個可行的解決方法以初始化所述蜜源得到初始蜜源a_i，給每個所述初始蜜源a_i配一只雇傭蜂：

a_i＝[1,randperm(n_citys-1)+1,1] (1)

式中，i∈{1,2,...,Popsize/2}，Popsize/2是所述雇傭蜂的數量，n_citys表示所述城市個數；

步驟S3，所述雇傭蜂通過預定算法從多個低啟發式算法操作中選擇一個所述低啟發式算法操作從而更新所述初始蜜源得到新蜜源n_i：

n_i＝llh_x(a_i) (2)

式中，llh_x是第x個所述低啟發式算法操作；

步驟S4，所述雇傭蜂根據公式(3)比較適應值fit_i并采用貪婪方法從所述初始蜜源a_i以及所述新蜜源n_i中進行選定操作：

式中，f_i是函數值；

步驟S5，所述雇傭蜂通過輪盤賭方法招募跟隨蜂，所述跟隨蜂對所述雇傭蜂所對應的蜜源進行選擇，所述雇傭蜂所對應的蜜源被選擇的概率P_i如公式(4)所示：

步驟S6，所述雇傭蜂在預定的迭代時間內未找到最優蜜源時，所述雇傭蜂被迫轉變成偵查蜂同時放棄所述雇傭蜂對應的所述蜜源；

步驟S7，所述偵查蜂根據預定搜索方法繼續搜索得到所述最優蜜源；

步驟S8，重復所述步驟S3至所述步驟S7直到達到預定最大循環次數，得到唯一所述最優蜜源并作為所述最短路徑序列。

2.根據權利要求1所述的一種多點位置最短路徑計算方法，其特征在于：

其中，所述步驟S3包括如下子步驟：

步驟S3-1，創建一個空選擇表；

步驟S3-2，在所述空選擇表中設計有多個不同類型的低啟發式算法操作得到鄰域操作表；

步驟S3-3，在所述鄰域操作表中記錄低啟發式算法的多個調用對應的調用分數并形成調用表，所述調用分數根據公式(5)計算所得：

式中，f_{_current}是當前所述初始蜜源，f_{_new}是所述新蜜源，w是所述當前所述初始蜜源f_{_current}與所述新蜜源f_{_new}之間的適應度的差，α和β是自適應值，n是所述調用表的第n個調用，t_current表示當前迭代的次數，t_total表示預先設定的總迭代次數，θ是一個成本因素，W_i,j表示所述調用表中的第i行第j列單元格的所述調用分數，W_i,i表示所述調用表中第i行第i列單元格的所述調用分數；

步驟S3-4，基于所述調用表選擇一個低啟發式算法操作得到所述新蜜源n_i。

3.根據權利要求2所述的一種多點位置最短路徑計算方法，其特征在于：

其中，所述低啟發式算法操作為RRS操作、RI操作、RIS操作、RS操作、RSS操作、SS操作中任意一個或是復數個的組合。

4.根據權利要求2所述的一種多點位置最短路徑計算方法，其特征在于：

其中，所述調用分數為獎勵調用分數、懲罰調用分數以及未改進調用分數中的任意多個。