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

在審

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

本發明涉及一種TSP問題路徑規劃方法，包括以下步驟：初始化；讀取位置并計算距離；貪婪算法初始化種群；最差的若干個體換為隨機生成的個體；計算適應度；選擇；交叉；變異；隨機對若干個體進行模擬退火；計算適應度；當代最優解及其變異解分別給第一和第二個個體；迭代至滿足終止條件。本發明貪婪算法產生的種群具有隨機性且質量較高，能加速尋優。最差的若干個體換為隨機生成的個體，減少差解影響并避免早熟。模擬退火可發現一些更優解，且避免早熟和陷入局優。最優解及其變異解的存儲保留了優秀信息且增加了種群多樣性。本發明能有效、快速的規劃出一條最短訪問路徑，因此是一種可為TSP問題提供路徑規劃的有效方法。

技術領域

本發明涉及一種TSP問題路徑規劃方法，屬于組合優化、路徑規劃技術領域。

背景技術

旅行商問題，即TSP問題(Traveling Salesman Problem)，是組合優化領域中著名的NP-hard問題，即其在最壞情況下的時間復雜度隨問題規模的增大按指數方式增長，到目前為止還沒有找到一個多項式時間的有效算法。TSP問題一般描述為：有一旅行商要訪問給定的n個城市，從起點出發，每個城市必須訪問且只能訪問一次，最終返回起點，需要規劃一條包含所有n個城市的最短訪問路徑。TSP問題并不僅僅是旅行商問題，現實生活中的許多其他問題，如印刷電路鉆孔、城市管道鋪設優化、物流行業中的車輛調度、公路網絡的建設、制造業中的切割路徑規劃等，也都可以轉變為TSP問題來解決。因此，如何快速、有效的解決TSP問題具有很高的實際應用價值。

遺傳算法(Genetic Algorithm，GA)，是在1975年由J.Holland教授首次提出的。它是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。遺傳算法根據遺傳學機理，對問題的解進行類似自然進化過程的處理，使得問題的解朝著更加適應環境的方向進化，進而獲得最優解。通常而言，遺傳算法具有簡單、通用、魯棒性強、適于并行處理是的特點。而且，遺傳算法是一種不需要指導的，能在搜索過程中自動獲取和積聚搜索空間的有關信息，并根據得到的信息調整搜索過程，進而得到接近問題最優解的通用搜索算法。因此，遺傳算法非常適合應用在組合優化這種需要在龐大的搜索空間中尋優的問題上。1985年，有學者首次采用遺傳算法求解TSP問題。但是傳統的遺傳算法存在收斂速度慢、容易早熟收斂、易陷入局部最優等缺點，解決TSP問題時得到的路徑比較差，或者存在多段路徑交叉這種不太合理的情況。因此，需要對傳統的方法進行改進，提出一些新的方法來處理TSP問題。

發明內容

本發明的目的是：能夠針對待訪問的城市，有效、快速的規劃出一條最短訪問路徑。

為了達到上述目的，本發明的技術方案是提供了一種TSP問題路徑規劃方法，其特征在于，包括以下步驟：

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

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

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

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

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

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

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