基于改進麻雀搜索算法的農業機器人路徑規劃

摘" 要： 針對農業機器人在進行路徑規劃時存在尋優結果差和搜索穩定性低的問題，提出一種改進的麻雀搜索算法SSAPSO。首先利用Cubic混沌映射初始化種群來增強麻雀種群位置的多樣性。然后通過螢火蟲擾動策略，增加算法的靈活性和搜索范圍。最后引入粒子群技術以提高算法的尋優精度和穩定性。實驗結果表明，在不同障礙物覆蓋率的柵格地圖環境下，SSAPSO能高效且穩定地求解農業機器人最優路徑，從而提高農業機器人的工作效率。

關鍵詞： 麻雀搜索算法； 粒子群算法； 農業機器人； 路徑規劃

中圖分類號：TP3" " " " " 文獻標識碼：A" " "文章編號：1006-8228（2023）12-115-05

Path planning for agricultural robots based on improved sparrow search algorithm

Mao Shuang， Dai Yongqiang， Liu Huan

（College of Information Science amp; Technology， Gansu Agricultural University， Lanzhou， Gansu 730070， China）

Abstract： An improved sparrow search algorithm， SSAPSO， is proposed to address the problems of poor search results and low search stability in path planning for agricultural robots. Firstly， Cubic chaotic mapping is used to initialize the population to enhance the diversity of sparrow population locations. Then， a firefly perturbation strategy is used to increase the flexibility and search range of the algorithm. Finally， particle swarm techniques are introduced to improve the search accuracy and stability. The experimental results show that SSAPSO can solve the optimal path of agricultural robots efficiently and stably in a raster map environment with different obstacle coverage， thus improving the efficiency of agricultural robots.

Key words： sparrow search algorithm （SSA）; particle swarm optimization （PSO） algorithm; agricultural robot; path planning

0 引言

隨著人工智能技術的快速發展，農業生產領域的各個環節得到了重塑，將機器人技術與智能算法相融合，應用于現代農業中，不僅具有廣泛的研究前景和巨大的應用價值，同時也是機器人在農業應用領域中備受關注的難點技術之一，尤其是路徑規劃。

當前遺傳算法、蟻群算法以及粒子群算法等智能仿生算法[1]，在機器人路徑規劃的實際問題中得到了廣泛的應用。潘忠英等[2]提出一種A*-ISSA算法策略，通過自適應多普勒策略和量子行為來提高麻雀算法的收斂精度，并將A*與ISSA算法相結合，提高了農業機器人的作業效率。雷超帆等[3]提出一種融合粒子群與蟻群算法的策略，利用粒子群算法優化蟻群算法參數來實現路徑規劃，提高蟻群算法的綜合性能及機器人路徑規劃能力。梁景泉等[4]提出一種粒子群優化算法與灰狼算法相結合的策略，通過粒子群算法來解決灰狼算法容易早熟收斂、局部最優以及收斂速度慢等問題。提高了機器人路徑規劃效率。劉燁[5]等提出一種基于遺傳機制的改進蟻群算法策略，該策略改進信息素分配方式，增加刪除算子，提高了機器人的路徑尋優能力。馬凱凱等[6]提出一種粒子群算法與引力算法相結合的混合算法，將粒子群算法的全局搜索能力和引力算法的局部挖掘能力相結合，從而提高了機器人搜索速度。以上幾種融合算法策略，均能夠解決機器人路徑規劃中所遇到的一些基本問題，但是存在求解效率較低、優化精度不高等問題。

在此基礎上，本文提出一種改進麻雀搜索算法的農業機器人路徑規劃策略。麻雀搜索算法（Sparrow Search Algorithm， SSA）[7]是近幾年較新的群體智能算法。本文采用Cubic混沌映射對麻雀種群進行初始化以增加麻雀種群的多樣性，并通過螢火蟲擾動策略使得算法靈活性增強，搜索范圍擴大，收斂速度加快。最后，考慮到原有算法易陷入局部最優和穩定性差等特點，在改進麻雀搜索算法中引入粒子群技術來增強搜索能力和穩定性。實驗證明，本文提出的路徑規劃策略，在障礙物覆蓋率不一致的柵格地圖環境下能高效且穩定地解決農業機器人路徑規劃問題。

1 算法簡介

1.1 SSA算法

麻雀搜索算法是一種仿生優化算法，其靈感來自麻雀種群的覓食行為。該麻雀群體可分為發現者、加入者和偵察者。發現者主要負責尋找食物和帶領其他麻雀尋找食物源，其他麻雀則依靠這些發現者尋找食物。偵察者觀察麻雀群體內部的環境有無危險，提醒全麻雀群體安全。

發現者的位置更新公式如下：

[Xt+1i，j=Xti，j?exp-iα?itermax，" R2lt;STXti，j+Q?L，" " " " " " " " " R2≥ST]" ⑴

其中，[itermax]表示最大迭代次數，[Xt+1i，j]表示第[i]個麻雀在第[j]維的位置，[α∈（0，1）]是一個隨機數，[R2?[0，1]]為預警值，[ST∈[0.5，1]]為安全值，[Q]是服從正態分布的隨機數，[L]為[1×d]且元素值全為1的矩陣。

加入者的位置更新公式如下：

[Xt+1i，j=Q?expXworst-Xti，ji2，" " " " " " " " "igt;N2Xt+1p+Xti，j-Xt+1p?A+?L，" " "i≤N2]" ⑵

其中，[Xworst]表示第[t]次迭代全局最差位置，[Xt+1p]表示[t+1]次迭代發現者最優位置，[A]為多維矩陣，元素賦值為1或-1，且[A+=AT（AAT）-1]。

偵察者位置更新公式如下：

[Xt+1i，j=Xtbest+β?Xti，j-Xtbest，" " " "figt;fgXti，j+K?Xti，j-Xtworstf1-fw+ε，" " "fi=fg]" ⑶

其中，[Xtbest]為當前全局最優位置，[β]為步長控制參數。[k∈[-1，1]]用于控制麻雀的活動方向，[fi]表示個體適應度值，[fg]為最佳適應度值，[fw]為最差適應度值，[ε]為防止分母為零，記為最小常數。

1.2 PSO算法

粒子群算法（Particle Swarm Optimization， PSO）[8]其主要通過更新粒子的速度、位置等信息尋找最優解。假設種群有N個粒子在D維空間搜索，初始粒子群算法更新表示為：

[vd+1ij=ωvdij+c1r1pdij-xdij+c2r2pdgj-xdij]

[vd+1ij=vdij+vd+1ij] ⑷

其中，[d]為迭代次數，[vij]表示第[i]個粒子[j]維的速度，[xij]表示第[i]個粒子[j]維的位置。[ω]表示慣性權重，[c1、c2]表示學習因子，[r1、r2]表示范圍在[0，1]之間的隨機數。

2 改進的SSA算法（CFSSA）

2.1 Cubic混沌映射初始化麻雀種群

Cubic混沌映射[9]具有隨機性、均勻性、有序性，以及不重復全部狀態的特性。

在初始化階段，麻雀個體之間呈非均勻分布，造成其初始位置相對聚集，不利于尋找全局最佳位置。為此，本文利用Cubic混沌因子初始化種群，克服盲目性，同時也使得個體初始位置更均勻分布于搜索空間，增加了麻雀種群多樣性，也為麻雀搜索算法后期優化奠定基礎。

Cubic表達式如下：

[xn+1=ρxn1-x2n]" ⑸

其中，[xn?（0，1）]，[ρ]為控制參數。[xn]的初值為（0，1），取[xn=0.3]，[ρ=2.595]。

2.2 螢火蟲擾動策略

麻雀搜索算法采用螢火蟲算法擾動麻雀位置[10]，每代麻雀個體位置更新后，利用螢火蟲算法擾動并更新個體位置，以使得個體麻雀有足夠能力跳出局部最優。當擾動結束時，將擾動前后個體麻雀適應度函數進行對比，若擾動后個體麻雀表現更優，則更新位置，公式如下：

[xi=xi+β?xj-xi+α?rand*-12]" ⑹

其中，[xi]和[xj]為麻雀[i]和[j]的空間位置，[α]為步長因子，[rand*∈0，1]區間服從均勻分布的隨機數。

2.3 混合算法設計（SSAPSO）

混合麻雀算法與粒子群算法的核心思想是：將改進后的麻雀算法的相關參數作為粒子群算法的位置信息，使用粒子群的位置信息來運行麻雀算法，最終進行路徑規劃（如圖1所示）。

混合算法的運行步驟如下：

步驟1 系數初始化。設置麻雀、粒子群種群數量、迭代次數相關參數等，使用公式（5）進行麻雀種群位置的初始化，增加搜索范圍的多樣性。

步驟2 運用適應度值函數對麻雀進行排序，以獲取其個體最優和全局最優適應度值，并記錄其個體和全局最優位置。

步驟3 使用公式⑴、公式⑵、公式⑶更新發現者、加入者、偵察者的位置。

步驟4 使用公式⑹對處于最優位置的麻雀進行螢火蟲隨機擾動。

步驟5 計算適應度值函數，保留麻雀個體位置和全局最優位置。

步驟6 判斷當前的個體位置和全局最優位置，是否優于粒子群的個體最優和全局最優。如果所處位置優于當前，則進入粒子群算法階段，否則返回步驟⑵。

步驟7 使用公式⑷更新各粒子群的位置和速度。

步驟8 更新粒子群個體最優和全局最優位置。

步驟9 判斷迭代次數是否滿足最大值，若滿足則輸出全局最佳位置，全局最佳位置所對應的位置信息作為麻雀算法的重要參數，運行麻雀算法進行路徑規劃，否則返回步驟⑹。

3 SSAPSO算法性能測試

為驗證SSAPSO算法的改進效果，采用四個基準測試函數進行仿真實驗，其中[f1]、[f2]、[f3]為單峰函數，[f4]為多峰函數，具體描述如表1所示。

將SSAPSO算法與麻雀搜索算法（Sparrow Search Algorithm， SSA）、粒子群算法（Particle Swarm Optimization， PSO）、改進的麻雀搜索算法（CFSSA）在Matlab2021a中進行對比實驗。針對這四種算法，每個算法獨立運行30次。其中，每運行一次的算法迭代次數為1000，種群數量為30。

如表2給出了SSA、PSO、CFSSA、SSAPSO對于四種基準函數的仿真實驗結果。從表2可以看出，均值和標準差反映了SSA、PSO、CFSSA、SSAPSO對測試函數[f1]到[f4]所求解的質量，可得出SSAPSO算法優于其他算法。標準差反映出算法的魯棒性和穩定性，對于函數[f1]到[f4]，SSAPSO有較明顯的優勢。對于求解單峰函數[f1]、[f2]、[f3]，SSAPSO算法的尋優性能明顯強于其他算法。在求解多峰函數[f4]時，SSAPSO的求解精度最高，說明SSAPSO的穩定性強于其他算法。

綜上所述，引入多種策略使得算法在尋優效率上有明顯的提升，本文設計的SSAPSO算法在測試函數上表現出優秀的優化能力與搜索精度，進一步驗證了改進算法是有效可行的。

4 路徑規劃仿真測試

4.1 環境建模

在農業機器人規劃一條路徑之前，需要對農業機器人的工作環境進行建模和預處理。柵格法[11]是農業機器人路徑規劃工作環境建模的一種傳統方法。如圖2所示，設定黑色柵格為障礙物區域用“1”表示，農業機器人不可以通過，白色柵格為空閑區域用“0”表示，農業機器人可以通過，柵格的長度為1m，柵格按從下至上、從左往右的順序編號。每個柵格都有惟一的序號和位置坐標，轉換公式如下：

[xi=αmodi，MM-0.5yi=αNN+0.5-ceiliNN]" ⑺

其中，[xi]和[yi]為第[i]個柵格位置的坐標；[α]表示小柵格的邊長，通常取1；[MM]和[NN]分別為行方向和列方向的柵格數；[mod]為冗余運算符；[ceil]為向上取整。

4.2 實驗參數設置

為了驗證SSAPSO算法在路徑規劃中的尋優性能，將其與SSA、PSO和CFSSA算法進行對比分析。其中，20m×20m柵格地圖環境下的障礙物覆蓋率達到15.3%，40m×40m柵格地圖環境下的障礙物覆蓋率達到23.3%，50m×50m柵格地圖環境下的障礙物覆蓋率達到32.2%。實驗結果評價指標選取30次，各算法種群數量為30，最大迭代次數為200。

4.3 實驗結果與分析

根據表3可知，在路徑最優值方面，SSAPSO的最優路徑長度較CFSSA縮短5.7%，較SSA縮短14.4%，較PSO縮短12.3%。在平均路徑長度方面，SSAPSO平均路徑長度較CFSSA縮短4.5%，較SSA縮短12.5%，較PSO縮短26.6%。標準差反應算法的穩定性，在求解最優值路徑的穩定性方面，SSAPSO路徑穩定性比CFSSA提高了50%，比SSA提高了78%，比PSO提高了93%。在運行時間上，各算法運行時間都隨地圖環境復雜性提高而增加。SSAPSO算法的運行時間增加是由于采用多種改進策略，增強了算法的種群多樣性，提高了尋優精度。

根據圖3可知，PSO和SSA算法容易陷入局部最優解，導致路徑不夠平滑。SSAPSO相較于其他算法，能最快獲得最優路徑且路徑也更加平滑。根據圖4可知，PSO和SSA算法的路徑存在轉折點過多，路徑的平滑度低，不利于農業機器人的平穩移動。相較于PSO和SSA，SSAPSO算法搜索到的路徑轉折點更少，規劃出的路徑質量更高。根據圖5可知，隨著地圖維度的增大，SSAPSO、CFSSA、SSA和PSO這4種算法規劃出的路徑拐點數量也隨之增加。其中，SSAPSO算法所規劃的路徑拐點個數最少，收斂快。因此，SSAPSO算法的路徑規劃速度更快、穩定性更好，路徑規劃求解質量也明顯優于其他算法。

通過仿真實驗的對比和分析可知，在不同障礙物覆蓋率的地圖環境中，SSAPSO可以高效穩定地求解農業機器人路徑規劃問題，能夠獲得較好的路徑求解結果。

5 結束語

本文針對農業機器人在進行路徑規劃時會存在尋優結果差和搜索穩定性低的問題，提出一種改進的麻雀搜索算法。首先，采用Cubic混沌映射改善初始種群不均的問題。然后，利用螢火蟲擾動策略，提高算法的探索能力和收斂精度。最后，為了避免在搜索過程中陷入局部極值的問題，引入粒子群算法，該算法能夠更容易地跳出當前狀態，從而避免陷入局部最優，進一步提升了算法的局部搜索能力。實驗結果表明，SSAPSO優化后的路徑最短、求解精度最高、穩定性最好，很大程度上提高了農業機器人的路徑尋優能力，保證了農業機器人的作業效率。

參考文獻（References）：

[1] 林韓熙，向丹，歐陽劍，等.移動機器人路徑規劃算法的研究

綜述[J].計算機工程與應用，2021，57（18）：38-48.

[2] 潘忠英，尚猛.改進麻雀算法和A～*算法的農業機器人路徑

規劃[J]. 機械設計與研究，2022，38（1）：31-37.

[3] 雷超帆，趙華東，江南.融合粒子群與蟻群算法的機器人路徑

規劃[J].重慶理工大學學報（自然科學），2020，34（1）：235-241.

[4] 梁景泉，周子程，劉秀燕.粒子群算法改進灰狼算法的機器人

路徑規劃[J].軟件導刊，2022，21（5）：96-100.

[5] 劉燁，杜艷平，張騰丹，等.基于遺傳機制改進蟻群算法的室內

移動機器人路徑規劃研究[J].北京印刷學院學報，2022，30（2）：57-62.

[6] 馬凱凱，李翠明，吳新民.基于引力搜索和粒子群混合算法的

移動機器人路徑規劃[J].機械設計與制造工程，2019，48（12）：43-46.

[7] 薛建凱.一種新型的群智能優化技術的研究與應用[D].

上海：東華大學，2020.

[8] 吳大飛，楊光永，樊康生，等.多策略融合的改進粒子群優化

算法[J].計算機應用研究，2022，39（11）：3358-3364.

[9] Feng Junhong，ZhangJie，ZhuXiaoshu，etal.A novel chaos

optimization algorithm[J].Multimedia Tools and Applications，2017，76（16）：17405-17436.

[10] 劉睿，莫愿斌.一種改進的麻雀搜索算法[J].計算機技術與

發展，2022，32（3）：21-26.

[11] 王影，梁凱，于攀，等.基于柵格模型與改進蟻群算法的機器

人路徑規劃研究[J].內蒙古科技大學學報，2019，38（4）：349-354.