[發明專利]基于遺傳蟻群算法的路徑規劃方法及系統

在審

• 申請號: 201610005195.8
• 申請日: 2016-01-04
• 公開（公告）號: CN105527965A
• 公開（公告）日: 2016-04-27
• 發明（設計）人: 賀乃寶;陸毅;高倩;沈琳;羅印升;潘瑜;劉波;俞燁
• 申請（專利權）人: 江蘇理工學院
• 主分類號: G05D1/02
• 分類號: G05D1/02;G06N3/12
• 代理公司: 南京同澤專利事務所(特殊普通合伙) 32245
• 代理人: 蔣全強

1.一種路徑規劃方法，其特征在于,包括如下步驟：

步驟S1，將遺傳算法得到的一部分優化解轉化為蟻群算法的信息素初始值；

步驟S2，通過蟻群算法再進行路徑尋優，尋優結束后對符合條件的路徑進 行交叉操作，最終得到最優路徑。

2.根據權利要求1所述的路徑規劃方法，其特征在于,

所述步驟S1中將遺傳算法得到的一部分優化解轉化為蟻群算法的信息素初 始值的方法包括：

步驟S11，對環境進行建模；

步驟S12，初始化遺傳參數，以產生初始種群；

步驟S13，設置適應度函數，計算每個種群的適應度；

步驟S14，將適應度較高的前50％組解轉換為蟻群算法的信息素初始值

3.根據權利要求2所述的路徑規劃方法，其特征在于,

所述步驟S2中通過蟻群算法再進行路徑尋優，尋優結束后對符合條件的路 徑進行交叉操作，最終得到最優路徑的方法包括如下步驟：

步驟S21，設置蟻群規模m₂，最大迭代次數N_c以及迭代次數初值u為0，并 按下式初始化剩余信息素：

式中：d_ij表示節點i和節點j之間的距離；

步驟S22，每只螞蟻按照狀態轉移公式選擇下一節點，直到到達目標點則輸 出路徑，若比當前迭代最優路徑短，則對其更新，狀態轉移公式如下：

Pijk=[τij(t)]α·[ηij(t)]βΣs∈allowk[τis(t)]α·[ηis(t)]β,s∈allowk0,s∉allowk;]]>

式中：allow_k(k＝1,2...m₂)為螞蟻k待訪問節點的集合，開始時，allow_k中有(m₂-1) 個元素，即包括除了螞蟻k出發節點的其他所有節點，隨著時間的推進，allow_k中 的元素逐漸減少，直至為空，即表示所有的節點均訪問完畢；

τ_ij(t)表示在t時刻節點i、節點j間路徑上的信息素濃度；α為信息素重要 程度因子；β為啟發函數重要程度因子；

η_ij(t)為啟發函數，表示t時刻螞蟻從節點i轉移到節點j的期望程度，計算 公式如下：d_ij表示節點i和節點j之間的距離；

步驟S23，對尋優過的路徑按如下公式進行全局信息素更新，同時輸出本次 迭代的最優路徑，同時判斷本次迭代最優路徑與當前全局最優路徑是否有除起 始點和目標點以外的相同點；

若有，則以該節點為交叉點，對兩條路徑進行交叉操作，產生新路徑與全 局最優路徑比較，若新路徑短，則更新全局最優路徑；

對尋優過的路徑進行全局信息素更新的公式如下：

τ_ij(t+1)＝(1-ρ)τ_ij(t)+ρΔτ_ij(t)+Δ₁τ_ij-Δ₂τ_ij；

Δτij=Σk=1m2Δτijk;]]>

式中，ρ表示全局信息素揮發系數，表示第k只螞蟻在節點i與節點j 連接路徑上釋放的信息素濃度，Δ₁τ_ij表示經過本輪最優路徑的信息素增量，Δ₂τ_ij 表示經過本輪最差路徑的信息素增量；L₁、L₂分別表示本次循環中的局部最優 長度、局部最差長度；k₁、k₂分別表示本次循環局部最優、局部最差螞蟻個數；

步驟S24，循環次數u＝u+1；

步驟S25，把螞蟻重新放回起始點，進行下一輪迭代；

步驟S26，若迭代次數u>N_c，則尋優結束，輸出最優路徑；否則轉入步驟 S25。