基于林地綜合代價地圖與開拓優化機制的改進蟻群算法

摘 要：針對傳統蟻群算法在林業機器人路徑規劃中未能考慮林區地形與地表狀態，且收斂速度慢，易陷入局部最優的問題，提出一種基于林地綜合代價地圖與開拓優化機制的改進蟻群算法。基于林區地形地表構建林地綜合代價地圖；在蟻群搜索階段中引入開拓優化機制；在輪盤賭中引入隨機游走機制，并將其應用到林業機器人路徑規劃問題中。實驗表明：改進蟻群算法能搜尋到更佳路徑，具有更好的全局尋優能力。

關鍵詞：蟻群算法；精英獎勵；雙層蟻群算法；林間路徑規劃

中圖分類號：TP183 文獻標志碼：A 文章編號：1671-5276（2024）04-0146-05

Improved Ant Colony Algorithm Based on Forest Comprehensive Cost Map and Research-optimization Mechanism

HE Haotian， PENG Fuming， FANG Bin， XIANG Fulei， ZHANG Shaojie

（School of Automation， Nanjing University of Science and Technology， Nanjing 210094， China）

Abstract：An improved ant colony algorithm based on the comprehensive cost map of forest land and the research-optimization mechanism is proposed to address the problem of the traditional ant colony algorithms which is absent of considerationof forest terrain and surface conditions in forestry robot path planning， slow at convergence speed and prone to falling into local optima. On the terrain and surface of the forest area， a comprehensive forest land cost map is constructed; a pioneering optimization mechanism is introduced in the ant colony search stage;and a random walk mechanism is led into the roulette wheel mechanism， which is applied the path planning problem of forestry robots. The experiments show that the proposed algorithm proposed can search for better paths and has better exploration and optimization capabilities.

Keywords：ant colony；elite rewards; double layer ant colony algorithm; forest path planning

0 引言

林業機器人是促進林業現代化、提高林業效率的關鍵。路徑規劃與軌跡跟蹤是移動機器人領域的核心問題。蟻群算法是一種經典的仿生學算法，該算法可用于路徑規劃。相較于傳統的路徑規劃算法，蟻群算法具有正反饋機制、魯棒性強、并行性好等優點，在尋求最短路徑上有更好的效果。然而，傳統蟻群算法收斂速度較慢且容易陷入局部最優，導致規劃出的路徑不理想。對此，學者提出了大量改進策略。

針對收斂速度慢的問題，張子然等^[1]利用k-means算法對地圖進行預處理，使得機器人優先選擇復雜程度小的區域進行尋優，提升了算法的收斂速度；馬康康等^[2]使信息素沿起點與終點連接線向兩邊正態分布，大大降低了算法初期盲目性；徐超毅等^[3]使用雙向搜索的A^*算法預先得出兩條路徑作為較優解，以設定的系數提高區域內信息素濃度。

針對陷入局部最優的問題，WU等^[4]在信息素更新時引入最大最小機制，將信息素限制在一個自適應的范圍內，以防止信息素過大而陷入局部最優；趙高杰等^[5]提出了一種改進的變步長蟻群算法，根據不同的環境改變步長并設計了自適應揮發因子；董志洋等^[6]基于優勝劣汰的思想進行信息素更新，避免搜索過程陷入局部最優。

此外，一些融合算法也被用于改進蟻群的性能。陳丹鳳等^[7]利用強化學習，在每輪搜索結束后對動作參數進行優化，提高了路徑規劃的效率；吳宇等^[8]在啟發函數中加入人工勢場因子，使得算法不容易陷入U型障礙區；陳嘉航等^[9]將注意力機制融入信息素表，利用局部路徑注意力機制提高了尋路效率；張恒等^[10]提出了一種改進雙層蟻群算法，將蟻群劃分為引導層蟻群和普通層蟻群，為引導層蟻群設計應對死鎖問題的自由尋路-剪枝策略;許凱波等^[11]在每次迭代中先用外層蟻群算法尋優，再用內層蟻群算法在局部小環境下進行優化，使得生成路徑質量更高；WANG等^[12]設計了基于排序的雙層蟻群算法，在局部搜索時引入探索因子以防止算法陷入局部最優;YANG等^[13]融合蟻群算法與軌跡優化，在復雜圖上使用精英蟻群算法生成初始無碰撞路徑，在此基礎上使用局部蟻群算法優化路徑質量。

針對以往蟻群算法中容易陷入局部最優且生成路徑質量差、收斂速度慢等問題，本文提出了一種分組變異搜索的雙層蟻群算法。該算法引入優化開拓機制，將種群劃分為優化組與開拓組，為每組分配各自的信息素表，通過信息素懲罰因子鼓勵開拓組走不同的道路。在一輪搜索結束后，將有潛力的路徑更新到優化組的信息素表，以提高算法的全局尋優能力；引入了隨機游走機制，通過頭部隨機削弱提高算法陷入局部最優時的變異性，使算法跳出局部最優。最后，在復雜環境與林地環境進行測試，驗證了算法的有效性。

1 林地綜合代價地圖

傳統的柵格地圖假定機器人工作在二維平面上，但在林業環境中，山區地勢起伏較大，且不同地表環境對機器人的移動均有影響。傳統的柵格地圖只考慮節點間移動的距離代價，忽略了因地勢起伏而產生的能耗代價，亦忽略了由于不同地表環境而導致的對機體的后續維護成本。

基于此，本文構造了林區條件下的綜合代價地圖。結合林業生產的實際情況，本文在綜合代價地圖中定義了4種常見路面：干燥帶、潮濕帶、落葉帶和顛簸帶。其中，干燥帶最適宜車輛通過；潮濕帶有可能導致車輪陷入，并且導致車輪軸卡泥；落葉帶容易導致車輪發生側滑；顛簸帶在通過時會導致底盤與樹根磕碰，造成后續維護的困難；本文依照其實際工程中對車輛的影響優先級，定義了不同路面的通過系數，如表1所示。

依據不同路面之間的通過系數與地形圖，節點間移動綜合代價的計算公式如下所示。

式中：J_ij為小車從i點到j點的綜合能耗；F_ij為小車受到的綜合阻力；d_ij為小車從i點到j點的距離；θ_ij為當前地形坡度；ξ為小車的重力系數，需指定；μ為當前小車的通過系數。依據該綜合代價，生成綜合代價地圖，如圖1所示。

結合式（1）與圖1可知，式（1）實質上為小車在綜合代價地圖上的能耗。相較于傳統的二維柵格地圖，該地圖綜合考慮了小車的爬坡能耗與路面通過條件，平衡了路徑長度、能耗與后期維護成本，更加符合生產實際。

2 基于開拓優化機制的改進蟻群算法

2.1 開拓優化機制

在傳統的蟻群算法中，絕大多數螞蟻會沿著轉移概率最大的路徑行走，隨著迭代次數增多，算法陷入局部最優而難以跳出。不同于傳統的限制信息素濃度，單純增加突變概率的優化方法，本文提出了一種新的開拓優化機制，具體步驟如下。

將原有的種群分為兩組，其中的70%為一組，該組成為“優化組”。該組按照傳統蟻群算法的方式進行搜索，保證算法不會因變異而發散；其余的30%稱為“開拓組”，該組擁有獨立于優化組的信息素表。在同一輪搜索中，優先使用優化組進行搜索，搜索結束后，按照式（2）更新優化組的信息素表。

式中：τ^y_ij為優化組所屬的信息素；ρ_y為優化組的信息素揮發率；L_y為當前優化組路徑長度；Δτ_ij（t）為信息素增量；Q_y為優化組信息素強度；R_y為優化組路徑。

在更新了優化組的信息素表之后，使用開拓組進行搜索，搜索結束后，按照式（3）更新優化組的信息素表。

式中：τ^k_ij為開拓組所屬的信息素；ρ_k為開拓組的信息素揮發率；L_k為當前開拓組路徑長度；Q_k為開拓組信息素強度；λ為強度系數，是一個常數；R_k為開拓組路徑。開拓優化機制示意圖如圖2所示。

在開拓組的信息素更新完畢之后，依照式（4）再次更新優化組的信息素：

式中：q為選擇子，當開拓組當前路徑長度小于4倍的當前最短路徑時，該路徑被視為有潛力的潛在路徑，此時令q為0，將該條路徑的信息素更新到優化組的信息素表中；反之，q為1，不更新該路徑。

該機制的意義在于，在進行一輪更新之后，通過對優化組中信息素較高的節點進行懲罰，開拓組可以避開信息素濃度高的節點，選擇更少走過的路徑；在開拓組進行優化后，優化組可從開拓組中選擇出有潛力的路徑，將其信息素同步至優化組的信息素表，在下一輪搜索實行進一步優化。在不增加種群數量的前提下，既保證了算法的收斂性，也增強了算法跳出局部最優的能力。

2.2 隨機游走機制

在傳統蟻群算法中，算法依賴輪盤賭機制實現節點選擇的隨機發散。為了提高算法在陷入局部最優時的變異速度，本文引入了一種概率自適應隨機游走機制，該機制下的狀態轉移概率如式（5）所示。

式中：τ_ij（t）為i點到j點的信息素濃度；η_ij（t）為i點到j點的啟發值；α、 β分別為信息素濃度與啟發值的權重；a_k為此輪搜索候選點列表；φ_j為懲罰因子，定義如下：

式中：l為當前最小代價曲線的斜率；p是一個隨機數；p₀是變異概率。其意義在于，在路徑長度的收斂率小于0.3時，認為算法陷入局部最優，此時以一定的概率p₀為狀態轉移概率最大的方向，添加一個自適應因子懲罰因子，使得個體選擇其他未走過的方向。變異概率p₀的定義如下：

式中：m為當前迭代數；m₀為迭代數閾值，當超過了這個閾值時，變異概率不再增加；γ為變異概率的權重系數。

該機制可以動態調節算法的變異概率，在算法后期陷入局部最優時，以一定的概率給當前概率最高的節點添加一個懲罰值，自適應地增加算法的變異概率，且由于變異概率是隨著迭代次數動態調整的，可以避免影響算法早期的收斂性。

3 實驗與分析

為了驗證算法的優越性，本文在12th Gen Intel（R） Core（TM）i5-12500H2.50 GHz， 16.00 G內存，Windows11系統和MatlabR2023b環境下采用20×20的柵地圖進行測試，并選取ACO、MAACO進行對照。各個算法的種群規模大小設為100，本文算法中的優化組數量為70，開拓組數量為30，最大迭代次數為50，信息素濃度權重為1.5，啟發值的權重為6.0，信息素蒸發系數為0.5，信息素增加強度系數為5.0，分別比較其路徑長度與綜合能耗，其結果如表2所示。

對比實驗中20×20柵格地圖的起點為（1，1），終點為（20，20）。3種算法的軌跡如圖3所示，其收斂情況如圖4所示，結果對比如表2所示。相比于傳統ACO的算法，本文算法在路徑長度與綜合代價上分別有2.654 0%與11.085 9%的提升；相比于MAACO的算法，本文算法在路徑長度與綜合代價上分別有9.179 3%與14.133 0%的提升。由圖可見，傳統ACO算法與MAACO算法收斂速度慢，且很早的陷入了局部最優，而本文算法，由于采取了開拓優化機制，有效地跳出了局部最優。為了驗證本文算法在大規模地圖下的尋優能力，本文在30×30與50×50的地圖環境下對算法進行了對比測試。在30×30地圖下迭代100輪，在50×50地圖下迭代300輪，測試結果如圖5—圖6所示，其路徑長度與綜合代價如表3、表4所示?？梢?，在大規模地圖下，本文算法具有更強的全局尋優能力，并且，相較于另外兩個算法，本文算法尋路過程中的拐點相對更少，路徑質量更高。在50×50的大地圖下，可明顯看到，MAACO算法陷入了局部最優，而由于擁有開拓優化機制，本文算法在路徑選擇上擁有更好的全局解。

4 結語

本文提出了一種基于林地綜合代價地圖與開拓優化機制的改進蟻群算法。首先，構建了林地綜合代價地圖，在地圖中融合能耗與路面通過條件，平衡了路徑長度、能耗與后期維護成本，更加符合生產實際；其次，引入開拓優化機制，通過對種群進行分工，使開拓組避開優化組現有路徑，優化組利用開拓組的搜索結果，增強了算法的全局尋優能力；在輪盤賭中加入隨機游走機制，在算法陷入局部最優時，以一定的概率為轉移概率，最高的點添加懲罰項，使得算法跳出局部最優；最后，將其應用到林間仿真環境下進行機器人路徑規劃問題研究。實驗結果表明：相較于現有算法，本文算法規劃得出的路徑能耗更小，并且在惡劣區域的通行長度更??；在大地圖環境下拐點數量更少，且收斂速度更快，一定程度上提高了林業機器人的路徑規劃質量，降低了實際生產中的能耗與維護成本。

參考文獻：

[1] 張子然，黃衛華，陳陽，等. 基于雙向搜索的改進蟻群路徑規劃算法[J]. 計算機工程與應用，2021，57（21）：270-277.

[2] 馬康康，王雷，李東東，等. 基于信息素差異分布策略的路徑規劃蟻群改進算法[J]. 南京航空航天大學學報，2023，55（1）：100-107.

[3] 徐超毅，龔橋梁. 基于改進蟻群算法的機器人路徑規劃研究[J]. 河南城建學院學報，2023，32（4）：91-96，127.

[4] WU L，HUANG X D，CUI J G，et al. Modified adaptive ant colony optimization algorithm and its application for solving path planning of mobile robot[J]. Expert Systems with Applications，2023，215：119410.

[5] 趙高杰，魯守銀，袁魯浩. 基于變步長蟻群算法的移動機器人路徑規劃[J]. 山東建筑大學學報，2022，37（6）：90-94，108.

[6] 董志洋，李慧，葛靖宇，等. 改進蟻群算法的無人機三維環境路徑規劃[J]. 測繪通報，2023（5）：153-157.

[7] 陳丹鳳，雷昊，劉俊朗，等. 基于強化蟻群算法的機器人路徑規劃研究[J]. 兵器裝備工程學報，2023，44（6）：239-245，303.

[8] 吳宇，郝萬君，曹選，等. 改進蟻群與勢場融合算法的平滑路徑規劃[J]. 計算機仿真，2023，40（3）：141-146.

[9] 陳嘉航，李媛媛. 融合頭腦風暴和注意力機制的改進蟻群路徑規劃算法研究[J]. 電光與控制，2023，30（4）：1-5.

[10] 張恒，何麗，袁亮，等. 基于改進雙層蟻群算法的移動機器人路徑規劃[J]. 控制與決策，2022，37（2）：303-313.

[11] 許凱波，魯海燕，黃洋，等. 基于雙層蟻群算法和動態環境的機器人路徑規劃方法[J]. 電子學報，2019，47（10）：2166-2176.

[12] WANG C，NAN Y，ZHANG S L，et al. Application of the adaptive double-layer ant colony algorithm in UAV trajectory planning[C]//2021 4th International Conference on Intelligent Autonomous Systems （ICoIAS）. Wuhan，China： IEEE，2021：371-377.

[13] YANG H，QI J，MIAO Y C，et al. A new robot navigation algorithm based on a double-layer ant algorithm and trajectory optimization[J]. IEEE Transactions on Industrial Electronics，2019，66（11）：8557-8566.

收稿日期：2024-05-21