[發明專利]一種TSP問題路徑規劃方法

在審

• 申請號: 201910256712.2
• 申請日: 2019-04-01
• 公開（公告）號: CN109948865A
• 公開（公告）日: 2019-06-28
• 發明（設計）人: 徐鑫;沈波
• 申請（專利權）人: 東華大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/12
• 代理公司: 上海申匯專利代理有限公司 31001
• 代理人: 翁若瑩;柏子雵

1.一種TSP問題路徑規劃方法，其特征在于，包括以下步驟：

步驟1、將迭代次數gn初始化為1，初始化最大迭代次數GN_max；

步驟2、讀取各城市的位置信息，并計算各城市之間的距離；

步驟3、用貪婪算法產生初始種群，并計算其適應度值，包括以下步驟：

對每個個體，先隨機選一個城市作為起點，然后搜索未加入的城市，找到距當前城市最近的城市，將其加入個體中并作為當前城市，繼續搜索并添加城市，直到所有城市都加入到個體中，得到用貪婪算法產生的個體，重復上述操作，得到所有初始個體，計算每一個初始個體的適應度值F，設個體為x＝(x₁,x₂,...,x_n)，n為城市的數目，則個體x所對應的路徑長度D為：則有：

步驟4、將適應度值F最差的若干個個體替換為隨機生成的個體；

步驟5、根據適應度函數計算所有個體的適應度值；

步驟6、依據步驟5計算得到的適應度值對種群中的個體進行選擇操作；

步驟7、對種群中的個體進行交叉操作；

步驟8、對種群中的個體進行變異操作；

步驟9、從種群中隨機選擇若干個個體進行模擬退火操作；

步驟10、計算新種群中所有個體的適應度值；

步驟11、將當前代的最優解賦給種群中的第一個個體，并將該最優個體變異后賦給種群中第二個個體；

步驟12、將迭代次數gn加1，更新迭代次數；

步驟13、判斷迭代次數gn是否達到最大迭代次數GN_max，若達到，則輸出最優路徑，結束算法，否則跳轉至步驟4。

2.根據權利要求1所述的TSP問題路徑規劃方法，其特征在于，步驟1中，還需要初始化如下參數：個體數N、交叉概率P_c、變異概率P_m、模擬退火初始溫度T₀、終止溫度T_f、模擬退火Markov鏈長度M、溫度衰減率Delta。

3.根據權利要求1所述的TSP問題路徑規劃方法，其特征在于，所述步驟4包括以下步驟：將個體按照適應度值F排序，對于最差的若干個個體，隨機生成一個個體將其替換。

4.根據權利要求1所述的TSP問題路徑規劃方法，其特征在于，步驟6中，對種群中的個體進行選擇操作時采用輪盤賭選擇法，對于個體x_i而言，其被選擇的概率為P_i，則有：

式中，N為個體的總數；F(x_i)為個體x_i的適應度值。

5.根據權利要求1所述的TSP問題路徑規劃方法，其特征在于，步驟7中，交叉操作采用部分匹配交叉(PMX)法。

6.根據權利要求1所述的TSP問題路徑規劃方法，其特征在于，步驟8中，變異操作采用倒位變異。

7.根據權利要求1所述的TSP問題路徑規劃方法，其特征在于，步驟9中，對隨機選擇的若干個體進行模擬退火操作，其中要以一定的概率p來接受比原個體更差的個體作為新解，式中，D_new為擾動后個體對應的路徑長度，D為原個體對應的路徑長度，T為模擬退火中當前的溫度，最后用模擬退火過程中搜索到的最優個體來替換選中的那個個體，模擬退火中溫度用下式更新：T_new＝T·Delta，T_new為更新后的溫度，Delta溫度衰減率。