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

有效

• 申請號: 201710454872.9
• 申請日: 2017-06-15
• 公開（公告）號: CN107272679B
• 公開（公告）日: 2020-06-16
• 發明（設計）人: 黃杰;萬棄寒;衛錦;朱仟;曹山山;閔溪青;張云龍
• 申請（專利權）人: 東南大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 柏尚春

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

(1)利用柵格法對地圖環境進行建模，包括設置起始節點、目標節點、障礙物柵格；

(2)初始化蟻群算法基本參數，并使蟻群初始化在起始節點處；

(3)每只螞蟻從起始節點開始搜索遍歷，根據轉移概率選擇下一節點，螞蟻走過的每個節點記錄在禁忌表中，當螞蟻到達目標節點時，計算螞蟻所選路徑長度和路徑上的拐點個數；

(4)當所有螞蟻完成搜索后，應用拐點較少原則選取當次迭代的最優路徑；

(5)對當次迭代的最優路徑應用簡化路徑原則，得到優化后的當次迭代最優路徑；

(6)對當次迭代的所有可行路徑應用預先排序規則，選取出較優路徑，對較優路徑上的信息素揮發系數進行自適應調整策略，并在此基礎上更新每條較優路徑上的信息素濃度，其中信息素揮發系數自適應調整策略的計算公式為：

ρ(NC)＝pre_argu·tanh(10·(shortest_length-min(L))/mean(L))+pre_argu

其中，NC為當前迭代次數，shortest_length為當次迭代最優路徑長度，min(L)為現有最短路徑長度，mean(L)為當前局部最優路徑平均長度，即當前迭代次數下，每輪迭代得到的最優路徑長度的平均值，pre_argu為自適應調整因子前置參數；

(7)重復執行步驟(2)-步驟(6)，直到迭代次數達到最大迭代次數，計算各輪迭代的最優路徑長度，得到全局最優路徑。

2.根據權利要求1所述的基于改進的蟻群算法的路徑規劃方法，其特征在于，所述步驟(4)中的拐點較少原則具體為：

第一輪迭代完成后，比較每條路徑長度和路徑中的拐點個數，選擇長度最短的路徑作為當次迭代的最優路徑，如果有路徑長度相同，則選擇拐點較少的路徑作為當次迭代的最優路徑；

在后續迭代過程中，每輪迭代完成后，計算當次迭代所產生的最優路徑中的拐點個數，比較當次迭代所產生的最優路徑長度與現有最優路徑長度，如果相同，則選擇拐點較少的路徑；如果不同，則選擇路徑長度較短的路徑。

3.根據權利要求1所述的基于改進的蟻群算法的路徑規劃方法，其特征在于，所述步驟(5)中簡化路徑原則具體為：對路徑中所經過的每一個節點與起始節點進行是否為鄰節點判斷，如果當前節點為起始節點的鄰節點，則直接由起始節點導向該節點，省去中間節點；如果當前節點不是起始節點的鄰節點，則保留該節點，繼續上述操作，直至遍歷完路徑中所有節點。

4.根據權利要求1所述的基于改進的蟻群算法的路徑規劃方法，其特征在于，所述步驟(6)中所述的預先排序規則具體為：每輪迭代完成后，對當次迭代所產生的全部可行路徑按照長度由短到長進行排序，選取排序前三分之一的路徑作為較優路徑。

5.根據權利要求1所述的基于改進的蟻群算法的路徑規劃方法，其特征在于，所述自適應調整因子前置參數取值為0.3。