[發明專利]基于改進粒子群算法的多路徑規劃方法

有效

• 申請號: 201410162014.3
• 申請日: 2014-04-21
• 公開（公告）號: CN104063745B
• 公開（公告）日: 2017-05-03
• 發明（設計）人: 張雪潔;嚴祥光;周文歡;蔣悅達
• 申請（專利權）人: 河海大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04
• 代理公司: 南京蘇高專利商標事務所(普通合伙)32204
• 代理人: 李玉平

1.一種基于改進粒子群算法的多路徑規劃方法，其特征在于，包括如下步驟：

(1)利用貪心算法初始化粒子群，利用貪心算法，從每一個城市出發，選擇與當前城市距離最近的城市作為下一個城市，遍歷所有城市，得到N個初始的城市序列；

(2)如果達到最大迭代次數轉到步驟(5)，如不滿足則對種群進行更新，找到個體最好位置Pi_best，以及全局最好位置G_best；

(3)更新所有粒子的位置；

其中，X_i(k)為第i個粒子的當前位置，即第i個當前城市序列，ω,c₁,c₂,c₃為(0,1)之間的數，c₃variation(X)表示以概率c₃對X進行變異操作，X_i(K+1)為第i個粒子新的位置，即新生成的第i個城市序列；

(4)采用模擬退火降溫方法選擇接受的粒子位置，以避免陷入局部最優解；初始溫度設為最大迭代次數的三分之一，退火接受變壞解的概率設為溫度與最大迭代次數的比值，退火系數取0.99；迭代次數加一，轉到步驟(2)；

(5)輸出最優城市序列，并輸出最短距離；

(6)根據實際需求，對城市數據進行預處理；分如下兩種情況：

a對于只有一個出發城市的多路徑問題，如果要計算出首發相連的N條路徑，這N條路徑除了出發城市相同外其余經過的城市各不相同，但覆蓋所有城市，則需增加N個與出發城市位置相同的虛擬城市；

b對于出發城市互不相同的多路徑問題，則不需要進行預處理；

(7)使用上述算法計算出一條城市序列X＝(x₁,x₂,…,x_i,x_v1,x_j,…,x_k,x_v2,x_l,…,x_n)；假設需要計算兩條路徑，其中x_v1和x_v2代表兩個虛擬城市或者出發城市；

(8)將算出來的城市序列看成首尾相連的環狀；城市序列中只要遇到虛擬城市或者出發城市就代表回到上一個出發城市，這樣將環分割成多條路徑，X₁＝(x_v1,x_j,…,x_k,x_v1)，X₁^*＝(x_v2,x_l,…,x_n,x₁,x₂,…,x_i,x_v2)，得到最終需要的多條路徑。