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

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

中圖分類號：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 引言

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

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

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

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

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

1 林地綜合代價地圖

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

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

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

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

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

2 基于開拓優(yōu)化機制的改進蟻群算法

2.1 開拓優(yōu)化機制

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

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

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

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

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

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

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

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

2.2 隨機游走機制

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

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

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

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

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

3 實驗與分析

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

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

4 結語

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

參考文獻：

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

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

[3] 徐超毅，龔橋梁. 基于改進蟻群算法的機器人路徑規(guī)劃研究[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] 趙高杰，魯守銀，袁魯浩. 基于變步長蟻群算法的移動機器人路徑規(guī)劃[J]. 山東建筑大學學報，2022，37（6）：90-94，108.

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

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

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

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

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

[11] 許凱波，魯海燕，黃洋，等. 基于雙層蟻群算法和動態(tài)環(huán)境的機器人路徑規(guī)劃方法[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