基于林地綜合代價(jià)地圖與開拓優(yōu)化機(jī)制的改進(jìn)蟻群算法

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

關(guān)鍵詞：蟻群算法；精英獎(jiǎng)勵(lì)；雙層蟻群算法；林間路徑規(guī)劃

中圖分類號：TP183 文獻(xiàn)標(biāo)志碼：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è)機(jī)器人是促進(jìn)林業(yè)現(xiàn)代化、提高林業(yè)效率的關(guān)鍵。路徑規(guī)劃與軌跡跟蹤是移動(dòng)機(jī)器人領(lǐng)域的核心問題。蟻群算法是一種經(jīng)典的仿生學(xué)算法，該算法可用于路徑規(guī)劃。相較于傳統(tǒng)的路徑規(guī)劃算法，蟻群算法具有正反饋機(jī)制、魯棒性強(qiáng)、并行性好等優(yōu)點(diǎn)，在尋求最短路徑上有更好的效果。然而，傳統(tǒng)蟻群算法收斂速度較慢且容易陷入局部最優(yōu)，導(dǎo)致規(guī)劃出的路徑不理想。對此，學(xué)者提出了大量改進(jìn)策略。

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

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

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

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

1 林地綜合代價(jià)地圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 隨機(jī)游走機(jī)制

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

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

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

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

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

3 實(shí)驗(yàn)與分析

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

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

4 結(jié)語

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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